Aplicar ordenamiento de nodo horizontal en un árbol .dot

Question

Estoy intentando recrear un diagrama de ejemplo para un árbol de búsqueda binaria con GraphViz. Esta es la forma en que debe ser en el final:

Este es mi primer intento:

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; 
} 

Pero, por desgracia GraphViz no se preocupa por las posiciones horizontales de los árboles, así que llegar :

¿Cómo puedo agregar restricciones para que las posiciones horizontales de los vértices refleja su orden total?

Answer 1

Puede seguir el enfoque habitual de agregar nodos invisibles y bordes invisibles, y jugar con el peso del borde, etc. como se propone en el graphviz FAQ about balanced trees. En algunos simple cases, esto es suficiente.

Pero hay una solución mejor: Graphviz viene con una herramienta llamada gvpr (gráfico de exploración patrón y lenguaje de procesamiento) que permite a

gráficos de entrada copia a su salida, posiblemente la transformación de su estructura y atributos, la creación de nuevos gráficos, o imprimir la información arbitraria

y puesto Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees, aquí está cómo a eso (todo el crédito va a ERG):

Guardar el siguiente script gvpr en un archivo llamado 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); 
    } 
} 

Asumiendo que su archivo de puntos que contiene el gráfico se llama binarytree.gv, puede ejecutar la siguiente línea:

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

El resultado es :

Al cambiar una o dos líneas en el script, incluso podrá tener los nodos secundarios individuales a la izquierda en lugar del derecho.