3
$\begingroup$

How can I traverse this tree, to get a sequence of vertices {8,4,2,9,5,1,6,3,7}? I've failed to produce it with DepthFirstScan, does this particular order even has a name?

TreeGraph[{1->2,1->3,2->4,2->5,3->6,3->7,4->8,5->9}, VertexLabels -> "Name"]

enter image description here

$\endgroup$
  • $\begingroup$ Which algorithm did you use to produce this order or the vertices? $\endgroup$ – A.G. Sep 11 '17 at 18:21
  • $\begingroup$ You can get pretty close using DepthFirstScan and the "PostvisitVertex" event - are you sure that's not what you want? Your order seems a bit strange, given that e.g. 2 is visited between visiting the two subbranches $\endgroup$ – Lukas Lang Sep 11 '17 at 18:58
  • $\begingroup$ @A.G. I don't know what's the algorithm is called, but it outputs the vertices while backtracking backwards from DFS. $\endgroup$ – swish Sep 11 '17 at 20:40
  • 1
    $\begingroup$ @swish As I understand a vertex is listed when the DFS has exhausted its adjacency list. If that is correct, node "1" should be last in the list. Is that correct? $\endgroup$ – A.G. Sep 11 '17 at 22:16
  • 1
    $\begingroup$ i am sure this is not what you want, but it does give {8,4,2,9,5,1,6,3,7}: rubeGoldbergSort[g_] := SortBy[VertexList[g], {PropertyValue[{g, #}, VertexCoordinates] &}]; rubeGoldbergSort@ TreeGraph[{1 -> 2, 1 -> 3, 2 -> 4, 2 -> 5, 3 -> 6, 3 -> 7, 4 -> 8, 5 -> 9}, VertexLabels -> "Name"]:) $\endgroup$ – kglr Sep 12 '17 at 8:33
1
$\begingroup$

Based on swish's comment ("Suprisingly it also gives the right answer for a bigger tree graph I have, so it probably is not a coincidence and this sort function is indeed traverses the tree the way I want it to"), perhaps:

coordinateSort[g_] := SortBy[VertexList[g], PropertyValue[{g, #}, VertexCoordinates]&]; 

coordinateSort@TreeGraph[{1 -> 2, 1 -> 3, 2 -> 4, 2 -> 5, 3 -> 6, 3 -> 7, 4 -> 8, 5 -> 9}]

{8, 4, 2, 9, 5, 1, 6, 3, 7}

$\endgroup$
1
$\begingroup$

As noted in the comments, the following gets you close:

g = TreeGraph[{1->2,1->3,2->4,2->5,3->6,3->7,4->8,5->9}, VertexLabels -> "Name"]

Reap[DepthFirstScan[g, 1, {"PostvisitVertex" -> Sow}]][[2, 1]]
(* {8, 4, 9, 5, 2, 6, 7, 3, 1} *)

The difference between this and your order is that a vertex is only visited after all subbranches have been visited. (whereas your order lists them after the first subbranch, which seems a bit arbitrary)

$\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.