001 package org.expasy.jpl.commons.collection.graph;
002
003
004 import java.util.ArrayList;
005 import java.util.Arrays;
006 import java.util.Collection;
007 import java.util.HashMap;
008 import java.util.HashSet;
009 import java.util.Iterator;
010 import java.util.List;
011 import java.util.Map;
012 import java.util.Set;
013 import org.apache.commons.collections15.Predicate;
014 import edu.uci.ics.jung.graph.Graph;
015 import edu.uci.ics.jung.graph.KPartiteGraph;
016 import edu.uci.ics.jung.graph.SparseMultigraph;
017 import edu.uci.ics.jung.graph.util.EdgeType;
018 import edu.uci.ics.jung.graph.util.Pair;
019
020
021 /**
022 * A simple implementation of {@code KPartiteGraph}.
023 *
024 * @author nikitin
025 *
026 * @param <V> vertex type.
027 * @param <E> edge type.
028 *
029 * @version 1.0
030 *
031 */
032 public final class KPartiteGraphImpl<V, E> extends SparseMultigraph<V, E>
033 implements KPartiteGraph<V, E>, Node {
034
035 private static final long serialVersionUID = 7653446445107694853L;
036
037 private Map<String, V> nodes;
038
039 private Collection<Predicate<V>> predicates;
040 private List<Set<V>> subSets;
041 private boolean subsets;
042
043 private String id;
044 private static int ID;
045
046 // Need public empty constructor because jung object may use
047 // reflection
048 public KPartiteGraphImpl() {
049 id = "KPG" + String.valueOf(ID++);
050 nodes = new HashMap<String, V>();
051 }
052
053 private KPartiteGraphImpl(Collection<Predicate<V>> predicates,
054 boolean subsets) {
055 this();
056
057 if (predicates == null) {
058 throw new IllegalArgumentException(
059 "undefined predicates: cannot instanciate K partite graph");
060 }
061
062 this.predicates = predicates;
063 this.subsets = subsets;
064
065 if (subsets) {
066 subSets = new ArrayList<Set<V>>();
067
068 for (int i = 0; i < predicates.size(); i++) {
069 subSets.add(new HashSet<V>());
070 }
071 }
072 }
073
074 public static <V, E> KPartiteGraphImpl<V, E> newInstance(
075 List<Predicate<V>> partitions, boolean subsets) {
076 return new KPartiteGraphImpl<V, E>(partitions, subsets);
077 }
078
079 public void setId(String id) {
080 this.id = id;
081 }
082
083 public void setPartitions(Collection<Predicate<V>> predicates) {
084 this.predicates = predicates;
085 }
086
087 public int getPartitionIndex(Predicate<V> predicate) {
088
089 if (predicates == null || predicates.size() == 0) {
090 return -1;
091 }
092
093 int i = 0;
094 Iterator<Predicate<V>> iter = predicates.iterator();
095
096 while (iter.hasNext()) {
097 if (predicate == iter.next()) {
098 return i;
099 }
100 i++;
101 }
102 return -1;
103 }
104
105 /**
106 * Look for the partition of the given vertex.
107 *
108 * @param vertex the vertex to search partition index from.
109 * @return the partition index or -1 if not found.
110 */
111 public int getPartitionIndex(V vertex) {
112 int i = 0;
113
114 // no predicates defined
115 if (predicates == null || predicates.size() == 0) {
116 return -1;
117 }
118
119 // evaluate all predicates
120 Iterator<Predicate<V>> iter = predicates.iterator();
121
122 while (iter.hasNext()) {
123
124 if (iter.next().evaluate(vertex)) {
125 break;
126 }
127 i++;
128 }
129
130 // no predicate match
131 if (i == predicates.size()) {
132 return -1;
133 }
134
135 return i;
136 }
137
138 @Override
139 public Collection<Predicate<V>> getPartitions() {
140 return predicates;
141 }
142
143 @Override
144 public boolean addVertex(V vertex) {
145 int i = -1;
146
147 // skip the partition search for null predicates
148 // only possible if instanciation has been done by reflection by jung
149 // classes like:
150 // VertexPredicateFilter, EdgePredicateFilter or GraphCollapser...
151 if (predicates != null) {
152
153 // vertex belongs to partition i
154 i = getPartitionIndex(vertex);
155
156 if (i < 0) {
157 throw new IllegalArgumentException("no partition for vertex "
158 + vertex);
159 }
160 }
161
162 if (!containsVertex(vertex)) {
163
164 if (subsets && predicates != null) {
165 subSets.get(i).add(vertex);
166 }
167
168 nodes.put(vertex.toString(), vertex);
169
170 return super.addVertex(vertex);
171 }
172 return true;
173 }
174
175 @Override
176 public boolean removeVertex(V vertex) {
177 int i = -1;
178
179 // skip the partition search for null predicates
180 // only possible if instanciation has been done by reflection by jung
181 // classes like:
182 // VertexPredicateFilter, EdgePredicateFilter or GraphCollapser...
183 if (predicates != null) {
184
185 // vertex belongs to partition i
186 i = getPartitionIndex(vertex);
187
188 if (i < 0) {
189 throw new IllegalArgumentException("no partition for vertex "
190 + vertex);
191 }
192 }
193
194 if (containsVertex(vertex)) {
195
196 if (subsets && predicates != null) {
197 subSets.get(i).remove(vertex);
198 }
199
200 nodes.remove(vertex.toString());
201
202 return super.removeVertex(vertex);
203 }
204 return subsets;
205
206 }
207
208 public boolean addEdge(E edge, V v1, V v2) {
209 checkEdge(v1, v2);
210
211 return super.addEdge(edge, v1, v2);
212 };
213
214 public boolean addEdge(E edge, V v1, V v2, EdgeType type) {
215 checkEdge(v1, v2);
216
217 return super.addEdge(edge, v1, v2, type);
218 }
219
220 public boolean removeEdge(E edge) {
221
222 if (containsEdge(edge)) {
223 edges.remove(edge.toString());
224 return super.removeEdge(edge);
225 }
226 return true;
227 }
228
229 public Set<String> getVerticesId() {
230 return nodes.keySet();
231 }
232
233 public V getVertex(String id) {
234 return nodes.get(id);
235 }
236
237 @SuppressWarnings("unchecked")
238 public int getVertexCount(Predicate<V> predicate) {
239 return getVertexCount(Arrays.asList(predicate));
240 }
241
242 public int getVertexCount(Collection<Predicate<V>> predicates) {
243 return getVertices(predicates).size();
244 }
245
246 @SuppressWarnings("unchecked")
247 public int getEdgeCount(Predicate<V> predicate) {
248 return getEdgeCount(Arrays.asList(predicate));
249 }
250
251 public int getEdgeCount(Collection<Predicate<V>> predicates) {
252 return getEdges(predicates).size();
253 }
254
255 /**
256 * @return all vertices which satisfy the specified {@code node type}
257 * predicate.
258 * @throws IllegalArgumentException if not valid predicate.
259 */
260 public Collection<V> getVertices(Collection<Predicate<V>> predicates) {
261 Collection<V> l = new HashSet<V>();
262
263 for (Predicate<V> predicate : predicates) {
264 l.addAll(getVertices(predicate));
265 }
266
267 return l;
268 }
269
270 /**
271 * @return all vertices which satisfy the specified {@code node type}
272 * predicate.
273 * @throws IllegalArgumentException if not valid predicate.
274 */
275 @Override
276 public Collection<V> getVertices(Predicate<V> predicate) {
277 Collection<V> l = new HashSet<V>();
278
279 int i = getPartitionIndex(predicate);
280
281 if (i < 0) {
282 throw new IllegalArgumentException("the given predicate '"
283 + predicate + "' is not a valid graph predicate "
284 + "(please choose one predicate defined among "
285 + "the following partitions " + predicates + ")");
286 }
287
288 if (subsets) {
289
290 if (i >= 0) {
291 return subSets.get(i);
292 }
293 return l;
294 } else {
295 for (V vertex : getVertices()) {
296 if (predicate.evaluate(vertex)) {
297 l.add(vertex);
298 }
299 }
300 return l;
301 }
302 }
303
304 public Set<V> getNeighbors(V vertex, Collection<Predicate<V>> predicates) {
305 Collection<V> l = getNeighbors(vertex);
306 Set<V> selected = new HashSet<V>();
307
308 for (Iterator<V> it = l.iterator(); it.hasNext();) {
309 V v = it.next();
310 for (Predicate<V> predicate : predicates) {
311 if (predicate.evaluate(v)) {
312 selected.add(v);
313 }
314
315 }
316 }
317 return selected;
318 }
319
320 public Collection<V> getNeighbors(V vertex, Predicate<V> predicate) {
321 Collection<V> l = getNeighbors(vertex);
322 Collection<V> selected = new HashSet<V>();
323
324 for (Iterator<V> it = l.iterator(); it.hasNext();) {
325 V v = it.next();
326
327 if (predicate.evaluate(v)) {
328 selected.add(v);
329 }
330 }
331
332 return selected;
333 }
334
335 @SuppressWarnings("unchecked")
336 public Collection<E> getEdges(Predicate<V> predicate) {
337 return getEdges(Arrays.asList(predicate));
338 }
339
340 public Collection<E> getEdges(Collection<Predicate<V>> predicates) {
341
342 Set<E> selected = new HashSet<E>();
343 for (E edge : getEdges()) {
344 Pair<V> endpoints = getEndpoints(edge);
345
346 for (Predicate<V> predicate : predicates) {
347 if (predicate.evaluate(endpoints.getFirst())
348 || predicate.evaluate(endpoints.getSecond())) {
349 selected.add(edge);
350 }
351 }
352 }
353
354 return selected;
355 }
356
357 public Collection<E> getIncidentEdges(V vertex,
358 Collection<Predicate<V>> predicates) {
359
360 Collection<E> edges = super.getIncidentEdges(vertex);
361 Set<E> selected = new HashSet<E>();
362 for (E edge : edges) {
363 Pair<V> endpoints = getEndpoints(edge);
364
365 for (Predicate<V> predicate : predicates) {
366 if (predicate.evaluate(endpoints.getFirst())
367 || predicate.evaluate(endpoints.getSecond())) {
368 selected.add(edge);
369 }
370 }
371 }
372
373 return selected;
374 }
375
376 public Collection<E> getIncidentEdges(V vertex, Predicate<V> predicate) {
377
378 Collection<E> edges = super.getIncidentEdges(vertex);
379 HashSet<E> selected = new HashSet<E>();
380 for (E edge : edges) {
381 Pair<V> endpoints = getEndpoints(edge);
382
383 if (predicate.evaluate(endpoints.getFirst())
384 || predicate.evaluate(endpoints.getSecond())) {
385 selected.add(edge);
386 }
387 }
388
389 return selected;
390 }
391
392 private void checkEdge(V v1, V v2) {
393 if (predicates != null) {
394 // v1 and v2 have to be of different partition
395 int i = getPartitionIndex(v1);
396 int j = getPartitionIndex(v2);
397
398 if (i == -1) {
399 throw new IllegalArgumentException("vertex " + v1
400 + " is not found in any partition (" + predicates + ")");
401 }
402
403 if (j == -1) {
404 throw new IllegalArgumentException("vertex " + v2
405 + " is not found in any partition (" + predicates + ")");
406 }
407
408 // add edge only if v1 is in partition 1 and v2 in partition 2
409 if (i == j) {
410 throw new IllegalArgumentException(
411 "vertices of the same partition cannot be connected");
412 }
413 }
414 }
415
416 @Override
417 public final String getId() {
418 return id;
419 }
420
421 public String toString() {
422 StringBuilder sb = new StringBuilder();
423
424 sb.append(id + "=");
425 sb.append("(V#" + getVertexCount() + ":" + getVertices());
426 sb.append(", E#" + getEdgeCount() + ":[");
427
428 for (E edge : getEdges()) {
429 Pair<V> pair = getEndpoints(edge);
430 sb.append(pair.getFirst() + "--" + pair.getSecond() + " (" + edge
431 + "), ");
432 }
433 if (getEdgeCount() > 0) {
434 sb.delete(sb.length() - 2, sb.length());
435 }
436 sb.append("])");
437
438 return sb.toString();
439 }
440
441 public static class Collapser<V, E> extends GraphCollapser<V, E> {
442
443 public Collapser(KPartiteGraphImpl<V, E> originalGraph) {
444 super(originalGraph);
445 }
446
447 public void setOriGraph(KPartiteGraphImpl<V, E> originalGraph) {
448 this.originalGraph = originalGraph;
449 }
450
451 @SuppressWarnings("unchecked")
452 @Override
453 public void initGraph(Graph<V, E> g) {
454 ((KPartiteGraphImpl) g).predicates =
455 (List) ((KPartiteGraphImpl) originalGraph).getPartitions();
456 }
457
458 }
459
460 public static class PredicateImpl<T> implements Predicate<T> {
461
462 private String name;
463 private Predicate<T> predicate;
464
465 private PredicateImpl(String name, Predicate<T> predicate) {
466 this.name = name;
467 this.predicate = predicate;
468 }
469
470 public static <T> PredicateImpl<T> newInstance(String name,
471 Predicate<T> predicate) {
472 return new PredicateImpl<T>(name, predicate);
473 }
474
475 public String getName() {
476 return name;
477 }
478
479 @Override
480 public boolean evaluate(T o) {
481 return predicate.evaluate(o);
482 }
483
484 public String toString() {
485 return "Predicate " + name;
486 }
487
488 }
489 }