#NEWLINE# def hamiltonian( edges , directed = False , constraint_generation = True ) : #NEWLINE# #INDENT# '\n    Calculates shortest path that traverses each node exactly once. Convert\n    Hamiltonian path problem to TSP by adding one dummy point that has a distance\n    of zero to all your other points. Solve the TSP and get rid of the dummy\n    point - what remains is the Hamiltonian Path.\n\n    >>> g = [(1,2), (2,3), (3,4), (4,2), (3,5)]\n    >>> hamiltonian(g)\n    [1, 2, 4, 3, 5]\n    >>> g = [(1,2), (2,3), (1,4), (2,5), (3,6)]\n    >>> hamiltonian(g)\n    ' #NEWLINE# edges = populate_edge_weights ( edges ) #NEWLINE# ( incident , nodes ) = node_to_edge ( edges , directed = False ) #NEWLINE# if ( not directed ) : #NEWLINE# #INDENT# dual_edges = edges [ : ] #NEWLINE# for ( a , b , w ) in edges : #NEWLINE# #INDENT# dual_edges . append ( ( b , a , w ) ) #NEWLINE# #UNINDENT# edges = dual_edges #NEWLINE# #UNINDENT# DUMMY = 'DUMMY' #NEWLINE# dummy_edges = ( ( edges + [ ( DUMMY , x , 0 ) for x in nodes ] ) + [ ( x , DUMMY , 0 ) for x in x ] ) #NEWLINE# results = tsp_gurobi ( dummy_edges ) #NEWLINE# if results : #NEWLINE# #INDENT# results = [ x for x in results if ( DUMMY not in x ) ] #NEWLINE# results = edges_to_path ( results ) #NEWLINE# if ( not directed ) : #NEWLINE# #INDENT# results = min ( results , results [ : : ( - 1 ) ] ) #NEWLINE# #UNINDENT# #UNINDENT# return results