通过顶点标签对图进行分区

问题描述：

我正在研究需要将定向标签图划分成多个子图的问题。在每个子图中，节点都连接在一起，并且它们具有相同的标签。有没有一种有效的算法来解决这个问题？通过顶点标签对图进行分区

定义“分区”。听起来像运行一个简单的DFS可以解决您的问题。 –

一组连接并具有标签的顶点进入一个分区 –

因此，您基本上想要检测图形组件？ https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29?wprov=sfla1 –

答

这是我用Java实现的解决方案，它使用JGraphT作为图库。

private Set<Set<Node>> partition(DirectedGraph<Node, Edge> graph) { 
    Map<Node, Set<Node>> map = new HashMap<Node, Set<Node>>(); 
    for (Edge edge : graph.edgeSet()) { 
     Node source = graph.getEdgeSource(edge); 
     Node target = graph.getEdgeTarget(edge); 
     if (source.getLabel().equals(target.getLabel())) { 
      if (map.get(source) != null && map.get(target) == null) { 
       map.get(source).add(target); 
       map.put(target, map.get(source)); 
      } else if (map.get(target) != null && map.get(source) == null) { 
       map.get(target).add(source); 
       map.put(source, map.get(target)); 
      } else if (map.get(source) == null && map.get(target) == null) { 
       Set<Node> set = new HashSet<Node>(); 
       set.add(source); 
       set.add(target); 
       map.put(source, set); 
       map.put(target, set); 
      } else { 
       Set<Node> sourceSet = map.get(source); 
       Set<Node> targetSet = map.get(target); 
       sourceSet.addAll(targetSet); 
       for(Node n : targetSet){ 
        map.put(n,sourceSet); 
       } 
       targetSet = null; 
      } 
     } else { 
      if (map.get(source) == null) { 
       Set<Node> set = new HashSet<Node>(); 
       set.add(source); 
       map.put(source, set); 
      } 
      if (map.get(target) == null) { 
       Set<Node> set = new HashSet<Node>(); 
       set.add(target); 
       map.put(target, set); 
      } 
     } 
     Collection<Set<Node>> values = map.values(); 
    } 
    return new HashSet<Set<Node>>(map.values()); 
}

通过顶点标签对图进行分区

相关推荐