21

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はツリーの水平位置を気にしないので、次のようになります。

ここに画像の説明を入力してください

頂点の水平位置がそれらの全体の順序を反映するように制約を追加するにはどうすればよいですか？

4

1 に答える 1

26

バランスの取れたツリーに関するgraphvizFAQで提案されているように、非表示のノードと非表示のエッジを追加し、エッジの重みなどで遊ぶという通常のアプローチに従うことができます。いくつかの単純なケースでは、これで十分です。

しかし、より良い解決策があります。Graphvizには、 gvpr（グラフパターンのスキャンおよび処理言語）と呼ばれるツールが付属しています。

入力グラフをその出力にコピーし、場合によってはそれらの構造と属性を変換したり、新しいグラフを作成したり、任意の情報を印刷したりします

そして、Emden R. Gansnerは、バイナリツリーを適切にレイアウトするスクリプトを作成することですでにすべての作業を行っているので、その方法は次のとおりです（すべてのクレジットは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

結果は次のとおりです。

Emden R. Gansnerのおかげで、graphivとgvprスクリプトでうまくレイアウトされた二分木

スクリプトの1行か2行を切り替えることで、単一の子ノードを右側ではなく左側に配置することもできます。

于 2012-06-05T22:04:46.843 に答える