001: /*
002: * Generic graph library
003: * Copyright (C) 2000,2003,2004,2007 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.graph;
021:
022: import java.util.ArrayList;
023: import java.util.Iterator;
024: import java.util.NoSuchElementException;
025:
026: /**
027: * A simple Graph implementation where the vertex objects
028: * store a list of incoming and outgoing edges.
029: * The edge link fields are stored in the edge objects,
030: * which means a fairly low space overhead.
031: *
032: * <p> The abstract allocateEdge() method must be implemented.
033: *
034: * @see Graph
035: * @see AbstractEdge
036: * @see AbstractVertex
037: * @author David Hovemeyer
038: */
039: public abstract class AbstractGraph<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>
040: implements Graph<EdgeType, VertexType> {
041:
042: /* ----------------------------------------------------------------------
043: * Helper classes
044: * ---------------------------------------------------------------------- */
045:
046: /**
047: * Iterator over outgoing edges.
048: */
049: private static class OutgoingEdgeIterator<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>
050: implements Iterator<EdgeType> {
051:
052: private EdgeType edge;
053:
054: public OutgoingEdgeIterator(VertexType source) {
055: this .edge = source.getFirstOutgoingEdge();
056: }
057:
058: public boolean hasNext() {
059: return edge != null;
060: }
061:
062: public EdgeType next() {
063: if (!hasNext())
064: throw new NoSuchElementException();
065: EdgeType result = edge;
066: edge = edge.getNextOutgoingEdge();
067: return result;
068: }
069:
070: public void remove() {
071: throw new UnsupportedOperationException();
072: }
073: }
074:
075: /**
076: * Iterator over incoming edges.
077: */
078: private static class IncomingEdgeIterator<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>
079: implements Iterator<EdgeType> {
080:
081: private EdgeType edge;
082:
083: public IncomingEdgeIterator(VertexType target) {
084: this .edge = target.getFirstIncomingEdge();
085: }
086:
087: public boolean hasNext() {
088: return edge != null;
089: }
090:
091: public EdgeType next() {
092: if (!hasNext())
093: throw new NoSuchElementException();
094: EdgeType result = edge;
095: edge = edge.getNextIncomingEdge();
096: return result;
097: }
098:
099: public void remove() {
100: throw new UnsupportedOperationException();
101: }
102: }
103:
104: /* ----------------------------------------------------------------------
105: * Fields
106: * ---------------------------------------------------------------------- */
107:
108: private ArrayList<VertexType> vertexList;
109: private ArrayList<EdgeType> edgeList;
110: private int maxVertexLabel;
111: // private int nextVertexId;
112: private int maxEdgeLabel;
113:
114: /* ----------------------------------------------------------------------
115: * Public methods
116: * ---------------------------------------------------------------------- */
117:
118: public AbstractGraph() {
119: this .vertexList = new ArrayList<VertexType>();
120: this .edgeList = new ArrayList<EdgeType>();
121: this .maxVertexLabel = 0;
122: this .maxEdgeLabel = 0;
123: }
124:
125: public int getNumEdges() {
126: return edgeList.size();
127: }
128:
129: public int getNumVertices() {
130: return vertexList.size();
131: }
132:
133: public Iterator<EdgeType> edgeIterator() {
134: return edgeList.iterator();
135: }
136:
137: public Iterator<VertexType> vertexIterator() {
138: return vertexList.iterator();
139: }
140:
141: public void addVertex(VertexType v) {
142: vertexList.add(v);
143: v.setLabel(maxVertexLabel++);
144: }
145:
146: public boolean containsVertex(VertexType v) {
147: for (VertexType existingVertex : vertexList) {
148: if (v == existingVertex)
149: return true;
150: }
151: return false;
152: }
153:
154: public EdgeType createEdge(VertexType source, VertexType target) {
155: EdgeType edge = allocateEdge(source, target);
156: edgeList.add(edge);
157: source.addOutgoingEdge(edge);
158: target.addIncomingEdge(edge);
159: edge.setLabel(maxEdgeLabel++);
160: return edge;
161: }
162:
163: public EdgeType lookupEdge(VertexType source, VertexType target) {
164: Iterator<EdgeType> i = outgoingEdgeIterator(source);
165: while (i.hasNext()) {
166: EdgeType edge = i.next();
167: if (edge.getTarget() == target)
168: return edge;
169: }
170: return null;
171: }
172:
173: public int getNumVertexLabels() {
174: return maxVertexLabel;
175: }
176:
177: public void setNumVertexLabels(int numLabels) {
178: this .maxVertexLabel = numLabels;
179: }
180:
181: public int getNumEdgeLabels() {
182: return maxEdgeLabel;
183: }
184:
185: public void setNumEdgeLabels(int numLabels) {
186: maxEdgeLabel = numLabels;
187: }
188:
189: public void removeEdge(EdgeType edge) {
190: if (!edgeList.remove(edge))
191: throw new IllegalArgumentException(
192: "removing nonexistent edge!");
193: edge.getSource().removeOutgoingEdge(edge);
194: edge.getTarget().removeIncomingEdge(edge);
195: }
196:
197: public void removeVertex(VertexType v) {
198: if (!vertexList.remove(v))
199: throw new IllegalArgumentException(
200: "removing nonexistent vertex!");
201:
202: for (Iterator<EdgeType> i = incomingEdgeIterator(v); i
203: .hasNext();)
204: removeEdge(i.next());
205:
206: for (Iterator<EdgeType> i = outgoingEdgeIterator(v); i
207: .hasNext();)
208: removeEdge(i.next());
209: }
210:
211: public Iterator<EdgeType> outgoingEdgeIterator(VertexType source) {
212: return new OutgoingEdgeIterator<EdgeType, VertexType>(source);
213: }
214:
215: public Iterator<EdgeType> incomingEdgeIterator(VertexType target) {
216: return new IncomingEdgeIterator<EdgeType, VertexType>(target);
217: }
218:
219: public int getNumIncomingEdges(VertexType vertex) {
220: int count = 0;
221: EdgeType e = vertex.firstIncomingEdge;
222: while (e != null) {
223: ++count;
224: e = e.getNextIncomingEdge();
225: }
226: return count;
227: }
228:
229: public int getNumOutgoingEdges(VertexType vertex) {
230: int count = 0;
231: EdgeType e = vertex.firstOutgoingEdge;
232: while (e != null) {
233: ++count;
234: e = e.getNextOutgoingEdge();
235: }
236: return count;
237: }
238:
239: public Iterator<VertexType> successorIterator(
240: final VertexType source) {
241: return new Iterator<VertexType>() {
242: private Iterator<EdgeType> iter = outgoingEdgeIterator(source);
243:
244: public boolean hasNext() {
245: return iter.hasNext();
246: }
247:
248: public VertexType next() {
249: return iter.next().getTarget();
250: }
251:
252: public void remove() {
253: iter.remove();
254: }
255: };
256: }
257:
258: public Iterator<VertexType> predecessorIterator(
259: final VertexType target) {
260: return new Iterator<VertexType>() {
261: private Iterator<EdgeType> iter = incomingEdgeIterator(target);
262:
263: public boolean hasNext() {
264: return iter.hasNext();
265: }
266:
267: public VertexType next() {
268: return iter.next().getSource();
269: }
270:
271: public void remove() {
272: iter.remove();
273: }
274: };
275: }
276:
277: /* ----------------------------------------------------------------------
278: * Downcall methods
279: * ---------------------------------------------------------------------- */
280:
281: protected abstract EdgeType allocateEdge(VertexType source,
282: VertexType target);
283:
284: }
285:
286: // vim:ts=4
|