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

Improve this question
$\endgroup$
8
  • $\begingroup$ Which algorithm did you use to produce this order or the vertices? $\endgroup$ Commented Sep 11, 2017 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$ Commented Sep 11, 2017 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$ Commented Sep 11, 2017 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$ Commented Sep 11, 2017 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$ Commented Sep 12, 2017 at 8:33

2 Answers 2

Reset to default
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}

Improve this answer
$\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)

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.