How to get rank of nodes after processing with Graphviz dot?

Question

I use dot to render a graph, and it works ok.

Now I need to somehow get the rank that dot assigned to each node, is there a way to do it?

e.g. from this .dot file:

digraph D {
    Ivan -> Herbert [label="15,16"];
    Ivan -> Diego [label="23", color="slategray"];
    Roberto -> Herbert [label="17,18"];
    Roberto -> Ivan [label="19,20"];
    Diego -> Roberto [label="21", color="slategray", style=dashed, color=red, constraint=false]
    {rank=max;}
}

I'd like to get information like:

rank of "Roberto" is 1
rank of "Ivan" is 2
rank of "Diego" is 3
rank of "Herbert" is 3

Where the rank of a node is the depth of it in the graph rendering, i.e. the top node has rank 1, its children 2, etc.

Notice that my graph usually is more complex and always includes cycles, and the visual layout is shown to the user, so a "Do It Yourself" approach is out the table because the rank of each node needs to be the same as the dot rendering.

I'm currently using python but I can use any other tool to achieve this.

Answer 1

Here is (very lightly tested) GVPR (https://www.graphviz.org/pdf/gvpr.1.pdf) program that seems to do what you want.
Dot does not seem to keep a rank number once it has calculated X-Y coordinates. So this program reverse calculates a rank number from a nodes Y (or X) coordinate.
Linux command line is: dot -Tdot yourgraph.gv | gvpr -f listRank.gvpr

The listRank.gvpr program:

BEGIN {
  int i, j, N, R=0,  nIndx=0, list[string];
  string rankList[double];
  string nodeIndx[int];
  string str1, RankDir="TB"; 
  node_t aNode, thisNode[];
  double dist;

  void setRank(){
    R++;
    str1=substr(rankList[dist],1);     // strip leading delimiter
    unset(nodeIndx);                      // delete array of node indices
    N=split(str1, nodeIndx, "|");
    for (i=0; i<N; i++){              // for each node in this rank (w/ same Y/X pos)
      j=nodeIndx[i];
      aNode=thisNode[j];
      print ("rank of \"", aNode.name, "\"  is ",  R);
    }
  }
}
BEG_G{
  if (hasAttr($G, "rankdir") && $G.rankdir!="")
    RankDir=$G.rankdir;
  print ("// RANKDIR: ", RankDir);
}
N {
  thisNode[++nIndx]=$;  // index the nodes
  if (RankDir=="LR|RL"){        // ksh pattern matching
    dist=$.X;
  } else {
    dist=$.Y;
  }
  // build a string containing all node indices, based on (indexed by) Y/X value
  rankList[dist]=sprintf("%s|%s", rankList[dist], nIndx);
}
END_G{
  // for each rank, in sorted order
  if (RankDir=="TB|RL"){        //      ksh pattern matching
    forr (rankList[dist]){      //  decreasing sort
      setRank();
    }
  }else{
    for (rankList[dist]){       // increasing sort
      setRank();
    }
  }
}

Here is outful for this file(https://www.graphviz.org/Gallery/directed/cluster.html)

rank of "start"  is 1
rank of "a0"  is 2
rank of "b0"  is 2
rank of "a1"  is 3
rank of "b1"  is 3
rank of "a2"  is 4
rank of "b2"  is 4
rank of "a3"  is 5
rank of "b3"  is 5
rank of "end"  is 6

Answer 2

I'm sure there is a more efficient algorithm, but you can do this in networkx by first getting all the 'root' nodes (i.e., nodes with no 'in' edges), then performing a BFS on the graph from each of those nodes, defining ranks as you go.

I do not know if it is exactly the same as was what DOT defines, but it does construct an accurate topological ranking.

Code:

from collections import defaultdict
import networkx as nx

graph = nx.drawing.nx_agraph.read_dot('graph.dot')
roots = []
ranks = defaultdict(int)
for node in graph.nodes:
    if not list(graph.predecessors(node)):
        roots.append(node)
        ranks[node] = 1

for root in roots:
    for (head, tail) in nx.bfs_edges(graph, root):
        ranks[tail] = max(ranks[tail], ranks[head] + 1)

print(ranks)

Output:

defaultdict(<class 'int'>, {'a': 1, 'e': 1, 'b': 2, 'c': 3, 'd': 3})