# How to extract list of vertices of Hamiltonian path

G = graphs.Grid2dGraph(5,5)
hp=G.hamiltonian_path(algorithm="backtrack")
hp.show()
list(hp)


How do I extract list of vertices from hp as they go along the path. list(hp) seems to output some random list of all vertices (not along the found path).

edit retag close merge delete

Sort by ยป oldest newest most voted

For example, one can find the ends in the path graph hp and then a path (as a list of vertices) connecting them:

ends = [v for v in hp.vertices() if hp.degree(v)==1]
hp_list = hp.all_paths(*ends)[0]

more

OK, but isn't it a bit like double evaluation? Path hp was already found, why I need to find another path inside already found path hp? Sage must know the order of vertices to produce the path when plotting hp. All the information must be stored inside hp - I just need to get it out of it.

( 2022-09-08 18:54:49 +0100 )edit

Since hp is a path graph it's very easy to find a path within it. The hard problem of finding Hamiltonian path (to obtain graph hp) is solved only once here. Notice that hp as an object is not a path but a graph composed of a path. My code essentially extracts the path (as a list of vertices) from the graph hp.

( 2022-09-08 19:16:17 +0100 )edit
1

A faster option to get the path as a list of vertices is

ends = [v for v in hp if hp.degree(v)==1]
P = hp.shortest_path(*ends)


and to get the path as a list of edges, you can use:

P = list(hp.breadth_first_search(ends[0], edges=True))

( 2022-09-10 09:01:30 +0100 )edit