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