2
$\begingroup$

I have many graphs and I want to group all vertices by its "level",but I don't know how to define the "level" exactly,just by its topological order to discern they.I give some example in follow and label its "level".

All of the graphs is a In directed acyclic graphs got by TransitiveReductionGraph,and its vertex name is difference.

Question

How to group vertices in all graphs by its "level"?The expected result is:

{{"swallow","allowance","shallow",100,"thought","drought","detective",1},
{"wallow",101,"ought","rough","detect",2,3},{"allow",102,103,4},{104,5},{105}}

Current try

graphs=(Uncompress@*FromCharacterCode@*Flatten@*(ImageData[#1, "Byte"] &)@*
   Import)["http://ooo.0o0.ooo/2016/11/24/58374fe8b5196.png"];

For graphs[[1]] I can get such result:

Function[g, 
  DeleteDuplicates /@ 
   Flatten[VertexOutComponent[g, #] & /@ 
     VertexList[g, _?(VertexInDegree[g, #] == 0 &)], {2}]]@graphs[[1]]

{{swallow,allowance,shallow},{wallow,allow},{allow}}

Of course,in graphs[[1]] I want to get {{swallow,allowance,shallow},{wallow},{allow}}.How to refine this code for all graphs?

$\endgroup$
1
  • $\begingroup$ I think it's not going to be possible to define the level uniquely ... I mean more than one level assignment may be a good solution. Nice question, +1! $\endgroup$
    – Szabolcs
    Commented Nov 25, 2016 at 10:00

1 Answer 1

2
$\begingroup$
rule = Flatten[MapIndexed[Thread[# -> #2[[1]]] &, #] & /@ 
       (Quiet[NestWhileList[{vl = VertexList[#[[2]], _?(Function[v, 
                 VertexInDegree[#[[2]], v] == 0])], VertexDelete[#[[2]], vl]} &, {{}, #}, 
        #[[2, 0]] =!=  VertexDelete &]][[2 ;; -2, 1]] & /@ graphs)];

allvertices = Join @@ (VertexList /@ graphs);

Pick[allvertices, allvertices /. rule, #] & /@ Range[Max[rule[[All, -1]]]]

{{"swallow", "allowance", "shallow", 100, "thought", "drought", "detective", 1},
{"wallow", 101, "ought", "rough", "detect", 2, 3},
{"allow", 102, 103, 4},
{104, 5},
{105}}

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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