001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.structure.basic;
018:
019: import java.io.IOException;
020: import java.io.ObjectInputStream;
021: import java.util.ArrayList;
022: import java.util.Iterator;
023: import java.util.List;
024:
025: import org.geotools.graph.structure.DirectedEdge;
026: import org.geotools.graph.structure.DirectedNode;
027: import org.geotools.graph.structure.Edge;
028: import org.geotools.graph.structure.Node;
029:
030: /**
031: * Basic implementation of DirectedNode.
032: *
033: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
034: *
035: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/basic/BasicDirectedNode.java $
036: */
037: public class BasicDirectedNode extends BasicGraphable implements
038: DirectedNode {
039:
040: /** In adjacency list **/
041: transient private ArrayList m_in;
042:
043: /** Out adjacecy list **/
044: transient private ArrayList m_out;
045:
046: /**
047: * Constructs a new BasicDirectedNode.
048: */
049: public BasicDirectedNode() {
050: super ();
051: m_in = new ArrayList();
052: m_out = new ArrayList();
053: }
054:
055: /**
056: * Unsupported operation. Directed nodes classify edges as <B>in</B> and
057: * <B>out</B>. addIn(Edge) and addOut(Edge) should be used instead of this
058: * method.
059: *
060: * @throws UnsupportedOperationException
061: *
062: * @see DirectedNode#addIn(DirectedEdge)
063: * @see DirectedNode#addOut(DirectedEdge)
064: *
065: */
066: public void add(Edge e) {
067: throw new UnsupportedOperationException("add(Edge)");
068: }
069:
070: /**
071: * Adds an edge to the <B>in</B> adjacency list of the node which is an
072: * underlying List implementation. No checking is done on the edge
073: * (duplication, looping...), it is simply added to the list. It is also
074: * assumed that the edge being added has the node as its out node.
075: *
076: * @see DirectedNode#addIn(DirectedEdge)
077: * @see DirectedEdge#getOutNode()
078: *
079: */
080: public void addIn(DirectedEdge e) {
081: m_in.add(e);
082: }
083:
084: /**
085: * Adds an edge to the <B>ou</B> adjacency list of the node which is an
086: * underlying List implementation. No checking is done on the edge
087: * (duplication, looping...), it is simply added to the list. It is also
088: * assumed that the edge being added has the node as its in node.
089: *
090: * @see DirectedNode#addOut(DirectedEdge)
091: * @see DirectedEdge#getInNode()
092: *
093: */
094: public void addOut(DirectedEdge e) {
095: m_out.add(e);
096: }
097:
098: /**
099: * Removes the edge from both the in and out adjacency lists.
100: *
101: * @see Node#remove(Edge)
102: */
103: public void remove(Edge e) {
104: m_in.remove(e);
105: m_out.remove(e);
106: }
107:
108: /**
109: * @see DirectedNode#removeIn(DirectedEdge)
110: */
111: public void removeIn(DirectedEdge e) {
112: m_in.remove(e);
113: }
114:
115: /**
116: * @see DirectedNode#removeOut(DirectedEdge)
117: */
118: public void removeOut(DirectedEdge e) {
119: m_out.remove(e);
120: }
121:
122: /**
123: * First searches for an in edge with an out node == this, and in
124: * node == other. If none is found an edge with out node == other, and in
125: * node == this is searched for.
126: *
127: * @see Node#remove(Edge)
128: */
129: public Edge getEdge(Node other) {
130: Edge e = getInEdge((DirectedNode) other);
131: if (e != null)
132: return (e);
133: return (getOutEdge((DirectedNode) other));
134: }
135:
136: /**
137: * @see DirectedNode#getInEdge(DirectedNode)
138: */
139: public Edge getInEdge(DirectedNode other) {
140: //must explictley check that the edge has node other, and one node this,
141: // just checking other is not good enough because of loops
142: for (int i = 0; i < m_in.size(); i++) {
143: DirectedEdge edge = (DirectedEdge) m_in.get(i);
144: if (edge.getInNode().equals(other)
145: && edge.getOutNode().equals(this ))
146: return (edge);
147: }
148: return (null);
149: }
150:
151: /**
152: * @see DirectedNode#getOutEdge(DirectedNode)
153: */
154: public Edge getOutEdge(DirectedNode other) {
155: //must explictley check that the edge has node other, and one node this,
156: // just checking other is not good enough because of loops
157: for (int i = 0; i < m_out.size(); i++) {
158: DirectedEdge edge = (DirectedEdge) m_out.get(i);
159: if (edge.getOutNode().equals(other)
160: && edge.getInNode().equals(this ))
161: return (edge);
162: }
163: return (null);
164: }
165:
166: /**
167: * Returns the combination of both the in and out adjacecy lists.
168: */
169: public List getEdges() {
170: ArrayList edges = new ArrayList();
171: edges.addAll(m_in);
172: edges.addAll(m_out);
173: return (edges);
174: }
175:
176: /**
177: * @see DirectedNode#getInEdges()
178: */
179: public List getInEdges() {
180: return (m_in);
181: }
182:
183: /**
184: * @see DirectedNode#getOutEdges()
185: */
186: public List getOutEdges() {
187: return (m_out);
188: }
189:
190: /**
191: * A combination of the results of getInEdges(Node) and getOutEdges(Node).
192: *
193: * @see Node#getEdges(Node)
194: * @see DirectedNode#getInEdges(DirectedNode)
195: * @see DirectedNode#getOutEdges(DirectedNode)
196: */
197: public List getEdges(Node other) {
198: List edges = getInEdges((DirectedNode) other);
199: edges.addAll(getOutEdges((DirectedNode) other));
200: return (edges);
201: }
202:
203: /**
204: * @see DirectedNode#getInEdges(DirectedNode)
205: */
206: public List getInEdges(DirectedNode other) {
207: ArrayList edges = new ArrayList();
208: for (int i = 0; i < m_in.size(); i++) {
209: DirectedEdge edge = (DirectedEdge) m_in.get(i);
210: if (edge.getInNode().equals(other))
211: edges.add(edge);
212: }
213: return (edges);
214: }
215:
216: /**
217: * @see DirectedNode#getOutEdges(DirectedNode)
218: */
219: public List getOutEdges(DirectedNode other) {
220: ArrayList edges = new ArrayList();
221: for (int i = 0; i < m_out.size(); i++) {
222: DirectedEdge edge = (DirectedEdge) m_out.get(i);
223: if (edge.getOutNode().equals(other))
224: edges.add(edge);
225: }
226: return (edges);
227: }
228:
229: /**
230: * Returns sum of sizes of in and out adjacency lists.
231: *
232: * @see Node#getDegree()
233: */
234: public int getDegree() {
235: return (m_in.size() + m_out.size());
236: }
237:
238: /**
239: * @see DirectedNode#getInDegree()
240: */
241: public int getInDegree() {
242: return (m_in.size());
243: }
244:
245: /**
246: * @see DirectedNode#getOutDegree()
247: */
248: public int getOutDegree() {
249: return (m_out.size());
250: }
251:
252: /**
253: * Returns an iterator over all out nodes of out edges and in nodes of in
254: * edges.
255: *
256: * @see org.geotools.graph.structure.Graphable#getRelated()
257: */
258: public Iterator getRelated() {
259: ArrayList related = new ArrayList(m_out.size() + m_in.size());
260: for (int i = 0; i < m_in.size(); i++) {
261: DirectedEdge e = (DirectedEdge) m_in.get(i);
262: related.add(e.getInNode());
263: }
264:
265: for (int i = 0; i < m_out.size(); i++) {
266: DirectedEdge e = (DirectedEdge) m_out.get(i);
267: related.add(e.getOutNode());
268: }
269: return (related.iterator());
270: }
271:
272: /**
273: * Returns all in nodes of in edges.
274: *
275: * @see org.geotools.graph.structure.DirectedGraphable#getInRelated()
276: */
277: public Iterator getInRelated() {
278: ArrayList related = new ArrayList(m_in.size());
279: for (int i = 0; i < m_in.size(); i++) {
280: DirectedEdge e = (DirectedEdge) m_in.get(i);
281: related.add(e.getInNode());
282: }
283:
284: return (related.iterator());
285: }
286:
287: /**
288: * Returns all out nodes of out edges.
289: *
290: * @see org.geotools.graph.structure.DirectedGraphable#getOutRelated()
291: */
292: public Iterator getOutRelated() {
293: ArrayList related = new ArrayList(m_out.size());
294: for (int i = 0; i < m_out.size(); i++) {
295: DirectedEdge e = (DirectedEdge) m_out.get(i);
296: related.add(e.getOutNode());
297: }
298: return (related.iterator());
299: }
300:
301: /**
302: * Overides the default deserialization operation. The edge adjacency lists
303: * of a BasicDirectedNode is not written out when the node is serialized so
304: * they must be recreated upon deserialization.
305: *
306: * @param in Object input stream containing serialized object.
307: *
308: * @throws IOException
309: * @throws ClassNotFoundException
310: */
311: private void readObject(ObjectInputStream in) throws IOException,
312: ClassNotFoundException {
313:
314: in.defaultReadObject();
315:
316: //recreate edge adjacency lists
317: m_in = new ArrayList();
318: m_out = new ArrayList();
319: }
320: }
|