Timeline for Depth first scan of a tree backwards
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2017 at 13:33 | history | tweeted | twitter.com/StackMma/status/909047697834946561 | ||
| Sep 13, 2017 at 14:55 | vote | accept | swish | ||
| Sep 12, 2017 at 21:00 | answer | added | kglr | timeline score: 1 | |
| Sep 12, 2017 at 12:50 | comment | added | swish | @kglr I'm also unaware of the original method, outputing vertices on backward motion of DFS was just a guess. But coordinate sort on default layout is apparently does the same thing. | |
| Sep 12, 2017 at 12:21 | comment | added | kglr | swish, but this depends only on the layout. I was assuming the sequence was generated by something more subtle. | |
| Sep 12, 2017 at 12:08 | comment | added | swish | @kglr Suprisingly it also gives the right answer for a bigger tree graph I have, so it probably not a coincidence and this sort function is indeed traverses the tree the way I want it to, thx :) | |
| Sep 12, 2017 at 8:33 | comment | added | kglr | 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"]:) | |
| Sep 12, 2017 at 7:57 | answer | added | Lukas Lang | timeline score: 1 | |
| Sep 11, 2017 at 22:16 | comment | added | A.G. | @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? | |
| Sep 11, 2017 at 20:40 | comment | added | swish | @A.G. I don't know what's the algorithm is called, but it outputs the vertices while backtracking backwards from DFS. | |
| Sep 11, 2017 at 18:58 | comment | added | Lukas Lang | 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 | |
| Sep 11, 2017 at 18:21 | comment | added | A.G. | Which algorithm did you use to produce this order or the vertices? | |
| Sep 11, 2017 at 16:44 | history | asked | swish | CC BY-SA 3.0 |