Erzwingen der horizontalen Knotenreihenfolge in einer .dot-Struktur

Question

Ich versuche, ein Beispieldiagramm für einen binären Suchbaum mit GraphViz neu zu erstellen. Dies ist, wie es am Ende aussehen soll:

Dies ist mein erster Versuch:

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

Aber leider GraphViz nicht kümmert sich um die horizontalen Positionen des Baumes, so dass ich :

Wie kann ich Einschränkungen, so dass die horizontalen Positionen der Eckpunkte spiegelt ihre gesamte Bestellung wider?

Answer 1

Sie könnten dem üblichen Ansatz folgen, unsichtbare Knoten und unsichtbare Kanten hinzuzufügen und mit Kantengewicht usw. zu spielen, wie auf der graphviz FAQ about balanced trees vorgeschlagen. In einigen simple cases ist dies genug.

Aber es ist eine bessere Lösung: Graphviz kommt mit einem Werkzeug gvpr (Graph Mustererkennungs- und Verarbeitungssprache) genannt, die

zu ermöglicht

Kopie Eingangsgraphen seinem Ausgang, möglicherweise ihre Struktur transformieren und Attribute, neue Diagramme erstellen oder Drucke von beliebigen Informationen

und da Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees, here, wie man an, dass (alle Kredite gehen an ERG):

Speichern Sie das folgende gvpr Skript in einer Datei namens 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); 
    } 
} 

Ihre Punktdatei Angenommen, der Graph enthält binarytree.gv genannt wird, können Sie die folgende Zeile aus:

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

Das Ergebnis ist :

Wenn Sie eine oder zwei Zeilen im Skript umschalten, werden die einzelnen untergeordneten Knoten sogar nach links statt nach rechts verschoben.