| 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.ArrayList; | |
| 13 | import java.util.Collections; | |
| 14 | import java.util.Comparator; | |
| 15 | import java.util.HashMap; | |
| 16 | import java.util.HashSet; | |
| 17 | import java.util.Iterator; | |
| 18 | import java.util.List; | |
| 19 | import java.util.Map; | |
| 20 | import java.util.Set; | |
| 21 | ||
| 22 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
| 23 | import edu.uci.ics.jung.graph.Element; | |
| 24 | import edu.uci.ics.jung.graph.Graph; | |
| 25 | ||
| 26 | /** | |
| 27 | * A data structure representing the clusters, connected set of vertices (or edges), in a graph. The clusters can be | |
| 28 | * retrieved based upon their position index in the collection. Also, given a vertex (or edge) the corresponding | |
| 29 | * clusters can be retrieved. There is no requirement that the union of the set of vertices (or edges) in each | |
| 30 | * cluster needs to equal the set of all vertices in the graph. | |
| 31 | * @author Scott White | |
| 32 | */ | |
| 33 | public abstract class ClusterSet { | |
| 34 | private List mClusters; | |
| 35 | private Map mUDCToClustersMap; | |
| 36 | private ArchetypeGraph mUnderlyingGraph; | |
| 37 | ||
| 38 | /** | |
| 39 | * Creates a new instance. | |
| 40 | */ | |
| 41 | 17 | public ClusterSet(ArchetypeGraph underlyingGraph) { |
| 42 | 17 | mClusters = new ArrayList(); |
| 43 | 17 | mUDCToClustersMap = new HashMap(); |
| 44 | 17 | mUnderlyingGraph = underlyingGraph; |
| 45 | 17 | } |
| 46 | ||
| 47 | /** | |
| 48 | * Adds a new cluster to the collection. | |
| 49 | * @param elements the set of vertices (or edges) comprising a component to be added | |
| 50 | */ | |
| 51 | public void addCluster(Set elements) { | |
| 52 | 32 | if (elements == null || elements.size() == 0) { |
| 53 | 0 | throw new IllegalArgumentException("The set of elements must have at least one element"); |
| 54 | } | |
| 55 | ||
| 56 | 32 | for (Iterator udcIt=elements.iterator();udcIt.hasNext();) { |
| 57 | 80 | Element udc = (Element) udcIt.next(); |
| 58 | ||
| 59 | 80 | checkLegality(udc); |
| 60 | ||
| 61 | 80 | Set components = (Set) mUDCToClustersMap.get(udc); |
| 62 | 80 | if (components == null) { |
| 63 | 75 | components = new HashSet(); |
| 64 | 75 | mUDCToClustersMap.put(udc,components); |
| 65 | } | |
| 66 | ||
| 67 | 80 | components.add(elements); |
| 68 | } | |
| 69 | 32 | mClusters.add(elements); |
| 70 | ||
| 71 | 32 | } |
| 72 | ||
| 73 | protected void checkLegality(Element e) | |
| 74 | { | |
| 75 | 80 | if (e.getGraph() != getUnderlyingGraph()) { |
| 76 | 0 | throw new IllegalArgumentException("All elements passed in must be from the correct underlying graph."); |
| 77 | } | |
| 78 | 80 | } |
| 79 | ||
| 80 | /** | |
| 81 | * Constructs a new graph from the given cluster | |
| 82 | * @param index the position index of the cluster in the collection | |
| 83 | * @return a new graph representing the cluster | |
| 84 | */ | |
| 85 | abstract public Graph getClusterAsNewSubGraph(int index); | |
| 86 | ||
| 87 | /** | |
| 88 | * Returns the corresponding cluster set in the other graph. If any of the vertices (or edges) in the specified | |
| 89 | * graph are not equivalent to the corresponding vertices (or edges) in this graph then an IllegalArgumentException | |
| 90 | * is thrown. | |
| 91 | * @param anotherGraph another graph whose corresponding clusters are to be retrieved | |
| 92 | * @return the set of clsuters for the new graph | |
| 93 | */ | |
| 94 | abstract public ClusterSet createEquivalentClusterSet(Graph anotherGraph); | |
| 95 | ||
| 96 | /** | |
| 97 | * Given a vertex (or edge), retrieves the clusters which that vertex (or edge) belongs to if any | |
| 98 | * @param element the vertex (or edge) whose cluster is to be retrieved. | |
| 99 | * @return the set of clusters (set of non-overlapping vertices (or edges)) | |
| 100 | */ | |
| 101 | public Set getClusters(Element element) { | |
| 102 | 22 | return (Set) mUDCToClustersMap.get(element); |
| 103 | } | |
| 104 | ||
| 105 | /** | |
| 106 | * Given the cluster's position in the list (0-based), retrieve the cluster (set of vertices) | |
| 107 | * @param index the 0-based index of the cluster in the list. | |
| 108 | * @return the set of vertices (or edges) comprising the cluster | |
| 109 | */ | |
| 110 | public Set getCluster(int index) { | |
| 111 | 37 | return (Set) mClusters.get(index); |
| 112 | } | |
| 113 | ||
| 114 | /** | |
| 115 | * Returns an iterator to the component list. | |
| 116 | * @return the iterator to the component list | |
| 117 | */ | |
| 118 | public Iterator iterator() { | |
| 119 | 2 | return mClusters.iterator(); |
| 120 | } | |
| 121 | ||
| 122 | /** | |
| 123 | * the size of the cluster collection. | |
| 124 | * @return the number of clusters in the collection | |
| 125 | */ | |
| 126 | public int size() { | |
| 127 | 36 | return mClusters.size(); |
| 128 | } | |
| 129 | ||
| 130 | /** | |
| 131 | * Sorts the clusters by size. | |
| 132 | */ | |
| 133 | public void sort() { | |
| 134 | 0 | Collections.sort(mClusters, new Comparator() { |
| 135 | public int compare(Object o1, Object o2) { | |
| 136 | Set cluster1 = (Set) o1; | |
| 137 | Set cluster2 = (Set) o2; | |
| 138 | if (cluster1.size() < cluster2.size()) return 1; | |
| 139 | if (cluster1.size() > cluster2.size()) return -1; | |
| 140 | return 0; | |
| 141 | } | |
| 142 | }); | |
| 143 | ||
| 144 | 0 | } |
| 145 | ||
| 146 | public ArchetypeGraph getUnderlyingGraph() { | |
| 147 | 80 | return mUnderlyingGraph; |
| 148 | } | |
| 149 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |