引入子图时，为什么Graphviz不再最小化边长 [英] Why does Graphviz no longer minimise edge lengths when subgraphs are introduced

问题描述

我有这个Graphviz图:

digraph
{
   rankdir="LR";
   overlap = true;
   Node[shape=record, height="0.4", width="0.4"];
   Edge[dir=none];

   A B C D E F G H I 

   A -> B -> C
   D -> E -> F
   G -> H -> I

   Edge[constraint=false]

   A -> D -> G

   subgraph clusterX
   {
      A
      B
   }

   subgraph clusterY
   {
      E
      H
      F
      I
   }
}

产生以下输出:

我本来希望A和D之间的边缘长度最小化，以便将节点布置为:

A B C
D E F
G H I

而不是

D E F
G H I
A B C

如果删除子图定义，这将按预期工作.

引入子图后，为什么Graphviz会在底部放置A B C?

解决方案

这与最小化边缘长度无关，尤其是因为在示例中，边缘是用属性constraint=false定义的./p>

虽然这不是一个完整的答案，但我认为可以在以下两点内找到它:

• 图中节点的出现顺序很重要.
• 将rankdir更改为LR包含不可预测的(或至少很难预测的)行为，和/或可能仍然是一两个错误(在graphviz邮件列表上的Emden R. Gansner的回复，以及Stephen North的以下回答-他们应该知道，所以我在此引用一些内容...

  ---

  为什么节点的出现顺序很重要?默认情况下，除非边缘和约束条件导致布局更好，否则在自上而下的图中，首先提到的节点将出现在随后的节点的左侧.

  因此，在没有聚类和rankdir=LR的情况下，图形显示如下(毫无意外):

  A D G
  B E H
  C F I
  

  到目前为止，太好了.但是，当应用rankdir=LR时会发生什么?

  ERG写道:

  Dot通过正常的TB布局处理rankdir = LR，然后旋转 逆时针旋转90度(然后当然是 节点旋转，边缘方向等).因此，第一个子图是 可以将其放置在TB布局中第二个子图的左侧 期望值，然后轮换后最终低于它.如果你想 将第一个子图放在顶部，在图中将其列出第二个.

  因此，如果这是正确的，并且没有群集，则节点应如下所示:

  G H I
  D E F
  A B C
  

  实际上，它们确实是这样的:

  A B C
  D E F
  G H I
  

  为什么?斯蒂芬·诺斯回答:

  在某些时候，我们决定将自上而下设置为默认值，
  即使图形被旋转，也有代码将平面翻转 内部边缘.

  因此，该图的布局为TB，逆时针旋转且平边翻转了:

  A D G     G H I     A B C
  B E H --> D E F --> D E F
  C F I     A B C     G H I
  

  尽管这对于简单的图形而言效果很好，但是当涉及到群集时，情况似乎有所不同.通常，边缘也会在群集内翻转(如在clusterY中一样)，但是在某些情况下，平坦边缘翻转无法正常工作.您的例子就是其中一种.

  为什么在翻转这些边缘时出现错误或限制?因为使用rankdir=TB时，相同的图通常可以正确显示.

  ---

  幸运的是，解决方法通常很容易-例如，您可以使用节点的出现顺序来影响布局:

  digraph
  {
     rankdir="LR";
     node[shape=record, height="0.4", width="0.4"];
     edge[dir=none];
  
     E; // E is first node to appear
     A -> B -> C;
     D -> E -> F;
     G -> H -> I;
  
     edge[constraint=false]
     A -> D -> G;
  
     subgraph clusterX { A; B; }
     subgraph clusterY { E; F; H; I; }
  }
  

  I have this Graphviz graph:

  digraph
  {
     rankdir="LR";
     overlap = true;
     Node[shape=record, height="0.4", width="0.4"];
     Edge[dir=none];
  
     A B C D E F G H I 
  
     A -> B -> C
     D -> E -> F
     G -> H -> I
  
     Edge[constraint=false]
  
     A -> D -> G
  
     subgraph clusterX
     {
        A
        B
     }
  
     subgraph clusterY
     {
        E
        H
        F
        I
     }
  }
  

  which produces this output:

  I would have expected the length of the edge between A and D to be minimised so that the nodes would be arranged as:

  A B C
  D E F
  G H I
  

  rather than

  D E F
  G H I
  A B C
  

  This works as expected if I remove the subgraph definitions.

  Why does Graphviz place A B C at the bottom when the subgraphs are introduced?

  解决方案

  This is not really about minimizing edge lengths, especially since in the example the edges are defined with the attribute constraint=false.

  While this is not a complete answer, I think it can be found somewhere within the following two points:

  • The order of appearance of nodes in the graph is important.
  • Changing rankdir to LR contains unpredictable (or at least difficult to predict) behaviour, and/or probably still a bug or two (search rankdir).

  I'll try to explain as good as I can and understand graphviz, but you may want to go ahead and read right away this reply of Emden R. Gansner on the graphviz mailing list as well as the following answer of Stephen North - they ought to know, so I will cite some of it...

  ---

  Why is the order of appearance of nodes important? By default, in a top-down graph, first mentioned nodes will appear on the left of the following nodes unless edges and constraints result in a better layout.

  Therefore, without clusters and rankdir=LR, the graphs appears like this (no surprises):

  A D G
  B E H
  C F I
  

  So far, so good. But what happens when rankdir=LR is applied?

  ERG wrote:

  Dot handles rankdir=LR by a normal TB layout and then rotating the layout counterclockwise by 90 degrees (and then, of course, handling node rotation, edge direction, etc.). Thus, subgraph one is positioned to the left of subgraph two in the TB layout as you would expect, and then ends up lower than it after rotation. If you want subgraph one to be on top, list it second in the graph.

  So if that would be correct, without clusters, the nodes should appear like this:

  G H I
  D E F
  A B C
  

  In reality, they do appear like this:

  A B C
  D E F
  G H I
  

  Why? Stephen North replied:

  At some point we decided that top-to-bottom should be the default,
  even if the graph is rotated, so there's code that flips the flat edges internally.

  So, the graph is layed out TB, rotated counterclock wise and flat edges flipped:

  A D G     G H I     A B C
  B E H --> D E F --> D E F
  C F I     A B C     G H I
  

  While this works quite well for simple graphs, it seems that when clusters are involved, things are a little different. Usually edges are also flipped within clusters (as in clusterY), but there are cases where the flat edge flipping does not work as one would think. Your example is one of those cases.

  Why is the error or limitation in the flipping of those edges? Because the same graphs usually display correctly when using rankdir=TB.

  ---

  Fortunately, workarounds are often easy - for example, you may use the order of appearance of the nodes to influence the layout:

  digraph
  {
     rankdir="LR";
     node[shape=record, height="0.4", width="0.4"];
     edge[dir=none];
  
     E; // E is first node to appear
     A -> B -> C;
     D -> E -> F;
     G -> H -> I;
  
     edge[constraint=false]
     A -> D -> G;
  
     subgraph clusterX { A; B; }
     subgraph clusterY { E; F; H; I; }
  }
  

  这篇关于引入子图时，为什么Graphviz不再最小化边长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！