Graphs


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   * Graphs.java
27   * ----------------
28   * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29   *
30   * Original Author:  Barak Naveh
31   * Contributor(s):   Christian Hammer
32   *                   Mikael Hansen
33   *
34   * $Id: Graphs.java 504 2006-07-03 02:37:26Z perfecthash $
35   *
36   * Changes
37   * -------
38   * 10-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  import org.jgrapht.graph.*;
50  
51  
52  /**
53   * A collection of utilities to assist with graph manipulation.
54   *
55   * @author Barak Naveh
56   * @since Jul 31, 2003
57   */
58  public abstract class Graphs
59  {
60  
61      //~ Methods ---------------------------------------------------------------
62  
63      /**
64       * Creates a new edge and adds it to the specified graph similarly to the
65       * {@link Graph#addEdge(Object, Object)} method.
66       *
67       * @param g the graph for which the edge to be added.
68       * @param sourceVertex source vertex of the edge.
69       * @param targetVertex target vertex of the edge.
70       * @param weight weight of the edge.
71       *
72       * @return The newly created edge if added to the graph, otherwise <code>
73       *         null</code>.
74       *
75       * @see Graph#addEdge(Object, Object)
76       */
77      public static <V, E> E addEdge(
78          Graph<V, E> g,
79          V sourceVertex,
80          V targetVertex,
81          double weight)
82      {
83          EdgeFactory<V, E> ef = g.getEdgeFactory();
84          E e = ef.createEdge(sourceVertex, targetVertex);
85  
86          // we first create the edge and set the weight to make sure that
87          // listeners will see the correct weight upon addEdge.
88  
89          assert (g instanceof WeightedGraph) : g.getClass();
90          ((WeightedGraph<V, E>) g).setEdgeWeight(e, weight);
91  
92          return g.addEdge(sourceVertex, targetVertex, e) ? e : null;
93      }
94  
95      /**
96       * Adds the specified source and target vertices to the graph, if not
97       * already included, and creates a new edge and adds it to the specified
98       * graph similarly to the {@link Graph#addEdge(Object, Object)} method.
99       *
100      * @param g the graph for which the specified edge to be added.
101      * @param sourceVertex source vertex of the edge.
102      * @param targetVertex target vertex of the edge.
103      *
104      * @return The newly created edge if added to the graph, otherwise <code>
105      *         null</code>.
106      */
107     public static <V, E> E addEdgeWithVertices(
108         Graph<V, E> g,
109         V sourceVertex,
110         V targetVertex)
111     {
112         g.addVertex(sourceVertex);
113         g.addVertex(targetVertex);
114 
115         return g.addEdge(sourceVertex, targetVertex);
116     }
117 
118     /**
119      * Adds the specified edge to the graph, including its vertices if not
120      * already included.
121      *
122      * @param targetGraph the graph for which the specified edge to be added.
123      * @param sourceGraph the graph in which the specified edge is already
124      *                    present
125      * @param edge edge to add
126      *
127      * @return <tt>true</tt> if the target graph did not already contain the
128      *         specified edge.
129      */
130     public static <V, E> boolean addEdgeWithVertices(
131         Graph<V, E> targetGraph,
132         Graph<V, E> sourceGraph,
133         E edge)
134     {
135         V sourceVertex = sourceGraph.getEdgeSource(edge);
136         V targetVertex = sourceGraph.getEdgeTarget(edge);
137 
138         targetGraph.addVertex(sourceVertex);
139         targetGraph.addVertex(targetVertex);
140 
141         return targetGraph.addEdge(sourceVertex, targetVertex, edge);
142     }
143 
144     /**
145      * Adds the specified source and target vertices to the graph, if not
146      * already included, and creates a new weighted edge and adds it to the
147      * specified graph similarly to the {@link Graph#addEdge(Object, Object)}
148      * method.
149      *
150      * @param g the graph for which the specified edge to be added.
151      * @param sourceVertex source vertex of the edge.
152      * @param targetVertex target vertex of the edge.
153      * @param weight weight of the edge.
154      *
155      * @return The newly created edge if added to the graph, otherwise <code>
156      *         null</code>.
157      */
158     public static <V, E> E addEdgeWithVertices(
159         Graph<V, E> g,
160         V sourceVertex,
161         V targetVertex,
162         double weight)
163     {
164         g.addVertex(sourceVertex);
165         g.addVertex(targetVertex);
166 
167         return addEdge(g, sourceVertex, targetVertex, weight);
168     }
169 
170     /**
171      * Adds all the vertices and all the edges of the specified source graph to
172      * the specified destination graph. First all vertices of the source graph
173      * are added to the destination graph. Then every edge of the source graph
174      * is added to the destination graph. This method returns <code>true</code>
175      * if the destination graph has been modified as a result of this operation,
176      * otherwise it returns <code>false</code>.
177      *
178      * <p>The behavior of this operation is undefined if any of the specified
179      * graphs is modified while operation is in progress.</p>
180      *
181      * @param destination the graph to which vertices and edges are added.
182      * @param source the graph used as source for vertices and edges to add.
183      *
184      * @return <code>true</code> if and only if the destination graph has been
185      *         changed as a result of this operation.
186      */
187     public static <V, E> boolean addGraph(
188         Graph<V, E> destination,
189         Graph<V, E> source)
190     {
191         boolean modified = addAllVertices(destination, source.vertexSet());
192         modified |= addAllEdges(destination, source, source.edgeSet());
193 
194         return modified;
195     }
196 
197     /**
198      * Adds all the vertices and all the edges of the specified source digraph
199      * to the specified destination digraph, reversing all of the edges.
200      *
201      * <p>The behavior of this operation is undefined if any of the specified
202      * graphs is modified while operation is in progress.</p>
203      *
204      * @param destination the graph to which vertices and edges are added.
205      * @param source the graph used as source for vertices and edges to add.
206      */
207     public static <V, E> void addGraphReversed(
208         DirectedGraph<V, E> destination,
209         DirectedGraph<V, E> source)
210     {
211         addAllVertices(destination, source.vertexSet());
212 
213         for (E edge : source.edgeSet()) {
214             destination.addEdge(
215                 source.getEdgeTarget(edge),
216                 source.getEdgeSource(edge));
217         }
218     }
219 
220     /**
221      * Adds a subset of the edges of the specified source graph to the specified
222      * destination graph. The behavior of this operation is undefined if either
223      * of the graphs is modified while the operation is in progress. {@link
224      * #addEdgeWithVertices} is used for the transfer, so source vertexes will
225      * be added automatically to the target graph.
226      *
227      * @param destination the graph to which edges are to be added
228      * @param source the graph used as a source for edges to add
229      * @param edges the edges to be added
230      *
231      * @return <tt>true</tt> if this graph changed as a result of the call
232      */
233     public static <V, E> boolean addAllEdges(
234         Graph<V, E> destination,
235         Graph<V, E> source,
236         Collection<? extends E> edges)
237     {
238         boolean modified = false;
239 
240         for (E e : edges) {
241             V s = source.getEdgeSource(e);
242             V t = source.getEdgeTarget(e);
243             destination.addVertex(s);
244             destination.addVertex(t);
245             modified |= destination.addEdge(s, t, e);
246         }
247 
248         return modified;
249     }
250 
251     /**
252      * Adds all of the specified vertices to the destination graph. The behavior
253      * of this operation is undefined if the specified vertex collection is
254      * modified while the operation is in progress. This method will invoke the
255      * {@link Graph#addVertex(Object)} method.
256      *
257      * @param destination the graph to which edges are to be added
258      * @param vertices the vertices to be added to the graph.
259      *
260      * @return <tt>true</tt> if graph changed as a result of the call
261      *
262      * @throws NullPointerException if the specified vertices contains one or
263      *                              more null vertices, or if the specified
264      *                              vertex collection is <tt>null</tt>.
265      *
266      * @see Graph#addVertex(Object)
267      */
268     public static <V, E> boolean addAllVertices(
269         Graph<V, E> destination,
270         Collection<? extends V> vertices)
271     {
272         boolean modified = false;
273 
274         for (V v : vertices) {
275             modified |= destination.addVertex(v);
276         }
277 
278         return modified;
279     }
280 
281     /**
282      * Returns a list of vertices that are the neighbors of a specified vertex.
283      * If the graph is a multigraph vertices may appear more than once in the
284      * returned list.
285      *
286      * @param g the graph to look for neighbors in.
287      * @param vertex the vertex to get the neighbors of.
288      *
289      * @return a list of the vertices that are the neighbors of the specified
290      *         vertex.
291      */
292     public static <V, E> List<V> neighborListOf(Graph<V, E> g,
293         V vertex)
294     {
295         List<V> neighbors = new ArrayList<V>();
296 
297         for (E e : g.edgesOf(vertex)) {
298             neighbors.add(getOppositeVertex(g, e, vertex));
299         }
300 
301         return neighbors;
302     }
303 
304     /**
305      * Returns a list of vertices that are the predecessors of a specified
306      * vertex. If the graph is a multigraph, vertices may appear more than once
307      * in the returned list.
308      *
309      * @param g the graph to look for predecessors in.
310      * @param vertex the vertex to get the predecessors of.
311      *
312      * @return a list of the vertices that are the predecessors of the specified
313      *         vertex.
314      */
315     public static <V, E> List<V> predecessorListOf(
316         DirectedGraph<V, E> g,
317         V vertex)
318     {
319         List<V> predecessors = new ArrayList<V>();
320         Set<? extends E> edges = g.incomingEdgesOf(vertex);
321 
322         for (E e : edges) {
323             predecessors.add(getOppositeVertex(g, e, vertex));
324         }
325 
326         return predecessors;
327     }
328 
329     /**
330      * Returns a list of vertices that are the successors of a specified vertex.
331      * If the graph is a multigraph vertices may appear more than once in the
332      * returned list.
333      *
334      * @param g the graph to look for successors in.
335      * @param vertex the vertex to get the successors of.
336      *
337      * @return a list of the vertices that are the successors of the specified
338      *         vertex.
339      */
340     public static <V, E> List<V> successorListOf(
341         DirectedGraph<V, E> g,
342         V vertex)
343     {
344         List<V> successors = new ArrayList<V>();
345         Set<? extends E> edges = g.outgoingEdgesOf(vertex);
346 
347         for (E e : edges) {
348             successors.add(getOppositeVertex(g, e, vertex));
349         }
350 
351         return successors;
352     }
353 
354     /**
355      * Returns an undirected view of the specified graph. If the specified graph
356      * is directed, returns an undirected view of it. If the specified graph is
357      * undirected, just returns it.
358      *
359      * @param g the graph for which an undirected view to be returned.
360      *
361      * @return an undirected view of the specified graph, if it is directed, or
362      *         or the specified graph itself if it is undirected.
363      *
364      * @throws IllegalArgumentException if the graph is neither DirectedGraph
365      *                                  nor UndirectedGraph.
366      *
367      * @see AsUndirectedGraph
368      */
369     public static <V, E> UndirectedGraph<V, E> undirectedGraph(Graph<V, E> g)
370     {
371         if (g instanceof DirectedGraph) {
372             return new AsUndirectedGraph<V, E>((DirectedGraph<V, E>) g);
373         } else if (g instanceof UndirectedGraph) {
374             return (UndirectedGraph<V, E>) g;
375         } else {
376             throw new IllegalArgumentException  (
377                 "Graph must be either DirectedGraph or UndirectedGraph");
378         }
379     }
380 
381     /**
382      * Tests whether an edge is incident to a vertex.
383      *
384      * @param g graph containing e and v
385      * @param e edge in g
386      * @param v vertex in g
387      *
388      * @return true iff e is incident on v
389      */
390     public static <V, E> boolean testIncidence(Graph<V, E> g, E e, V v)
391     {
392         return (g.getEdgeSource(e).equals(v))
393             || (g.getEdgeTarget(e).equals(v));
394     }
395 
396     /**
397      * Gets the vertex opposite another vertex across an edge.
398      *
399      * @param g graph containing e and v
400      * @param e edge in g
401      * @param v vertex in g
402      *
403      * @return vertex opposite to v across e
404      */
405     public static <V, E> V getOppositeVertex(Graph<V, E> g, E e, V v)
406     {
407         V source = g.getEdgeSource(e);
408         V target = g.getEdgeTarget(e);
409         if (v.equals(source)) {
410             return target;
411         } else if (v.equals(target)) {
412             return source;
413         } else {
414             throw new IllegalArgumentException  ("no such vertex");
415         }
416     }
417 }
418
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags