# How to group these vertices by its “level”

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?

• 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! – Szabolcs Nov 25 '16 at 10:00

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}}