java - 使用 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 个子图和一个引用子图中特定节点的“外部”图。请注意，子图不是簇。

您的问题似乎有两部分:(1)您可以使用 jgrapht 创建一个包含集群的图表吗？(2)您可以在示例中创建 DOT 文件吗？答案是:(1) 是，(2) 否，至少不是开箱即用的，因为 DOTExporter不支持“子图”。

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

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

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

1. 创建一个包含顶点和边的常规图形(在您的情况下是图形中的所有节点和弧)。
2. 创建归纳子图簇(在您的例子中，一个子图用于进程 1，另一个子图用于进程 2。为此，您可以使用 AsSubgraph 类
3. 创建一个不包含集群内部存在的任何弧的图表。为此，您可以使用 MaskSubgraph类。
4. 使用 DOTExporter 导出您在步骤 (2) 和 (3) 中创建的图表。类(class)。
5. 最后一步，您必须将导出的图表合并到一个文件中。我将使用步骤 (3) 中的图表作为“基础”图表，并使用 subgraph 插入其他图表。关键工作。

使用您的示例:

1. 第 (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];
}

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