Make large nodes span multiple ranks

Help
1

I am creating control flow graphs. Each node contains a block of instructions. Some nodes have many instructions, some have only one. The dot layout puts huge nodes and tiny nodes on the same rank and it makes for sparse graphs that are hard to read. Here is a small example of what I am talking about:
bad

digraph {
    node [shape=rect];
    C0 [height=4]
    A0 [height=2]
    S->C0 
    C0->E 
    B0->A0
    A0->E
    S->B0
    B0->B1
    B1->B2
    B2->E
}

What I would like to be able to do is have a node span multiple ranks so that the space can be utilized better, something more like this:
better
In practice the height disparities are much more exaggerated. I simulated what I wanted by creating clusters with an invisible multi-rank subgraph inside:

digraph {
    graph [compound=true]
    node [shape=rect];
    subgraph cluster_C {
        C0 [style=invis]
        C1 [style=invis]
        C2 [style=invis]
        C0->C1 [style=invis]
        C1->C2 [style=invis]
    }
    subgraph cluster_A {
        A0 [style=invis]
        A1 [style=invis]
        A0->A1 [style=invis]
    }
    S->C0 [lhead=cluster_C]
    C2->E [ltail=cluster_C]
    S->B0
    B0->A0 [lhead=cluster_A]
    A1->E [ltail=cluster_A]
    B0->B1
    B1->B2
    B2->E
}

The only problem is that I can’t put any content in there. If I add a label to the cluster, it just stretches out the cluster. It doesn’t fill it. Ideally I would want large nodes that are just the size of the contents.

2

If we were able to place text within the clusters, how would you size the clusters? By eyeball (manually) or programmatically? i.e. how would you determine how many invisible nodes for a given cluster?

3

Another issue: Graphviz does not do “word wrap” (text wrap) ( a work-around: Text wrapping in Graphviz?).
Do you have a plan for this?

4

It isn’t too hard to come up with an estimate of the height of a node based on the number of instructions it contains. Or I could even do a first pass that just creates the nodes and parses the result to get the exact measurements. Then I could create the stand-in longer clusters choosing the number of invisible nodes based on the known long node heights. Assuming that this is done conservatively in such a way that the resulting stand-in clusters are never shorter than the actual long node, I can imagine creating a base layout in .dot format, replacing the stand-in clusters with the actual long nodes, fixing up the edges, and rendering the final graph. I’m just wondering if there are some alternatives that might work better.

I would love to see something like a “rankspan” attribute for nodes that would more or less do the same thing as I would be doing manually above. I’d have to think about it a little more to specify what happens when the long node is larger than the size of internal subgraph. Maybe you could just apportion the excess height proportionally between the spanned ranks.

I’m not sure what you mean about the text-wrapping. I am manually doing text-wrapping.

5

There are several ways to try to build your desired graph.

  1. neato -Goverlap=false -Gmode=hier // not a fan of this
  2. post-process your clusters & replace them with nodes of the same size, then push that through neato -n // ugh, lots of things to go wrong
  3. use rankdir=LR (ranks now vbertical) and rank=same // my current favorite
digraph {
  rankdir=LR
    node [shape=rect];
    C0 [height=4]
    A0 [height=2]
    S->C0 
    C0->E 
    B0->A0
    A0->E
    S->B0
    B0->B1
    B1->B2
    B2->E
    {rank=same S B0 A0 E}
    {rank=same B1 B2}
}

Giving:
tallFlow1

The issue with #3 is that you will have to determine what nodes go in what (vertical) ranks. Non-trivial, but doable in smallish numbers.

6

You could use shape=plaintext instead of invisible nodes within the clusters:

digraph {
    graph [compound=true]
    node [shape=rect];
    subgraph cluster_C {
        C0 [shape=plaintext]
        C1 [shape=plaintext]
        C2 [shape=plaintext]
        C0->C1 [style=invis]
        C1->C2 [style=invis]
    }
    subgraph cluster_A {
        A0 [shape=plaintext]
        A1 [shape=plaintext]
        A0->A1 [style=invis]
    }
    S->C0 [lhead=cluster_C]
    C2->E [ltail=cluster_C]
    S->B0
    B0->A0 [lhead=cluster_A]
    A1->E [ltail=cluster_A]
    B0->B1
    B1->B2
    B2->E
}

Untitled Graph 99(1)

Try it yourself here!

You can also use shape=plain (See Node Shapes | Graphviz) or experiment with the node attributes width, height and margin to get the size of the cluster that you want.

7

Thanks for the hints.

The rankdir flip is an interesting idea. It won’t work in general, but clever. It is desirable to keep edges coming out of the tops and bottoms and I can use ports for that, but I would like to keep edges from going upwards (except for backedges). I’ll experiment with the multipass approach to see what I can get out of that.