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.Edge;
026: import org.geotools.graph.structure.Node;
027:
028: /**
029: * Basic implementation of Node.
030: *
031: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
032: *
033: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/basic/BasicNode.java $
034: */
035: public class BasicNode extends BasicGraphable implements Node {
036:
037: /** List of edges incident with the node. */
038: transient private ArrayList m_edges;
039:
040: /**
041: * Constructs a BasicNode.
042: *
043: */
044: public BasicNode() {
045: super ();
046: m_edges = new ArrayList();
047: }
048:
049: /**
050: * Adds an edge to the adjacency list of the node which is an underlying List
051: * implementation. No checking is done on the edge (duplication, looping...),
052: * it is simply added to the list.
053: *
054: * @see Node#add(Edge)
055: */
056: public void add(Edge e) {
057: m_edges.add(e);
058: }
059:
060: /**
061: * @see Node#remove(Edge)
062: */
063: public void remove(Edge e) {
064: m_edges.remove(e);
065: }
066:
067: /**
068: * @see Node#getDegree()
069: */
070: public int getDegree() {
071: //since edges that loop on a node add 2 to the degree
072: // of the node, the degree is not simply the size of the edge
073: // list
074: int degree = 0;
075:
076: for (int i = 0; i < m_edges.size(); i++) {
077: Edge e = (Edge) m_edges.get(i);
078: if (e.getNodeA().equals(this ))
079: degree++;
080: if (e.getNodeB().equals(this ))
081: degree++;
082: }
083:
084: return (degree);
085: }
086:
087: /**
088: * @see Node#getEdge(Node)
089: */
090: public Edge getEdge(Node other) {
091: //must explictley check that the edge has node other, and one node this,
092: // just checking other is not good enough because of loops
093: for (int i = 0; i < m_edges.size(); i++) {
094: Edge e = (Edge) m_edges.get(i);
095: if ((e.getNodeA().equals(this ) && e.getNodeB()
096: .equals(other))
097: || (e.getNodeA().equals(other) && e.getNodeB()
098: .equals(this )))
099: return (e);
100: }
101: return (null);
102: }
103:
104: /**
105: * @see Node#getEdges(Node)
106: */
107: public List getEdges(Node other) {
108: //must explictley check that the edge has node other, and one node this,
109: // just checking other is not good enough because of loops
110: ArrayList edges = new ArrayList();
111: for (int i = 0; i < m_edges.size(); i++) {
112: Edge e = (Edge) m_edges.get(i);
113: if ((e.getNodeA().equals(this ) && e.getNodeB()
114: .equals(other))
115: || (e.getNodeA().equals(other) && e.getNodeB()
116: .equals(this )))
117: edges.add(e);
118: }
119: return (edges);
120: }
121:
122: /**
123: * @see Node#getEdges()
124: */
125: public List getEdges() {
126: return (m_edges);
127: }
128:
129: /**
130: * Returns all nodes that are incident with adjacent edges minus itself. This
131: * iterator is generated by calculating an underlying collection upon each
132: * method call.
133: *
134: * @see org.geotools.graph.structure.Graphable#getRelated()
135: */
136: public Iterator getRelated() {
137: ArrayList related = new ArrayList(m_edges.size());
138: for (int i = 0; i < m_edges.size(); i++) {
139: Edge e = (Edge) m_edges.get(i);
140: related.add(e.getOtherNode(this ));
141: }
142: return (related.iterator());
143: }
144:
145: /**
146: * Overides the default deserialization operation. The edge adjacency list
147: * of a BasicNode is not written out when the node is serialized so it must
148: * be recreated upon deserialization.
149: *
150: * @param in Object input stream containing serialized object.
151: *
152: * @throws IOException
153: * @throws ClassNotFoundException
154: */
155: private void readObject(ObjectInputStream in) throws IOException,
156: ClassNotFoundException {
157:
158: in.defaultReadObject();
159:
160: //recreate edge adjacency list
161: m_edges = new ArrayList();
162: }
163:
164: }
|