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

Line | Hits | Source
--- | --- | ---
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 |  | `*/`
31 | 11 | `public 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 |  | ``
40 | 11 | `ClusterSet clusterSet = new VertexClusterSet(aGraph);`
41 |  | ``
42 | 11 | `HashSet unvisitedVertices = new HashSet();`
43 | 11 | `for (Iterator vIt=aGraph.getVertices().iterator(); vIt.hasNext();) {`
44 | 50 | `unvisitedVertices.add(vIt.next());`
45 |  | `}`
46 |  | ``
47 | 30 | `while (!unvisitedVertices.isEmpty()) {`
48 | 19 | `Set weakComponentSet = new HashSet();`
49 | 19 | `ArchetypeVertex root = (ArchetypeVertex) unvisitedVertices.iterator().next();`
50 | 19 | `unvisitedVertices.remove(root);`
51 | 19 | `weakComponentSet.add(root);`
52 |  | ``
53 | 19 | `Buffer queue = new UnboundedFifoBuffer();`
54 | 19 | `queue.add(root);`
55 |  | ``
56 | 69 | `while (!queue.isEmpty()) {`
57 | 50 | `ArchetypeVertex currentVertex = (ArchetypeVertex) queue.remove();`
58 | 50 | `Set neighbors = currentVertex.getNeighbors();`
59 |  | ``
60 | 50 | `for (Iterator nIt = neighbors.iterator(); nIt.hasNext();) {`
61 | 74 | `ArchetypeVertex neighbor = (ArchetypeVertex) nIt.next();`
62 | 74 | `if (unvisitedVertices.contains(neighbor)) {`
63 | 31 | `queue.add(neighbor);`
64 | 31 | `unvisitedVertices.remove(neighbor);`
65 | 31 | `weakComponentSet.add(neighbor);`
66 |  | `}`
67 |  | `}`
68 |  | `}`
69 | 19 | `clusterSet.addCluster(weakComponentSet);`
70 |  | `}`
71 |  | ``
72 | 11 | `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.