在.dot树中强制执行水平节点排序 [英] Enforcing horizontal node ordering in a .dot tree

问题描述

我正在尝试使用GraphViz为二进制搜索树重新创建示例图.最终应该是这样的:

I am trying to recreate an example diagram for a binary search tree with GraphViz. This is how it should look in the end:

这是我的第一次尝试:

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不在乎树的水平位置，所以我得到了:

But unfortunately GraphViz doesn't care about the horizontal positions of the tree, so I get:

如何添加约束，以使顶点的水平位置反映其总体顺序?

How can I add constraints so that the horizontal positions of the vertices reflects their total ordering?

推荐答案

您可以按照在简单情况下，就足够了.

You could follow the usual approach of adding invisible nodes and invisible edges, and playing with edge weight etc. as proposed on the graphviz FAQ about balanced trees. In some simple cases, this is enough.

但是有一个更好的解决方案:Graphviz附带了一个名为 gvpr (图形模式扫描和处理语言)的工具，该工具可以

But there is a better solution: Graphviz comes with a tool called gvpr (graph pattern scanning and processing language) which allows to

将输入图复制到其输出，可能会改变其结构和属性，创建新图或打印任意信息

copy input graphs to its output, possibly transforming their structure and attributes, creating new graphs, or printing arbitrary information

并且由于 Emden R. Gansner已经完成了所有工作创建一个可以很好地布局二叉树的脚本，这里介绍了如何做到这一点(所有功劳归功于ERG):

And since Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees, heres how to to that (all credit goes to ERG):

将以下gvpr脚本保存到名为tree.gv的文件中:

Save the following gvpr script into a file called 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，则可以执行以下行:

Assuming your dot file containing the graph is called binarytree.gv, you may execute the following line:

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

结果是:

通过在脚本中切换一两行，您甚至可以使单个子节点位于左侧而不是右侧.

By switching around a line or two in the script, you'll even get to have the single child nodes go to the left instead of the right side.

这篇关于在.dot树中强制执行水平节点排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！