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.build.line;
018:
019: import java.util.ArrayList;
020: import java.util.HashMap;
021: import java.util.Iterator;
022: import java.util.List;
023: import java.util.Map;
024:
025: import org.geotools.graph.build.GraphBuilder;
026: import org.geotools.graph.build.GraphGenerator;
027: import org.geotools.graph.structure.Edge;
028: import org.geotools.graph.structure.Graph;
029: import org.geotools.graph.structure.Graphable;
030: import org.geotools.graph.structure.Node;
031: import org.geotools.graph.structure.line.OptXYNode;
032: import org.geotools.graph.structure.opt.OptEdge;
033: import org.geotools.graph.structure.opt.OptNode;
034:
035: import com.vividsolutions.jts.geom.Coordinate;
036: import com.vividsolutions.jts.geom.LineSegment;
037:
038: /**
039: * An implementation of GraphGenerator used to generate an optimized graph
040: * representing a line network. Graphs are generated by supplying the generator
041: * with objects of type LineSegment via the add(Object) method. <BR>
042: * <BR>
043: * For each line segment added, an edge in the graph is created. The builder
044: * records the end coordinates of each line added, and maintains a map of
045: * coordinates to nodes, creating nodes when neccessary.<BR>
046: * <BR>
047: * Edges created by the generator are of type OptBasicEdge.<BR>
048: * Nodes created by the generator are of type OptXYNode. <BR>
049: * <BR>
050: * Since building optimized graphs requires knowing the degree of nodes before
051: * creating them, the physical construction of the graph is delayed until a call
052: * to generate() is made. No component is created with a call to add(Object),
053: * only information about the object is recorded.
054: *
055: * @see org.geotools.graph.structure.opt.OptEdge
056: * @see org.geotools.graph.structure.line.OptXYNode
057: *
058: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
059: *
060: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/build/line/OptLineGraphGenerator.java $
061: */
062: public class OptLineGraphGenerator implements LineGraphGenerator {
063:
064: /** coordinate to node / count **/
065: private HashMap m_coord2count;
066:
067: /** lines added to the network **/
068: private ArrayList m_lines;
069:
070: /** underlying builder **/
071: private GraphBuilder m_builder;
072:
073: /**
074: * Constructs a new OptLineGraphGenerator.
075: */
076: public OptLineGraphGenerator() {
077: m_coord2count = new HashMap();
078: m_lines = new ArrayList();
079: setGraphBuilder(new OptLineGraphBuilder());
080: }
081:
082: /**
083: * Adds a line to the graph. Note that this method returns null since actual
084: * building of the graph components is delayed until generate() is called.
085: *
086: * @param obj A LineSegment object.
087: *
088: * @return null because the actual building of the graph components is delayed
089: * until generate() is called.
090: */
091: public Graphable add(Object obj) {
092: LineSegment line = (LineSegment) obj;
093: Integer count;
094:
095: //update count of first coordinate
096: if ((count = (Integer) m_coord2count.get(line.p0)) == null) {
097: m_coord2count.put(line.p0, new Integer(1));
098: } else
099: m_coord2count.put(line.p0,
100: new Integer(count.intValue() + 1));
101:
102: //update count of second coordinate
103: if ((count = (Integer) m_coord2count.get(line.p1)) == null) {
104: m_coord2count.put(line.p1, new Integer(1));
105: } else
106: m_coord2count.put(line.p1,
107: new Integer(count.intValue() + 1));
108:
109: //hold onto a reference to the line
110: m_lines.add(line);
111:
112: //return null, no componenets created
113: return (null);
114: }
115:
116: /**
117: * Returns the edge which represents a line. This method must be called
118: * after the call to generate(). Note that if the exact same line
119: * has been added to the graph multiple times, then only one of the edges
120: * that represents it will be returned. It is undefined which edge will be
121: * returned.
122: *
123: * @param obj An instance of LineSegment.
124: *
125: * @return Edge that represents the line.
126: *
127: * @see GraphGenerator#get(Object)
128: */
129: public Graphable get(Object obj) {
130: LineSegment line = (LineSegment) obj;
131:
132: Node n1 = (Node) m_coord2count.get(line.p0);
133: Node n2 = (Node) m_coord2count.get(line.p0);
134:
135: return (n1.getEdge(n2));
136:
137: //note: if there are identical lines in the graph then it is undefined
138: //which of them will be returned
139: }
140:
141: /**
142: * Unsupported operation.
143: *
144: * @throws UnsupportedOperationException
145: */
146: public Graphable remove(Object obj) {
147: throw new UnsupportedOperationException(getClass().getName()
148: + "#remove(Object)");
149: }
150:
151: /**
152: * @see GraphGenerator#setGraphBuilder(GraphBuilder)
153: */
154: public void setGraphBuilder(GraphBuilder builder) {
155: m_builder = builder;
156: }
157:
158: /**
159: * @see GraphGenerator#getGraphBuilder()
160: */
161: public GraphBuilder getGraphBuilder() {
162: return (m_builder);
163: }
164:
165: /**
166: * @see GraphGenerator#getGraph()
167: */
168: public Graph getGraph() {
169: return (m_builder.getGraph());
170: }
171:
172: /**
173: * Performs the actual generation of the graph.
174: */
175: public void generate() {
176: generateNodes();
177: generateEdges();
178: }
179:
180: /**
181: * Returns the coordinate to node map. Note that before the call to generate
182: * the map does not contain any nodes.
183: *
184: * @return Coordinate to node map.
185: */
186: public Map getNodeMap() {
187: return (m_coord2count);
188: }
189:
190: /**
191: * Returns the lines added to the graph.
192: *
193: * @return A list of LineSegment objects.
194: */
195: protected List getLines() {
196: return (m_lines);
197: }
198:
199: protected void generateNodes() {
200: //create nodes from coordiante counts
201: for (Iterator itr = m_coord2count.entrySet().iterator(); itr
202: .hasNext();) {
203: Map.Entry entry = (Map.Entry) itr.next();
204: Coordinate coord = (Coordinate) entry.getKey();
205: Integer count = (Integer) entry.getValue();
206:
207: OptXYNode node = (OptXYNode) m_builder.buildNode();
208: node.setDegree(count.intValue());
209: node.setCoordinate(coord);
210:
211: m_builder.addNode(node);
212:
213: entry.setValue(node);
214: }
215: }
216:
217: protected void generateEdges() {
218: //relate nodes
219: for (Iterator itr = m_lines.iterator(); itr.hasNext();) {
220: LineSegment line = (LineSegment) itr.next();
221: generateEdge(line);
222: }
223: }
224:
225: protected Edge generateEdge(LineSegment line) {
226: OptNode n1 = (OptNode) m_coord2count.get(line.p0);
227: OptNode n2 = (OptNode) m_coord2count.get(line.p1);
228:
229: OptEdge edge = (OptEdge) m_builder.buildEdge(n1, n2);
230: m_builder.addEdge(edge);
231:
232: return (edge);
233: }
234:
235: //TODO DOCUMENT ME!
236: public Node getNode(Coordinate c) {
237: return ((Node) m_coord2count.get(c));
238:
239: }
240:
241: public Edge getEdge(Coordinate c1, Coordinate c2) {
242: Node n1 = (Node) m_coord2count.get(c1);
243: Node n2 = (Node) m_coord2count.get(c2);
244:
245: return (n1.getEdge(n2));
246: }
247: }
|