Ask Your Question
0

How to extract list of vertices of Hamiltonian path

asked 2022-09-08 14:41:31 +0100

azerbajdzan gravatar image
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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2022-09-08 17:42:30 +0100

Max Alekseyev gravatar image

updated 2022-09-08 17:43:09 +0100

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]
edit flag offensive delete link more

Comments

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.

azerbajdzan gravatar imageazerbajdzan ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 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))
David Coudert gravatar imageDavid Coudert ( 2022-09-10 09:01:30 +0100 )edit

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: 2022-09-08 14:41:31 +0100

Seen: 296 times

Last updated: Sep 08 '22