如何使用JGraphT将图划分为同类顶点连通子图？

要实现「将图划分为由同类别连通顶点组成的子图」，JGraphT没有直接的内置方法，但可以通过组合现有工具类快速实现，核心思路是先按类别分组顶点，再对每个类别提取诱导子图并找出连通分量，具体步骤如下：

实现步骤 #

• 第一步：按类别对顶点预分组
  用Map<类别类型, Set<V>>将所有顶点按所属类别归类，键为类别标识（比如Integer），值为对应类别的顶点集合。
• 第二步：生成每个类别的诱导子图
  对每个类别的顶点集合，使用AsSubgraph类构建原图的诱导子图——该子图仅包含对应类别的顶点，以及这些顶点在原图中存在的边。
• 第三步：提取诱导子图的连通分量
  借助ConnectivityInspector类，调用其connectedSets()方法，获取该类别下的所有连通顶点组。
• 第四步：汇总结果
  将所有类别的连通顶点组收集到List<Set<V>>中，即为最终的划分结果。

代码示例 #

import org.jgrapht.graph.AsSubgraph;
import org.jgrapht.alg.connectivity.ConnectivityInspector;
import org.jgrapht.graph.DefaultUndirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import java.util.*;

public class CategoryBasedPartitioning {
    public static void main(String[] args) {
        // 构建示例无向图
        DefaultUndirectedGraph<Integer, DefaultEdge> originalGraph = new DefaultUndirectedGraph<>(DefaultEdge.class);
        
        // 添加顶点与边
        originalGraph.addVertex(1);
        originalGraph.addVertex(2);
        originalGraph.addVertex(3);
        originalGraph.addVertex(4);
        originalGraph.addVertex(5);
        originalGraph.addVertex(6);
        
        originalGraph.addEdge(1, 2);
        originalGraph.addEdge(2, 3);
        originalGraph.addEdge(4, 5);

        // 定义顶点-类别映射
        Map<Integer, Integer> vertexToCategory = new HashMap<>();
        vertexToCategory.put(1, 0); // 类别0（对应示例中的红色）
        vertexToCategory.put(2, 0);
        vertexToCategory.put(3, 1); // 类别1（对应示例中的蓝色）
        vertexToCategory.put(4, 0);
        vertexToCategory.put(5, 0);
        vertexToCategory.put(6, 1);

        // 按类别分组顶点
        Map<Integer, Set<Integer>> categoryVertexMap = new HashMap<>();
        for (Map.Entry<Integer, Integer> entry : vertexToCategory.entrySet()) {
            categoryVertexMap.computeIfAbsent(entry.getValue(), k -> new HashSet<>()).add(entry.getKey());
        }

        // 生成最终划分结果
        List<Set<Integer>> partitionResult = new ArrayList<>();
        for (Set<Integer> categoryVertices : categoryVertexMap.values()) {
            // 生成当前类别的诱导子图
            AsSubgraph<Integer, DefaultEdge> categorySubgraph = new AsSubgraph<>(originalGraph, categoryVertices);
            // 获取子图的所有连通分量
            ConnectivityInspector<Integer, DefaultEdge> connectivityInspector = new ConnectivityInspector<>(categorySubgraph);
            partitionResult.addAll(connectivityInspector.connectedSets());
        }

        // 输出结果
        partitionResult.forEach(group -> System.out.println("连通顶点组：" + group));
    }
}

关于PartitioningImpl的说明 #

PartitioningImpl只是用来表示划分结果的容器类，而非生成划分的工具。如果你需要将最终的List<Set<V>>封装为标准的Partitioning对象，可以直接通过构造器创建：

import org.jgrapht.graph.PartitioningImpl;

// 将上述partitionResult转换为Partitioning对象
PartitioningImpl<Integer> partitioning = new PartitioningImpl<>(partitionResult);

内容的提问来源于stack exchange，提问作者micycle