Graphviz: enforce nonoverlap among clusters

Question

I'm trying to generate a layout of several undirected graphs (trees) in the same .dot file for a research project; the goal is to be able to easily inspect the trees visually. In order to achieve this, I'm making a subgraph cluster_ for each tree, see example:

graph {
layout = neato

subgraph cluster_0 {
label = "n= 7, tree 1";
nd_93 [label= "1"];
nd_94 [label= "2"];
nd_95 [label= "3"];
nd_96 [label= "4"];
nd_97 [label= "5"];
nd_98 [label= "6"];
nd_99 [label= "7"];
nd_93 -- nd_94;
nd_93 -- nd_97;
nd_94 -- nd_95;
nd_94 -- nd_96;
nd_97 -- nd_98;
nd_97 -- nd_99;
}
subgraph cluster_1 {
label = "n= 8, tree 1";
nd_238 [label= "1"];
nd_239 [label= "2"];
nd_240 [label= "3"];
nd_241 [label= "4"];
nd_242 [label= "5"];
nd_243 [label= "6"];
nd_244 [label= "7"];
nd_245 [label= "8"];
nd_238 -- nd_239;
nd_238 -- nd_243;
nd_239 -- nd_240;
nd_239 -- nd_241;
nd_239 -- nd_242;
nd_243 -- nd_244;
nd_243 -- nd_245;
}
subgraph cluster_2 {
label = "n= 9, tree 1";
nd_380 [label= "1"];
nd_381 [label= "2"];
nd_382 [label= "3"];
nd_383 [label= "4"];
nd_384 [label= "5"];
nd_385 [label= "6"];
nd_386 [label= "7"];
nd_387 [label= "8"];
nd_388 [label= "9"];
nd_380 -- nd_381;
nd_380 -- nd_385;
nd_381 -- nd_382;
nd_382 -- nd_383;
nd_382 -- nd_384;
nd_385 -- nd_386;
nd_386 -- nd_387;
nd_386 -- nd_388;
}
subgraph cluster_232 {
label = "n= 13, tree 1";
nd_20639 [label= "1"];
nd_20640 [label= "2"];
nd_20641 [label= "3"];
nd_20642 [label= "4"];
nd_20643 [label= "5"];
nd_20644 [label= "6"];
nd_20645 [label= "7"];
nd_20646 [label= "8"];
nd_20647 [label= "9"];
nd_20648 [label= "10"];
nd_20649 [label= "11"];
nd_20650 [label= "12"];
nd_20651 [label= "13"];
nd_20639 -- nd_20640;
nd_20639 -- nd_20648;
nd_20640 -- nd_20641;
nd_20640 -- nd_20645;
nd_20641 -- nd_20642;
nd_20641 -- nd_20643;
nd_20641 -- nd_20644;
nd_20645 -- nd_20646;
nd_20645 -- nd_20647;
nd_20648 -- nd_20649;
nd_20649 -- nd_20650;
nd_20649 -- nd_20651;
}
}

The layout=dot makes the trees appear each next to each other in a horizontal line, which is not desirable when there are more trees than just four (and in the real file there are going to be around 300 trees) -- it becomes harder to find patterns. .

The layout=neato produces nicer results concerning the layout of the trees themselves (the layout of the nodes in each cluster is more faithful to an undirected tree -- dot produces drawings of rooted trees) and the clusters (the actual trees) appear closer together and can be inspected visually more easily.

However, the layout produces serious overlaps between the boundaries of the clusters, and the labels (that I need to see in order to identify the trees). Other layouts seem to work better, but are not quite right: fdp does not produce overlaps in the cluster boundaries, but produces edge crossings. Layout sfdp removes the cluster boundaries and does not display labels altogether.

fdp: sfdp:

QUESTION Does somebody know if there is some layout option, or perhaps some fine tuning of the options layout, mode, spline, ... so that

1. the clusters do not overlap (as in fdp),
2. the layout of the trees (the individual clusters) is not that of a rooted tree (as in neato, not as in dot), and
3. there are no edge crossings (as in neato and sfdp, not as in fdp)

The clusters can be arranged in any way on the plane, it is not important for the moment to have tree (cluster) n= 13, tree 1 close to n= 13, tree 2 (which does not appear in the example).

Answer 1

You could:

• Produce (300) separate graphs in a special directory, say graphs/. Clusters probably no longer needed. Assume that the names of files just created have the format tree_nn_xxxxx.raw where nn is the number of nodes with two digits (01, 02, ...) and xxxxx is an index to distinguish between graphs of the same number of vertices; .raw is just a mock extension to be able to "capture" them from a regexp *.raw.

• Run each through neato (or any of the engines). Note: make the output format -Tdot. For example,

for f in $(ls graphs/*.raw); do
    # '$f' contains '.raw'
    f_no_ext=${f:0: $(( ${#f} - 4 ))}
    dot -Tdot $f > $f_no_ext.dot
done

• Then, you can use gvpack to combine those files into one (very large) graph. For example,

function normalize_value {
    n=$1
    if [ $n -lt 10 ]; then
        echo "0"$n
    else
        echo $n
    fi
}
for n in `seq 1 14`; do
    echo $n
    nn=$(normalize_value $n)
    gvpack -array_it20 graphs/tree_$nn*.dot > graphs/big_graph_$nn.dot
done

You will probably want to run some experiments with gvpack to get a "best" layout.

• Finally, run each big_graph_* file through neato -n2 -Tsvg to visualize the result. For example,

for n in `seq 1 14`; do
    echo $n
    nn=$(normalize_value $n)
    
    echo "    Run neato"
    neato -n2 -Tsvg graphs/big_graph_$nn.dot > all_trees_with_nonbip_$nn.svg
done