binary tree - Hacer cumplir el orden de los nodos horizontales en un árbol.dot

binary-tree graphviz

Question

Estoy intentando recrear un diagrama de ejemplo para un árbol de búsqueda binario con GraphViz. Así es como debería verse al 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, desafortunadamente, a GraphViz no le importan las posiciones horizontales del árbol, así que obtengo:

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

Answer 1

Puede seguir el enfoque habitual de agregar nodos invisibles y bordes invisibles, y jugar con el peso de los bordes, etc., tal 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 los gráficos de entrada a su salida, posiblemente transformando su estructura y atributos, creando nuevos gráficos o imprimiendo información arbitraria

Y dado que Emden R. Gansner ya hizo todo el trabajo al crear un script que presenta muy bien los árboles binarios , aquí se explica cómo (todo el crédito es para ERG):

Guarde la siguiente secuencia de comandos 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 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á hacer que los nodos secundarios individuales se dirijan hacia la izquierda en lugar del lado derecho.