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.core.graph;
021
022 import java.util.List;
023
024 import ch.bfh.algo.Direction;
025 import ch.bfh.algo.DirectionException;
026 import ch.bfh.algo.InvalidAccessorException;
027 import ch.bfh.algo.Position;
028 import ch.bfh.algo.core.GenericGraph;
029 import ch.bfh.algo.core.GenericSequence;
030 import ch.bfh.algo.core.position.PositionList;
031 import ch.bfh.algo.core.position.PositionListAdapter;
032 import ch.bfh.algo.core.position.PositionListIterator;
033 import ch.bfh.algo.core.sequence.GenericLinkedSequence;
034 import ch.bfh.algo.graph.GraphFactory;
035 import ch.bfh.algo.sequence.LinkedPosition;
036 import ch.bfh.algo.sequence.LinkedSequence;
037 import ch.bfh.algo.sequence.SequenceFactory;
038
039 public class GenericAdjacencyListGraph<E,V,PE extends GenericEdge<E,V,PE,PV>,PV extends GenericVertex<E,V,PE,PV>> extends GenericLinkedSequence<V,PV> implements GenericGraph<E,V,PE,PV>{
040
041 private final GenericSequence<E,PE> edgeElements;
042
043 private final LinkedSequence<PV> vertices=new LinkedSequence<PV>();
044 private final LinkedSequence<PE> directed=new LinkedSequence<PE>();
045 private final LinkedSequence<PE> undirected=new LinkedSequence<PE>();
046 private final List<PE> all=new ListMergeAdapter<PE>(this.undirected,this.directed);
047
048 private final LinkedSequence<PE> graphType; // the type is either "this.directed" or "this.undirected"
049
050 private PositionList<V,PV> allVertices;
051 private PositionList<E,PE> allEdges;
052 private PositionList<E,PE> undirectedEdges;
053 private PositionList<E,PE> directedEdges;
054
055 protected final GraphFactory<PE,PV> factory;
056
057 public GenericAdjacencyListGraph(final GraphFactory<PE,PV> factory, boolean directed){
058 super(new SequenceFactory<PV>(){
059 public PV cast(Position<?> position){ return factory.castVertex(position); }
060 public PV createPosition(){ return factory.createVertex(); }
061 });
062 this.edgeElements=new GenericLinkedSequence<E,PE>(new SequenceFactory<PE>(){
063 public PE cast(Position<?> position){ return factory.castEdge(position); }
064 public PE createPosition(){ return factory.createEdge(); }
065 });
066 this.factory=factory;
067 if(directed) this.graphType=this.directed;
068 else this.graphType=this.undirected;
069 }
070
071 public GraphFactory<PE,PV> getFactory(){
072 return this.factory;
073 }
074
075 protected PV insertBetween(PV previous, PV next, V element, PV position){
076 PV vertex=super.insertBetween(previous,next,element,position);
077 vertex.insert(this.vertices);
078 return vertex;
079 }
080
081 public PV insertVertex(V element){
082 return this.insert(element);
083 }
084
085 public PE insertEdge(E element){
086 PE edge=this.edgeElements.insert(element);
087 edge.insert(this.graphType);
088 return edge;
089 }
090
091 public Position<E> insertEdge(E element, Position<?> origin, Position<?> destination) throws InvalidAccessorException {
092 try{return this.insertEdge(element,this.factory.castVertex(origin),this.factory.castVertex(destination));}
093 catch(ClassCastException e){ throw new InvalidAccessorException(); }
094 }
095
096 public PE insertEdge(E element, PV origin, PV destination){
097 PE edge=this.insertEdge(element);
098 this.setOrigin(edge,origin);
099 this.setDestination(edge,destination);
100 return edge;
101 }
102
103 public V delete(PV position){
104 return this.deleteVertex(position);
105 }
106
107 public V deleteVertex(PV position){
108 V element=super.delete(position);
109 position.delete();
110 return element;
111 }
112
113 public V deleteVertex(Position<?> position) throws InvalidAccessorException {
114 return this.delete(position);
115 }
116
117 public E deleteEdge(Position<?> position) throws InvalidAccessorException {
118 try{return this.deleteEdge(this.factory.castEdge(position));}
119 catch(ClassCastException e){ throw new InvalidAccessorException(); }
120 }
121
122 public E deleteEdge(PE position){
123 E element=this.edgeElements.delete(position);
124 position.delete();
125 return element;
126 }
127
128 public PositionList<V,PV> vertices(){
129 return this.allVertices();
130 }
131
132 private PositionList<V,PV> allVertices(){
133 if(this.allVertices==null){ this.allVertices=new PositionListAdapter<V,PV>(this.vertices); }
134 return this.allVertices;
135 }
136
137 public PositionList<E,PE> edges(){
138 return this.allEdges;
139 }
140
141 public PositionList<E,PE> edges(Direction type){
142 switch(type){
143 case ALL : return this.allEdges();
144 case DIRECTED : return this.directedEdges();
145 case UNDIRECTED : return this.undirectedEdges();
146 case IN : return this.directedEdges();
147 case OUT : return this.directedEdges();
148 }
149 throw new DirectionException();
150 }
151
152 private PositionList<E,PE> undirectedEdges(){
153 if(this.undirectedEdges==null){ this.undirectedEdges=new PositionListAdapter<E,PE>(this.undirected); }
154 return this.undirectedEdges;
155 }
156
157 private PositionList<E,PE> directedEdges(){
158 if(this.directedEdges==null){ this.directedEdges=new PositionListAdapter<E,PE>(this.directed); }
159 return this.directedEdges;
160 }
161
162 private PositionList<E,PE> allEdges(){
163 if(this.allEdges==null){ this.allEdges=new PositionListAdapter<E,PE>(this.all); }
164 return this.allEdges;
165 }
166
167 public PositionList<E,PE> incidentEdges(Position<?> vertex, Direction type){
168 try{return this.incidentEdges(this.factory.castVertex(vertex),type);}
169 catch(ClassCastException e){ throw new InvalidAccessorException(); }
170 }
171
172 public PositionList<E,PE> incidentEdges(PV vertex, Direction type){
173 this.validate(vertex);
174 return vertex.incidentEdges(type);
175 }
176
177 public PositionList<V,PV> adjacentVertices(Position<?> vertex, Direction type){
178 try{return this.adjacentVertices(this.factory.castVertex(vertex),type);}
179 catch(ClassCastException e){ throw new InvalidAccessorException(); }
180 }
181
182 public PositionList<V,PV> adjacentVertices(PV vertex, Direction type){
183 this.validate(vertex);
184 return vertex.adjacentVertices(type);
185 }
186
187 public void setOrigin(Position<?> edge, Position<?> vertex){
188 try{this.setOrigin(this.factory.castEdge(edge),this.factory.castVertex(vertex));}
189 catch(ClassCastException e){ throw new InvalidAccessorException(); }
190 }
191
192 public LinkedPosition<PE> setOrigin(PE edge, PV origin){
193 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
194 this.validate(origin);
195 if(edge.origin()!=origin){
196 edge.clearOrigin();
197 if(edge.isDirected(this.directed)){
198 return origin.attachOutDirected(edge);
199 }
200 else{
201 return origin.attachOutUndirected(edge);
202 }
203 }
204 return null;
205 }
206
207 public LinkedPosition<PE> setOriginBefore(PE edge, PV origin, LinkedPosition<PE> position){
208 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
209 this.validate(origin);
210 if(edge.origin()!=origin){
211 edge.clearOrigin();
212 if(edge.isDirected(this.directed)){
213 return origin.attachOutDirectedBefore(edge,position);
214 }
215 else{
216 return origin.attachOutUndirectedBefore(edge,position);
217 }
218 }
219 return null;
220 }
221
222 public LinkedPosition<PE> setOriginAfter(PE edge, PV origin,LinkedPosition<PE> position){
223 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
224 this.validate(origin);
225 if(edge.origin()!=origin){
226 edge.clearOrigin();
227 if(edge.isDirected(this.directed)){
228 return origin.attachOutDirectedAfter(edge,position);
229 }
230 else{
231 return origin.attachOutUndirectedAfter(edge,position);
232 }
233 }
234 return null;
235 }
236
237 public void setDestination(Position<?> edge, Position<?> vertex){
238 try{this.setDestination(this.factory.castEdge(edge),this.factory.castVertex(vertex));}
239 catch(ClassCastException e){ throw new InvalidAccessorException(); }
240 }
241
242 public void setDestination(PE edge, PV destination){
243 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
244 this.validate(destination);
245 if(edge.destination()!=destination){
246 edge.clearDestination();
247 if(edge.isDirected(this.directed)){
248 destination.attachInDirected(edge);
249 }
250 else{
251 destination.attachInUndirected(edge);
252 }
253 }
254 }
255
256 public void detach(Position<?> edge, Position<?> vertex){
257 try{this.detach(this.factory.castEdge(edge),this.factory.castVertex(vertex));}
258 catch(ClassCastException e){ throw new InvalidAccessorException(); }
259 }
260
261 public void detachVertex(PE edge, PV vertex){
262 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
263 this.validate(vertex);
264 if(vertex==edge.origin()) edge.clearOrigin();
265 else if(vertex==edge.destination()) edge.clearDestination();
266
267 }
268
269 public PV origin(Position<?> edge){
270 try{return this.origin(this.factory.castEdge(edge));}
271 catch(ClassCastException e){ throw new InvalidAccessorException(); }
272 }
273
274 public PV origin(PE edge){
275 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
276 return edge.origin();
277 }
278
279 public PV destination(Position<?> edge){
280 try{return this.destination(this.factory.castEdge(edge));}
281 catch(ClassCastException e){ throw new InvalidAccessorException(); }
282 }
283
284 public PV destination(PE edge){
285 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
286 return edge.destination();
287 }
288
289 public void setDirected(Position<?> edge){
290 try{this.setDirected(this.factory.castEdge(edge));}
291 catch(ClassCastException e){ throw new InvalidAccessorException(); }
292 }
293
294 public void setDirected(PE edge){
295 if(!this.isDirected(edge)){
296 edge.setDirected(this.directed);
297 }
298 }
299
300 public void setUndirected(Position<?> edge){
301 try{this.setUndirected(this.factory.castEdge(edge));}
302 catch(ClassCastException e){ throw new InvalidAccessorException(); }
303 }
304
305 public void setUndirected(PE edge){
306 if(this.isDirected(edge)){
307 edge.setUndirected(this.undirected);
308 }
309 }
310
311 public boolean isDirected(Position<?> edge){
312 try{return this.isDirected(this.factory.castEdge(edge));}
313 catch(ClassCastException e){ throw new InvalidAccessorException(); }
314 }
315
316 public boolean isDirected(PE edge){
317 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
318 return edge.isDirected(this.directed);
319 }
320
321 public void reverse(Position<?> edge){
322 try{this.reverse(this.factory.castEdge(edge));}
323 catch(ClassCastException e){ throw new InvalidAccessorException(); }
324 }
325
326 public void reverse(PE edge){
327 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
328 GenericVertex<E,V,PE,PV> v0=edge.origin(), v1=edge.destination();
329 if(v0!=v1){
330 if(v1!=null) this.setOrigin(edge,v1);
331 if(v0!=null) this.setDestination(edge,v0);
332 }
333 }
334
335 public PV opposite(Position<?> edge, Position<?> vertex){
336 try{return this.opposite(this.factory.castEdge(edge),this.factory.castVertex(vertex));}
337 catch(ClassCastException e){ throw new InvalidAccessorException(); }
338 }
339
340 public PV opposite(PE edge, PV vertex){
341 if(!this.edgeElements.encloses(edge)) throw new InvalidAccessorException();
342 this.validate(vertex);
343 return edge.oppositeVertex(vertex);
344 }
345
346 public V replaceVertex(Position<?> vertex, V element){
347 return this.replace(vertex,element);
348 }
349
350 public E replaceEdge(Position<?> edge, E element){
351 return this.edgeElements.replace(edge,element);
352 }
353
354 public void swapEdge(Position<?> edge0, Position<?> edge1){
355 this.edgeElements.swap(edge0,edge1);
356 }
357
358 public void swapVertex(Position<?> vertex0, Position<?> vertex1){
359 this.swap(vertex0,vertex1);
360 }
361
362 public GenericSequence<V,PV> vertexElements(){
363 return this;
364 }
365
366 public GenericSequence<E,PE> edgeElements(){
367 return this.edgeElements;
368 }
369
370 public PV insertBefore(PV position, V element){
371 throw new UnsupportedOperationException();
372 }
373
374 public PV insertAfter(PV position, V element){
375 throw new UnsupportedOperationException();
376 }
377
378 public PositionListIterator<V,PV> positionListIterator(){
379 return super.positionListIterator();
380 }
381
382 public PositionListIterator<V,PV> positionListIterator(int rank){
383 return super.positionListIterator(rank);
384 }
385
386 public E edgeElement(Position<?> edge){
387 try{return this.edgeElement(this.factory.castEdge(edge));}
388 catch(ClassCastException e){ throw new InvalidAccessorException(); }
389 }
390
391 public E edgeElement(PE edge){
392 return this.edgeElements.element(edge);
393 }
394
395 public V vertexElement(Position<?> vertex){
396 return this.element(vertex);
397 }
398
399 }