在.dot樹中執行水平節點排序

Question

我正在嘗試用GraphViz重新創建二叉查找樹的示例圖。這是它應該如何看到底：

這是我第一次嘗試：

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

但不幸的是GraphViz的不關心樹的水平位置，所以我得到：

我怎樣才能添加約束，使頂點的水平位置反映他們的總排序？

Answer 1

您可以按照graphviz FAQ about balanced trees上建議的方法添加隱形節點和不可見邊緣，以及使用邊緣權重等。在一些simple cases，這就夠了。

但是有一個更好的解決方案：Graphviz的帶有一個稱爲gvpr工具（圖模式掃描和處理語言），其允許以

拷貝輸入圖形到它的輸出，有可能改變它們的結構和屬性，創建新的圖形，或打印任意信息

而且，由於Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees，繼承人如何到（全部歸功於ERG）：

保存以下gvpr腳本到一個文件名爲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); 
    } 
} 

假設包含圖形的點文件被稱爲binarytree.gv，您可以執行以下行：

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

結果：

通過在腳本中切換一行或兩行，您甚至可以讓單個子節點進入左側而不是右側。