# Coverage details for edu.uci.ics.jung.graph.impl.BipartiteGraph

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 |  | `/*`
11 |  | `* Created on Aug 6, 2003`
12 |  | `*/`
13 |  | `package edu.uci.ics.jung.graph.impl;`
14 |  | ``
15 |  | `import java.util.Collections;`
16 |  | `import java.util.HashSet;`
17 |  | `import java.util.Iterator;`
18 |  | `import java.util.Set;`
19 |  | ``
20 |  | `import org.apache.commons.collections.MultiHashMap;`
21 |  | `import org.apache.commons.collections.MultiMap;`
22 |  | ``
23 |  | `import edu.uci.ics.jung.exceptions.FatalException;`
24 |  | `import edu.uci.ics.jung.graph.Edge;`
25 |  | `import edu.uci.ics.jung.graph.Graph;`
26 |  | `import edu.uci.ics.jung.graph.Vertex;`
27 |  | `import edu.uci.ics.jung.utils.GraphUtils;`
28 |  | `import edu.uci.ics.jung.utils.UserData;`
29 |  | ``
30 |  | `/**`
31 |  | `* A Bipartite graph is divided into A vertices and B vertices. Edges`
32 |  | `* only connect A vertices to B vertices, and vice versa. This class`
33 |  | `* extends <i>UndirectedSparseGraph</i>; thus, the Graph is made up of`
34 |  | `* <i>UndirectedSparseVertices</i>. <p>`
35 |  | `* Vertices can only be added to the graph with a flag that says`
36 |  | `* which class they will be added to (using <i>BipartiteGraph.Choice</i> );`
37 |  | `* edges must be of type <i>BipartiteGraph</i>, which must consist of two`
38 |  | `* vertices, one each from CLASSA and CLASSB.`
39 |  | `* <pre>`
40 |  | `* BipartiteGraph bpg = new BipartiteGraph;`
41 |  | `* Vertex va = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSA );`
42 |  | `* Vertex vb = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSB );`
43 |  | `* bpg.addBipartiteEdge( new BipartiteEdge( va, vb ));`
44 |  | `* </pre>`
45 |  | `* Note that the traditional <i>addVertex()</i> and <i>addEdge()</i> will`
46 |  | `* both throw a <i>FatalException</i>.<p>`
47 |  | `* The function <i>fold</i> creates an <i>UndirectedGraph</i>`
48 |  | `* based on finding vertices that share a common neighbor.`
49 |  | `*`
50 |  | `* @author danyelf`
51 |  | `* @since 1.0.1`
52 |  | `*/`
53 | 21 | `public class BipartiteGraph extends UndirectedSparseGraph {`
54 |  | ``
55 | 21 | `private Set aSet = new HashSet();`
56 | 21 | `private Set bSet = new HashSet();`
57 |  | ``
58 |  | `public void initialize() {`
59 | 24 | `super.initialize();`
60 | 24 | `aSet = new HashSet();`
61 | 24 | `bSet = new HashSet();`
62 | 24 | `}`
63 |  | ``
64 |  | `/**`
65 |  | `* Returns the set of all vertices from that class.`
66 |  | `* All vertices in the return set will be of class`
67 |  | `* A or class B, depending on the parameter.`
68 |  | `*/`
69 |  | `public Set getAllVertices( Choice choice ) {`
70 | 141 | `if (choice == CLASSA ) {`
71 | 71 | `return Collections.unmodifiableSet(aSet);`
72 | 70 | `} else if (choice == CLASSB ) {`
73 | 70 | `return Collections.unmodifiableSet(bSet);`
74 |  | `} else`
75 | 0 | `throw new IllegalArgumentException("Invalid partition specification " + choice);`
76 |  | `}`
77 |  | ``
78 |  | `// public ArchetypeGraph copy() {`
79 |  | `// System.out.println( this.getClass() );`
80 |  | `// ArchetypeGraph c = newInstance();`
81 |  | `// for (Iterator iter = getVertices().iterator(); iter.hasNext();) {`
82 |  | `// ArchetypeVertex av = (ArchetypeVertex) iter.next();`
83 |  | `// ArchetypeVertex avNew = av.copy(c);`
84 |  | `// }`
85 |  | `// for (Iterator iter = getEdges().iterator(); iter.hasNext();) {`
86 |  | `// ArchetypeEdge ae = (ArchetypeEdge) iter.next();`
87 |  | `// ae.copy(c);`
88 |  | `// }`
89 |  | `// c.importUserData(this);`
90 |  | `// return c;`
91 |  | `//`
92 |  | `// }`
93 |  | ``
94 |  | `/**`
95 |  | `* Returns the partition for vertex <code>v</code>.`
96 |  | `* @param v`
97 |  | `*/`
98 |  | `public Choice getPartition(BipartiteVertex v)`
99 |  | `{`
100 | 29 | `if (aSet.contains(v))`
101 | 19 | `return CLASSA;`
102 | 10 | `else if (bSet.contains(v))`
103 | 9 | `return CLASSB;`
104 |  | `else {`
105 | 1 | `if ( v.getGraph() == this )`
106 | 0 | `throw new IllegalArgumentException("Inconsistent state in graph!");`
107 | 1 | `throw new IllegalArgumentException("Vertex " + v + " is not part of this graph");`
108 |  | `}`
109 |  | `}`
110 |  | ``
111 |  | `/**`
112 |  | `* Adds a single vertex to the graph in the specified partition.`
113 |  | `* Note that the vertex must be compatible with BipartiteVertex.`
114 |  | `*`
115 |  | `* <p>Throws an <code>IllegalArgumentException</code>`
116 |  | `* if <code>v</code> is not an element of either partition.</p>`
117 |  | `*`
118 |  | `* @param v the vertex to be added to the class`
119 |  | `* @param choice the class to which the vertex should be added`
120 |  | `* @return the input vertex`
121 |  | `*/`
122 |  | `public BipartiteVertex addVertex(BipartiteVertex v, Choice choice) {`
123 | 94 | `String exists = "Specified partition already contains vertex ";`
124 | 94 | `String dup = "Another partition already contains vertex ";`
125 | 94 | `if (choice == CLASSA )`
126 |  | `{`
127 | 61 | `if (aSet.contains(v))`
128 | 1 | `throw new IllegalArgumentException(exists + v);`
129 | 60 | `if (bSet.contains(v))`
130 | 0 | `throw new IllegalArgumentException(dup + v);`
131 | 60 | `aSet.add(v);`
132 |  | `}`
133 | 33 | `else if (choice == CLASSB )`
134 |  | `{`
135 | 33 | `if (bSet.contains(v))`
136 | 0 | `throw new IllegalArgumentException(exists + v);`
137 | 33 | `if (aSet.contains(v))`
138 | 0 | `throw new IllegalArgumentException(dup + v);`
139 | 33 | `bSet.add(v);`
140 |  | `}`
141 |  | `else`
142 | 0 | `throw new IllegalArgumentException("Invalid partition specification for vertex " + v + ": " + choice);`
143 | 93 | `super.addVertex(v);`
144 | 93 | `return v;`
145 |  | `}`
146 |  | ``
147 |  | `/**`
148 |  | `* Adds a BipartiteEdge to the Graph. This function is simply a`
149 |  | `* typed version of addEdge`
150 |  | `* @param bpe a BipartiteEdge`
151 |  | `* @return the edge, now a member of the graph.`
152 |  | `*/`
153 |  | `public BipartiteEdge addBipartiteEdge(BipartiteEdge bpe) {`
154 | 75 | `return (BipartiteEdge) super.addEdge(bpe);`
155 |  | `}`
156 |  | ``
157 |  | `/**`
158 |  | `* DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.`
159 |  | `* @see edu.uci.ics.jung.graph.impl.UndirectedSparseGraph#addEdge(edu.uci.ics.jung.graph.Edge)`
160 |  | `* @deprecated Use addBipartiteEdge`
161 |  | `*/`
162 |  | `public Edge addEdge(Edge ae) {`
163 | 1 | `throw new FatalException("Only add BipartiteEdges");`
164 |  | `}`
165 |  | ``
166 |  | `/**`
167 |  | `* DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.`
168 |  | `* @see edu.uci.ics.jung.graph.impl.UndirectedSparseGraph#addVertex(edu.uci.ics.jung.graph.Vertex)`
169 |  | `* @deprecated Use addBipartiteVertex`
170 |  | `*/`
171 |  | `public Vertex addVertex(Vertex av) {`
172 | 2 | `throw new FatalException("Use addVertexX to add vertices to a BipartiteGraph ");`
173 |  | `}`
174 |  | ``
175 |  | `/**`
176 |  | `* This small enumerated type merely forces a user to pick class "A"`
177 |  | `* or "B" when adding a Vertex to a BipartiteGraph.`
178 |  | `*/`
179 | 21 | `public static final class Choice {`
180 |  | `}`
181 | 3 | `public static final Choice CLASSA = new Choice();`
182 | 3 | `public static final Choice CLASSB = new Choice();`
183 |  | ``
184 |  | `/**`
185 |  | `* Creates a one-part graph from a bipartite graph by folding`
186 |  | `* Vertices from one class into a second class. This function`
187 |  | `* creates a new UndirectedGraph (with vertex set V') in which: <br>`
188 |  | `* <ul>`
189 |  | `* <li> each vertex in V' has an equivalent V in bpg.getAllVertices( class ) </li>`
190 |  | `* <li> an edge E' joins V'1 and V'2 iff there is a path of length 2 from`
191 |  | `* V1 to V2 (by way of some third vertex in the other class, VXs) </li>`
192 |  | `* <li> each edge E' is annotated with the set of vertices VXs </li>`
193 |  | `* </ul>`
194 |  | `*`
195 |  | `* In social network analysis and related fields, this operation transforms`
196 |  | `* an actor-by-event chart into an actor-by-actor chart.`
197 |  | `*`
198 |  | `* @param bpg The bipartite graph to be folded`
199 |  | `* @param vertexSet Chooses the set of vertices to be brought into`
200 |  | `* the new Graph.`
201 |  | `* @return an UndirectedSparseGraph.`
202 |  | `*/`
203 |  | `public static Graph fold(BipartiteGraph bpg, Choice vertexSet) {`
204 | 1 | `Graph newGraph = new UndirectedSparseGraph();`
205 | 1 | `Set vertices = bpg.getAllVertices( vertexSet );`
206 | 1 | `for (Iterator iter = vertices.iterator(); iter.hasNext();) {`
207 | 3 | `BipartiteVertex v = (BipartiteVertex) iter.next();`
208 | 3 | `v.copy(newGraph);`
209 |  | `}`
210 |  | ``
211 | 1 | `Set coveredNodes = new HashSet();`
212 |  | ``
213 | 1 | `for (Iterator iter = vertices.iterator(); iter.hasNext();) {`
214 | 3 | `BipartiteVertex v = (BipartiteVertex) iter.next();`
215 | 3 | `coveredNodes.add( v );`
216 |  | ``
217 |  | `// the set of all Bs that touch this A`
218 | 3 | `Set hyperEdges = v.getNeighbors();`
219 |  | ``
220 |  | `// this will ultimately contain a mapping from`
221 |  | `// the next adjacent "A" to the list of "B"s that support that`
222 |  | `// connection (that is, all Bs that run between this A and its neighbor`
223 | 3 | `MultiMap mm = new MultiHashMap();`
224 | 3 | `for (Iterator iterator = hyperEdges.iterator();`
225 | 8 | `iterator.hasNext();`
226 |  | `) {`
227 | 5 | `Vertex hyperEdge = (Vertex) iterator.next();`
228 | 5 | `addAll(mm, hyperEdge.getNeighbors(), hyperEdge);`
229 |  | `}`
230 | 3 | `for (Iterator iterator = mm.keySet().iterator();`
231 | 7 | `iterator.hasNext();`
232 |  | `) {`
233 | 4 | `Vertex aVertex = (Vertex) iterator.next();`
234 |  | ``
235 | 4 | `if ( coveredNodes.contains( aVertex )) continue;`
236 |  | ``
237 | 1 | `Edge newEdge = GraphUtils.addEdge(`
238 |  | `newGraph,`
239 |  | `(Vertex)v.getEqualVertex(newGraph),`
240 |  | `(Vertex)aVertex.getEqualVertex(newGraph));`
241 | 1 | `newEdge.addUserDatum(BIPARTITE_USER_TAG, mm.get(aVertex), UserData.SHARED);`
242 |  | `}`
243 |  | `}`
244 | 1 | `return newGraph;`
245 |  | `}`
246 |  | ``
247 |  | `/**`
248 |  | `* The tag for the UserData attached to a single Edge.`
249 |  | `*/`
250 | 3 | `public static final Object BIPARTITE_USER_TAG = "BipartiteUserTag";`
251 |  | ``
252 |  | `/**`
253 |  | `* Adds all pairs (key, value) to the multimap from`
254 |  | `* the initial set keySet.`
255 |  | `* @param set`
256 |  | `* @param hyperEdge`
257 |  | `*/`
258 |  | `private static void addAll(MultiMap mm, Set keyset, Object value) {`
259 | 5 | `for (Iterator iter = keyset.iterator(); iter.hasNext();) {`
260 | 9 | `Object key = iter.next();`
261 | 9 | `mm.put(key, value);`
262 |  | `}`
263 | 5 | `}`
264 |  | ``
265 |  | `/* (non-Javadoc)`
266 |  | `* @see edu.uci.ics.jung.graph.Graph#removeVertex(edu.uci.ics.jung.graph.Vertex)`
267 |  | `*/`
268 |  | `public void removeVertex(Vertex v) {`
269 | 5 | `super.removeVertex(v);`
270 | 5 | `if ( aSet.contains(v)) {`
271 | 5 | `aSet.remove( v);`
272 |  | `} else {`
273 | 0 | `bSet.remove( v);`
274 |  | `}`
275 | 5 | `}`
276 |  | ``
277 |  | `}`

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.