Imponer el ordenamiento horizontal de nodos en un árbol .dot

Estoy intentando recrear un diagtwig de ejemplo para un árbol de búsqueda binaria con GraphViz. Así es como debería verse al final:

enter image description here

Este es mi primer bash:

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 desafortunadamente GraphViz no se preocupa por las posiciones horizontales del árbol, entonces obtengo:

enter image description here

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

Puede seguir el enfoque habitual de agregar nodos invisibles y bordes invisibles, y jugar con el peso del borde, etc. como se propone en las preguntas frecuentes de graphviz sobre árboles equilibrados . En algunos casos simples , esto es suficiente.

Pero hay una solución mejor: Graphviz viene con una herramienta llamada gvpr ( escaneo de patrones de gráficos y lenguaje de procesamiento ) que permite

copie gráficos de entrada a su salida, posiblemente transformando su estructura y atributos, creando nuevos gráficos o imprimiendo información arbitraria

Y como Emden R. Gansner ya hizo todo el trabajo al crear un script que diseña muy bien los árboles binarios , aquí está cómo hacerlo (todo el crédito va a ERG):

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

Suponiendo que su archivo de punto 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:

Árbol binario bien trazado con gráficos y un script gvpr gracias a Emden R. Gansner

Al cambiar una o dos líneas en el guión, incluso podrá hacer que los nodos secundarios individuales vayan a la izquierda en lugar de a la derecha.