Ask Your Question
2

hamiltonian paths?

asked 2016-08-25 14:15:24 -0500

iconjack gravatar image

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?

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
2

answered 2016-11-04 16:57:23 -0500

fieldofnodes gravatar image

Hi,

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

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 problem.

Good luck, fieldofnodes

edit flag offensive delete link more
0

answered 2016-11-05 11:37:41 -0500

fidbc gravatar image

Here 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!

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-08-25 14:15:24 -0500

Seen: 1,645 times

Last updated: Nov 05 '16