使用 jgrapht 创建带簇的图

Question

有什么方法可以使用 jgrapht 创建带簇的图吗？具有两个集群 "process #1" 和 "process #2" 的示例图：

预期的点文件内容：

digraph G {
subgraph cluster_0 {
style=filled;
color=lightgrey;
node [style=filled,color=white];
a0 -> a1 -> a2 -> a3;
label = "process #1";
}

subgraph cluster_1 {
node [style=filled];
b0 -> b1 -> b2 -> b3;
label = "process #2";
color=blue
}
start -> a0;
start -> b0;
a1 -> b3;
b2 -> a3;
a3 -> a0;
a3 -> end;
b3 -> end;

start [shape=Mdiamond];
end [shape=Msquare];
}

Answer 1

你的图表设计有点奇特。当我目视查看您的图表时，我看到一个基本图表和 2 个集群 节点组 。当我查看您的 DOT 文件时，我看到 2 个子图和一个 'outer' 图，它指代子图中的特定节点。请注意，子图不是簇。

您的问题似乎有两个部分：(1) 您可以使用 jgrapht 创建一个带簇的图形吗？(2) 您可以在您的示例中创建 DOT 文件吗？答案是：(1) 是，(2) 否，至少不是开箱即用，因为 DOTExporter 不支持 'subgraphs'.

有几种不同的方法可以创建聚类图。

创建一个包含边和顶点的规则图，并维护一个单独的 List<Set<V>> 来存储您的集群。您可以使用 AsSubgraph class.
JGraphT 支持任何类型的顶点。所以一个顶点也可以是一个图！您可以创建一个图，其中每个顶点本身就是一个图；这些顶点之间的边表示这些特殊顶点之间的关系。我们在 BlockCutpointGraph 实现中做了类似的事情。

如果您想以与示例 DOT 文件类似的方式导出图形，则必须做一些工作。您可以实现自己的自定义 DOTExporter，或修改现有的。也许一个简单的替代方案（不是最干净的）是按照以下几行做一些事情：

创建一个包含顶点和边的规则图（在您的例子中是图中的所有节点和弧线）。
创建你的诱导子图集群（在你的例子中，一个子图用于进程 1，另一个子图用于进程 2。为此你可以使用 AsSubgraph class
创建一个不包含集群内部存在的任何弧的图形。为此，您可以使用 MaskSubgraph class.
使用 DOTExporter class 导出您在步骤 (2) 和 (3) 中创建的图表。
作为最后一步，您必须将导出的图形合并到一个文件中。我将使用步骤 (3) 中的图表作为 'base' 图表，并使用 subgraph 键插入其他图表。

使用你的例子：

来自步骤 (3) 的基础图：

    digraph G {
      start -> a0;
      start -> b0;
      a1 -> b3;
      b2 -> a3;
      a3 -> a0;
      a3 -> end;
      b3 -> end;

      start [shape=Mdiamond];
      end [shape=Msquare];
    }

步骤 (2) 中的一个导出子图：

    digraph cluster_0 {
        style=filled;
        color=lightgrey;
        node [style=filled,color=white];
        a0 -> a1 -> a2 -> a3;
        label = "process #1";
    }

这里要把digraph换成subgraph，把这张图插入到基础图中得到：

digraph G {
  subgraph cluster_0 {
    style=filled;
    color=lightgrey;
    node [style=filled,color=white];
    a0 -> a1 -> a2 -> a3;
    label = "process #1";
  }

  start -> a0;
  start -> b0;
  a1 -> b3;
  b2 -> a3;
  a3 -> a0;
  a3 -> end;
  b3 -> end;

  start [shape=Mdiamond];
  end [shape=Msquare];
}

显然，您必须对剩余的集群重复此操作。

使用 jgrapht 创建带簇的图

Creating graph with clusters using jgrapht

java

jgrapht