그래프를 버텍스 라벨로 나누기

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