Side-by-side binary trees in GraphViz

2.5k views Asked by At

I'm trying to format 2 (or ideally N) disconnected binary trees side-by-side, and I want the formatting to be "proper" for a binary tree, roughly like so:

enter image description here

Even if some nodes are missing, the rest should stay exactly where they are.

I generated an approximation of this balancing for one tree with a script called tree.gv from this Stack answer:

dot one_tree.dot | gvpr -c -f tree.gv | neato -n -Tpdf -o tree.pdf

It's not perfectly balanced the way I would like, but it's very workable. enter image description here

Now I want multiple trees side by side. Here's what I've tried:

dot trees.dot | neato -n -Goverlap=false -Tpdf -o tree.pdf

Properly side-by-side, but the bottom black leaves should be splayed right, leaving room for their missing siblings.

dot trees.dot | gvpr -c -f tree.gv | neato -n -Tpdf -o tree.pdf

Each tree is properly formatted, but they overlap. enter image description here

Surely combining the two will work?

dot trees.dot | gvpr -c -f tree.gv | neato -n -Goverlap=false -Tpdf -o tree.pdf

enter image description here

Here is trees.dot:

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    Lower;
    Lower -> LowerR;
    Lower -> LowerL;
    LowerL -> LowerLR;
    LowerR -> LowerRR;
    node [fillcolor="red"];
    Upper;
    Upper -> UpperR;
    Upper -> UpperL;
}
1

There are 1 answers

1
stefan On

The main trick to form trees is to use an extra invisible node with high edge weight that is then placed directly below the parent node. The order of appearence counts.

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    Lower;
    LowerL;
    LowerM [style=invis];
    LowerR;
    Lower -> LowerR;
    Lower -> LowerM [weight=100 style=invis];
    Lower -> LowerL;
    LowerLM [style=invis];
    LowerLR;
    LowerRM [style=invis];
    LowerRR;
    LowerL -> LowerLR;
    LowerL -> LowerLM [weight=100 style=invis];
    LowerR -> LowerRR;
    LowerR -> LowerRM [weight=100 style=invis];
    node [fillcolor="red"];
    Upper;
    UpperR;
    UpperM [style=invis];
    UpperL;
    Upper -> UpperR;
    Upper -> UpperM [weight=100 style=invis];
    Upper -> UpperL;
}

enter image description here

To prevent independent trees or tree branches from horizontal overlapping you have to use clusters (see my answer to Making graphviz trees have parents centred above children)

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    graph [style=invis];
    subgraph cluster_Lower {
        Lower;
        LowerL;
        LowerM [style=invis];
        LowerR;
        Lower -> LowerR;
        Lower -> LowerM [weight=100 style=invis];
        Lower -> LowerL;
        LowerLM [style=invis];
        LowerLR;
        LowerRM [style=invis];
        LowerRR;
        LowerL -> LowerLR;
        LowerL -> LowerLM [weight=100 style=invis];
        LowerR -> LowerRR;
        LowerR -> LowerRM [weight=100 style=invis];
    }
    node [fillcolor="red"];
    subgraph cluster_Upper {
        Upper;
        UpperR;
        UpperM [style=invis];
        UpperL;
        Upper -> UpperR;
        Upper -> UpperM [weight=100 style=invis];
        Upper -> UpperL;
    }
}

enter image description here