Graph


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   * Graph.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: Graph.java 505 2006-07-03 05:41:25Z perfecthash $
35   *
36   * Changes
37   * -------
38   * 24-Jul-2003 : Initial revision (BN);
39   * 06-Nov-2003 : Change edge sharing semantics (JVS);
40   * 11-Mar-2004 : Made generic (CH);
41   * 07-May-2006 : Changed from List<Edge> to Set<Edge> (JVS);
42   * 28-May-2006 : Moved connectivity info from edge to graph (JVS);
43   *
44   */
45  package org.jgrapht;
46  
47  import java.util.*;
48  
49  
50  /**
51   * The root interface in the graph hierarchy.  A mathematical graph-theory graph
52   * object <tt>G(V,E)</tt> contains a set <tt>V</tt> of vertices and a set <tt>
53   * E</tt> of edges. Each edge e=(v1,v2) in E connects vertex v1 to vertex v2.
54   * for more information about graphs and their related definitions see <a
55   * HREF="http://mathworld.wolfram.com/Graph.html">
56   * http://mathworld.wolfram.com/Graph.html</a>.
57   *
58   * <p>This library generally follows the terminology found at: <a
59   * HREF="http://mathworld.wolfram.com/topics/GraphTheory.html">
60   * http://mathworld.wolfram.com/topics/GraphTheory.html</a>. Implementation of
61   * this interface can provide simple-graphs, multigraphs, pseudographs etc. The
62   * package <code>org.jgrapht.graph</code> provides a gallery of abstract and
63   * concrete graph implementations.</p>
64   *
65   * <p>This library works best when vertices represent arbitrary objects and
66   * edges represent the relationships between them.  Vertex and edge instances
67   * may be shared by more than one graph.</p>
68   *
69   * Through generics, a graph can be typed to specific classes for vertices
70   * <code>V</code> and edges <code>E&lt;T&gt;</code>. Such a graph can contain
71   * vertices of type <code>V</code> and all sub-types and Edges of type <code>
72   * E</code> and all sub-types.
73   *
74   * @author Barak Naveh
75   * @since Jul 14, 2003
76   */
77  public interface Graph<V, E>
78  {
79  
80      //~ Methods ---------------------------------------------------------------
81  
82      /**
83       * Returns a set of all edges connecting source vertex to target vertex if
84       * such vertices exist in this graph. If any of the vertices does not exist
85       * or is <code>null</code>, returns <code>null</code>. If both vertices
86       * exist but no edges found, returns an empty set.
87       *
88       * <p>In undirected graphs, some of the returned edges may have their source
89       * and target vertices in the opposite order. In simple graphs the returned
90       * set is either singleton set or empty set.</p>
91       *
92       * @param sourceVertex source vertex of the edge.
93       * @param targetVertex target vertex of the edge.
94       *
95       * @return a set of all edges connecting source vertex to target vertex.
96       */
97      public Set<E> getAllEdges(V sourceVertex, V targetVertex);
98  
99      /**
100      * Returns an edge connecting source vertex to target vertex if such
101      * vertices and such edge exist in this graph. Otherwise returns <code>
102      * null</code>. If any of the specified vertices is <code>null</code>
103      * returns <code>null</code>
104      *
105      * <p>In undirected graphs, the returned edge may have its source and target
106      * vertices in the opposite order.</p>
107      *
108      * @param sourceVertex source vertex of the edge.
109      * @param targetVertex target vertex of the edge.
110      *
111      * @return an edge connecting source vertex to target vertex.
112      */
113     public E getEdge(V sourceVertex, V targetVertex);
114 
115     /**
116      * Returns the edge factory using which this graph creates new edges. The
117      * edge factory is defined when the graph is constructed and must not be
118      * modified.
119      *
120      * @return the edge factory using which this graph creates new edges.
121      */
122     public EdgeFactory<V, E> getEdgeFactory();
123 
124     /**
125      * Creates a new edge in this graph, going from the source vertex to the
126      * target vertex, and returns the created edge. Some graphs do not allow
127      * edge-multiplicity. In such cases, if the graph already contains an edge
128      * from the specified source to the specified target, than this method does
129      * not change the graph and returns <code>null</code>.
130      *
131      * <p>The source and target vertices must already be contained in this
132      * graph. If they are not found in graph IllegalArgumentException is
133      * thrown.</p>
134      *
135      * <p>This method creates the new edge <code>e</code> using this graph's
136      * <code>EdgeFactory</code>. For the new edge to be added <code>e</code>
137      * must <i>not</i> be equal to any other edge the graph (even if the graph
138      * allows edge-multiplicity). More formally, the graph must not contain any
139      * edge <code>e2</code> such that <code>e2.equals(e)</code>. If such <code>
140      * e2</code> is found then the newly created edge <code>e</code> is
141      * abandoned, the method leaves this graph unchanged returns <code>
142      * null</code>.</p>
143      *
144      * @param sourceVertex source vertex of the edge.
145      * @param targetVertex target vertex of the edge.
146      *
147      * @return The newly created edge if added to the graph, otherwise <code>
148      *         null</code>.
149      *
150      * @throws IllegalArgumentException if source or target vertices are not
151      *                                  found in the graph.
152      * @throws NullPointerException if any of the specified vertices is <code>
153      *                              null</code>.
154      *
155      * @see #getEdgeFactory()
156      */
157     public E addEdge(V sourceVertex, V targetVertex);
158 
159     /**
160      * Adds the specified edge to this graph, going from the source vertex to
161      * the target vertex. More formally, adds the specified edge, <code>
162      * e</code>, to this graph if this graph contains no edge <code>e2</code>
163      * such that <code>e2.equals(e)</code>. If this graph already contains such
164      * an edge, the call leaves this graph unchanged and returns <tt>false</tt>.
165      * Some graphs do not allow edge-multiplicity. In such cases, if the graph
166      * already contains an edge from the specified source to the specified
167      * target, than this method does not change the graph and returns <code>
168      * false</code>.  If the edge was added to the graph, returns <code>
169      * true</code>.
170      *
171      * <p>The source and target vertices must already be contained in this
172      * graph. If they are not found in graph IllegalArgumentException is
173      * thrown.</p>
174      *
175      * @param sourceVertex source vertex of the edge.
176      * @param targetVertex target vertex of the edge.
177      * @param e edge to be added to this graph.
178      *
179      * @return <tt>true</tt> if this graph did not already contain the specified
180      *         edge.
181      *
182      * @throws IllegalArgumentException if source or target vertices are not
183      *                                  found in the graph.
184      * @throws ClassCastException if the specified edge is not assignment
185      *                            compatible with the class of edges produced by
186      *                            the edge factory of this graph.
187      * @throws NullPointerException if any of the specified vertices is <code>
188      *                              null</code>.
189      *
190      * @see #addEdge(Object, Object)
191      * @see #getEdgeFactory()
192      */
193     public boolean addEdge(V sourceVertex, V targetVertex, E e);
194 
195     /**
196      * Adds the specified vertex to this graph if not already present. More
197      * formally, adds the specified vertex, <code>v</code>, to this graph if
198      * this graph contains no vertex <code>u</code> such that <code>
199      * u.equals(v)</code>. If this graph already contains such vertex, the call
200      * leaves this graph unchanged and returns <tt>false</tt>. In combination
201      * with the restriction on constructors, this ensures that graphs never
202      * contain duplicate vertices.
203      *
204      * @param v vertex to be added to this graph.
205      *
206      * @return <tt>true</tt> if this graph did not already contain the specified
207      *         vertex.
208      *
209      * @throws NullPointerException if the specified vertex is <code>
210      *                              null</code>.
211      */
212     public boolean addVertex(V v);
213 
214     /**
215      * Returns <tt>true</tt> if and only if this graph contains an edge going
216      * from the source vertex to the target vertex. In undirected graphs the
217      * same result is obtained when source and target are inverted. If any of
218      * the specified vertices does not exist in the graph, or if is <code>
219      * null</code>, returns <code>false</code>.
220      *
221      * @param sourceVertex source vertex of the edge.
222      * @param targetVertex target vertex of the edge.
223      *
224      * @return <tt>true</tt> if this graph contains the specified edge.
225      */
226     public boolean containsEdge(V sourceVertex, V targetVertex);
227 
228     /**
229      * Returns <tt>true</tt> if this graph contains the specified edge.  More
230      * formally, returns <tt>true</tt> if and only if this graph contains an
231      * edge <code>e2</code> such that <code>e.equals(e2)</code>. If the
232      * specified edge is <code>null</code> returns <code>false</code>.
233      *
234      * @param e edge whose presence in this graph is to be tested.
235      *
236      * @return <tt>true</tt> if this graph contains the specified edge.
237      */
238     public boolean containsEdge(E e);
239 
240     /**
241      * Returns <tt>true</tt> if this graph contains the specified vertex.  More
242      * formally, returns <tt>true</tt> if and only if this graph contains a
243      * vertex <code>u</code> such that <code>u.equals(v)</code>. If the
244      * specified vertex is <code>null</code> returns <code>false</code>.
245      *
246      * @param v vertex whose presence in this graph is to be tested.
247      *
248      * @return <tt>true</tt> if this graph contains the specified vertex.
249      */
250     public boolean containsVertex(V v);
251 
252     /**
253      * Returns a set of the edges contained in this graph. The set is backed by
254      * the graph, so changes to the graph are reflected in the set. If the graph
255      * is modified while an iteration over the set is in progress, the results
256      * of the iteration are undefined.
257      *
258      * <p>The graph implementation may maintain a particular set ordering (e.g.
259      * via {@link java.util.LinkedHashSet}) for deterministic iteration, but
260      * this is not required.  It is the responsibility of callers who rely on
261      * this behavior to only use graph implementations which support it.</p>
262      *
263      * @return a set of the edges contained in this graph.
264      */
265     public Set<E> edgeSet();
266 
267     /**
268      * Returns a set of all edges touching the specified vertex. If no edges are
269      * touching the specified vertex returns an empty set.
270      *
271      * @param vertex the vertex for which a set of touching edges is to be
272      *               returned.
273      *
274      * @return a set of all edges touching the specified vertex.
275      *
276      * @throws IllegalArgumentException if vertex is not
277      *                                  found in the graph.
278      * @throws NullPointerException if vertex is <code>null</code>.
279      */
280     public Set<E> edgesOf(V vertex);
281 
282     /**
283      * Removes all the edges in this graph that are also contained in the
284      * specified edge collection.  After this call returns, this graph will
285      * contain no edges in common with the specified edges. This method will
286      * invoke the {@link #removeEdge(Object)} method.
287      *
288      * @param edges edges to be removed from this graph.
289      *
290      * @return <tt>true</tt> if this graph changed as a result of the call
291      *
292      * @throws NullPointerException if the specified edge collection is <tt>
293      *                              null</tt>.
294      *
295      * @see #removeEdge(Object)
296      * @see #containsEdge(Object)
297      */
298     public boolean removeAllEdges(Collection<? extends E> edges);
299 
300     /**
301      * Removes all the edges going from the specified source vertex to the
302      * specified target vertex, and returns a set of all removed edges. Returns
303      * <code>null</code> if any of the specified vertices does not exist in the
304      * graph. If both vertices exist but no edge is found, returns an empty set.
305      * This method will either invoke the {@link #removeEdge(Object)} method, or
306      * the {@link #removeEdge(Object, Object)} method.
307      *
308      * @param sourceVertex source vertex of the edge.
309      * @param targetVertex target vertex of the edge.
310      *
311      * @return the removed edges, or <code>null</code> if no either vertex not
312      *         part of graph
313      */
314     public Set<E> removeAllEdges(V sourceVertex, V targetVertex);
315 
316     /**
317      * Removes all the vertices in this graph that are also contained in the
318      * specified vertex collection.  After this call returns, this graph will
319      * contain no vertices in common with the specified vertices. This method
320      * will invoke the {@link #removeVertex(Object)} method.
321      *
322      * @param vertices vertices to be removed from this graph.
323      *
324      * @return <tt>true</tt> if this graph changed as a result of the call
325      *
326      * @throws NullPointerException if the specified vertex collection is <tt>
327      *                              null</tt>.
328      *
329      * @see #removeVertex(Object)
330      * @see #containsVertex(Object)
331      */
332     public boolean removeAllVertices(Collection<? extends V> vertices);
333 
334     /**
335      * Removes an edge going from source vertex to target vertex, if such
336      * vertices and such edge exist in this graph. Returns the edge if removed
337      * or <code>null</code> otherwise.
338      *
339      * @param sourceVertex source vertex of the edge.
340      * @param targetVertex target vertex of the edge.
341      *
342      * @return The removed edge, or <code>null</code> if no edge removed.
343      */
344     public E removeEdge(V sourceVertex, V targetVertex);
345 
346     /**
347      * Removes the specified edge from the graph. Removes the specified edge
348      * from this graph if it is present. More formally, removes an edge <code>
349      * e2</code> such that <code>e2.equals(e)</code>, if the graph contains such
350      * edge. Returns <tt>true</tt> if the graph contained the specified edge.
351      * (The graph will not contain the specified edge once the call returns).
352      *
353      * <p>If the specified edge is <code>null</code> returns <code>
354      * false</code>.</p>
355      *
356      * @param e edge to be removed from this graph, if present.
357      *
358      * @return <code>true</code> if and only if the graph contained the
359      *         specified edge.
360      */
361     public boolean removeEdge(E e);
362 
363     /**
364      * Removes the specified vertex from this graph including all its touching
365      * edges if present.  More formally, if the graph contains a vertex <code>
366      * u</code> such that <code>u.equals(v)</code>, the call removes all edges
367      * that touch <code>u</code> and then removes <code>u</code> itself. If no
368      * such <code>u</code> is found, the call leaves the graph unchanged.
369      * Returns <tt>true</tt> if the graph contained the specified vertex. (The
370      * graph will not contain the specified vertex once the call returns).
371      *
372      * <p>If the specified vertex is <code>null</code> returns <code>
373      * false</code>.</p>
374      *
375      * @param v vertex to be removed from this graph, if present.
376      *
377      * @return <code>true</code> if the graph contained the specified vertex;
378      *         <code>false</code> otherwise.
379      */
380     public boolean removeVertex(V v);
381 
382     /**
383      * Returns a set of the vertices contained in this graph. The set is backed
384      * by the graph, so changes to the graph are reflected in the set. If the
385      * graph is modified while an iteration over the set is in progress, the
386      * results of the iteration are undefined.
387      *
388      * <p>The graph implementation may maintain a particular set ordering (e.g.
389      * via {@link java.util.LinkedHashSet}) for deterministic iteration, but
390      * this is not required.  It is the responsibility of callers who rely on
391      * this behavior to only use graph implementations which support it.</p>
392      *
393      * @return a set view of the vertices contained in this graph.
394      */
395     public Set<V> vertexSet();
396 
397     /**
398      * Returns the source vertex of an edge.  For an undirected graph, source
399      * and target are distinguishable designations (but without any mathematical
400      * meaning).
401      *
402      * @param e edge of interest
403      *
404      * @return source vertex
405      */
406     public V getEdgeSource(E e);
407 
408     /**
409      * Returns the target vertex of an edge.  For an undirected graph, source
410      * and target are distinguishable designations (but without any mathematical
411      * meaning).
412      *
413      * @param e edge of interest
414      *
415      * @return target vertex
416      */
417     public V getEdgeTarget(E e);
418 
419     /**
420      * Returns the weight assigned to a given edge.  Unweighted graphs return
421      * 1.0 (as defined by {@link WeightedGraph#DEFAULT_EDGE_WEIGHT}), allowing
422      * weighted-graph algorithms to apply to them where meaningful.
423      *
424      * @param e edge of interest
425      *
426      * @return edge weight
427      *
428      * @see WeightedGraph
429      */
430     public double getEdgeWeight(E e);
431 }
432
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags