001: /*
002: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * - Redistributions of source code must retain the above copyright notice,
008: * this list of conditions and the following disclaimer.
009: * - Redistributions in binary form must reproduce the above copyright notice,
010: * this list of conditions and the following disclaimer in the documentation
011: * and/or other materials provided with the distribution.
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
014: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
015: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
016: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
017: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
018: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
019: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
020: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
021: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
022: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
023: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
024: */
025: package classycle.graph;
026:
027: import java.util.HashSet;
028:
029: /**
030: * Class searching for all (or only the shortest) paths between classes
031: * of a start set and classes of a final set.
032: *
033: * @author Franz-Josef Elmer
034: */
035: public class PathsFinder {
036: private final VertexCondition _startSetCondition;
037: private final VertexCondition _finalSetCondition;
038: private final boolean _shortestPathsOnly;
039: private final boolean _directPathsOnly;
040:
041: /**
042: * Creates an instance for the specified vertex conditions.
043: * @param startSetCondition Condition defining the start set.
044: * @param finalSetCondition Condition defining the final set.
045: * @param shortestPathsOnly if <code>true</code> only the shortest
046: * paths are returned.
047: */
048: public PathsFinder(VertexCondition startSetCondition,
049: VertexCondition finalSetCondition, boolean shortestPathsOnly) {
050: this (startSetCondition, finalSetCondition, shortestPathsOnly,
051: false);
052: }
053:
054: /**
055: * Creates an instance for the specified vertex conditions.
056: * @param startSetCondition Condition defining the start set.
057: * @param finalSetCondition Condition defining the final set.
058: * @param shortestPathsOnly if <code>true</code> only the shortest
059: * paths are returned.
060: * @param directPathsOnly if <code>true</code> only paths of length 1
061: * are returned.
062: */
063: public PathsFinder(VertexCondition startSetCondition,
064: VertexCondition finalSetCondition,
065: boolean shortestPathsOnly, boolean directPathsOnly) {
066: _startSetCondition = startSetCondition;
067: _finalSetCondition = finalSetCondition;
068: _shortestPathsOnly = shortestPathsOnly;
069: _directPathsOnly = directPathsOnly;
070: }
071:
072: public VertexCondition getFinalSetCondition() {
073: return _finalSetCondition;
074: }
075:
076: public boolean isShortestPathsOnly() {
077: return _shortestPathsOnly;
078: }
079:
080: public VertexCondition getStartSetCondition() {
081: return _startSetCondition;
082: }
083:
084: /**
085: * Finds all paths from the specified start vertices to the vertices
086: * fullfilling the specified condition.
087: * @param graph Complete graph.
088: * @return All vertices including start and end vertices defining the
089: * subgraph with all paths.
090: */
091: public AtomicVertex[] findPaths(AtomicVertex[] graph) {
092: prepareGraph(graph);
093: HashSet pathVertices = new HashSet();
094: HashSet currentPath = new HashSet();
095: for (int i = 0; i < graph.length; i++) {
096: AtomicVertex vertex = graph[i];
097: if (_startSetCondition.isFulfilled(vertex)) {
098: if (_directPathsOnly) {
099: findDirectPaths(vertex, pathVertices);
100: } else {
101: prepareIfFinal(vertex);
102: int pathLength = calculateShortestPath(vertex,
103: currentPath);
104: if (pathLength < Integer.MAX_VALUE) {
105: vertex.setOrder(pathLength);
106: followPaths(vertex, pathVertices);
107: }
108: }
109: }
110: }
111: return (AtomicVertex[]) pathVertices
112: .toArray(new AtomicVertex[pathVertices.size()]);
113: }
114:
115: private void findDirectPaths(AtomicVertex vertex,
116: HashSet pathVertices) {
117: if (_finalSetCondition.isFulfilled(vertex)) {
118: pathVertices.add(vertex);
119: } else {
120: for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
121: Vertex headVertex = vertex.getHeadVertex(i);
122: if (_finalSetCondition.isFulfilled(headVertex)) {
123: pathVertices.add(vertex);
124: pathVertices.add(headVertex);
125: }
126: }
127: }
128: }
129:
130: private void prepareGraph(AtomicVertex[] graph) {
131: for (int i = 0; i < graph.length; i++) {
132: AtomicVertex vertex = graph[i];
133: prepareVertex(vertex);
134: for (int j = 0, n = vertex.getNumberOfOutgoingArcs(); j < n; j++) {
135: prepareVertex((AtomicVertex) vertex.getHeadVertex(j));
136: }
137: }
138: }
139:
140: private void prepareVertex(AtomicVertex vertex) {
141: vertex.reset();
142: vertex.setOrder(Integer.MAX_VALUE);
143: if (_startSetCondition.isFulfilled(vertex)) {
144: vertex.visit();
145: }
146: }
147:
148: private int calculateShortestPath(AtomicVertex vertex,
149: HashSet currentPath) {
150: currentPath.add(vertex);
151: int shortestPath = Integer.MAX_VALUE;
152: for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
153: AtomicVertex nextVertex = (AtomicVertex) vertex
154: .getHeadVertex(i);
155: prepareIfFinal(nextVertex);
156: int pathLength = _startSetCondition.isFulfilled(nextVertex) ? Integer.MAX_VALUE
157: : nextVertex.getOrder();
158: if (!currentPath.contains(nextVertex)
159: && !nextVertex.isVisited()) {
160: pathLength = calculateShortestPath(nextVertex,
161: currentPath);
162: nextVertex.setOrder(pathLength);
163: nextVertex.visit();
164: }
165: shortestPath = Math.min(shortestPath, pathLength);
166: }
167: currentPath.remove(vertex);
168: if (shortestPath < Integer.MAX_VALUE) {
169: shortestPath++;
170: }
171: return shortestPath;
172: }
173:
174: private void prepareIfFinal(AtomicVertex vertex) {
175: if (_finalSetCondition.isFulfilled(vertex)) {
176: vertex.visit();
177: vertex.setOrder(0);
178: }
179: }
180:
181: private void followPaths(AtomicVertex vertex, HashSet pathVertices) {
182: pathVertices.add(vertex);
183: int shortestPathLength = vertex.getOrder() - 1;
184: for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
185: AtomicVertex nextVertex = (AtomicVertex) vertex
186: .getHeadVertex(i);
187: int pathLength = nextVertex.getOrder();
188: if (pathLength < Integer.MAX_VALUE
189: && !pathVertices.contains(nextVertex)) {
190: if (!_shortestPathsOnly
191: || pathLength == shortestPathLength) {
192: pathVertices.add(nextVertex);
193: if (pathLength > 0) {
194: followPaths(nextVertex, pathVertices);
195: }
196: }
197: }
198: }
199: }
200:
201: // private int search(AtomicVertex vertex, HashSet currentPath,
202: // HashSet pathVertices)
203: // {
204: // currentPath.add(vertex);
205: // boolean found = false;
206: // int shortestPath = Integer.MAX_VALUE;
207: // for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
208: // {
209: // AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
210: // int pathLength = nextVertex.getOrder();
211: // if (!nextVertex.isVisited() && !currentPath.contains(nextVertex))
212: // {
213: // pathLength = search(nextVertex, currentPath, pathVertices);
214: // nextVertex.setOrder(pathLength);
215: // nextVertex.visit();
216: // }
217: // shortestPath = Math.min(shortestPath, pathLength);
218: // }
219: // for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
220: // {
221: // AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
222: // int pathLength = nextVertex.getOrder();
223: // if (pathLength < Integer.MAX_VALUE)
224: // {
225: // if (!_shortestPathsOnly || pathLength == shortestPath)
226: // {
227: // pathVertices.add(nextVertex);
228: // }
229: // }
230: // }
231: // currentPath.remove(vertex);
232: // if (shortestPath < Integer.MAX_VALUE)
233: // {
234: // shortestPath++;
235: // }
236: // return shortestPath;
237: // }
238:
239: }
|