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. |
copyright © 2003, jcoverage ltd. all rights reserved. |