java使用jgrapht创建带集群的图形

Question

有没有办法使用jgrapht创建带有集群的图形？ 带有两个簇“进程1”和“进程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

你的图形设计有点奇怪。当我目测你的图时，我看到一个基本图和两组聚集的节点。当我查看你的点文件时，我看到两个子图，以及一个“外部”图，它指的是子图中的特定节点。请注意，子图不是簇

你的问题似乎有两个部分：（1）你能用jgrapht创建一个带有簇的图吗？（2）你能在你的例子中创建点文件吗。答案是：（1）是，（2）不是，至少不是现成的，因为DOTExporter不支持“子图”

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

1. 创建一个带有边和顶点的常规图，并保持一个单独的List<Set<V>>来存储集群。您可以使用AsSubgraph类来可视化特定集群诱导的子图
2. JGraphT支持任何类型的顶点。所以顶点也可以是图！你可以创建一个图，其中每个顶点本身就是一个图；这些顶点之间的边表示这些特殊顶点之间的关系。我们在BlockCutpointGraph实现中做了类似的事情

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

1. 创建一个带有顶点和边的常规图形（在您的情况下，图形中的所有节点和圆弧）
2. 创建诱导子图集群（在您的例子中，一个子图用于process1，另一个子图用于Process2）。为此，您可以使用AsSubgraph类
3. 创建一个不包含集群内部存在的任何弧的图形。为此，可以使用MaskSubgraph类
4. 使用DOTExporter类导出在步骤（2）和（3）中创建的图形
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];
    }

1. 步骤（2）中的一个诱导子图：

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

在这里，您必须用subgraph替换digraph，并将此图插入基本图中，以获得：

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];
}

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