获取 JGraphT 中的所有子图

Question

如何在 List<MyGraph> 或 Set<MyGraph> 集合中获取 JGraphT 中图形的所有可能子图？ 我已经阅读了 JGraphT 的文档，但找不到任何可以帮助我解决该特定问题的内容。

Answer 1

这个问题的答案取决于 OP 是否想要 vertex-induced subgraph or an edge-induced subgraph. To create a vertex or edge induced subgraph in JGraphT, use the AsSubgraph class。没有一种方法可以简单地生成所有可能的子图，因为这是一个非常不常见的过程，但很容易自己实现。请注意，有 2^n 个可能的顶点诱导子图，其中 n 是顶点数。所以子图的数量很大。

1. 创建一个包含所有可能的顶点子集的列表。这称为幂集（有很多关于如何生成幂集的 SO 帖子）
2. 对于幂集中的每个集合，使用 AsSubgraph 生成一个导出子图。

粗略地看，代码如下所示：

//Initiate some graph. The vertex/edge type is irrelevant for this question
Graph<Integer,DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);
...

//Generate powerset
List<Set<Integer>> powerSet = powerSet(graph.vertexSet());

//Create subgraphs:
for(Set<Integer> subset : powerSet)
    Graph<Integer,DefaultEdge> subGraph = new AsSubgraph(graph, subset);

要实现powerSet功能，SO上可以找到很多例子。要计算边缘诱导子图，请重复上述操作，但不要使用 graph.vertexSet()，而是使用 graph.edgeSet();