# Visiting nodes in a tree bottom up

I have a problem that can be reduced to this one:

Suppose I have an unbalanced (almost random) tree. The leaves of the tree have one property already set, and all vertex (including the leaves) have another property that I have to update upon visiting.

To update that property, I need to cast a function f[father_Vertex,{son_Vertex..}] in an ordered way, as shown below:

Example

(*build some tree*)
s = KaryTree[23, 3, DirectedEdges -> True];
leaves = Flatten@Position[VertexDegree[s], 1];
(*Draw it*)
HighlightGraph[#, leaves, VertexLabels -> "Name", ImagePadding -> 20] &@s
(*Assign a property to the leaves*)
leaves = Flatten@Position[VertexDegree[s], 1]
s1 = Fold[SetProperty[{#1, #2}, "leavesProp" -> RandomInteger[{1, 5}]] &, s, leaves];
(*Assign another property to all Vertex*)
s2 = Fold[SetProperty[{#1, #2}, "toUpdateProp" -> ""] &, s1, VertexList[s1]];


Now, to cast my function, I need to visit node sets updating the properties in a hierarchical order:

Which is the easiest way to accomplish this navigation scheme?

Edit

The visiting order at each tree level is interchangeable {s1, s2, s3, s4} and {s5, s6, s7}

Edit2

Trying to be more clear. This is the desired order of invocation. All calls to f within the same round could be done in any order. The red one could be done in the first or second round.

-
I would guess you could simply go through them in reverse numerical order since they are numbered based on the layering. – jVincent Sep 6 '12 at 13:53
Convert the graph to a linked list and use Cases? – R. M. Sep 6 '12 at 13:58
@jVincent Nope, this is just an example – Dr. belisarius Sep 6 '12 at 14:00
@R.M Not sure how to do it recursively in the hierarchical order – Dr. belisarius Sep 6 '12 at 14:10
You can get the vertices ordered by distance from the root node. Pedestrian code for this: In[180]:= distance[v_] := Length[FindShortestPath[s, 1, v]] - 1 In[196]:= orderedvertices = With[{verts = VertexList[s]}, verts[[Reverse[Ordering[Map[distance, verts]]]]]] Out[196]= {23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}. You can now fold your property setting over this ordered list of vertices. – Daniel Lichtblau Sep 6 '12 at 14:15

You can build the list of elements of the form {parent,childrenlist}, ordered by tree depth (largest first), as below.

Clear[distance, ordervertices, orderedvertices, families, children,
orderedparents, orderedvisits];

distance[s_, v_] := Length[FindShortestPath[s, 1, v]] - 1

ordervertices[s_] :=
With[{verts = VertexList[s]},
verts[[Reverse[Ordering[Map[distance[s, #] &, verts]]]]]]

ordervertices = ordervertices[s2]

(* Out[245]= {23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, \
8, 7, 6, 5, 4, 3, 2, 1} *)

families =
Map[{#[[1, 1]], #[[All, 2]]} &,
SplitBy[Sort[List @@@ EdgeList[s2]], First]]

(* Out[246]= {{1, {2, 3, 4}}, {2, {5, 6, 7}}, {3, {8, 9, 10}}, {4, {11,
12, 13}}, {5, {14, 15, 16}}, {6, {17, 18, 19}}, {7, {20, 21,
22}}, {8, {23}}} *)

Map[(children[#[[1]]] = #[[2]]) &, families];

orderedparents =
Select[ordervertices, MemberQ[families[[All, 1]], #] &]

(* Out[249]= {8, 7, 6, 5, 4, 3, 2, 1} *)

orderedvisits = Map[{#, children[#]} &, orderedparents]

(* Out[250]= {{8, {23}}, {7, {20, 21, 22}}, {6, {17, 18, 19}}, {5, {14,
15, 16}}, {4, {11, 12, 13}}, {3, {8, 9, 10}}, {2, {5, 6,
7}}, {1, {2, 3, 4}}} *)


Probably does not answer your question, but way too long for a comment. I'm sure the code could be improved also, though it should be fine for smallish graphs.

-
I'm not sure why do you say Probably does not answer your question. I think it does! Is there some subtlety escaping me? – Dr. belisarius Sep 6 '12 at 15:54
No subtlety, I just was not sure if the result gave quite what you needed for subsequent traversal and property additions. A part of my confusion stems from inexperience with Graph[] objects. had it been non-atomic, I think it would have been straightforward to traverse by Level. But as a Graph?...Let's just say I'm still in the Stone Age where those are concerned. – Daniel Lichtblau Sep 6 '12 at 16:11
Ok, preventively upvoted :). I'll test it and report again. Thanks! – Dr. belisarius Sep 6 '12 at 16:16
or you could get orders by BreadthFirstScan. It group the result by round: set = Rest[ Reap[BreadthFirstScan[s, 1, {"DiscoverVertex" -> (Sow[{#2, #1, #3}] &)}]][[2, 1]]]; Reverse[{#[[1, 1]], #[[All, 2]]} & /@ GatherBy[#, First] & /@ GatherBy[set, Last][[All, All, {1, 2}]]] – halmir Sep 7 '12 at 0:48
@haimir Thanks. I had messed a bit with BreadthFirstScan but was not getting it to do what I wanted. – Daniel Lichtblau Sep 7 '12 at 1:12