树可视化库 - 计算给定树数据的所有节点和线坐标的库

Question

（视觉）C++ 世界。我有一个树结构，想要将其可视化。更具体地说：

我有一个树数据。我想要处理这些数据并计算每个节点以及连接它们的每条线的坐标（在任何逻辑坐标空间中，例如 2000x2000 逻辑像素）的库。连接两个节点的线可能不是简单的直线，它可能是曲线或由直线段组成的某种路径。理想情况下，我希望也为给定的树节点坐标计算定义路径的线，以防用户拖动并重新排列节点。

很快，我需要一个库来为我计算给定图形的所有必要的几何坐标。然后我将使用这些坐标通过 GDI 根据需要绘制图形。

我听说过 Graphviz、点语言等等。但我不确定它（或其替代品，如 OGDF 或 igraph）是否可以实现我想要的功能。我想要实现的想法是自己渲染图形，但需要生成坐标的帮助。此外，用户必须能够重新定位节点，因此必须可以重新计算连接重新排列的节点的线路径，以便例如线不会穿过任何现有节点。

Answer 1

是的，graphviz 可以做到这一点。

布局有向图

假设您在 tree.gv 中有以下图：

digraph g{
  a[label="I"];
  b[label="am"];
  c[label="a"];
  d[label="tree"];
  e[label="with"];
  f[label="7"];
  g[label="nodes"];

  a -> b -> c;
  b -> d -> e;
  d -> f;
  d -> g;
}

dot 可以布局此图：dot tree.gv 其结果in

digraph g {
    node [label="\N"];
    graph [bb="0,0,208,252"];
    a [label=I, pos="63,234", width="0.75", height="0.5"];
    b [label=am, pos="63,162", width="0.75", height="0.5"];
    c [label=a, pos="27,90", width="0.75", height="0.5"];
    d [label=tree, pos="99,90", width="0.75", height="0.5"];
    e [label=with, pos="27,18", width="0.75", height="0.5"];
    f [label=7, pos="99,18", width="0.75", height="0.5"];
    g [label=nodes, pos="176,18", width="0.89579", height="0.5"];
    a -> b [pos="e,63,180.1 63,215.7 63,207.98 63,198.71 63,190.11"];
    b -> c [pos="e,35.304,107.15 54.65,144.76 50.288,136.28 44.853,125.71 39.959,116.2"];
    b -> d [pos="e,90.696,107.15 71.35,144.76 75.712,136.28 81.147,125.71 86.041,116.2"];
    d -> e [pos="e,41.796,33.385 84.43,74.834 74.25,64.938 60.476,51.546 48.969,40.359"];
    d -> f [pos="e,99,36.104 99,71.697 99,63.983 99,54.712 99,46.112"];
    d -> g [pos="e,159.91,33.626 114.58,74.834 125.4,65.003 140,51.723 152.26,40.582"];
}

所有坐标都可以在输出中找到。如果您需要有关如何绘制图表的更多详细信息，您可以尝试使用 xdot 格式：dot -Txdot tree.gv

digraph g {
    node [label="\N"];
    graph [bb="0,0,208,252",
        _draw_="c 9 -#ffffffff C 9 -#ffffffff P 4 0 -1 0 252 209 252 209 -1 ",
        xdotversion="1.2"];
    a [label=I, pos="63,234", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 63 234 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 63 228 0 5 1 -I "];
    b [label=am, pos="63,162", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 63 162 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 63 156 0 17 2 -am "];
    c [label=a, pos="27,90", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 27 90 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 27 84 0 7 1 -a "];
    d [label=tree, pos="99,90", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 99 90 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 99 84 0 21 4 -tree "];
    e [label=with, pos="27,18", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 27 18 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 27 12 0 24 4 -with "];
    f [label=7, pos="99,18", width="0.75", height="0.5", _draw_="c 9 -#000000ff e 99 18 27 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 99 12 0 7 1 -7 "];
    g [label=nodes, pos="176,18", width="0.89579", height="0.5", _draw_="c 9 -#000000ff e 176 18 32 18 ", _ldraw_="F 14.000000 11 -Times-Roman c 9 -#000000ff T 176 12 0 34 5 -nodes "];
    a -> b [pos="e,63,180.1 63,215.7 63,207.98 63,198.71 63,190.11", _draw_="c 9 -#000000ff B 4 63 216 63 208 63 199 63 190 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 67 190 63 180 60 190 "];
    b -> c [pos="e,35.304,107.15 54.65,144.76 50.288,136.28 44.853,125.71 39.959,116.2", _draw_="c 9 -#000000ff B 4 55 145 50 136 45 126 40 116 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 43 114 35 107 37 118 "];
    b -> d [pos="e,90.696,107.15 71.35,144.76 75.712,136.28 81.147,125.71 86.041,116.2", _draw_="c 9 -#000000ff B 4 71 145 76 136 81 126 86 116 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 89 118 91 107 83 114 "];
    d -> e [pos="e,41.796,33.385 84.43,74.834 74.25,64.938 60.476,51.546 48.969,40.359", _draw_="c 9 -#000000ff B 4 84 75 74 65 60 52 49 40 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 51 38 42 33 47 43 "];
    d -> f [pos="e,99,36.104 99,71.697 99,63.983 99,54.712 99,46.112", _draw_="c 9 -#000000ff B 4 99 72 99 64 99 55 99 46 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 103 46 99 36 96 46 "];
    d -> g [pos="e,159.91,33.626 114.58,74.834 125.4,65.003 140,51.723 152.26,40.582", _draw_="c 9 -#000000ff B 4 115 75 125 65 140 52 152 41 ", _hdraw_="S 5 -solid c 9 -#000000ff C 9 -#000000ff P 3 155 43 160 34 150 38 "];
}

有关此格式的详细信息可以在 graphviz 网站上找到。

仅布局边/重新计算边

您可以使用上述输出之一，修改任何节点的位置，并且使用它作为以下命令的输入：

neato -n tree.modified.gv

这将仅重新计算边缘（有关neato dot和neato选项的更多信息可以在其手册页）。

下面您可以看到未修改和修改的布局的示例 - 我更改了 b 和 g 节点的位置。

自动布局：

修改后的布局：