Coverage details for edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer

LineHitsSource
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.HashSet;
13 import java.util.Iterator;
14 import java.util.Set;
15  
16 import org.apache.commons.collections.Buffer;
17 import org.apache.commons.collections.buffer.UnboundedFifoBuffer;
18  
19 import edu.uci.ics.jung.graph.ArchetypeGraph;
20 import edu.uci.ics.jung.graph.ArchetypeVertex;
21  
22  
23 /**
24  * Finds all weak components in a graph where a weak component is defined as
25  * a maximal subgraph in which all pairs of vertices in the subgraph are reachable from one
26  * another in the underlying undirected subgraph.
27  * <p>
28  * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges.
29  * @author Scott White
30  */
3111public class WeakComponentClusterer implements GraphClusterer {
32  
33     /**
34      * Extracts the weak components from a graph.
35      * @param aGraph the graph whose weak components are to be extracted
36      * @return the list of weak components
37      */
38     public ClusterSet extract(ArchetypeGraph aGraph) {
39  
4011        ClusterSet clusterSet = new VertexClusterSet(aGraph);
41  
4211        HashSet unvisitedVertices = new HashSet();
4311        for (Iterator vIt=aGraph.getVertices().iterator(); vIt.hasNext();) {
4450            unvisitedVertices.add(vIt.next());
45         }
46  
4730        while (!unvisitedVertices.isEmpty()) {
4819            Set weakComponentSet = new HashSet();
4919            ArchetypeVertex root = (ArchetypeVertex) unvisitedVertices.iterator().next();
5019            unvisitedVertices.remove(root);
5119            weakComponentSet.add(root);
52  
5319            Buffer queue = new UnboundedFifoBuffer();
5419            queue.add(root);
55  
5669            while (!queue.isEmpty()) {
5750                ArchetypeVertex currentVertex = (ArchetypeVertex) queue.remove();
5850                Set neighbors = currentVertex.getNeighbors();
59  
6050                for (Iterator nIt = neighbors.iterator(); nIt.hasNext();) {
6174                    ArchetypeVertex neighbor = (ArchetypeVertex) nIt.next();
6274                    if (unvisitedVertices.contains(neighbor)) {
6331                        queue.add(neighbor);
6431                        unvisitedVertices.remove(neighbor);
6531                        weakComponentSet.add(neighbor);
66                     }
67                 }
68             }
6919            clusterSet.addCluster(weakComponentSet);
70         }
71  
7211        return clusterSet;
73     }
74  
75 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.