third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.cluster;
  11
  12 import java.util.Collection;
  13 import java.util.HashSet;
  14 import java.util.Set;
  15
  16 import org.apache.commons.collections15.Buffer;
  17 import org.apache.commons.collections15.Transformer;
  18 import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
  19
  20 import edu.uci.ics.jung.graph.Graph;
  21
  22
  23
  24 /**
  25  * Finds all weak components in a graph as sets of vertex sets.  A weak component is defined as
  26  * a maximal subgraph in which all pairs of vertices in the subgraph are reachable from one
  27  * another in the underlying undirected subgraph.
  28  * <p>This implementation identifies components as sets of vertex sets.
  29  * To create the induced graphs from any or all of these vertex sets,
  30  * see <code>algorithms.filters.FilterUtils</code>.
  31  * <p>
  32  * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges.
  33  * @author Scott White
  34  */
  35 public class WeakComponentClusterer<V,E> implements Transformer<Graph<V,E>, Set<Set<V>>>
  36 {
  37         /**
  38      * Extracts the weak components from a graph.
  39      * @param graph the graph whose weak components are to be extracted
  40      * @return the list of weak components
  41      */
  42     public Set<Set<V>> transform(Graph<V,E> graph) {
  43
  44         Set<Set<V>> clusterSet = new HashSet<Set<V>>();
  45
  46         HashSet<V> unvisitedVertices = new HashSet<V>(graph.getVertices());
  47
  48         while (!unvisitedVertices.isEmpty()) {
  49                 Set<V> cluster = new HashSet<V>();
  50             V root = unvisitedVertices.iterator().next();
  51             unvisitedVertices.remove(root);
  52             cluster.add(root);
  53
  54             Buffer<V> queue = new UnboundedFifoBuffer<V>();
  55             queue.add(root);
  56
  57             while (!queue.isEmpty()) {
  58                 V currentVertex = queue.remove();
  59                 Collection<V> neighbors = graph.getNeighbors(currentVertex);
  60
  61                 for(V neighbor : neighbors) {
  62                     if (unvisitedVertices.contains(neighbor)) {
  63                         queue.add(neighbor);
  64                         unvisitedVertices.remove(neighbor);
  65                         cluster.add(neighbor);
  66                     }
  67                 }
  68             }
  69             clusterSet.add(cluster);
  70         }
  71         return clusterSet;
  72     }
  73 }