如何通过消除蛇行和更好的边缘交叉来影响Graphviz/点以制作更好的控制流图? [英] How can I influence Graphviz/dot to make nicer control-flow graphs by removing snaking and better edge crossings?

问题描述

我正在为Python程序绘制控制流程图，并希望影响不应跨越的边缘类型.有没有办法做到这一点?

I am drawing control-flow graphs for Python programs and would like to influence which kind of edges should not be crossed over. Is there a way to do this?

考虑以下简单的Python程序:

Consider this simple Python program:

try:
    a += 1
except:
    a += 2
else:
    a = 3

和一个点程序代表通过 https://github生成的控制流.com/rocky/python-control-flow/

And a dot program to represent the control flow for that generated via https://github.com/rocky/python-control-flow/

digraph G {
  mclimit=1.5;
  rankdir=TD; ordering=out;
  graph[fontsize=10 fontname="Verdana"];
  color="#efefef";
  node[shape=box style=filled fontsize=8 fontname="Verdana" fillcolor="#efefef"];
  edge[fontsize=8 fontname="Verdana"];

  node_0 [shape = "oval"][label="Basic Block 0\loffsets: 0..12\lflags=entry, block, unconditional, try\ljumps=[34]\l"];
  node_1 [label="Basic Block 1\loffsets: 14..30\lflags=except, unconditional\ljumps=[38]\l"];
  node_2 [label="Basic Block 2\loffsets: 32..32\lflags=end finally\l"];
  node_3 [label="Basic Block 3\loffsets: 34..36\l"];
  node_4 [label="Basic Block 4\loffsets: 38..40\lflags=no fallthrough\l"];

  node_0 -> node_2 [weight=1][color="red"];
  node_3 -> node_4 [weight=10];
  node_0 -> node_1 [weight=1][color="red"];
  node_2 -> node_3 [weight=10];
  node_0 -> node_1 [weight=10][style="invis"];
  node_1 -> node_2 [weight=10][style="invis"];
  node_1 -> node_4 [weight=1];
  node_0 -> node_3 [weight=1];
}

上面为点生成的图像为

The image that dot produces for the above is

请注意，一条线如何蜿蜒并向下穿过直线箭头.相反，我希望如果没有一个向下的直线箭头会被交叉.花键边缘将使交叉的位置更好.

Notice how one line snakes around and crosses a straight arrow down. Instead I would prefer if none of the straight downward arrows would be crossed. Splined edges would make better crossing places.

如果您查看该点，则有两个不可见的向下边缘，用于对齐. (在字节码中，它们遵循指令的线性顺序).

If you look at the dot, I have two invisible downward edges which I use for alignment. (In the bytecode these follow the linear sequence of instructions).

因此，如果需要越过一条向下的直线(此处不需要)，则不可见的边缘将优先于可见的边缘.

So if a downward straight line needs to be crossed (and here it doesn't), invisible edges would be preferred over those that are visible.

有什么想法吗?

修改

到目前为止，一个极好的答案是建议更改定义边缘的顺序，并在某些情况下指定应进行边缘连接的位置.

The one excellent answer so far suggests changing the order that the edges are defined and specifying in certain situations where edge attachments should be made.

在此应用程序中，我确实具有来自统治者树的分层嵌套信息，并且可以对边缘进行分类:那些边缘，那些循环，跳转到复合结构末端的边缘，那些破坏循环的边缘，等等.

In this application, I do have hierarchical nesting information from a dominator tree, and I can classify the edges: those that loop, those that jump to the end of a compound structure, those that break out a loop, and so on.

因此，现在的问题恰恰是如何使用此信息来避免出现那些弯腰的箭头，并确保最好采用跳出循环的方式来越过例如"if"/"else"跳转的边缘边缘.

So now the problem becomes exactly how one uses this information to avoid those snaking arrows, and ensures that breaks out of loops are preferred to cross over edges over say "if"/"else" jump edges.

感觉就像是VLSI设计:提出了一套适用于每种(控制流)结构的模式，然后这些模式将正确嵌套和排序.

This feels like VLSI design: come up with a set of patterns that work for each kind of (control-flow) structure and those will then nest and sequence properly.

我已经尝试了边缘的排序和放置，但是我对何时早晚放置东西没有直觉.

I have experimented with the edge ordering and placement, and I just don't have an intuitive sense of when to put something earlier or later.

对于结构化控制流边缘的指导或更好的指导，将不胜感激.

Guidance, or better, a design rule for structured control flow edges would be greatly appreciated.

推荐答案

您需要做两件事来改善这种情况:

You need to do two things to improve the situation:

• 先绘制要控制的边缘(之一)，然后再控制其他边缘，
• 告诉graphviz您希望将它们连接到的位置(北，东...)

我已经相应地编辑了您的代码

I have edited your code accordingly

digraph G {
  mclimit=1.5;
  rankdir=TD; ordering=out;
  graph[fontsize=10 fontname="Verdana"];
  color="#efefef";
  node[shape=box style=filled fontsize=8 fontname="Verdana" fillcolor="#efefef"];
  edge[fontsize=8 fontname="Verdana"];

  node_0 [shape = "oval"][label="Basic Block 0\loffsets: 0..12\lflags=entry, block, unconditional, try\ljumps=[34]\l"];
  node_1 [label="Basic Block 1\loffsets: 14..30\lflags=except, unconditional\ljumps=[38]\l"];
  node_2 [label="Basic Block 2\loffsets: 32..32\lflags=end finally\l"];
  node_3 [label="Basic Block 3\loffsets: 34..36\l"];
  node_4 [label="Basic Block 4\loffsets: 38..40\lflags=no fallthrough\l"];

  node_0 -> node_3:nw [weight=1];           /* moved up and added directions*/
  node_0 -> node_2 [weight=1][color="red"];
  node_3 -> node_4 [weight=10];
  node_0 -> node_1 [weight=1][color="red"];
  node_2 -> node_3 [weight=10];
  node_0 -> node_1 [weight=10][style="invis"];
  node_1 -> node_2 [weight=10][style="invis"];
  node_1:se -> node_4:ne [weight=1];            /* added directions */
}

这给你

这里涉及到一些试验和错误，但是我相信这会有所帮助.

There's a bit of trial and error involved here but I'm sure this should help.

这篇关于如何通过消除蛇行和更好的边缘交叉来影响Graphviz/点以制作更好的控制流图?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！