识别 JgraphT 中的脱节图

Question

我有一个用例如下。我需要从一组输入构建一个图表，如下 -

SimpleDirectedGraph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
g.addVertex("APP");
g.addVertex("CHROME");
g.addVertex("MOZILLA");
g.addVertex("LAPTOP");
g.addVertex("SERVER");
g.addVertex("CHROME_DEV");
g.addVertex("MOZILLA_DEV");
g.addVertex("APP_DEV");

为服务器添加边

g.addEdge("SERVER", "APP");
g.addEdge("SERVER", "CHROME");
g.addEdge("SERVER", "MOZILLA");

为笔记本电脑添加边缘

g.addEdge("LAPTOP", "APP_DEV");
g.addEdge("LAPTOP", "CHROME_DEV");
g.addEdge("LAPTOP", "MOZILLA_DEV");

在这两个集合之间添加连接边

g.addEdge("CHROME", "CHROME_DEV");
g.addEdge("MOZILLA", "MOZILLA_DEV");

现在我可以构建这样的图，结构如下所示 -

但我的使用从这里开始。想象一下，我已经从上图中删除了连接边

g.removeEdge("CHROME", "CHROME_DEV");
g.removeEdge("MOZILLA", "MOZILLA_DEV");

现在我的图表基本上彼此不相交。我如何找出它是不相交的图以及如何获得两个不相交的图。之后我将不得不在这里分别处理这两个不相交的图。

Answer 1

您要找的是'connected components'。在 ConnectivityInspector.

有一个 look

测试你的图是否连通：

Graph<String, DefaultEdge> g = new SimpleDirectedGraph<>(DefaultEdge.class);
ConnectivityInspector ci = new ConnectivityInspector(g);
//Test whether the graph is connected:
ci.isConnected();

您可以使用以下方法获取每个连接组件的顶点： Set<String> vertexSets = ci.connectedSets(); 对于这些集合中的每一个，您可以创建一个在这些顶点上导出的图：

Set<String> vertexSets = ci.connectedSets();
for(Set<String> vertexSet : vertexSets){
    Graph<String, DefaultEdge> subgraph = new AsSubGraph(g,vertexSet);
    //Do something with the subgraph
}

可以找到有关图形连通性的更多信息here。出于您的问题的目的，您还可以查看 'strongly' 和 'weakly' 连接组件之间的区别。

识别 JgraphT 中的脱节图

Identifying disjoined graphs in JgraphT

java

graph

jgrapht