将图划分为具有相同类别的邻居组

Question

使用JGraphT，我想将图划分为组，其中每个组由具有相同“类”的顶点的连接子图组成（使用下面的颜色表示）。

示例——所需的组为红色：

我认为这是一个相当简单的需求，但我找不到（内置）方法来做到这一点。我注意到有一个

PartitioningImpl

类，它使用

List<Set<V>> classes

构造，但我没有找到一种方法来 使用 来划分图形。

理想情况下，我会提供 something 与我的图形和顶点类（例如

V

-->

Integer

的映射），它会返回类似于分区顶点组

List<Set<V>>

的内容。

Answer 1

有时你无法避免编写一些代码

LOOP over classes
   LOOP over nodes that are in class
       Copy node to new graph
   LOOP over edges that connect nodes in class
       Copy edge to new graph
   LOOP over connected components in new graph
       Save component as a group graph for class

Answer 2

这是使用 JGraphT 的相当简单的方法：

• 删除不同类中相邻顶点之间的边。
• 然后，将

  ConnectivityInspector

  应用于结果图以识别连接的组件，这将代表组。

SimpleGraph<V, E> graph; // given by user
Map<V, Integer> classes; // given by user

List<E> toRemove = new ArrayList<>();
graph.edgeSet().forEach(e -> {
    V a = graph.getEdgeSource(e);
    V b = graph.getEdgeTarget(e);
    if (!classes.get(a).equals(classes.get(b))) {
        toRemove.add(e);
    }
});

graph.removeAllEdges(toRemove);
ConnectivityInspector<V, E> ci = new ConnectivityInspector<>(graph);
List<Set<V>> groups = ci.connectedSets();