Subgraph


1   /* ==========================================
2    * JGraphT : a free Java graph-theory library
3    * ==========================================
4    *
5    * Project Info:  http://jgrapht.sourceforge.net/
6    * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
7    *
8    * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9    *
10   * This library is free software; you can redistribute it and/or modify it
11   * under the terms of the GNU Lesser General Public License as published by
12   * the Free Software Foundation; either version 2.1 of the License, or
13   * (at your option) any later version.
14   *
15   * This library is distributed in the hope that it will be useful, but
16   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18   * License for more details.
19   *
20   * You should have received a copy of the GNU Lesser General Public License
21   * along with this library; if not, write to the Free Software Foundation,
22   * Inc.,
23   * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24   */
25  /* -------------
26   * Subgraph.java
27   * -------------
28   * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29   *
30   * Original Author:  Barak Naveh
31   * Contributor(s):   Christian Hammer
32   *
33   * $Id: Subgraph.java 504 2006-07-03 02:37:26Z perfecthash $
34   *
35   * Changes
36   * -------
37   * 24-Jul-2003 : Initial revision (BN);
38   * 26-Jul-2003 : Accurate constructors to avoid casting problems (BN);
39   * 10-Aug-2003 : Adaptation to new event model (BN);
40   * 23-Oct-2003 : Allowed non-listenable graph as base (BN);
41   * 07-Feb-2004 : Enabled serialization (BN);
42   * 11-Mar-2004 : Made generic (CH);
43   * 15-Mar-2004 : Integrity is now checked using Maps (CH);
44   * 20-Mar-2004 : Cancelled verification of element identity to base graph (BN);
45   * 21-Sep-2004 : Added induced subgraph (who?)
46   * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
47   * 28-May-2006 : Moved connectivity info from edge to graph (JVS);
48   *
49   */
50  package org.jgrapht.graph;
51  
52  import java.io.*;
53  
54  import java.util.*;
55  
56  import org.jgrapht.*;
57  import org.jgrapht.event.*;
58  import org.jgrapht.util.*;
59  
60  
61  /**
62   * A subgraph is a graph that has a subset of vertices and a subset of edges
63   * with respect to some base graph. More formally, a subgraph G(V,E) that is
64   * based on a base graph Gb(Vb,Eb) satisfies the following <b><i>subgraph
65   * property</i></b>: V is a subset of Vb and E is a subset of Eb. Other than
66   * this property, a subgraph is a graph with any respect and fully complies with
67   * the <code>Graph</code> interface.
68   *
69   * <p>If the base graph is a {@link org.jgrapht.ListenableGraph}, the subgraph
70   * listens on the base graph and guarantees the subgraph property. If an edge or
71   * a vertex is removed from the base graph, it is automatically removed from the
72   * subgraph. Subgraph listeners are informed on such removal only if it results
73   * in a cascaded removal from the subgraph. If the subgraph has been created as
74   * an induced subgraph it also keeps track of edges being added to its vertices.
75   * If  vertices are added to the base graph, the subgraph remains
76   * unaffected.</p>
77   *
78   * <p>If the base graph is <i>not</i> a ListenableGraph, then the subgraph
79   * property cannot be guaranteed. If edges or vertices are removed from the base
80   * graph, they are <i>not</i> removed from the subgraph.</p>
81   *
82   * <p>Modifications to Subgraph are allowed as long as the subgraph property is
83   * maintained. Addition of vertices or edges are allowed as long as they also
84   * exist in the base graph. Removal of vertices or edges is always allowed. The
85   * base graph is <i>never</i> affected by any modification made to the
86   * subgraph.</p>
87   *
88   * <p>A subgraph may provide a "live-window" on a base graph, so that changes
89   * made to its vertices or edges are immediately reflected in the base graph,
90   * and vice versa. For that to happen, vertices and edges added to the subgraph
91   * must be <i>identical</i> (that is, reference-equal and not only value-equal)
92   * to their respective ones in the base graph. Previous versions of this class
93   * enforced such identity, at a severe performance cost. Currently it is no
94   * longer enforced. If you want to achieve a "live-window"functionality, your
95   * safest tactics would be to NOT override the <code>equals()</code> methods of
96   * your vertices and edges. If you use a class that has already overridden the
97   * <code>equals()</code> method, such as <code>String</code>, than you can use a
98   * wrapper around it, or else use it directly but exercise a great care to avoid
99   * having different-but-equal instances in the subgraph and the base graph.</p>
100  *
101  * <p>This graph implementation guarantees deterministic vertex and edge set
102  * ordering (via {@link LinkedHashSet}).</p>
103  *
104  * @author Barak Naveh
105  * @see Graph
106  * @see Set
107  * @since Jul 18, 2003
108  *
109  *        <p>TODO hb 27-Nov-05: Subgraph features the code for a directed graph
110  *        without specifying the interface. This makes types/typecasting
111  *        problematic. The class does not even test whether a directed graph is
112  *        stored in base when executing direction-related methods. My guess is
113  *        that all direction-related methods should move to DirectedSubgraph.
114  */
115 public class Subgraph<V, E>
116     extends AbstractGraph<V, E>
117     implements Serializable
118 {
119 
120     //~ Static fields/initializers --------------------------------------------
121 
122     private static final long serialVersionUID = 3208313055169665387L;
123     private static final String   NO_SUCH_EDGE_IN_BASE =
124         "no such edge in base graph";
125     private static final String   NO_SUCH_VERTEX_IN_BASE =
126         "no such vertex in base graph";
127 
128     //~ Instance fields -------------------------------------------------------
129 
130     //
131     Set<E> edgeSet = new LinkedHashSet<E>(); // friendly to improve performance
132     Set<V> vertexSet = new LinkedHashSet<V>(); // friendly to improve
133 
134     // performance
135 
136     //
137     private transient Set<E> unmodifiableEdgeSet = null;
138     private transient Set<V> unmodifiableVertexSet = null;
139     private Graph<V, E> base;
140     private boolean isInduced = false;
141 
142     //~ Constructors ----------------------------------------------------------
143 
144     /**
145      * Creates a new Subgraph.
146      *
147      * @param base the base (backing) graph on which the subgraph will be based.
148      * @param vertexSubset vertices to include in the subgraph. If <code>
149      *                     null</code> then all vertices are included.
150      * @param edgeSubset edges to in include in the subgraph. If <code>
151      *                   null</code> then all the edges whose vertices found in
152      *                   the graph are included.
153      */
154     public Subgraph(Graph<V, E> base, Set<V> vertexSubset, Set<E> edgeSubset)
155     {
156         super();
157 
158         this.base = base;
159 
160         if (base instanceof ListenableGraph) {
161             ((ListenableGraph<V, E>) base).addGraphListener(
162                 new BaseGraphListener());
163         }
164 
165         addVerticesUsingFilter(base.vertexSet(), vertexSubset);
166         addEdgesUsingFilter(base.edgeSet(), edgeSubset);
167     }
168 
169     /**
170      * Creates a new induced Subgraph. The subgraph will keep track of edges
171      * being added to its vertex subset as well as deletion of edges and
172      * vertices. If base it not listenable, this is identical to the call
173      * Subgraph(base, vertexSubset, null) .
174      *
175      * @param base the base (backing) graph on which the subgraph will be based.
176      * @param vertexSubset vertices to include in the subgraph. If <code>
177      *                     null</code> then all vertices are included.
178      */
179     public Subgraph(Graph<V, E> base, Set<V> vertexSubset)
180     {
181         this(base, vertexSubset, null);
182 
183         isInduced = true;
184     }
185 
186     //~ Methods ---------------------------------------------------------------
187 
188     /**
189      * @see Graph#getAllEdges(Object, Object)
190      */
191     public Set<E> getAllEdges(V sourceVertex, V targetVertex)
192     {
193         Set<E> edges = null;
194 
195         if (containsVertex(sourceVertex) && containsVertex(targetVertex)) {
196             edges = new ArrayUnenforcedSet<E>();
197 
198             Set<E> baseEdges = base.getAllEdges(sourceVertex, targetVertex);
199 
200             for (Iterator<E> iter = baseEdges.iterator(); iter.hasNext();) {
201                 E e = iter.next();
202 
203                 if (edgeSet.contains(e)) { // add if subgraph also contains
204                                            // it
205                     edges.add(e);
206                 }
207             }
208         }
209 
210         return edges;
211     }
212 
213     /**
214      * @see Graph#getEdge(Object, Object)
215      */
216     public E getEdge(V sourceVertex, V targetVertex)
217     {
218         Set<E> edges = getAllEdges(sourceVertex, targetVertex);
219 
220         if ((edges == null) || edges.isEmpty()) {
221             return null;
222         } else {
223             return edges.iterator().next();
224         }
225     }
226 
227     /**
228      * @see Graph#getEdgeFactory()
229      */
230     public EdgeFactory<V, E> getEdgeFactory()
231     {
232         return base.getEdgeFactory();
233     }
234 
235     /**
236      * @see Graph#addEdge(Object, Object)
237      */
238     public E addEdge(V sourceVertex, V targetVertex)
239     {
240         assertVertexExist(sourceVertex);
241         assertVertexExist(targetVertex);
242 
243         if (!base.containsEdge(sourceVertex, targetVertex)) {
244             throw new IllegalArgumentException  (NO_SUCH_EDGE_IN_BASE);
245         }
246 
247         Set<E> edges = base.getAllEdges(sourceVertex, targetVertex);
248 
249         for (Iterator<E> iter = edges.iterator(); iter.hasNext();) {
250             E e = iter.next();
251 
252             if (!containsEdge(e)) {
253                 edgeSet.add(e);
254 
255                 return e;
256             }
257         }
258 
259         return null;
260     }
261 
262     /**
263      * @see Graph#addEdge(Object, Object, Object)
264      */
265     public boolean addEdge(V sourceVertex, V targetVertex, E e)
266     {
267         if (e == null) {
268             throw new NullPointerException  ();
269         }
270 
271         if (!base.containsEdge(e)) {
272             throw new IllegalArgumentException  (NO_SUCH_EDGE_IN_BASE);
273         }
274 
275         assertVertexExist(sourceVertex);
276         assertVertexExist(targetVertex);
277 
278         assert (base.getEdgeSource(e) == sourceVertex);
279         assert (base.getEdgeTarget(e) == targetVertex);
280 
281         if (containsEdge(e)) {
282             return false;
283         } else {
284             edgeSet.add(e);
285 
286             return true;
287         }
288     }
289 
290     /**
291      * Adds the specified vertex to this subgraph.
292      *
293      * @param v the vertex to be added.
294      *
295      * @return <code>true</code> if the vertex was added, otherwise <code>
296      *         false</code>.
297      *
298      * @throws NullPointerException
299      * @throws IllegalArgumentException
300      *
301      * @see Subgraph
302      * @see Graph#addVertex(Object)
303      */
304     public boolean addVertex(V v)
305     {
306         if (v == null) {
307             throw new NullPointerException  ();
308         }
309 
310         if (!base.containsVertex(v)) {
311             throw new IllegalArgumentException  (NO_SUCH_VERTEX_IN_BASE);
312         }
313 
314         if (containsVertex(v)) {
315             return false;
316         } else {
317             vertexSet.add(v);
318 
319             return true;
320         }
321     }
322 
323     /**
324      * @see Graph#containsEdge(Object)
325      */
326     public boolean containsEdge(E e)
327     {
328         return edgeSet.contains(e);
329     }
330 
331     /**
332      * @see Graph#containsVertex(Object)
333      */
334     public boolean containsVertex(V v)
335     {
336         return vertexSet.contains(v);
337     }
338 
339     /**
340      * @see UndirectedGraph#degreeOf(Object)
341      */
342     public int degreeOf(V vertex)
343     {
344         assertVertexExist(vertex);
345 
346         // TODO hb 27-Nov-05: Check/understand this sophistication
347         // could the intend be to throw a ClassCastException
348         // for non-directed graphs?
349         // sophisticated way to check runtime class of base ;-)
350         ((UndirectedGraph<V, E>) base).degreeOf(vertex);
351 
352         int degree = 0;
353 
354         for (E e : base.edgesOf(vertex)) {
355             if (containsEdge(e)) {
356                 degree++;
357 
358                 if (getEdgeSource(e).equals(getEdgeTarget(e))) {
359                     degree++;
360                 }
361             }
362         }
363 
364         return degree;
365     }
366 
367     /**
368      * @see Graph#edgeSet()
369      */
370     public Set<E> edgeSet()
371     {
372         if (unmodifiableEdgeSet == null) {
373             unmodifiableEdgeSet = Collections.unmodifiableSet(edgeSet);
374         }
375 
376         return unmodifiableEdgeSet;
377     }
378 
379     /**
380      * @see Graph#edgesOf(Object)
381      */
382     public Set<E> edgesOf(V vertex)
383     {
384         assertVertexExist(vertex);
385 
386         Set<E> edges = new ArrayUnenforcedSet<E>();
387         Set<E> baseEdges = base.edgesOf(vertex);
388 
389         for (E e : baseEdges) {
390             if (containsEdge(e)) {
391                 edges.add(e);
392             }
393         }
394 
395         return edges;
396     }
397 
398     /**
399      * @see DirectedGraph#inDegreeOf(Object)
400      */
401     public int inDegreeOf(V vertex)
402     {
403         assertVertexExist(vertex);
404 
405         int degree = 0;
406 
407         for (E e : ((DirectedGraph<V, E>) base).incomingEdgesOf(vertex)) {
408             if (containsEdge(e)) {
409                 degree++;
410             }
411         }
412 
413         return degree;
414     }
415 
416     /**
417      * @see DirectedGraph#incomingEdgesOf(Object)
418      */
419     public Set<E> incomingEdgesOf(V vertex)
420     {
421         assertVertexExist(vertex);
422 
423         Set<E> edges = new ArrayUnenforcedSet<E>();
424         Set<E> baseEdges = ((DirectedGraph<V, E>) base).incomingEdgesOf(vertex);
425 
426         for (E e : baseEdges) {
427             if (containsEdge(e)) {
428                 edges.add(e);
429             }
430         }
431 
432         return edges;
433     }
434 
435     /**
436      * @see DirectedGraph#outDegreeOf(Object)
437      */
438     public int outDegreeOf(V vertex)
439     {
440         assertVertexExist(vertex);
441 
442         int degree = 0;
443 
444         for (E e : ((DirectedGraph<V, E>) base).outgoingEdgesOf(vertex)) {
445             if (containsEdge(e)) {
446                 degree++;
447             }
448         }
449 
450         return degree;
451     }
452 
453     /**
454      * @see DirectedGraph#outgoingEdgesOf(Object)
455      */
456     public Set<E> outgoingEdgesOf(V vertex)
457     {
458         assertVertexExist(vertex);
459 
460         Set<E> edges = new ArrayUnenforcedSet<E>();
461         Set<? extends E> baseEdges =
462             ((DirectedGraph<V, E>) base).outgoingEdgesOf(vertex);
463 
464         for (E e : baseEdges) {
465             if (containsEdge(e)) {
466                 edges.add(e);
467             }
468         }
469 
470         return edges;
471     }
472 
473     /**
474      * @see Graph#removeEdge(Object)
475      */
476     public boolean removeEdge(E e)
477     {
478         return edgeSet.remove(e);
479     }
480 
481     /**
482      * @see Graph#removeEdge(Object, Object)
483      */
484     public E removeEdge(V sourceVertex, V targetVertex)
485     {
486         E e = getEdge(sourceVertex, targetVertex);
487 
488         return edgeSet.remove(e) ? e : null;
489     }
490 
491     /**
492      * @see Graph#removeVertex(Object)
493      */
494     public boolean removeVertex(V v)
495     {
496         // If the base graph does NOT contain v it means we are here in
497         // response to removal of v from the base. In such case we don't need
498         // to remove all the edges of v as they were already removed.
499         if (containsVertex(v) && base.containsVertex(v)) {
500             removeAllEdges(edgesOf(v));
501         }
502 
503         return vertexSet.remove(v);
504     }
505 
506     /**
507      * @see Graph#vertexSet()
508      */
509     public Set<V> vertexSet()
510     {
511         if (unmodifiableVertexSet == null) {
512             unmodifiableVertexSet = Collections.unmodifiableSet(vertexSet);
513         }
514 
515         return unmodifiableVertexSet;
516     }
517 
518     /**
519      * @see Graph#getEdgeSource(Object)
520      */
521     public V getEdgeSource(E e)
522     {
523         return base.getEdgeSource(e);
524     }
525 
526     /**
527      * @see Graph#getEdgeTarget(Object)
528      */
529     public V getEdgeTarget(E e)
530     {
531         return base.getEdgeTarget(e);
532     }
533 
534     private void addEdgesUsingFilter(Set<E> edgeSet, Set<E> filter)
535     {
536         E e;
537         boolean containsVertices;
538         boolean edgeIncluded;
539 
540         for (Iterator<E> iter = edgeSet.iterator(); iter.hasNext();) {
541             e = iter.next();
542 
543             V sourceVertex = base.getEdgeSource(e);
544             V targetVertex = base.getEdgeTarget(e);
545             containsVertices =
546                 containsVertex(sourceVertex)
547                 && containsVertex(targetVertex);
548 
549             // note the use of short circuit evaluation
550             edgeIncluded = (filter == null) || filter.contains(e);
551 
552             if (containsVertices && edgeIncluded) {
553                 addEdge(sourceVertex, targetVertex, e);
554             }
555         }
556     }
557 
558     private void addVerticesUsingFilter(Set<V> vertexSet, Set<V> filter)
559     {
560         V v;
561 
562         for (Iterator<V> iter = vertexSet.iterator(); iter.hasNext();) {
563             v = iter.next();
564 
565             // note the use of short circuit evaluation
566             if ((filter == null) || filter.contains(v)) {
567                 addVertex(v);
568             }
569         }
570     }
571 
572     protected Graph<V, E> getBase()
573     {
574         return base;
575     }
576 
577     /**
578      * @see Graph#getEdgeWeight(Object)
579      */
580     public double getEdgeWeight(E e)
581     {
582         return base.getEdgeWeight(e);
583     }
584 
585     /**
586      * @see WeightedGraph#setEdgeWeight(Object, double)
587      */
588     public void setEdgeWeight(E e, double weight)
589     {
590         ((WeightedGraph<V, E>) base).setEdgeWeight(e, weight);
591     }
592 
593     //~ Inner Classes ---------------------------------------------------------
594 
595     /**
596      * An internal listener on the base graph.
597      *
598      * @author Barak Naveh
599      * @since Jul 20, 2003
600      */
601     private class BaseGraphListener
602         implements GraphListener<V, E>, Serializable
603     {
604         private static final long serialVersionUID = 4343535244243546391L;
605 
606         /**
607          * @see GraphListener#edgeAdded(GraphEdgeChangeEvent)
608          */
609         public void edgeAdded(GraphEdgeChangeEvent<V, E> e)
610         {
611             if (isInduced) {
612                 E edge = e.getEdge();
613                 addEdge(
614                     base.getEdgeSource(edge),
615                     base.getEdgeTarget(edge),
616                     edge);
617             }
618         }
619 
620         /**
621          * @see GraphListener#edgeRemoved(GraphEdgeChangeEvent)
622          */
623         public void edgeRemoved(GraphEdgeChangeEvent<V, E> e)
624         {
625             E edge = e.getEdge();
626 
627             removeEdge(edge);
628         }
629 
630         /**
631          * @see VertexSetListener#vertexAdded(GraphVertexChangeEvent)
632          */
633         public void vertexAdded(GraphVertexChangeEvent<V> e)
634         {
635             // we don't care
636         }
637 
638         /**
639          * @see VertexSetListener#vertexRemoved(GraphVertexChangeEvent)
640          */
641         public void vertexRemoved(GraphVertexChangeEvent<V> e)
642         {
643             V vertex = e.getVertex();
644 
645             removeVertex(vertex);
646         }
647     }
648 }
649
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags