| 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. |