AbstractGraph


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   * AbstractGraph.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: AbstractGraph.java 504 2006-07-03 02:37:26Z perfecthash $
34   *
35   * Changes
36   * -------
37   * 24-Jul-2003 : Initial revision (BN);
38   * 11-Mar-2004 : Made generic (CH);
39   * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
40   * 28-May-2006 : Moved connectivity info from edge to graph (JVS);
41   *
42   */
43  package org.jgrapht.graph;
44  
45  import java.util.*;
46  
47  import org.jgrapht.*;
48  
49  
50  /**
51   * A skeletal implementation of the <tt>Graph</tt> interface, to minimize the
52   * effort required to implement graph interfaces. This implementation is
53   * applicable to both: directed graphs and undirected graphs.
54   *
55   * @author Barak Naveh
56   * @see Graph
57   * @see DirectedGraph
58   * @see UndirectedGraph
59   */
60  public abstract class AbstractGraph<V, E>
61      implements Graph<V, E>
62  {
63  
64      //~ Constructors ----------------------------------------------------------
65  
66      /**
67       * Construct a new empty graph object.
68       */
69      public AbstractGraph()
70      {
71      }
72  
73      //~ Methods ---------------------------------------------------------------
74  
75      /**
76       * @see Graph#containsEdge(Object, Object)
77       */
78      public boolean containsEdge(V sourceVertex, V targetVertex)
79      {
80          return getEdge(sourceVertex, targetVertex) != null;
81      }
82  
83      /**
84       * @see Graph#removeAllEdges(Collection)
85       */
86      public boolean removeAllEdges(Collection<? extends E> edges)
87      {
88          boolean modified = false;
89  
90          for (E e : edges) {
91              modified |= removeEdge(e);
92          }
93  
94          return modified;
95      }
96  
97      /**
98       * @see Graph#removeAllEdges(Object, Object)
99       */
100     public Set<E> removeAllEdges(V sourceVertex, V targetVertex)
101     {
102         Set<E> removed = getAllEdges(sourceVertex, targetVertex);
103         removeAllEdges(removed);
104 
105         return removed;
106     }
107 
108     /**
109      * @see Graph#removeAllVertices(Collection)
110      */
111     public boolean removeAllVertices(Collection<? extends V> vertices)
112     {
113         boolean modified = false;
114 
115         for (V v : vertices) {
116             modified |= removeVertex(v);
117         }
118 
119         return modified;
120     }
121 
122     /**
123      * Returns a string of the parenthesized pair (V, E) representing this
124      * G=(V,E) graph. 'V' is the string representation of the vertex set, and
125      * 'E' is the string representation of the edge set.
126      *
127      * @return a string representation of this graph.
128      */
129     public String   toString()
130     {
131         return
132             toStringFromSets(
133                 vertexSet(),
134                 edgeSet(),
135                 (this instanceof DirectedGraph));
136     }
137 
138     /**
139      * Ensures that the specified vertex exists in this graph, or else throws
140      * exception.
141      *
142      * @param v vertex
143      *
144      * @return <code>true</code> if this assertion holds.
145      *
146      * @throws NullPointerException if specified vertex is <code>null</code>.
147      * @throws IllegalArgumentException if specified vertex does not exist in
148      *                                  this graph.
149      */
150     protected boolean assertVertexExist(V v)
151     {
152         if (containsVertex(v)) {
153             return true;
154         } else if (v == null) {
155             throw new NullPointerException  ();
156         } else {
157             throw new IllegalArgumentException  ("no such vertex in graph");
158         }
159     }
160 
161     /**
162      * Removes all the edges in this graph that are also contained in the
163      * specified edge array.  After this call returns, this graph will contain
164      * no edges in common with the specified edges. This method will invoke the
165      * {@link Graph#removeEdge(Object)} method.
166      *
167      * @param edges edges to be removed from this graph.
168      *
169      * @return <tt>true</tt> if this graph changed as a result of the call.
170      *
171      * @see Graph#removeEdge(Object)
172      * @see Graph#containsEdge(Object)
173      */
174     protected boolean removeAllEdges(E [] edges)
175     {
176         boolean modified = false;
177 
178         for (int i = 0; i < edges.length; i++) {
179             modified |= removeEdge(edges[i]);
180         }
181 
182         return modified;
183     }
184 
185     /**
186      * Helper for subclass implementations of toString(  ).
187      *
188      * @param vertexSet the vertex set V to be printed
189      * @param edgeSet the edge set E to be printed
190      * @param directed true to use parens for each edge (representing directed);
191      *                 false to use curly braces (representing undirected)
192      *
193      * @return a string representation of (V,E)
194      */
195     protected String   toStringFromSets(
196         Collection<? extends V> vertexSet,
197         Collection<? extends E> edgeSet,
198         boolean directed)
199     {
200         List<String  > renderedEdges = new ArrayList<String  >();
201 
202         StringBuffer   sb = new StringBuffer  ();
203         for (E e : edgeSet) {
204             if (
205                 (e.getClass() != DefaultEdge.class)
206                 && (e.getClass() != DefaultWeightedEdge.class)) {
207                 sb.append(e.toString());
208                 sb.append("=");
209             }
210             if (directed) {
211                 sb.append("(");
212             } else {
213                 sb.append("{");
214             }
215             sb.append(getEdgeSource(e));
216             sb.append(",");
217             sb.append(getEdgeTarget(e));
218             if (directed) {
219                 sb.append(")");
220             } else {
221                 sb.append("}");
222             }
223 
224             // REVIEW jvs 29-May-2006:  dump weight somewhere?
225             renderedEdges.add(sb.toString());
226             sb.setLength(0);
227         }
228 
229         return "(" + vertexSet + ", " + renderedEdges + ")";
230     }
231 }
232
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags