AbstractBaseGraph


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   * AbstractBaseGraph.java
27   * ----------------------
28   * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29   *
30   * Original Author:  Barak Naveh
31   * Contributor(s):   John V. Sichi
32   *                   Christian Hammer
33   *
34   * $Id: AbstractBaseGraph.java 504 2006-07-03 02:37:26Z perfecthash $
35   *
36   * Changes
37   * -------
38   * 24-Jul-2003 : Initial revision (BN);
39   * 10-Aug-2003 : General edge refactoring (BN);
40   * 06-Nov-2003 : Change edge sharing semantics (JVS);
41   * 07-Feb-2004 : Enabled serialization (BN);
42   * 11-Mar-2004 : Made generic (CH);
43   * 01-Jun-2005 : Added EdgeListFactory (JVS);
44   * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
45   * 28-May-2006 : Moved connectivity info from edge to graph (JVS);
46   *
47   */
48  package org.jgrapht.graph;
49  
50  import java.io.*;
51  
52  import java.util.*;
53  
54  import org.jgrapht.*;
55  import org.jgrapht.util.*;
56  
57  
58  /**
59   * The most general implementation of the {@link org.jgrapht.Graph} interface.
60   * Its subclasses add various restrictions to get more specific graphs. The
61   * decision whether it is directed or undirected is decided at construction time
62   * and cannot be later modified (see constructor for details).
63   *
64   * <p>This graph implementation guarantees deterministic vertex and edge set
65   * ordering (via {@link LinkedHashMap} and {@link LinkedHashSet}).</p>
66   *
67   * @author Barak Naveh
68   * @since Jul 24, 2003
69   */
70  public abstract class AbstractBaseGraph<V, E>
71      extends AbstractGraph<V, E>
72      implements Graph<V, E>, Cloneable  , Serializable
73  {
74  
75      //~ Static fields/initializers --------------------------------------------
76  
77      private static final String   LOOPS_NOT_ALLOWED = "loops not allowed";
78  
79      //~ Instance fields -------------------------------------------------------
80  
81      boolean allowingLoops;
82  
83      private EdgeFactory<V, E> edgeFactory;
84      private EdgeSetFactory<V, E> edgeSetFactory;
85      private Map<E, IntrusiveEdge> edgeMap;
86      private transient Set<E> unmodifiableEdgeSet = null;
87      private transient Set<V> unmodifiableVertexSet = null;
88      private Specifics specifics;
89      private boolean allowingMultipleEdges;
90  
91      private transient TypeUtil<V> vertexTypeDecl = null;
92  
93      //~ Constructors ----------------------------------------------------------
94  
95      /**
96       * Construct a new pseudograph. The pseudograph can either be directed or
97       * undirected, depending on the specified edge factory.
98       *
99       * @param ef the edge factory of the new graph.
100      * @param allowMultipleEdges whether to allow multiple edges or not.
101      * @param allowLoops whether to allow edges that are self-loops or not.
102      *
103      * @throws NullPointerException if the specified edge factory is <code>
104      *                              null</code>.
105      */
106     public AbstractBaseGraph(
107         EdgeFactory<V, E> ef,
108         boolean allowMultipleEdges,
109         boolean allowLoops)
110     {
111         if (ef == null) {
112             throw new NullPointerException  ();
113         }
114 
115         edgeMap = new LinkedHashMap<E, IntrusiveEdge>();
116         edgeFactory = ef;
117         allowingLoops = allowLoops;
118         allowingMultipleEdges = allowMultipleEdges;
119 
120         specifics = createSpecifics();
121 
122         this.edgeSetFactory = new ArrayListFactory<V, E>();
123     }
124 
125     //~ Methods ---------------------------------------------------------------
126 
127     /**
128      * @see Graph#getAllEdges(Object, Object)
129      */
130     public Set<E> getAllEdges(V sourceVertex, V targetVertex)
131     {
132         return specifics.getAllEdges(sourceVertex, targetVertex);
133     }
134 
135     /**
136      * Returns <code>true</code> if and only if self-loops are allowed in this
137      * graph. A self loop is an edge that its source and target vertices are the
138      * same.
139      *
140      * @return <code>true</code> if and only if graph loops are allowed.
141      */
142     public boolean isAllowingLoops()
143     {
144         return allowingLoops;
145     }
146 
147     /**
148      * Returns <code>true</code> if and only if multiple edges are allowed in
149      * this graph. The meaning of multiple edges is that there can be many edges
150      * going from vertex v1 to vertex v2.
151      *
152      * @return <code>true</code> if and only if multiple edges are allowed.
153      */
154     public boolean isAllowingMultipleEdges()
155     {
156         return allowingMultipleEdges;
157     }
158 
159     /**
160      * @see Graph#getEdge(Object, Object)
161      */
162     public E getEdge(V sourceVertex, V targetVertex)
163     {
164         return specifics.getEdge(sourceVertex, targetVertex);
165     }
166 
167     /**
168      * @see Graph#getEdgeFactory()
169      */
170     public EdgeFactory<V, E> getEdgeFactory()
171     {
172         return edgeFactory;
173     }
174 
175     /**
176      * Set the {@link EdgeSetFactory} to use for this graph. Initially, a graph
177      * is created with a default implementation which always supplies an {@link
178      * java.util.ArrayList} with capacity 1.
179      *
180      * @param edgeSetFactory factory to use for subsequently created edge sets
181      *                       (this call has no effect on existing edge sets)
182      */
183     public void setEdgeSetFactory(EdgeSetFactory<V, E> edgeSetFactory)
184     {
185         this.edgeSetFactory = edgeSetFactory;
186     }
187 
188     /**
189      * @see Graph#addEdge(Object, Object)
190      */
191     public E addEdge(V sourceVertex, V targetVertex)
192     {
193         assertVertexExist(sourceVertex);
194         assertVertexExist(targetVertex);
195 
196         if (!allowingMultipleEdges
197             && containsEdge(sourceVertex, targetVertex)) {
198             return null;
199         }
200 
201         if (!allowingLoops && sourceVertex.equals(targetVertex)) {
202             throw new IllegalArgumentException  (LOOPS_NOT_ALLOWED);
203         }
204 
205         E e = edgeFactory.createEdge(sourceVertex, targetVertex);
206 
207         if (containsEdge(e)) { // this restriction should stay!
208 
209             return null;
210         } else {
211             IntrusiveEdge intrusiveEdge =
212                 createIntrusiveEdge(e, sourceVertex, targetVertex);
213 
214             edgeMap.put(e, intrusiveEdge);
215             specifics.addEdgeToTouchingVertices(e);
216 
217             return e;
218         }
219     }
220 
221     /**
222      * @see Graph#addEdge(Object, Object, Object)
223      */
224     public boolean addEdge(V sourceVertex, V targetVertex, E e)
225     {
226         if (e == null) {
227             throw new NullPointerException  ();
228         } else if (containsEdge(e)) {
229             return false;
230         }
231 
232         assertVertexExist(sourceVertex);
233         assertVertexExist(targetVertex);
234 
235         if (!allowingMultipleEdges
236             && containsEdge(sourceVertex, targetVertex)) {
237             return false;
238         }
239 
240         if (!allowingLoops && sourceVertex.equals(targetVertex)) {
241             throw new IllegalArgumentException  (LOOPS_NOT_ALLOWED);
242         }
243 
244         IntrusiveEdge intrusiveEdge =
245             createIntrusiveEdge(e, sourceVertex, targetVertex);
246 
247         edgeMap.put(e, intrusiveEdge);
248         specifics.addEdgeToTouchingVertices(e);
249 
250         return true;
251     }
252 
253     private IntrusiveEdge createIntrusiveEdge(
254         E e,
255         V sourceVertex,
256         V targetVertex)
257     {
258         IntrusiveEdge intrusiveEdge;
259         if (e instanceof IntrusiveEdge) {
260             intrusiveEdge = (IntrusiveEdge) e;
261         } else {
262             intrusiveEdge = new IntrusiveEdge();
263         }
264         intrusiveEdge.source = sourceVertex;
265         intrusiveEdge.target = targetVertex;
266         return intrusiveEdge;
267     }
268 
269     /**
270      * @see Graph#addVertex(Object)
271      */
272     public boolean addVertex(V v)
273     {
274         if (v == null) {
275             throw new NullPointerException  ();
276         } else if (containsVertex(v)) {
277             return false;
278         } else {
279             specifics.addVertex(v);
280 
281             return true;
282         }
283     }
284 
285     /**
286      * @see Graph#getEdgeSource(Object)
287      */
288     public V getEdgeSource(E e)
289     {
290         return
291             TypeUtil.uncheckedCast(
292                 getIntrusiveEdge(e).source,
293                 vertexTypeDecl);
294     }
295 
296     /**
297      * @see Graph#getEdgeTarget(Object)
298      */
299     public V getEdgeTarget(E e)
300     {
301         return
302             TypeUtil.uncheckedCast(
303                 getIntrusiveEdge(e).target,
304                 vertexTypeDecl);
305     }
306 
307     private IntrusiveEdge getIntrusiveEdge(E e)
308     {
309         if (e instanceof IntrusiveEdge) {
310             return (IntrusiveEdge) e;
311         }
312 
313         return edgeMap.get(e);
314     }
315 
316     /**
317      * Returns a shallow copy of this graph instance.  Neither edges nor
318      * vertices are cloned.
319      *
320      * @return a shallow copy of this set.
321      *
322      * @throws RuntimeException
323      *
324      * @see java.lang.Object#clone()
325      */
326     public Object   clone()
327     {
328         try {
329             TypeUtil<AbstractBaseGraph<V, E>> typeDecl = null;
330 
331             AbstractBaseGraph<V, E> newGraph =
332                 TypeUtil.uncheckedCast(super.clone(), typeDecl);
333 
334             newGraph.edgeMap = new LinkedHashMap<E, IntrusiveEdge>();
335 
336             newGraph.edgeFactory = this.edgeFactory;
337             newGraph.unmodifiableEdgeSet = null;
338             newGraph.unmodifiableVertexSet = null;
339 
340             // NOTE:  it's important for this to happen in an object
341             // method so that the new inner class instance gets associated with
342             // the right outer class instance
343             newGraph.specifics = newGraph.createSpecifics();
344 
345             Graphs.addGraph(newGraph, this);
346 
347             return newGraph;
348         } catch (CloneNotSupportedException   e) {
349             e.printStackTrace();
350             throw new RuntimeException  ();
351         }
352     }
353 
354     /**
355      * @see Graph#containsEdge(Object)
356      */
357     public boolean containsEdge(E e)
358     {
359         return edgeMap.containsKey(e);
360     }
361 
362     /**
363      * @see Graph#containsVertex(Object)
364      */
365     public boolean containsVertex(V v)
366     {
367         return specifics.getVertexSet().contains(v);
368     }
369 
370     /**
371      * @see UndirectedGraph#degreeOf(Object)
372      */
373     public int degreeOf(V vertex)
374     {
375         return specifics.degreeOf(vertex);
376     }
377 
378     /**
379      * @see Graph#edgeSet()
380      */
381     public Set<E> edgeSet()
382     {
383         if (unmodifiableEdgeSet == null) {
384             unmodifiableEdgeSet = Collections.unmodifiableSet(edgeMap.keySet());
385         }
386 
387         return unmodifiableEdgeSet;
388     }
389 
390     /**
391      * @see Graph#edgesOf(Object)
392      */
393     public Set<E> edgesOf(V vertex)
394     {
395         return specifics.edgesOf(vertex);
396     }
397 
398     /**
399      * @see DirectedGraph#inDegreeOf(Object)
400      */
401     public int inDegreeOf(V vertex)
402     {
403         return specifics.inDegreeOf(vertex);
404     }
405 
406     /**
407      * @see DirectedGraph#incomingEdgesOf(Object)
408      */
409     public Set<E> incomingEdgesOf(V vertex)
410     {
411         return specifics.incomingEdgesOf(vertex);
412     }
413 
414     /**
415      * @see DirectedGraph#outDegreeOf(Object)
416      */
417     public int outDegreeOf(V vertex)
418     {
419         return specifics.outDegreeOf(vertex);
420     }
421 
422     /**
423      * @see DirectedGraph#outgoingEdgesOf(Object)
424      */
425     public Set<E> outgoingEdgesOf(V vertex)
426     {
427         return specifics.outgoingEdgesOf(vertex);
428     }
429 
430     /**
431      * @see Graph#removeEdge(Object, Object)
432      */
433     public E removeEdge(V sourceVertex, V targetVertex)
434     {
435         E e = getEdge(sourceVertex, targetVertex);
436 
437         if (e != null) {
438             specifics.removeEdgeFromTouchingVertices(e);
439             edgeMap.remove(e);
440         }
441 
442         return e;
443     }
444 
445     /**
446      * @see Graph#removeEdge(Object)
447      */
448     public boolean removeEdge(E e)
449     {
450         if (containsEdge(e)) {
451             specifics.removeEdgeFromTouchingVertices(e);
452             edgeMap.remove(e);
453 
454             return true;
455         } else {
456             return false;
457         }
458     }
459 
460     /**
461      * @see Graph#removeVertex(Object)
462      */
463     public boolean removeVertex(V v)
464     {
465         if (containsVertex(v)) {
466             Set<E> touchingEdgesList = edgesOf(v);
467 
468             // cannot iterate over list - will cause
469             // ConcurrentModificationException
470             removeAllEdges(new ArrayList<E>(touchingEdgesList));
471 
472             specifics.getVertexSet().remove(v); // remove the vertex itself
473 
474             return true;
475         } else {
476             return false;
477         }
478     }
479 
480     /**
481      * @see Graph#vertexSet()
482      */
483     public Set<V> vertexSet()
484     {
485         if (unmodifiableVertexSet == null) {
486             unmodifiableVertexSet =
487                 Collections.unmodifiableSet(specifics.getVertexSet());
488         }
489 
490         return unmodifiableVertexSet;
491     }
492 
493     /**
494      * @see Graph#getEdgeWeight(Object)
495      */
496     public double getEdgeWeight(E e)
497     {
498         if (e instanceof DefaultWeightedEdge) {
499             return ((DefaultWeightedEdge) e).weight;
500         } else {
501             return WeightedGraph.DEFAULT_EDGE_WEIGHT;
502         }
503     }
504 
505     /**
506      * @see WeightedGraph#setEdgeWeight(Object, double)
507      */
508     public void setEdgeWeight(E e, double weight)
509     {
510         assert (e instanceof DefaultWeightedEdge) : e.getClass();
511         ((DefaultWeightedEdge) e).weight = weight;
512     }
513 
514     private Specifics createSpecifics()
515     {
516         if (this instanceof DirectedGraph) {
517             return new DirectedSpecifics();
518         } else if (this instanceof UndirectedGraph) {
519             return new UndirectedSpecifics();
520         } else {
521             throw new IllegalArgumentException  (
522                 "must be instance of either DirectedGraph or UndirectedGraph");
523         }
524     }
525 
526     //~ Inner Classes ---------------------------------------------------------
527 
528     /**
529      * .
530      *
531      * @author Barak Naveh
532      */
533     private abstract class Specifics
534         implements Serializable
535     {
536         public abstract void addVertex(V vertex);
537 
538         public abstract Set<V> getVertexSet();
539 
540         /**
541          * .
542          *
543          * @param sourceVertex
544          * @param targetVertex
545          *
546          * @return
547          */
548         public abstract Set<E> getAllEdges(V sourceVertex,
549             V targetVertex);
550 
551         /**
552          * .
553          *
554          * @param sourceVertex
555          * @param targetVertex
556          *
557          * @return
558          */
559         public abstract E getEdge(V sourceVertex, V targetVertex);
560 
561         /**
562          * Adds the specified edge to the edge containers of its source and
563          * target vertices.
564          *
565          * @param e
566          */
567         public abstract void addEdgeToTouchingVertices(E e);
568 
569         /**
570          * .
571          *
572          * @param vertex
573          *
574          * @return
575          */
576         public abstract int degreeOf(V vertex);
577 
578         /**
579          * .
580          *
581          * @param vertex
582          *
583          * @return
584          */
585         public abstract Set<E> edgesOf(V vertex);
586 
587         /**
588          * .
589          *
590          * @param vertex
591          *
592          * @return
593          */
594         public abstract int inDegreeOf(V vertex);
595 
596         /**
597          * .
598          *
599          * @param vertex
600          *
601          * @return
602          */
603         public abstract Set<E> incomingEdgesOf(V vertex);
604 
605         /**
606          * .
607          *
608          * @param vertex
609          *
610          * @return
611          */
612         public abstract int outDegreeOf(V vertex);
613 
614         /**
615          * .
616          *
617          * @param vertex
618          *
619          * @return
620          */
621         public abstract Set<E> outgoingEdgesOf(V vertex);
622 
623         /**
624          * Removes the specified edge from the edge containers of its source and
625          * target vertices.
626          *
627          * @param e
628          */
629         public abstract void removeEdgeFromTouchingVertices(E e);
630     }
631 
632     private static class ArrayListFactory<VV, EE>
633         implements EdgeSetFactory<VV, EE>, Serializable
634     {
635         private static final long serialVersionUID = 5936902837403445985L;
636 
637         /**
638          * @see EdgeSetFactory.createEdgeSet
639          */
640         public Set<EE> createEdgeSet(VV vertex)
641         {
642             // NOTE:  use size 1 to keep memory usage under control
643             // for the common case of vertices with low degree
644             return new ArrayUnenforcedSet<EE>(1);
645         }
646     }
647 
648     /**
649      * A container for vertex edges.
650      *
651      * <p>In this edge container we use array lists to minimize memory toll.
652      * However, for high-degree vertices we replace the entire edge container
653      * with a direct access subclass (to be implemented).</p>
654      *
655      * @author Barak Naveh
656      */
657     private static class DirectedEdgeContainer<VV, EE>
658         implements Serializable
659     {
660         private static final long serialVersionUID = 7494242245729767106L;
661         Set<EE> incoming;
662         Set<EE> outgoing;
663         private transient Set<EE> unmodifiableIncoming = null;
664         private transient Set<EE> unmodifiableOutgoing = null;
665 
666         DirectedEdgeContainer(
667             EdgeSetFactory<VV, EE> edgeSetFactory,
668             VV vertex)
669         {
670             incoming = edgeSetFactory.createEdgeSet(vertex);
671             outgoing = edgeSetFactory.createEdgeSet(vertex);
672         }
673 
674         /**
675          * A lazy build of unmodifiable incoming edge set.
676          *
677          * @return
678          */
679         public Set<EE> getUnmodifiableIncomingEdges()
680         {
681             if (unmodifiableIncoming == null) {
682                 unmodifiableIncoming = Collections.unmodifiableSet(incoming);
683             }
684 
685             return unmodifiableIncoming;
686         }
687 
688         /**
689          * A lazy build of unmodifiable outgoing edge set.
690          *
691          * @return
692          */
693         public Set<EE> getUnmodifiableOutgoingEdges()
694         {
695             if (unmodifiableOutgoing == null) {
696                 unmodifiableOutgoing = Collections.unmodifiableSet(outgoing);
697             }
698 
699             return unmodifiableOutgoing;
700         }
701 
702         /**
703          * .
704          *
705          * @param e
706          */
707         public void addIncomingEdge(EE e)
708         {
709             incoming.add(e);
710         }
711 
712         /**
713          * .
714          *
715          * @param e
716          */
717         public void addOutgoingEdge(EE e)
718         {
719             outgoing.add(e);
720         }
721 
722         /**
723          * .
724          *
725          * @param e
726          */
727         public void removeIncomingEdge(EE e)
728         {
729             incoming.remove(e);
730         }
731 
732         /**
733          * .
734          *
735          * @param e
736          */
737         public void removeOutgoingEdge(EE e)
738         {
739             outgoing.remove(e);
740         }
741     }
742 
743     /**
744      * .
745      *
746      * @author Barak Naveh
747      */
748     private class DirectedSpecifics
749         extends Specifics
750         implements Serializable
751     {
752         private static final long serialVersionUID = 8971725103718958232L;
753         private static final String   NOT_IN_DIRECTED_GRAPH =
754             "no such operation in a directed graph";
755 
756         private Map<V, DirectedEdgeContainer<V, E>> vertexMapDirected =
757             new LinkedHashMap<V, DirectedEdgeContainer<V, E>>();
758 
759         public void addVertex(V v)
760         {
761             // add with a lazy edge container entry
762             vertexMapDirected.put(v, null);
763         }
764 
765         public Set<V> getVertexSet()
766         {
767             return vertexMapDirected.keySet();
768         }
769 
770         /**
771          * @see Graph#getAllEdges(Object, Object)
772          */
773         public Set<E> getAllEdges(V sourceVertex, V targetVertex)
774         {
775             Set<E> edges = null;
776 
777             if (containsVertex(sourceVertex)
778                 && containsVertex(targetVertex)) {
779                 edges = new ArrayUnenforcedSet<E>();
780 
781                 DirectedEdgeContainer<V, E> ec = getEdgeContainer(sourceVertex);
782 
783                 Iterator<E> iter = ec.outgoing.iterator();
784 
785                 while (iter.hasNext()) {
786                     E e = iter.next();
787 
788                     if (getEdgeTarget(e).equals(targetVertex)) {
789                         edges.add(e);
790                     }
791                 }
792             }
793 
794             return edges;
795         }
796 
797         /**
798          * @see Graph#getEdge(Object, Object)
799          */
800         public E getEdge(V sourceVertex, V targetVertex)
801         {
802             if (containsVertex(sourceVertex)
803                 && containsVertex(targetVertex)) {
804                 DirectedEdgeContainer<V, E> ec = getEdgeContainer(sourceVertex);
805 
806                 Iterator<E> iter = ec.outgoing.iterator();
807 
808                 while (iter.hasNext()) {
809                     E e = iter.next();
810 
811                     if (getEdgeTarget(e).equals(targetVertex)) {
812                         return e;
813                     }
814                 }
815             }
816 
817             return null;
818         }
819 
820         /**
821          * @see AbstractBaseGraph#addEdgeToTouchingVertices(Edge)
822          */
823         public void addEdgeToTouchingVertices(E e)
824         {
825             V source = getEdgeSource(e);
826             V target = getEdgeTarget(e);
827 
828             getEdgeContainer(source).addOutgoingEdge(e);
829             getEdgeContainer(target).addIncomingEdge(e);
830         }
831 
832         /**
833          * @see UndirectedGraph#degreeOf(Object)
834          */
835         public int degreeOf(V vertex)
836         {
837             throw new UnsupportedOperationException  (NOT_IN_DIRECTED_GRAPH);
838         }
839 
840         /**
841          * @see Graph#edgesOf(Object)
842          */
843         public Set<E> edgesOf(V vertex)
844         {
845             ArrayUnenforcedSet<E> inAndOut =
846                 new ArrayUnenforcedSet<E>(getEdgeContainer(vertex).incoming);
847             inAndOut.addAll(getEdgeContainer(vertex).outgoing);
848 
849             // we have two copies for each self-loop - remove one of them.
850             if (allowingLoops) {
851                 Set<E> loops = getAllEdges(vertex, vertex);
852 
853                 for (int i = 0; i < inAndOut.size();) {
854                     Object   e = inAndOut.get(i);
855 
856                     if (loops.contains(e)) {
857                         inAndOut.remove(i);
858                         loops.remove(e); // so we remove it only once
859                     } else {
860                         i++;
861                     }
862                 }
863             }
864 
865             return inAndOut;
866         }
867 
868         /**
869          * @see DirectedGraph#inDegree(Object)
870          */
871         public int inDegreeOf(V vertex)
872         {
873             return getEdgeContainer(vertex).incoming.size();
874         }
875 
876         /**
877          * @see DirectedGraph#incomingEdges(Object)
878          */
879         public Set<E> incomingEdgesOf(V vertex)
880         {
881             return getEdgeContainer(vertex).getUnmodifiableIncomingEdges();
882         }
883 
884         /**
885          * @see DirectedGraph#outDegree(Object)
886          */
887         public int outDegreeOf(V vertex)
888         {
889             return getEdgeContainer(vertex).outgoing.size();
890         }
891 
892         /**
893          * @see DirectedGraph#outgoingEdges(Object)
894          */
895         public Set<E> outgoingEdgesOf(V vertex)
896         {
897             return getEdgeContainer(vertex).getUnmodifiableOutgoingEdges();
898         }
899 
900         /**
901          * @see AbstractBaseGraph#removeEdgeFromTouchingVertices(Edge)
902          */
903         public void removeEdgeFromTouchingVertices(E e)
904         {
905             V source = getEdgeSource(e);
906             V target = getEdgeTarget(e);
907 
908             getEdgeContainer(source).removeOutgoingEdge(e);
909             getEdgeContainer(target).removeIncomingEdge(e);
910         }
911 
912         /**
913          * A lazy build of edge container for specified vertex.
914          *
915          * @param vertex a vertex in this graph.
916          *
917          * @return EdgeContainer
918          */
919         private DirectedEdgeContainer<V, E> getEdgeContainer(V vertex)
920         {
921             assertVertexExist(vertex);
922 
923             DirectedEdgeContainer<V, E> ec = vertexMapDirected.get(vertex);
924 
925             if (ec == null) {
926                 ec = new DirectedEdgeContainer<V, E>(edgeSetFactory, vertex);
927                 vertexMapDirected.put(vertex, ec);
928             }
929 
930             return ec;
931         }
932     }
933 
934     /**
935      * A container of for vertex edges.
936      *
937      * <p>In this edge container we use array lists to minimize memory toll.
938      * However, for high-degree vertices we replace the entire edge container
939      * with a direct access subclass (to be implemented).</p>
940      *
941      * @author Barak Naveh
942      */
943     private static class UndirectedEdgeContainer<VV, EE>
944         implements Serializable
945     {
946         private static final long serialVersionUID = -6623207588411170010L;
947         Set<EE> vertexEdges;
948         private transient Set<EE> unmodifiableVertexEdges = null;
949 
950         UndirectedEdgeContainer(
951             EdgeSetFactory<VV, EE> edgeSetFactory,
952             VV vertex)
953         {
954             vertexEdges = edgeSetFactory.createEdgeSet(vertex);
955         }
956 
957         /**
958          * A lazy build of unmodifiable list of vertex edges
959          *
960          * @return
961          */
962         public Set<EE> getUnmodifiableVertexEdges()
963         {
964             if (unmodifiableVertexEdges == null) {
965                 unmodifiableVertexEdges =
966                     Collections.unmodifiableSet(vertexEdges);
967             }
968 
969             return unmodifiableVertexEdges;
970         }
971 
972         /**
973          * .
974          *
975          * @param e
976          */
977         public void addEdge(EE e)
978         {
979             vertexEdges.add(e);
980         }
981 
982         /**
983          * .
984          *
985          * @return
986          */
987         public int edgeCount()
988         {
989             return vertexEdges.size();
990         }
991 
992         /**
993          * .
994          *
995          * @param e
996          */
997         public void removeEdge(EE e)
998         {
999             vertexEdges.remove(e);
1000        }
1001    }
1002
1003    /**
1004     * .
1005     *
1006     * @author Barak Naveh
1007     */
1008    private class UndirectedSpecifics
1009        extends Specifics
1010        implements Serializable
1011    {
1012        private static final long serialVersionUID = 6494588405178655873L;
1013        private static final String   NOT_IN_UNDIRECTED_GRAPH =
1014            "no such operation in an undirected graph";
1015
1016        private Map<V, UndirectedEdgeContainer<V, E>> vertexMapUndirected =
1017            new LinkedHashMap<V, UndirectedEdgeContainer<V, E>>();
1018
1019        public void addVertex(V v)
1020        {
1021            // add with a lazy edge container entry
1022            vertexMapUndirected.put(v, null);
1023        }
1024
1025        public Set<V> getVertexSet()
1026        {
1027            return vertexMapUndirected.keySet();
1028        }
1029
1030        /**
1031         * @see Graph#getAllEdges(Object, Object)
1032         */
1033        public Set<E> getAllEdges(V sourceVertex, V targetVertex)
1034        {
1035            Set<E> edges = null;
1036
1037            if (containsVertex(sourceVertex)
1038                && containsVertex(targetVertex)) {
1039                edges = new ArrayUnenforcedSet<E>();
1040
1041                Iterator<E> iter =
1042                    getEdgeContainer(sourceVertex).vertexEdges.iterator();
1043
1044                while (iter.hasNext()) {
1045                    E e = iter.next();
1046
1047                    boolean equalStraight =
1048                        sourceVertex.equals(getEdgeSource(e))
1049                        && targetVertex.equals(getEdgeTarget(e));
1050
1051                    boolean equalInverted =
1052                        sourceVertex.equals(getEdgeTarget(e))
1053                        && targetVertex.equals(getEdgeSource(e));
1054
1055                    if (equalStraight || equalInverted) {
1056                        edges.add(e);
1057                    }
1058                }
1059            }
1060
1061            return edges;
1062        }
1063
1064        /**
1065         * @see Graph#getEdge(Object, Object)
1066         */
1067        public E getEdge(V sourceVertex, V targetVertex)
1068        {
1069            if (containsVertex(sourceVertex)
1070                && containsVertex(targetVertex)) {
1071                Iterator<E> iter =
1072                    getEdgeContainer(sourceVertex).vertexEdges.iterator();
1073
1074                while (iter.hasNext()) {
1075                    E e = iter.next();
1076
1077                    boolean equalStraight =
1078                        sourceVertex.equals(getEdgeSource(e))
1079                        && targetVertex.equals(getEdgeTarget(e));
1080
1081                    boolean equalInverted =
1082                        sourceVertex.equals(getEdgeTarget(e))
1083                        && targetVertex.equals(getEdgeSource(e));
1084
1085                    if (equalStraight || equalInverted) {
1086                        return e;
1087                    }
1088                }
1089            }
1090
1091            return null;
1092        }
1093
1094        /**
1095         * @see AbstractBaseGraph#addEdgeToTouchingVertices(Edge)
1096         */
1097        public void addEdgeToTouchingVertices(E e)
1098        {
1099            V source = getEdgeSource(e);
1100            V target = getEdgeTarget(e);
1101
1102            getEdgeContainer(source).addEdge(e);
1103
1104            if (source != target) {
1105                getEdgeContainer(target).addEdge(e);
1106            }
1107        }
1108
1109        /**
1110         * @see UndirectedGraph#degreeOf(V)
1111         */
1112        public int degreeOf(V vertex)
1113        {
1114            if (allowingLoops) { // then we must count, and add loops twice
1115
1116                int degree = 0;
1117                Set<E> edges = getEdgeContainer(vertex).vertexEdges;
1118
1119                for (E e : edges) {
1120                    if (getEdgeSource(e).equals(getEdgeTarget(e))) {
1121                        degree += 2;
1122                    } else {
1123                        degree += 1;
1124                    }
1125                }
1126
1127                return degree;
1128            } else {
1129                return getEdgeContainer(vertex).edgeCount();
1130            }
1131        }
1132
1133        /**
1134         * @see Graph#edgesOf(V)
1135         */
1136        public Set<E> edgesOf(V vertex)
1137        {
1138            return getEdgeContainer(vertex).getUnmodifiableVertexEdges();
1139        }
1140
1141        /**
1142         * @see DirectedGraph#inDegreeOf(Object)
1143         */
1144        public int inDegreeOf(V vertex)
1145        {
1146            throw new UnsupportedOperationException  (NOT_IN_UNDIRECTED_GRAPH);
1147        }
1148
1149        /**
1150         * @see DirectedGraph#incomingEdgesOf(Object)
1151         */
1152        public Set<E> incomingEdgesOf(V vertex)
1153        {
1154            throw new UnsupportedOperationException  (NOT_IN_UNDIRECTED_GRAPH);
1155        }
1156
1157        /**
1158         * @see DirectedGraph#outDegreeOf(Object)
1159         */
1160        public int outDegreeOf(V vertex)
1161        {
1162            throw new UnsupportedOperationException  (NOT_IN_UNDIRECTED_GRAPH);
1163        }
1164
1165        /**
1166         * @see DirectedGraph#outgoingEdgesOf(Object)
1167         */
1168        public Set<E> outgoingEdgesOf(V vertex)
1169        {
1170            throw new UnsupportedOperationException  (NOT_IN_UNDIRECTED_GRAPH);
1171        }
1172
1173        /**
1174         * @see AbstractBaseGraph#removeEdgeFromTouchingVertices(Edge)
1175         */
1176        public void removeEdgeFromTouchingVertices(E e)
1177        {
1178            V source = getEdgeSource(e);
1179            V target = getEdgeTarget(e);
1180
1181            getEdgeContainer(source).removeEdge(e);
1182
1183            if (source != target) {
1184                getEdgeContainer(target).removeEdge(e);
1185            }
1186        }
1187
1188        /**
1189         * A lazy build of edge container for specified vertex.
1190         *
1191         * @param vertex a vertex in this graph.
1192         *
1193         * @return EdgeContainer
1194         */
1195        private UndirectedEdgeContainer<V, E> getEdgeContainer(V vertex)
1196        {
1197            assertVertexExist(vertex);
1198
1199            UndirectedEdgeContainer<V, E> ec = vertexMapUndirected.get(vertex);
1200
1201            if (ec == null) {
1202                ec = new UndirectedEdgeContainer<V, E>(
1203                        edgeSetFactory,
1204                        vertex);
1205                vertexMapUndirected.put(vertex, ec);
1206            }
1207
1208            return ec;
1209        }
1210    }
1211}
1212
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags