Skip to content

Instantly share code, notes, and snippets.

@jdelafon
Created June 29, 2016 11:47
Show Gist options
  • Save jdelafon/7c12a85d68fe004ca4e92c3ed7f8ed3b to your computer and use it in GitHub Desktop.
Save jdelafon/7c12a85d68fe004ca4e92c3ed7f8ed3b to your computer and use it in GitHub Desktop.
Deep search algorithm to find an Hamiltonian path in a graph
# Deep search algorithm to find an Hamiltonian path in a graph
# (visiting every edge once and only once)
"""
EXAMPLES
V = ['AA','AB','BC','CD','DE','EF']
E = [('AA','AB'),('AB','BC'),('BC','CD'),('CD','DE'),('DE','EF'),('EF','AA'),('AB','EF'),('EF','CD'),('CD','AB')]
returns [['AA','AB','BC','CD','DE','EF'], ['AB','BC','CD','DE','EF','AA'], ['BC','CD','DE','EF','AA','AB'],
['CD','DE','EF','AA','AB','BC'], ['DE','EF','AA','AB','BC','CD'], ['EF','AA','AB','BC','CD','DE']]
V = ['a','b','c','d','e']
E = [('a','b'),('a','c'),('b','d'),('d','c'),('d','e'),('e','c'),('c','e')]
returns [['a', 'b', 'd', 'c', 'e'], ['a', 'b', 'd', 'e', 'c']]
"""
import time
class Node(object):
def __init__(self, name='',idx=-1,active=1,label=''):
self.name = name # node name
self.idx = idx # node index
self.neighbours = set() # all accessible nodes
def __eq__(self,node):
return self.idx == node.idx and self.name == node.name
class Vertex(object):
def __init__(self,inc,out, name='',label='',active=1):
assert isinstance(inc,Node), "Expected Node class, got %s." % type(inc)
assert isinstance(out,Node), "Expected Node class, got %s." % type(out)
self.inc = inc # node it comes from
self.out = out # node it goes to
self.name = '' # vertex name
def __getitem__(self,i):
if i==0: return self.inc
if i==1: return self.out
def hamiltonian(V, E):
E = set([Vertex(Node(name=e[0],idx=V.index(e[0])),Node(name=e[1],idx=V.index(e[1]))) for e in E])
V = [Node(idx=i,name=V[i]) for i in range(len(V))]
for e in E:
V[e[0].idx].neighbours.add(V[e[1].idx])
t1 = time.time()
L = 1
paths = [[v] for v in V]
while L < len(V):
q = []
toremove = []
for p in paths:
if p[-1].neighbours:
for n in p[-1].neighbours:
if n not in p:
q.append(p+[n])
else:
toremove.append(p)
for p in toremove: paths.remove(p)
L+=1
paths = q
t2 = time.time()
print "Running time: %s" % (t2-t1,)
return [[n.name for n in p] for p in paths]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment