KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > graph > AsUndirectedGraph


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  * AsUndirectedGraph.java
27  * ----------------------
28  * (C) Copyright 2003-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): Christian Hammer
32  *
33  * $Id: AsUndirectedGraph.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 14-Aug-2003 : Initial revision (JVS);
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.io.*;
46
47 import java.util.*;
48
49 import org.jgrapht.*;
50 import org.jgrapht.util.*;
51
52
53 /**
54  * An undirected view of the backing directed graph specified in the
55  * constructor. This graph allows modules to apply algorithms designed for
56  * undirected graphs to a directed graph by simply ignoring edge direction. If
57  * the backing directed graph is an <a
58  * HREF="http://mathworld.wolfram.com/OrientedGraph.html">oriented graph</a>,
59  * then the view will be a simple graph; otherwise, it will be a multigraph.
60  * Query operations on this graph "read through" to the backing graph. Attempts
61  * to add edges will result in an <code>UnsupportedOperationException</code>,
62  * but vertex addition/removal and edge removal are all supported (and
63  * immediately reflected in the backing graph).
64  *
65  * <p>Note that edges returned by this graph's accessors are really just the
66  * edges of the underlying directed graph. Since there is no interface
67  * distinction between directed and undirected edges, this detail should be
68  * irrelevant to algorithms.</p>
69  *
70  * <p>This graph does <i>not</i> pass the hashCode and equals operations through
71  * to the backing graph, but relies on <tt>Object</tt>'s <tt>equals</tt> and
72  * <tt>hashCode</tt> methods. This graph will be serializable if the backing
73  * graph is serializable.</p>
74  *
75  * @author John V. Sichi
76  * @since Aug 14, 2003
77  */

78 public class AsUndirectedGraph<V, E>
79     extends GraphDelegator<V, E>
80     implements Serializable, UndirectedGraph<V, E>
81 {
82
83     //~ Static fields/initializers --------------------------------------------
84

85     private static final long serialVersionUID = 3257845485078065462L; // @todo renew
86
private static final String JavaDoc NO_EDGE_ADD =
87         "this graph does not support edge addition";
88     private static final String JavaDoc UNDIRECTED =
89         "this graph only supports undirected operations";
90
91     //~ Constructors ----------------------------------------------------------
92

93     /**
94      * Constructor for AsUndirectedGraph.
95      *
96      * @param g the backing directed graph over which an undirected view is to
97      * be created.
98      */

99     public AsUndirectedGraph(DirectedGraph<V, E> g)
100     {
101         super(g);
102     }
103
104     //~ Methods ---------------------------------------------------------------
105

106     /**
107      * @see Graph#getAllEdges(Object, Object)
108      */

109     public Set<E> getAllEdges(V sourceVertex, V targetVertex)
110     {
111         Set<E> forwardList = super.getAllEdges(sourceVertex, targetVertex);
112
113         if (sourceVertex.equals(targetVertex)) {
114             // avoid duplicating loops
115
return forwardList;
116         }
117
118         Set<E> reverseList = super.getAllEdges(targetVertex, sourceVertex);
119         Set<E> list =
120             new ArrayUnenforcedSet<E>(
121                 forwardList.size() + reverseList.size());
122         list.addAll(forwardList);
123         list.addAll(reverseList);
124
125         return list;
126     }
127
128     /**
129      * @see Graph#getEdge(Object, Object)
130      */

131     public E getEdge(V sourceVertex, V targetVertex)
132     {
133         E edge = super.getEdge(sourceVertex, targetVertex);
134
135         if (edge != null) {
136             return edge;
137         }
138
139         // try the other direction
140
return super.getEdge(targetVertex, sourceVertex);
141     }
142
143     /**
144      * @see Graph#addEdge(Object, Object)
145      */

146     public E addEdge(V sourceVertex, V targetVertex)
147     {
148         throw new UnsupportedOperationException JavaDoc(NO_EDGE_ADD);
149     }
150
151     /**
152      * @see Graph#addEdge(Object, Object, Object)
153      */

154     public boolean addEdge(V sourceVertex, V targetVertex, E e)
155     {
156         throw new UnsupportedOperationException JavaDoc(NO_EDGE_ADD);
157     }
158
159     /**
160      * @see UndirectedGraph#degreeOf(Object)
161      */

162     public int degreeOf(V vertex)
163     {
164         // this counts loops twice, which is consistent with AbstractBaseGraph
165
return super.inDegreeOf(vertex) + super.outDegreeOf(vertex);
166     }
167
168     /**
169      * @see DirectedGraph#inDegreeOf(Object)
170      */

171     public int inDegreeOf(V vertex)
172     {
173         throw new UnsupportedOperationException JavaDoc(UNDIRECTED);
174     }
175
176     /**
177      * @see DirectedGraph#incomingEdgesOf(Object)
178      */

179     public Set<E> incomingEdgesOf(V vertex)
180     {
181         throw new UnsupportedOperationException JavaDoc(UNDIRECTED);
182     }
183
184     /**
185      * @see DirectedGraph#outDegreeOf(Object)
186      */

187     public int outDegreeOf(V vertex)
188     {
189         throw new UnsupportedOperationException JavaDoc(UNDIRECTED);
190     }
191
192     /**
193      * @see DirectedGraph#outgoingEdgesOf(Object)
194      */

195     public Set<E> outgoingEdgesOf(V vertex)
196     {
197         throw new UnsupportedOperationException JavaDoc(UNDIRECTED);
198     }
199
200     /**
201      * @see AbstractBaseGraph#toString()
202      */

203     public String JavaDoc toString()
204     {
205         return super.toStringFromSets(vertexSet(), edgeSet(), false);
206     }
207 }
208
Popular Tags