Applicazione dell'ordine nodo orizzontale in un albero .dot

Question

Sto tentando di ricreare un diagramma di esempio per un albero di ricerca binario con GraphViz. Questo è come dovrebbe apparire alla fine:

Questo è il mio primo tentativo:

digraph G { 
    nodesep=0.3; 
    ranksep=0.2; 
    margin=0.1; 
    node [shape=circle]; 
    edge [arrowsize=0.8]; 
    6 -> 4; 
    6 -> 11; 
    4 -> 2; 
    4 -> 5; 
    2 -> 1; 
    2 -> 3; 
    11 -> 8; 
    11 -> 14; 
    8 -> 7; 
    8 -> 10; 
    10 -> 9; 
    14 -> 13; 
    14 -> 16; 
    13 -> 12; 
    16 -> 15; 
    16 -> 17; 
} 

Ma purtroppo GraphViz non si preoccupa per la posizione orizzontale della pianta, così ottengo :

Come posso aggiungere vincoli in modo che la posizione orizzontale dei vertici riflette il loro ordinamento totale?

Answer 1

È possibile seguire il solito approccio di aggiungere nodi invisibili e bordi invisibili e giocare con il peso del bordo ecc. Come proposto su graphviz FAQ about balanced trees. In alcuni simple cases, questo è sufficiente.

Ma c'è una soluzione migliore: Graphviz dotato di uno strumento chiamato gvpr (grafico modello di scansione e di elaborazione del linguaggio) che consente di

grafici ingresso copia alla sua uscita, eventualmente trasformando la loro struttura e gli attributi, la creazione di nuovi grafici, o la stampa di informazioni arbitrarie

e poiché Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees, Heres come a quella (tutto il merito va a ERG):

Salva il seguente script gvpr in un file chiamato tree.gv:

BEGIN { 
    double tw[node_t]; // width of tree rooted at node 
    double nw[node_t]; // width of node 
    double xoff[node_t]; // x offset of root from left side of its tree 
    double sp = 36;  // extra space between left and right subtrees 
    double wd, w, w1, w2; 
    double x, y, z; 
    edge_t e1, e2; 
    node_t n; 
} 
BEG_G { 
    $.bb = ""; 
    $tvtype=TV_postfwd; // visit root after all children visited 
} 
N { 
    sscanf ($.width, "%f", &w); 
    w *= 72; // convert inches to points 
    nw[$] = w; 
    if ($.outdegree == 0) { 
    tw[$] = w; 
    xoff[$] = w/2.0; 
    } 
    else if ($.outdegree == 1) { 
    e1 = fstout($); 
    w1 = tw[e1.head];  
    tw[$] = w1 + (sp+w)/2.0; 
    if (e1.side == "left") 
     xoff[$] = tw[$] - w/2.0; 
    else 
     xoff[$] = w/2.0; 
    } 
    else { 
    e1 = fstout($); 
    w1 = tw[e1.head];  
    e2 = nxtout(e1); 
    w2 = tw[e2.head];  
    wd = w1 + w2 + sp; 
    if (w > wd) 
     wd = w; 
    tw[$] = wd; 
    xoff[$] = w1 + sp/2.0; 
    } 
} 
BEG_G { 
    $tvtype=TV_fwd; // visit root first, then children 
} 
N { 
    if ($.indegree == 0) { 
    sscanf ($.pos, "%f,%f", &x, &y); 
    $.pos = sprintf("0,%f", y); 
    } 
    if ($.outdegree == 0) return; 
    sscanf ($.pos, "%f,%f", &x, &y); 
    wd = tw[$]; 
    e1 = fstout($); 
    n = e1.head; 
    sscanf (n.pos, "%f,%f", &z, &y); 
    if ($.outdegree == 1) { 
    if (e1.side == "left") 
     n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y); 
    else 
     n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y); 
    } 
    else { 
    n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y); 
    e2 = nxtout(e1); 
    n = e2.head; 
    sscanf (n.pos, "%f,%f", &z, &y); 
    n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y); 
    } 
} 

Assumendo che il file di punti che contiene il grafico si chiama binarytree.gv, è possibile eseguire la seguente riga:

dot binarytree.gv | gvpr -c -ftree.gv | neato -n -Tpng -o binarytree.png 

Il risultato è :

Passando da una linea o due nella sceneggiatura, si otterrà persino il fatto che i nodi figlio singolo si spostino a sinistra anziché a destra.