Best Graph Drawing Algorithm For Hierarchical Data?

Question

I have a collection of directed acyclic graphs that are nearly trees, in the following sense: each graph has a root, and the vertices are organized into levels such that if v₁ and v₂ are vertices, then if the level of v₁ is less than the level of v₂, then there is no edge from v₂ to v₁ in the graph, although there may be many edges from v₁ to vertices at the same or a greater level. For example, an expression tree, a function call graph, or a linear class hierarchy, would be examples of such graphs. Here is an example of such a graph:

              A1            
             /  \           A1 -> A4, A3
            /    \          A3 -> A2, A6, A7
          A4  A2--A3        A2 -> A6
              | \ / \
              A6 \_ A7

There are a plethora of graph-drawing algorithms, and I can't determine which is optimal for this situation. Some preliminary research indicates that algorithms for drawing Hasse diagrams might be appropriate, but it seems that the output of such algorithms isn't geared toward the type of data structures that I'm trying to model. There are also several algorithms for modeling hierarchical data, but I'm not sure which would balance ease of implementation with efficiency. One problem with the former approach is that these graphs have a root, as well as a direction. If possible, the algorithm would support cyclic graphs, and minimize the number of numeric computations, but this isn't necessary. For these reasons, I would prefer to avoid force-directed algorithms, and if possible, the GraphViz algorithms such as dot.

Answer 1

This isn't really an answer, but it was too long for a comment.

How do your graphs differ from a general directed acyclic graph?

A DAG doesn't have to have a root, but I think that makes little difference to drawing the graph.

As far as levels go, for any DAG, it is possible to define a function level(v) such that for any edge v_i → v_j, level(i) ≤ level(j). A trivial level function is the index of the vertex in a topological order of the vertices. Another one is the length of the longest path from the root to the vertex.

The Reingold-Tilford tree-drawing algorithm draws ordered trees (that is, trees where the edges from a vertex are ordered). Your examples suggest that your graphs are not ordered, and indeed that the main issue you face is finding an edge-ordering which minimizes edge-crossing. So possibly this is the problem you are looking to solve. (It's not an easy problem.)

dot actually does pretty well with DAGs, in my experience, although it sometimes needs a bit of a helping hand. In particular, if you know the level of each vertex, you can make a subgraph for each level with the attribute `rank = "same"'. (See this example.)

Answer 2

If it's exactly a tree, then I have seen this Reingold–Tilford Tree drawing algorithm work very well before.

BTW, I feel the decision to allow node A2 to 'go up' to the same level as its ancestor isn't really helping that much.

In stead I would allow a node to go down further instead of going up. The example could be drawn better as shown below in my opinion.

          A1            
         /  \           A1 -> A4, A3
        /    \          A3 -> A2, A6, A7
      A4     A3         A2 -> A6
            / | \
          A2  |  A7
            \ |
             A6

This way you don't even need to label edge direction. [Did I misunderstand your original diagram? I think there is no edge between A2 and A7 right?]