Making graphviz trees have parents centred above children

Question

I have the following graphviz code:

graph {
    node[width = 0.6, height = 0.6, fixedsize=true, shape=circle];
    a[label="22"];
    b[label="22"];
    c[label="34"];
    d[label="22"];
    e[label="99"];
    f[label="34"];
    g[label="40"];
    h[label="37"];
    i[label="22"];
    j[label="99"];
    k[label="135"];
    l[label="129"];
    m[label="40"];
    edge[penwidth=3.0];
    a -- b;
    b -- d;
    c -- f;
    d -- i;
    e -- j;
    g -- m;
    edge[penwidth=1.0];
    a -- c;
    b -- e;
    c -- g;
    d -- h;
    e -- k;
    g -- l;
}

This is meant to draw a binary tree with some edges highlighted. However, the tree doesn't look quite right - especially further-down the tree, the arrangement of parent and children looks like this:

          parent
child     child

whereas I would like it to look more like this:

    parent
child    child

(i.e. have the parent centred above its children, not sitting on top of one of them). Is this possible, and how would I do it if so?

Answer 1

I did play a lot and I think there is no perfect solution. There are some approaches.

---

The classic approach with additional invisible edges and nodes. This works out for small graphs but becomes very ugly on big ones. to ensure this is working out you have to fill the complete grid with invisible nodes. otherwise the dot engine will overrule you.

---

what I expected to work out was this approach

digraph {
    edge [weight=1]
    0->L
    0->R
    edge [weight=10]
    L->LL
    L->LR
    R->RL
    R->RR
    edge [weight=100]
    LL->LLL
    LL->LLR
    LR->LRL
    LR->LRR
    RL->RLL
    RL->RLR
    RR->RRL
    RR->RRR
}

Unfortunately it did not. It seems that the dot layout engine tries to minimize not the edge length, but the horizontal part only i.e. any parent position between the child nodes is considered ideal.

---

Another one i tried is

digraph {
    splines=line
    style=dotted
    edge [weight=1]
    subgraph cluster_0 {
        subgraph cluster_L {
            subgraph cluster_LL {
                LLL
                LLM [style=dotted]
                LLR
                LL->LLL
                LL->LLM [style=dotted weight=100]
                LL->LLR
            }
            LM [style=dotted]
            subgraph cluster_LR {
                LRL
                LRM [style=dotted]
                LRR
                LR->LRL
                LR->LRM [style=dotted weight=100]
                LR->LRR
            }
            L->LL
            L->LM [style=dotted weight=100]
            L->LR
        }
        M [style=dotted]
        subgraph cluster_R {
            subgraph cluster_RL {
                RLL
                RLM [style=dotted]
                RLR
                RL->RLL
                RL->RLM [style=dotted weight=100]
                RL->RLR
            }
            RM [style=dotted]
            R->RL
            R->RM [style=dotted weight=100]
            R->RR
        }
        0->L
        0->M [style=dotted weight=100]
        0->R
    }
}

which gives

It does seem to work out, the horizontal order depends on appearence. But clusters do not behave well with many other constructs, you have to try whether it works out for you.

---

If you omit the clusters the layout will be horizontally more compact. vertical edges are still prevented by the invisible middle nodes.

digraph {
    splines=line
    style=dotted
    edge [weight=1]
    LLL
    LLM [style=dotted]
    LLR
    LL->LLL
    LL->LLM [style=dotted weight=100]
    LL->LLR
    LM [style=dotted]
    LRL
    LRM [style=dotted]
    LRR
    LR->LRL
    LR->LRM [style=dotted weight=100]
    LR->LRR
    L->LL
    L->LM [style=dotted weight=100]
    L->LR
    M [style=dotted]
    RLL
    RLM [style=dotted]
    RLR
    RL->RLL
    RL->RLM [style=dotted weight=100]
    RL->RLR
    RM [style=dotted]
    R->RL
    R->RM [style=dotted weight=100]
    R->RR
    0->L
    0->M [style=dotted weight=100]
    0->R
}

which gives

---

Finally there is one thing left, a gvpr script for tree layout by ERG. Details you find in marapets answer to this question.

Answer 2

Following the instructions in this linked answer using gvpr and Emden R. Gansner's script to nicely layout binary trees, I get the following output:

Can't think of a better or faster way.