0
$\begingroup$

After applying FindHamiltonianCycle to a graph, one generates output that looks like the following:

{{1<->2,2<->3,3<->4,4<->5,5<->6,6<->7,7<->8,8<->9,9<->10,10<->11,11<->12,12<->13,13<->14,14<->15,15<->16,16<->17,17<->18,18<->19,19<->20,20<->21,21<->22,<<3670>>,77<->75,75<->73,73<->71,71<->69,69<->67,67<->65,65<->63,63<->61,61<->59,59<->57,57<->55,55<->53,53<->51,51<->49,49<->47,47<->45,45<->43,43<->41,41<->39,39<->36,36<->1}}

I've replaced \[UndirectedEdge] with "<->" here to deal with formatting.

How can I quickly return an ordered list of vertices in the path, and an ordered list of their (previously specified) coordinates?

$\endgroup$
2
$\begingroup$

Since vertices in VertexCoordinates are listed according to the graphs own vertex order (that is not necessarily {1, 2, ..., n}), it is safer to extract VertexList also to make the node $\rightarrow$ coordinate replacement.

g = Graph@{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1}
coord = VertexCoordinates /. AbsoluteOptions@g;
nodes = VertexList@g;
FindHamiltonianCycle[g, All]
pathNodes = Map[First, FindHamiltonianCycle[g], {2}]

(* ==>    {{1, 2, 3, 4}} *)

You can replace vertices with coordinates:

pathNodes /. Thread[nodes -> coord]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.