public static Set connectedComponents()

in src/main/java/com/twitter/sbf/graph/ConnectedComponents.java [49:81]

• 31 lines of code
• 6 McCabe index (conditional complexity)

  public static Set<IntSet> connectedComponents(GraphInterface g) {
    Set<IntSet> ret = new HashSet<>();
    Queue<Integer> q = new LinkedBlockingQueue<>();
    IntSet unSeen = new IntOpenHashSet();
    IntIterator nodeIter = g.getAllNodeIds();
    while (nodeIter.hasNext()) {
      unSeen.add(nodeIter.nextInt());
    }

    while (!unSeen.isEmpty()) {
      int newNode = unSeen.iterator().next();
      IntSet newComponent = new IntOpenHashSet();
      newComponent.add(newNode);
      q.add(newNode);
      unSeen.remove(newNode);
      while (!q.isEmpty()) {
        int currentNode = q.remove();
        IntIterator iter = g.getNeighbors(currentNode);
        while (iter.hasNext()) {
          int nbr = iter.nextInt();
          if (unSeen.contains(nbr)) {
            q.add(nbr);
            assert !newComponent.contains(nbr);
            newComponent.add(nbr);
            unSeen.remove(nbr);
          }
        }
      }
      ret.add(newComponent);
    }

    return ret;
  }