为什么Graphviz不再最小化边长

为什么Graphviz不再最小化边长

本文介绍了引入子图时,为什么Graphviz不再最小化边长的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有这个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,但是您可能想继续阅读并立即阅读,以及Stephen North的以下回答-他们应该知道,所以我在此引用一些内容...


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

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

A D G
B E H
C F I

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

ERG写道:

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

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:

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:

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不再最小化边长的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-05 04:30