001 /*
002 * www.ti.bfh.ch
003 *
004 * Copyright 2007, Berne University of Applied Sciences,
005 * School of Engineering and Information Technology
006 * and individual contributors as indicated by the @authors tag.
007 *
008 * This is free software; you can redistribute it and/or modify it under the terms of the
009 * GNU Lesser General Public License as published by the Free Software Foundation;
010 * either version 3 of the License, or (at your option) any later version.
011 *
012 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
014 * See the GNU Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public License along with this software;
017 * if not, see <http://www.gnu.org/licenses/>.
018 *
019 */
020 package ch.bfh.algo;
021
022 import java.util.List;
023
024 /**
025 * The <code>Graph</code> interface has the functionalities of both a
026 * directed and an undirected graph.
027 *
028 * A graph contains two types of elements: E and V. The E's are stored
029 * in the edges and the V's in the vertices. Edges and Vertices are
030 * seen as <code>Position</code>s, containing E's or V's.
031 *
032 * Here is the implementation of a BFS Traversal for a <code>Graph</code>.
033 * <pre>
034 public static Sequence<Position<String>> bfsTraversal(Graph<Integer,String> g){
035 Sequence<Position<String>> buffer = new LinkedSequence<Position<String>>();
036 Sequence<Position<String>> result = new LinkedSequence<Position<String>>();
037 Set<Position<String>> bufferedVertices = new HashSet<Position<String>>();
038 List<Position<String>> vertices = g.vertices();
039 for(Position<String> v : vertices){
040 if(! bufferedVertices.contains(v)){
041 buffer.add(v);
042 bufferedVertices.add(v);
043 while(! buffer.isEmpty()){
044 Position<Position<String>> pFirst= buffer.first();
045 v = (Position<String>)buffer.element(pFirst);
046 buffer.delete(pFirst);
047 result.add(v);
048
049 for(Position<String> v2 : g.adjacentVertices(v,Direction.ALL)){
050 if(!bufferedVertices.contains(v2) && v2 !=null){
051 bufferedVertices.add(v2);
052 buffer.add(v2);
053 }
054 }
055 }
056 }
057
058 }
059 return result;
060 }
061 * </pre>
062 *
063 * @author <a href="http://www.iam.unibe.ch/til/staff/kraehenbuehl">Juerg
064 * Kraehenbuehl</a> (code) and <a href="http://prof.hti.bfh.ch/bie1">Emmanuel
065 * Benoist</a> (Javadoc)
066 * @version 1.0
067 */
068 public interface Graph<E,V> extends Container<V>{
069
070 /**
071 * Creates a new vertex containing the <code>element</code>. This
072 * vertex is then returned (it is a
073 * <code>Position<V></code>).
074 *
075 * @param element the element to be used as a label for the new vertex.
076 * @return the new vertex
077 * <code>Position</code>
078 */
079 public Position<V> insertVertex(V element);
080
081 /**
082 * Creates a new edge containing the <code>element</code>. This
083 * edge is then returned (it is a <code>Position<E></code>).
084 * The edge does not have any extremities (adjacent
085 * vertices). They have to be defined afterward.
086 *
087 * @param element the element to be used as a label for the new edge.
088 * @return the new edge
089 * <code>Position</code>
090 */
091 public Position<E> insertEdge(E element);
092
093
094 /**
095 * Creates a new edge containing the <code>element</code>. Which
096 * extremities are the two vertices <code>origin</code> and
097 * <code>destination</code>. This edge is then returned (it is a
098 * <code>Position<E></code>).
099 *
100 * If the graph is directed, the new edge is directed; if we
101 * have an undirected graph, then the new edge is also undirected.
102 *
103 * @param element the element to be used as a label for the new edge.
104 * @param origin the vertex that will be the origin of the new edge
105 * @param destination the vertex that will become the destination
106 * of the new edge.
107 * @return the new edge
108 * <code>Position</code>
109 */
110 public Position<E> insertEdge(E element, Position<?> origin, Position<?> destination) throws InvalidAccessorException;
111
112
113 /**
114 * Deletes the edge <code>position</code>. The edge is
115 * automatically removed from the two vertices at its extremities.
116 *
117 * @param position the edge to be removed from the graph.
118 * @return the element contained by the removed edge.
119 * @throws InvalidAccessorException if the position is not a
120 * valide edge of this graph.
121 */
122 public E deleteEdge(Position<?> position) throws InvalidAccessorException;
123
124 /**
125 * Deletes the vertex <code>position</code>. This also removes all
126 * the edges that had position for an extremity.
127 *
128 * @param position the vertex to be removed from the graph.
129 * @return the element contained by the removed vertex.
130 * @throws InvalidAccessorException if the position is not a
131 * valide vertex of this graph.
132 */
133 public V deleteVertex(Position<?> position) throws InvalidAccessorException;
134
135 /**
136 * Replaces the element contained in the edge <code>edge</code> by <code>element</code>.
137 *
138 * @param edge the edge whose element will be replaced;
139 * @param element the new label of the <code>edge</code>.
140 * @return the old value of <code>edge</code> that has just be replaced.
141 * @throws InvalidAccessorException if the position is not a
142 * valide edge of this graph.
143 */
144 public E replaceEdge(Position<?> edge, E element) throws InvalidAccessorException;
145
146
147 /**
148 * Replaces the element contained in the vertex <code>vertex</code> by <code>element</code>.
149 *
150 * @param vertex the vertex whose element will be replaced;
151 * @param element the new label of the <code>vertex</code>.
152 * @return the old value of <code>vertex</code> that has just be replaced.
153 * @throws InvalidAccessorException if the position is not a
154 * valide edge of this graph.
155 */
156 public V replaceVertex(Position<?> vertex, V element) throws InvalidAccessorException;
157
158 /**
159 * Exchanges the content of the two edges <code>edge0</code> and <code>edge1</code>.
160 *
161 * @param edge0 the first edge
162 * @param edge1 the second edge
163 * @throws InvalidAccessorException if one of the edges is not a
164 * valide edge of this graph.
165 */
166 public void swapEdge(Position<?> edge0, Position<?> edge1) throws InvalidAccessorException;
167
168
169 /**
170 * Exchanges the content of the two vertices <code>vertex0</code> and <code>vertex1</code>.
171 *
172 * @param vertex0 the first vertex
173 * @param vertex1 the second vertex
174 * @throws InvalidAccessorException if one of the vertices is not a
175 * valide vertex of this graph.
176 */
177 public void swapVertex(Position<?> vertex0, Position<?> vertex1) throws InvalidAccessorException;
178
179
180 /**
181 * Defines the vertex <code>vertex</code> to be the new origin of the edge <code>edge</code>.
182 * If the edge is undirected, origin is simply one of the two extremities.
183 *
184 * @param edge the edge whose origin is being defined
185 * @param vertex the new origin
186 * @throws InvalidAccessorException if the vertex or the edge do not belong to the graph
187 */
188 public void setOrigin(Position<?> edge, Position<?> vertex) throws InvalidAccessorException;
189
190 /**
191 * Defines the vertex <code>vertex</code> to be the new destination of the edge <code>edge</code>.
192 * If the edge is undirected, destination is simply one of the two extremities.
193 *
194 * @param edge the edge whose destination is being defined
195 * @param vertex the new destination.
196 * @throws InvalidAccessorException if the vertex or the edge do not belong to the graph
197 */
198 public void setDestination(Position<?> edge, Position<?> vertex) throws InvalidAccessorException;
199
200 /**
201 * Returns the origine of the edge <code>edge</code>
202 *
203 * @param edge an edge
204 * @return the origin (a vertex) of the edge.
205 * @throws InvalidAccessorException if the vertex or the edge do not belong to the graph
206 */
207 public Position<V> origin(Position<?> edge) throws InvalidAccessorException;
208 /**
209 * Returns the destination of the edge <code>edge</code>
210 *
211 * @param edge an edge
212 * @return the destination (a vertex) of the edge.
213 * @throws InvalidAccessorException if the vertex or the edge do not belong to the graph
214 */
215 public Position<V> destination(Position<?> edge) throws InvalidAccessorException;
216
217
218 /**
219 * Separates <code>edge</code> from one of its extremities, the vertex <code>vertex</code>.
220 *
221 *
222 * @param edge an edge
223 * @param vertex one of the two extremities of edge
224 * @throws InvalidAccessorException if the vertex or the edge do
225 * not belong to the graph, or if the edge is not incident to the
226 * vertex.
227 */
228 public void detach(Position<?> edge, Position<?> vertex) throws InvalidAccessorException;
229
230 /**
231 * Defines the <code>edge</code> as a directed edge.
232 *
233 *
234 * @param edge an edge
235 * @throws InvalidAccessorException if the edge does not belong to
236 * the graph
237 */
238 public void setDirected(Position<?> edge) throws InvalidAccessorException;
239
240 /**
241 * Defines the <code>edge</code> as an undirected edge.
242 *
243 *
244 * @param edge an edge
245 * @throws InvalidAccessorException if the edge does not belong to
246 * the graph
247 */
248 public void setUndirected(Position<?> edge) throws InvalidAccessorException;
249
250 /**
251 * Verifies if an edge is directed.
252 *
253 * @param edge an edge
254 * @return true if <code>edge</code> is directed
255 * @throws InvalidAccessorException if the edge does not belong to
256 * the graph
257 */
258 public boolean isDirected(Position<?> edge) throws InvalidAccessorException;
259
260 /**
261 * Exchanges the two extremities of an edge. The origin becomes the destination and vice versa.
262 *
263 * @param edge an edge
264 * @throws InvalidAccessorException if the edge does not belong to
265 * the graph
266 */
267 public void reverse(Position<?> edge) throws InvalidAccessorException;
268
269
270 /**
271 * Returns the vertex that is opposite to the vertex
272 * <code>vertex</code> on the edge <code>edge</code>. It
273 * <code>vertex</code> is the origin of <code>edge</code>, then it
274 * returns its destination, and it returns its origin if
275 * <code>vertex</code> is the destination of <code>edge</code>.
276 *
277 * @param edge an edge
278 * @throws InvalidAccessorException if the edge does not belong to
279 * the graph
280 */
281 public Position<V> opposite(Position<?> edge, Position<?> vertex) throws InvalidAccessorException;
282
283 /**
284 * Returns a list of all the vertices contained in the graph.
285 *
286 * @return the list of all vertices
287 */
288 public List<Position<V>> vertices();
289
290 /**
291 * Returns a list of all the edges contained in the graph.
292 *
293 * @return the list of all edges
294 */
295 public List<Position<E>> edges();
296
297 /**
298 * Returns a list of all the edges of a desired type.
299 * <code>type</code> can have the following values:
300 * <ul><li><code>Direction.DIRECTED</code></li>
301 * <li><code>Direction.UNDIRECTED</code></li>
302 * <li><code>Direction.ALL</code></li>
303 * </ul>
304 * @param type the type of the edges
305 * @return the list of all edges
306 */
307 public List<Position<E>> edges(Direction type);
308
309
310 /**
311 * Returns a list of the incident edges of the
312 * <code>vertex</code>. Depending on the value of
313 * <code>type</code>, the result is different.
314 *
315 * <ul><li>if <code>type==Direction.IN</code> the method returns
316 * the in incident edges</li>
317 * <li>if <code>type==Direction.OUT</code> the method returns the
318 * out incident edges</li>
319 * <li>and if <code>type==Direction.ALL</code> then the method
320 * returns all the incident edges (including the undirected
321 * ones).</li> </ul>
322 *
323 * @param vertex the vertex
324 * @param type the type of the edges
325 * @return the list of all edges
326 */
327 public List<Position<E>> incidentEdges(Position<?> vertex, Direction type) throws InvalidAccessorException;
328
329
330 /**
331 * Returns a list of the vertices adjacent to
332 * <code>vertex</code>. Depending on the value of
333 * <code>type</code>, the result is different.
334 *
335 * <ul><li>if <code>type==Direction.IN</code> the method returns
336 * the vertices linked to <code>vertex</code> through an in incident edge</li>
337 * <li>if <code>type==Direction.OUT</code> the method returns the
338 * vertices linked to <code>vertex</code> through an out incident edges</li>
339 * <li>and if <code>type==Direction.ALL</code> then the method
340 * returns all the adjacent vertices.</li> </ul>
341 *
342 * @param vertex the vertex
343 * @param type the type of the edges
344 * @return the list of adjacent vertices
345 */
346 public List<Position<V>> adjacentVertices(Position<?> vertex, Direction type) throws InvalidAccessorException;
347
348 /**
349 * Returns a list of all elements contained in the vertices.
350 *
351 * @return the list of elements contained in the vertices
352 */
353 public List<V> vertexElements();
354
355 /**
356 * Returns a list of all elements contained in the edges.
357 *
358 * @return the list of elements contained in the edges
359 */
360 public List<E> edgeElements();
361
362 /**
363 * Returns the element contained in <code>vertex</code>
364 *
365 * @param vertex the vertex containing the element
366 * @return element contained in the vertex
367 */
368 public V vertexElement(Position<?> vertex) throws InvalidAccessorException;
369
370 /**
371 * Returns the element contained in <code>edge</code>
372 *
373 * @param edge the edge containing the element
374 * @return element contained in the edge
375 */
376 public E edgeElement(Position<?> edge) throws InvalidAccessorException;
377
378 }