Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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]];

Mathematica graphics

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

Mathematica graphics

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.

Mathematica graphics

share|improve this question
    
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? –  rm -rf Sep 6 '12 at 13:58
    
@jVincent Nope, this is just an example –  belisarius Sep 6 '12 at 14:00
    
@R.M Not sure how to do it recursively in the hierarchical order –  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

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
I'm not sure why do you say Probably does not answer your question. I think it does! Is there some subtlety escaping me? –  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! –  belisarius Sep 6 '12 at 16:16
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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