通過頂點標籤對圖進行分區

Question

我正在研究需要將定向標籤圖劃分成多個子圖的問題。在每個子圖中，節點都連接在一起，並且它們具有相同的標籤。有沒有一種有效的算法來解決這個問題？

Answer 1

這是我用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()); 
}