ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 05 Nov 2016 17:37:41 +0100hamiltonian paths?https://ask.sagemath.org/question/34584/hamiltonian-paths/A Hamiltonian cycle is a traversal of a graph that visits all vertices just once and then returns to the starting vertex. SageMath can find one for you with G.traveling_salesman_problem. A Hamiltonian **path** drops the requirement that the path form a cycle. Does SageMath offer a convenient way to list all Hamiltonian paths of a graph?Thu, 25 Aug 2016 21:15:24 +0200https://ask.sagemath.org/question/34584/hamiltonian-paths/Answer by fidbc for <p>A Hamiltonian cycle is a traversal of a graph that visits all vertices just once and then returns to the starting vertex. SageMath can find one for you with G.traveling_salesman_problem. A Hamiltonian <strong>path</strong> drops the requirement that the path form a cycle. Does SageMath offer a convenient way to list all Hamiltonian paths of a graph?</p>
https://ask.sagemath.org/question/34584/hamiltonian-paths/?answer=35456#post-id-35456Here is a convenient (however non efficient) way of doing it.
g=graphs.CycleGraph(4)
for hp in g.subgraph_search_iterator(graphs.PathGraph(g.num_verts())):
print hp
Hope this helps!Sat, 05 Nov 2016 17:37:41 +0100https://ask.sagemath.org/question/34584/hamiltonian-paths/?answer=35456#post-id-35456Answer by fieldofnodes for <p>A Hamiltonian cycle is a traversal of a graph that visits all vertices just once and then returns to the starting vertex. SageMath can find one for you with G.traveling_salesman_problem. A Hamiltonian <strong>path</strong> drops the requirement that the path form a cycle. Does SageMath offer a convenient way to list all Hamiltonian paths of a graph?</p>
https://ask.sagemath.org/question/34584/hamiltonian-paths/?answer=35440#post-id-35440Hi,
Sage has the command:
hamiltonian_cycle(algorithm='tsp')
> "Returns a Hamiltonian cycle/circuit of the current graph/digraph
>A graph (resp. digraph) is said to be Hamiltonian if it contains as a subgraph a cycle (resp. a circuit) going through all the >vertices.
>Computing a Hamiltonian cycle/circuit being NP-Complete, this algorithm could run for some time depending on the instance.
>ALGORITHM:
>>See Graph.traveling_salesman_problem for ‘tsp’ algorithm and find_hamiltonian from sage.graphs.generic_graph_pyx for >>‘backtrack’ algorithm.
>INPUT:
>>algorithm - one of ‘tsp’ or ‘backtrack’.
>OUTPUT:
>>If using the ‘tsp’ algorithm, returns a Hamiltonian cycle/circuit if it exists; otherwise, raises a EmptySetError exception. If >>using the ‘backtrack’ algorithm, returns a pair (B,P). If B is True then P is a Hamiltonian cycle and if B is False, P is a >>longest path found by the algorithm. Observe that if B is False, the graph may still be Hamiltonian. The ‘backtrack’ >>algorithm is only implemented for undirected graphs."
The above is directly from [Hamiltonian Cycle](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.hamiltonian_cycle)
Added in the same area on the page is:
sage: g = graphs.HeawoodGraph()
sage: g.hamiltonian_cycle()
TSP from Heawood graph: Graph on 14 vertices
sage: g = graphs.PetersenGraph()
sage: g.hamiltonian_cycle()
Traceback (most recent call last):
...
EmptySetError: The given graph is not Hamiltonian
So clearly there is some algorithms on your question, though it is also known that this is an [NP-Complete](http://mathworld.wolfram.com/NP-CompleteProblem.html) problem.
Good luck,
fieldofnodes
Fri, 04 Nov 2016 22:57:23 +0100https://ask.sagemath.org/question/34584/hamiltonian-paths/?answer=35440#post-id-35440