# Coverage details for edu.uci.ics.jung.algorithms.transformation.FoldingTransformer

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 Apr 21, 2004`
12 |  | `*/`
13 |  | `package edu.uci.ics.jung.algorithms.transformation;`
14 |  | ``
15 |  | `import java.util.HashMap;`
16 |  | `import java.util.HashSet;`
17 |  | `import java.util.Iterator;`
18 |  | `import java.util.Map;`
19 |  | `import java.util.Set;`
20 |  | ``
21 |  | `import org.apache.commons.collections.BidiMap;`
22 |  | `import org.apache.commons.collections.Predicate;`
23 |  | ``
24 |  | `import edu.uci.ics.jung.graph.ArchetypeVertex;`
25 |  | `import edu.uci.ics.jung.graph.Edge;`
26 |  | `import edu.uci.ics.jung.graph.Element;`
27 |  | `import edu.uci.ics.jung.graph.Graph;`
28 |  | `import edu.uci.ics.jung.graph.Hypergraph;`
29 |  | `import edu.uci.ics.jung.graph.KPartiteGraph;`
30 |  | `import edu.uci.ics.jung.graph.Vertex;`
31 |  | `import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;`
32 |  | `import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;`
33 |  | `import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;`
34 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;`
35 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;`
36 |  | `import edu.uci.ics.jung.utils.GraphUtils;`
37 |  | `import edu.uci.ics.jung.utils.PredicateUtils;`
38 |  | `import edu.uci.ics.jung.utils.TypedVertexGenerator;`
39 |  | `import edu.uci.ics.jung.utils.UserData;`
40 |  | `import edu.uci.ics.jung.utils.VertexGenerator;`
41 |  | `import edu.uci.ics.jung.utils.UserDataContainer.CopyAction;`
42 |  | ``
43 |  | `/**`
44 |  | `* A class for creating a "folded" graph based on a k-partite graph or a`
45 |  | `* hypergraph.`
46 |  | `*`
47 |  | `* <p>A "folded" graph is derived from a k-partite graph by identifying`
48 |  | `* a partition of vertices which will become the vertices of the new graph, copying`
49 |  | `* these vertices into the new graph, and then connecting those vertices whose`
50 |  | `* original analogues were connected indirectly through elements`
51 |  | `* of other partitions. (See <code>fold(KPartiteGraph, Predicate, NumberEdgeValue)</code>`
52 |  | `* for more details.)</p>`
53 |  | `*`
54 |  | `* <p>A "folded" graph is derived from a hypergraph by creating vertices based on`
55 |  | `* either the vertices or the hyperedges of the original graph, and connecting`
56 |  | `* vertices in the new graph if their corresponding vertices/hyperedges share a`
57 |  | `* connection with a common hyperedge/vertex. (See <code>fold(Hypergraph,`
58 |  | `* boolean, NumberEdgeValue)</code> for more details.)</p>`
59 |  | `*`
60 |  | `* @author Danyel Fisher`
61 |  | `* @author Joshua O'Madadhain`
62 |  | `*/`
63 |  | `public class FoldingTransformer`
64 |  | `{`
65 |  | `/**`
66 |  | `* Used in <code>fold()</code> as a user data key to the data attached to`
67 |  | `* the edges in the folded graph.`
68 |  | `*/`
69 |  | `public static final String FOLDED_DATA = "edu.uci.ics.jung.graph.KPartiteFolder:Folded Data";`
70 |  | ``
71 |  | `protected boolean parallel;`
72 | 2 | `protected CopyAction copy_action = UserData.REMOVE;`
73 |  | ``
74 |  | `/**`
75 |  | `* Specifies whether the graph being folded is undirected or not.`
76 |  | `* Set by <code>checkGraphConstraints</code>.`
77 |  | `*/`
78 |  | `private boolean undirected;`
79 |  | ``
80 |  | `/**`
81 |  | `* Creates an instance of this Folder. See the discussion of fold for notes`
82 |  | `* on the "parallel" argument.`
83 |  | `*`
84 |  | `*/`
85 | 2 | `public FoldingTransformer(boolean parallel) {`
86 | 2 | `this.parallel = parallel;`
87 | 2 | `}`
88 |  | ``
89 |  | `/**`
90 |  | `* Specifies whether the folded graphs create parallel edges or a decorated`
91 |  | `* single edge.`
92 |  | `* @param parallel`
93 |  | `*/`
94 |  | `public void setParallel(boolean parallel) {`
95 | 0 | `this.parallel = parallel;`
96 | 0 | `}`
97 |  | ``
98 |  | `/**`
99 |  | `* Specifies the copy action used to attach data to edges.`
100 |  | `* @param copy_action`
101 |  | `*/`
102 |  | `public void setCopyAction(CopyAction copy_action)`
103 |  | `{`
104 | 0 | `this.copy_action = copy_action;`
105 | 0 | `}`
106 |  | ``
107 |  | `/**`
108 |  | `* Equivalent to <code>fold(g, p, null)</code>.`
109 |  | `*/`
110 |  | `public Graph fold(KPartiteGraph g, Predicate p)`
111 |  | `{`
112 | 2 | `return fold(g, p, null);`
113 |  | `}`
114 |  | ``
115 |  | `/**`
116 |  | `* <p>`
117 |  | `* Converts <code>g</code> into a unipartite graph whose vertex set is the`
118 |  | `* vertices whose partition is specified by <code>p</code>. For vertices`
119 |  | `* <code>a</code> and <code>b</code> in this partition, the resultant`
120 |  | `* graph will include the edge <code>(a,b)</code> if the original graph`
121 |  | `* contains edges <code>(a,c)</code> and <code>(c,b)</code> for at least`
122 |  | `* one vertex <code>c</code>.`
123 |  | `* </p>`
124 |  | `*`
125 |  | `* <p>`
126 |  | `* If <code>parallel</code> is true, then each such connecting vertex`
127 |  | `* <code>c</code> will be represented by a single edge in the resultant`
128 |  | `* graph, and the resultant graph may therefore contain parallel edges.`
129 |  | `* Otherwise, each edge <code>(a,b)</code> in the resultant graph will be`
130 |  | `* annotated with the set of vertices <code>c</code> that connected`
131 |  | `* <code>a</code> to <code>b</code> in the original graph, and the`
132 |  | `* graph's edge requirements will be set to refuse parallel edges.`
133 |  | `* </p>`
134 |  | `*`
135 |  | `* <p>In either case, if the original graph contains both a directed edge from`
136 |  | `* <code>a</code> to <code>b</code>, and a directed edge from <code>b</code>`
137 |  | `* <code>a</code>, then a self-loop will be created from <code>a</code>`
138 |  | `* to itself in the folded graph. Undirected edges do not result in`
139 |  | `* self-loops.`
140 |  | `* </p>`
141 |  | `*`
142 |  | `* <p>`
143 |  | `* If <code>g</code> is neither strictly directed nor strictly undirected,`
144 |  | `* this method throws <code>IllegalArgumentException</code>. Parallel edges`
145 |  | `* in the original graph have no effect on the resultant graph: only one edge`
146 |  | `* <code>(a,c)</code> and one edge <code>(c,b)</code> are necessary to`
147 |  | `* induce a connection between <code>a</code> and <code>b</code> in the folded`
148 |  | `* graph, and any additional such edges are ignored.</p>`
149 |  | `*`
150 |  | `* <p>If <code>nev</code> is null,`
151 |  | `* adds the connecting element as a decoration on the corresponding edge in the new`
152 |  | `* graph; otherwise, sets the weight of each edge to the number of parallel`
153 |  | `* paths between the corresponding vertices in the original graph that are`
154 |  | `* encountered in the folding process.</p>`
155 |  | `*`
156 |  | `* @param g the graph to fold`
157 |  | `* @param p the predicate which specifies the partition to fold into`
158 |  | `* @return the folded graph`
159 |  | `* @throws IllegalArgumentException`
160 |  | `*/`
161 |  | `public Graph fold(KPartiteGraph g, Predicate p, NumberEdgeValue nev)`
162 |  | `{`
163 | 2 | `checkGraphConstraints(g);`
164 |  | ``
165 | 2 | `Graph newGraph = createGraph();`
166 |  | ``
167 |  | `// get vertices for the specified partition, copy into new graph`
168 | 2 | `Set vertices = PredicateUtils.getVertices(g, p);`
169 | 2 | `for (Iterator iter = vertices.iterator(); iter.hasNext();) {`
170 | 6 | `ArchetypeVertex v = (ArchetypeVertex) iter.next();`
171 | 6 | `v.copy(newGraph);`
172 |  | `}`
173 |  | ``
174 | 2 | `for (Iterator iter = vertices.iterator(); iter.hasNext();) {`
175 | 6 | `Vertex v = (Vertex) iter.next();`
176 | 6 | `Vertex v_new = (Vertex) v.getEqualVertex(newGraph);`
177 | 6 | `Set succs = v.getSuccessors();`
178 |  | ``
179 | 6 | `for (Iterator s_iter = succs.iterator(); s_iter.hasNext();) {`
180 | 10 | `Vertex s = (Vertex) s_iter.next();`
181 | 10 | `Set s_succs = s.getSuccessors();`
182 |  | ``
183 | 10 | `for (Iterator t_iter = s_succs.iterator(); t_iter.hasNext();) {`
184 | 13 | `Vertex t = (Vertex) t_iter.next();`
185 |  | ``
186 |  | `// if t is in the partition of interest`
187 |  | `// and has not been covered (undirected graphs only)`
188 | 13 | `if (!vertices.contains(t)) continue;`
189 |  | ``
190 | 13 | `Vertex t_new = (Vertex) t.getEqualVertex(newGraph);`
191 | 13 | `addEdge(newGraph, v_new, s, t_new, nev);`
192 |  | ``
193 |  | `}`
194 |  | `}`
195 |  | `}`
196 | 2 | `return newGraph;`
197 |  | `}`
198 |  | ``
199 |  | `// /**`
200 |  | `// * Equivalent to <code>fold(h, use_vertices, null)</code>.`
201 |  | `// */`
202 |  | `// public Graph fold(Hypergraph h, boolean use_vertices)`
203 |  | `// {`
204 |  | `// return fold(h, use_vertices, null);`
205 |  | `// }`
206 |  | `//`
207 |  | `// public Graph fold(Hypergraph h, boolean use_vertices, NumberEdgeValue nev)`
208 |  | `// {`
209 |  | `// return fold(h, null, use_vertices, nev, new BidirectionalHashMap());`
210 |  | `// }`
211 |  | ``
212 |  | `/**`
213 |  | `* Creates a <code>Graph</code> which is a "folded" version of <code>h</code>.`
214 |  | `*`
215 |  | `* <p>If <code>use_vertices</code> is true, the vertices of the new graph`
216 |  | `* correspond to the vertices of <code>h</code>, and <code>a</code>`
217 |  | `* is connected to <code>b</code> in the new graph if the corresponding vertices`
218 |  | `* in <code>h</code> are connected by a hyperedge. Thus, each hyperedge with`
219 |  | `* <i>k</i> vertices in <code>h</code> would induce a <i>k</i>-clique in the new graph.</p>`
220 |  | `*`
221 |  | `* <p>If <code>use_vertices</code> is false, then the vertices of the new`
222 |  | `* graph correspond to the hyperedges of <code>h</code>, and <code>a</code>`
223 |  | `* is connected to <code>b</code> in the new graph if the corresponding hyperedges`
224 |  | `* in <code>h</code> share a vertex. Thus, each vertex connected to <i>k</i>`
225 |  | `* hyperedges in <code>h</code> would induce a <i>k</i>-clique in the new graph.</p>`
226 |  | `*`
227 |  | `* <p>If <code>nev</code> is null,`
228 |  | `* adds the connecting element as a decoration on the corresponding edge in the new`
229 |  | `* graph; otherwise, sets the weight of each edge to the number of parallel`
230 |  | `* paths between the corresponding vertices in the original graph that are`
231 |  | `* encountered in the folding process.</p>`
232 |  | `*/`
233 |  | `public Graph fold(Hypergraph h, Graph target, boolean use_vertices, NumberEdgeValue nev, BidiMap map)`
234 |  | `{`
235 | 0 | `undirected = true;`
236 |  | ``
237 | 0 | `if (target == null)`
238 | 0 | `target = createGraph();`
239 |  | ``
240 | 0 | `VertexGenerator vg = GraphUtils.getVertexGenerator(target);`
241 | 0 | `if (vg == null)`
242 | 0 | `vg = new TypedVertexGenerator(target);`
243 |  | ``
244 | 0 | `Map m = new HashMap();`
245 |  | `Set vertices;`
246 |  | `Set edges;`
247 |  | ``
248 |  | `// vertices and hyperedges are duals of one another; we can treat`
249 |  | `// them equivalently for this purpose`
250 | 0 | `if (use_vertices)`
251 |  | `{`
252 | 0 | `vertices = h.getVertices();`
253 | 0 | `edges = h.getEdges();`
254 |  | `}`
255 |  | `else`
256 |  | `{`
257 | 0 | `vertices = h.getEdges();`
258 | 0 | `edges = h.getVertices();`
259 |  | `}`
260 |  | ``
261 |  | `// create vertices:`
262 |  | `// for each "vertex", create a new vertex and import user data`
263 | 0 | `for (Iterator iter = vertices.iterator(); iter.hasNext(); )`
264 |  | `{`
265 | 0 | `Element av = (Element)iter.next();`
266 | 0 | `Vertex v = vg.create();`
267 | 0 | `v.importUserData(av);`
268 | 0 | `target.addVertex(v);`
269 | 0 | `m.put(av, v);`
270 | 0 | `map.put(v, av);`
271 |  | `}`
272 |  | ``
273 |  | `// create edges:`
274 |  | `// for each "hyperedge", create an edge between each incident vertex pair`
275 | 0 | `for (Iterator iter = edges.iterator(); iter.hasNext(); )`
276 |  | `{`
277 | 0 | `Element he = (Element)iter.next();`
278 | 0 | `Set elts = he.getIncidentElements();`
279 | 0 | `Vertex[] v_array = new Vertex[elts.size()];`
280 | 0 | `int i = 0;`
281 | 0 | `for (Iterator e_iter = elts.iterator(); e_iter.hasNext(); )`
282 | 0 | `v_array[i++] = (Vertex)(m.get(e_iter.next()));`
283 | 0 | `for (i = 0; i < v_array.length; i++)`
284 | 0 | `for (int j = i + 1; j < v_array.length; j++)`
285 | 0 | `addEdge(target, v_array[i], he, v_array[j], nev);`
286 |  | `}`
287 |  | ``
288 | 0 | `return target;`
289 |  | `}`
290 |  | ``
291 |  | ``
292 |  | `/**`
293 |  | `* Creates a new edge from <code>firstEnd</code> to <code>secondEnd</code>`
294 |  | `* in <code>newGraph</code>. Note that`
295 |  | `* <code>firstEnd</code> and <code>secondEnd</code> are both parts of`
296 |  | `* <code>newGraph</code>, while`
297 |  | `* <code>intermediate</code> is part of the original graph. If <code>parallel</code> is set,`
298 |  | `* adds a new edge from <code>firstEnd</code> to <code>secondEnd</code>.`
299 |  | `* If <code>parallel</code> is not set, then (as appropriate) adds an edge`
300 |  | `* or creates one from <code>firstEnd</code> to <code>secondEnd</code>.`
301 |  | `*/`
302 |  | `protected void addEdge(Graph newGraph, Vertex firstEnd,`
303 |  | `Element intermediate, Vertex secondEnd, NumberEdgeValue nev)`
304 |  | `{`
305 | 13 | `if( undirected && firstEnd == secondEnd ) return;`
306 | 8 | `if (parallel) {`
307 |  | `Edge v_t;`
308 | 4 | `if (undirected)`
309 | 0 | `v_t = new UndirectedSparseEdge(firstEnd, secondEnd);`
310 |  | `else`
311 | 4 | `v_t = new DirectedSparseEdge(firstEnd, secondEnd);`
312 | 4 | `if (nev != null)`
313 | 0 | `nev.setNumber(v_t, new Integer(1));`
314 |  | `else`
315 | 4 | `v_t.addUserDatum(FOLDED_DATA, intermediate, copy_action);`
316 | 4 | `newGraph.addEdge(v_t);`
317 |  | `} else {`
318 | 4 | `Edge v_t = firstEnd.findEdge(secondEnd);`
319 | 4 | `if (v_t == null) {`
320 | 1 | `if (undirected)`
321 | 1 | `v_t = new UndirectedSparseEdge(firstEnd, secondEnd);`
322 |  | `else`
323 | 0 | `v_t = new DirectedSparseEdge(firstEnd, secondEnd);`
324 | 1 | `if (nev != null)`
325 | 0 | `nev.setNumber(v_t, new Integer(0));`
326 |  | `else`
327 | 1 | `v_t.addUserDatum(FOLDED_DATA, new HashSet(), copy_action);`
328 | 1 | `newGraph.addEdge(v_t);`
329 |  | `}`
330 | 4 | `if (nev != null)`
331 | 0 | `nev.setNumber(v_t, new Integer(nev.getNumber(v_t).intValue() + 1));`
332 |  | `else`
333 |  | `{`
334 | 4 | `Set folded_vertices = (Set) v_t.getUserDatum(FOLDED_DATA);`
335 | 4 | `folded_vertices.add(intermediate);`
336 |  | `}`
337 |  | `}`
338 | 8 | `}`
339 |  | ``
340 |  | `/**`
341 |  | `* Returns a base graph to use.`
342 |  | `*/`
343 |  | `protected Graph createGraph()`
344 |  | `{`
345 |  | `Graph newGraph;`
346 | 2 | `if (undirected)`
347 | 1 | `newGraph = new UndirectedSparseGraph();`
348 |  | `else`
349 | 1 | `newGraph = new DirectedSparseGraph();`
350 |  | ``
351 | 2 | `if (parallel)`
352 | 1 | `newGraph.getEdgeConstraints().remove(Graph.NOT_PARALLEL_EDGE);`
353 |  | ``
354 | 2 | `return newGraph;`
355 |  | `}`
356 |  | ``
357 |  | `/**`
358 |  | `* Checks for, and rejects, mixed-mode graphs, and sets the <code>undirected</code>`
359 |  | `* class variable state.`
360 |  | `*/`
361 |  | `protected void checkGraphConstraints(KPartiteGraph g) {`
362 | 2 | `undirected = PredicateUtils.enforcesUndirected(g);`
363 | 2 | `if (!undirected && !PredicateUtils.enforcesDirected(g))`
364 | 0 | `throw new IllegalArgumentException(`
365 |  | `"Graph must be strictly "`
366 |  | `+ "directed or strictly undirected (no mixed graphs allowed)");`
367 | 2 | `}`
368 |  | ``
369 |  | `}`

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.