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).
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]
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.
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.
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))
Asked: 2022-09-08 14:41:31 +0100
Seen: 399 times
Last updated: Sep 08 '22
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
