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.path;
018:
019: import java.util.ArrayList;
020: import java.util.HashMap;
021: import java.util.Iterator;
022: import java.util.List;
023:
024: import org.geotools.graph.structure.GraphVisitor;
025: import org.geotools.graph.structure.Graphable;
026: import org.geotools.graph.structure.Node;
027: import org.geotools.graph.util.IndexedStack;
028:
029: public class ExhaustivePathFinder {
030: public final static int CONTINUE_PATH = 0;
031: public final static int END_PATH_AND_CONTINUE = 1;
032: public final static int END_PATH_AND_STOP = 2;
033: public final static int KILL_PATH = 3;
034:
035: private int m_maxitr;
036: private int m_maxplen;
037:
038: public ExhaustivePathFinder() {
039: this (Integer.MAX_VALUE, Integer.MAX_VALUE);
040: }
041:
042: public ExhaustivePathFinder(int maxitr, int maxplen) {
043: m_maxitr = maxitr;
044: m_maxplen = maxplen;
045: }
046:
047: public Path getPath(Node from, Node to) {
048: final Node dst = to;
049: GraphVisitor visitor = new GraphVisitor() {
050: public int visit(Graphable component) {
051: if (component.equals(dst))
052: return (END_PATH_AND_STOP);
053: return (CONTINUE_PATH);
054: }
055: };
056: List paths = getPaths(from, visitor);
057: if (paths.isEmpty())
058: return (null);
059: return ((Path) paths.get(0));
060: }
061:
062: public List getPaths(Node from, Node to) {
063: final Node dst = to;
064: GraphVisitor visitor = new GraphVisitor() {
065: public int visit(Graphable component) {
066: if (component.equals(dst))
067: return (END_PATH_AND_CONTINUE);
068: return (CONTINUE_PATH);
069: }
070: };
071: return (getPaths(from, visitor));
072: }
073:
074: public List getPaths(Node from, GraphVisitor visitor) {
075: ArrayList paths = new ArrayList();
076:
077: //create a map to maintain iterator state
078: HashMap node2related = new HashMap();
079:
080: //create the stack and place start node on
081: IndexedStack stack = new IndexedStack();
082: stack.push(from);
083:
084: int iterations = 0;
085: O: while (!stack.isEmpty() && (iterations++ < m_maxitr)) {
086: //peek the stack
087: Node top = (Node) stack.peek();
088:
089: switch (visitor.visit(top)) {
090: case END_PATH_AND_CONTINUE:
091: paths.add(new Path(stack));
092: stack.pop();
093: continue;
094:
095: case END_PATH_AND_STOP:
096: paths.add(new Path(stack));
097: break O;
098:
099: case KILL_PATH:
100: stack.pop();
101: continue;
102:
103: case CONTINUE_PATH:
104:
105: }
106:
107: Iterator related = null;
108: if ((related = (Iterator) node2related.get(top)) == null) {
109: related = top.getRelated();
110: node2related.put(top, related);
111: }
112:
113: while (stack.size() < m_maxplen && related.hasNext()) {
114: Node adj = (Node) related.next();
115: if (stack.contains(adj))
116: continue;
117:
118: //push adjacent onto stack, and reset iterator
119: stack.push(adj);
120: node2related.put(adj, adj.getRelated());
121:
122: continue O;
123: }
124:
125: //all adjacent have been processed or are in stack
126: stack.pop();
127: }
128:
129: return (paths);
130: }
131: }
|