頂点ラベルでグラフを分割する

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()); 
}