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.Serializable;
020: import java.util.ArrayList;
021: import java.util.Collection;
022: import java.util.Iterator;
023: import java.util.List;
024:
025: import org.geotools.graph.structure.Edge;
026: import org.geotools.graph.structure.Graph;
027: import org.geotools.graph.structure.GraphVisitor;
028: import org.geotools.graph.structure.Graphable;
029: import org.geotools.graph.structure.Node;
030:
031: /**
032: * Basic implemenation of Graph.
033: *
034: * @see Graph
035: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
036: *
037: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/basic/BasicGraph.java $
038: */
039: public class BasicGraph implements Graph, Serializable {
040:
041: /** Nodes belonging to the graph */
042: transient private Collection m_nodes;
043:
044: /** Edges belonging to the graph */
045: transient private Collection m_edges;
046:
047: /**
048: * Constructs an empty graph with edge and node collections uninitialized.
049: * Mainly for serializability purposes.
050: */
051: public BasicGraph() {
052:
053: }
054:
055: /**
056: * Constructs a graph from a collection of nodes and a collection of edges.
057: * The relationships between the nodes (edges) are already assumed to be
058: * formed. Only the references to the node and edge collections are copied,
059: * not the underlying collections themselves.
060: *
061: * @param nodes Collection of nodes to be contained by the graph.
062: * @param edges Collection of edges to be contained by the graph.
063: */
064: public BasicGraph(Collection nodes, Collection edges) {
065: m_nodes = nodes;
066: m_edges = edges;
067: }
068:
069: /**
070: * Sets the node collection of the graph.
071: *
072: * @param nodes Collection of Node objects.
073: */
074: public void setNodes(Collection nodes) {
075: m_nodes = nodes;
076: }
077:
078: /**
079: * @see Graph#getNodes()
080: */
081: public Collection getNodes() {
082: return (m_nodes);
083: }
084:
085: /**
086: * Sets the edge collection for the graph.
087: *
088: * @param edges Collection of Edge objects.
089: */
090: public void setEdges(Collection edges) {
091: m_edges = edges;
092: }
093:
094: /**
095: * @see Graph#getEdges()
096: */
097: public Collection getEdges() {
098: return (m_edges);
099: }
100:
101: /**
102: * @see Graph#queryNodes(GraphVisitor)
103: */
104: public List queryNodes(GraphVisitor visitor) {
105: return (query(getNodes(), visitor));
106: }
107:
108: /**
109: * @see Graph#queryEdges(GraphVisitor)
110: */
111: public List queryEdges(GraphVisitor visitor) {
112: return (query(getEdges(), visitor));
113: }
114:
115: /**
116: * @see Graph#visitNodes(GraphVisitor)
117: */
118: public void visitNodes(GraphVisitor visitor) {
119: visit(m_nodes, visitor);
120: }
121:
122: /**
123: * @see Graph#visitEdges(GraphVisitor)
124: */
125: public void visitEdges(GraphVisitor visitor) {
126: visit(m_edges, visitor);
127: }
128:
129: /**
130: * @see Graph#getNodesOfDegree(int)
131: * @see Node#getDegree()
132: */
133: public List getNodesOfDegree(int n) {
134: final int degree = n;
135:
136: return (queryNodes(new GraphVisitor() {
137: public int visit(Graphable component) {
138: if (((Node) component).getDegree() == degree)
139: return (PASS_AND_CONTINUE);
140: return (FAIL_QUERY);
141: }
142: }));
143: }
144:
145: /**
146: * @see Graph#getVisitedNodes(boolean)
147: */
148: public List getVisitedNodes(boolean visited) {
149: return (getVisited(getNodes(), visited));
150: }
151:
152: /**
153: * @see Graph#getVisitedEdges(boolean)
154: */
155: public List getVisitedEdges(boolean visited) {
156: return (getVisited(getEdges(), visited));
157: }
158:
159: /**
160: * Initializes the nodes in the graph by setting all visited flags to false
161: * and all visited counts to zero.
162: *
163: * @see BasicGraphable#isVisited()
164: * @see BasicGraphable#getCount()
165: */
166: public void initNodes() {
167: for (Iterator itr = m_nodes.iterator(); itr.hasNext();) {
168: Node node = (Node) itr.next();
169: node.setVisited(false);
170: node.setCount(0);
171: }
172: }
173:
174: /**
175: * Initializes the edges in the graph by setting all visited flags to false
176: * and all visited counts to zero.
177: *
178: * @see BasicGraphable#isVisited()
179: * @see BasicGraphable#getCount()
180: */
181: public void initEdges() {
182: for (Iterator itr = m_edges.iterator(); itr.hasNext();) {
183: Edge edge = (Edge) itr.next();
184: edge.setVisited(false);
185: edge.setCount(0);
186: }
187: }
188:
189: /**
190: * Returns the string representation of the graph which is
191: * just the string representation of the edge and node collections.
192: *
193: * @return String represtentaton of graph.
194: */
195: public String toString() {
196: return ("V=" + m_nodes.toString() + "\n" + "E=" + m_edges
197: .toString());
198: }
199:
200: /*
201: * Internal query method.
202: */
203: private List query(Collection components, GraphVisitor visitor) {
204: ArrayList result = new ArrayList();
205:
206: for (Iterator itr = components.iterator(); itr.hasNext();) {
207: Graphable component = (Graphable) itr.next();
208:
209: switch (visitor.visit(component)) {
210: case PASS_AND_CONTINUE:
211: result.add(component);
212: continue;
213:
214: case PASS_AND_STOP:
215: result.add(component);
216: return (result);
217:
218: case FAIL_QUERY:
219: continue;
220: }
221: }
222:
223: return (result);
224: }
225:
226: /*
227: * Internal visit method
228: */
229: private void visit(Collection components, GraphVisitor visitor) {
230: for (Iterator itr = components.iterator(); itr.hasNext();) {
231: visitor.visit((Graphable) itr.next());
232: }
233: }
234:
235: /*
236: * Internal getVisited method.
237: */
238: private List getVisited(Collection components, boolean visited) {
239: final boolean isVisited = visited;
240: return (query(components, new GraphVisitor() {
241: public int visit(Graphable component) {
242: if (component.isVisited() == isVisited)
243: return (PASS_AND_CONTINUE);
244: return (FAIL_QUERY);
245: }
246: }));
247: }
248: }
|