KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > classycle > graph > PathsFinder


1 /*
2  * Copyright (c) 2003-2006, Franz-Josef Elmer, All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * - Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  * - Redistributions in binary form must reproduce the above copyright notice,
10  * this list of conditions and the following disclaimer in the documentation
11  * and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
14  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
22  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
23  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */

25 package classycle.graph;
26
27 import java.util.HashSet JavaDoc;
28
29
30 /**
31  * Class searching for all (or only the shortest) paths between classes
32  * of a start set and classes of a final set.
33  *
34  * @author Franz-Josef Elmer
35  */

36 public class PathsFinder
37 {
38   private final VertexCondition _startSetCondition;
39   private final VertexCondition _finalSetCondition;
40   private final boolean _shortestPathsOnly;
41   private final boolean _directPathsOnly;
42   
43   /**
44    * Creates an instance for the specified vertex conditions.
45    * @param startSetCondition Condition defining the start set.
46    * @param finalSetCondition Condition defining the final set.
47    * @param shortestPathsOnly if <code>true</code> only the shortest
48    * paths are returned.
49    */

50   public PathsFinder(VertexCondition startSetCondition,
51                      VertexCondition finalSetCondition,
52                      boolean shortestPathsOnly)
53   {
54     this(startSetCondition, finalSetCondition, shortestPathsOnly, false);
55   }
56
57   /**
58    * Creates an instance for the specified vertex conditions.
59    * @param startSetCondition Condition defining the start set.
60    * @param finalSetCondition Condition defining the final set.
61    * @param shortestPathsOnly if <code>true</code> only the shortest
62    * paths are returned.
63    * @param directPathsOnly if <code>true</code> only paths of length 1
64    * are returned.
65    */

66   public PathsFinder(VertexCondition startSetCondition,
67                      VertexCondition finalSetCondition,
68                      boolean shortestPathsOnly,
69                      boolean directPathsOnly)
70   {
71     _startSetCondition = startSetCondition;
72     _finalSetCondition = finalSetCondition;
73     _shortestPathsOnly = shortestPathsOnly;
74     _directPathsOnly = directPathsOnly;
75   }
76
77   public VertexCondition getFinalSetCondition()
78   {
79     return _finalSetCondition;
80   }
81
82   public boolean isShortestPathsOnly()
83   {
84     return _shortestPathsOnly;
85   }
86
87   public VertexCondition getStartSetCondition()
88   {
89     return _startSetCondition;
90   }
91   
92   /**
93    * Finds all paths from the specified start vertices to the vertices
94    * fullfilling the specified condition.
95    * @param graph Complete graph.
96    * @return All vertices including start and end vertices defining the
97    * subgraph with all paths.
98    */

99   public AtomicVertex[] findPaths(AtomicVertex[] graph)
100   {
101     prepareGraph(graph);
102     HashSet JavaDoc pathVertices = new HashSet JavaDoc();
103     HashSet JavaDoc currentPath = new HashSet JavaDoc();
104     for (int i = 0; i < graph.length; i++)
105     {
106       AtomicVertex vertex = graph[i];
107       if (_startSetCondition.isFulfilled(vertex))
108       {
109         if (_directPathsOnly)
110         {
111           findDirectPaths(vertex, pathVertices);
112         } else
113         {
114           prepareIfFinal(vertex);
115           int pathLength = calculateShortestPath(vertex, currentPath);
116           if (pathLength < Integer.MAX_VALUE)
117           {
118             vertex.setOrder(pathLength);
119             followPaths(vertex, pathVertices);
120           }
121         }
122       }
123     }
124     return (AtomicVertex[]) pathVertices.toArray(
125                                   new AtomicVertex[pathVertices.size()]);
126   }
127   
128   private void findDirectPaths(AtomicVertex vertex, HashSet JavaDoc pathVertices)
129   {
130     if (_finalSetCondition.isFulfilled(vertex))
131     {
132       pathVertices.add(vertex);
133     } else
134     {
135       for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
136       {
137         Vertex headVertex = vertex.getHeadVertex(i);
138         if (_finalSetCondition.isFulfilled(headVertex))
139         {
140           pathVertices.add(vertex);
141           pathVertices.add(headVertex);
142         }
143       }
144     }
145   }
146
147   private void prepareGraph(AtomicVertex[] graph)
148   {
149     for (int i = 0; i < graph.length; i++)
150     {
151       AtomicVertex vertex = graph[i];
152       prepareVertex(vertex);
153       for (int j = 0, n = vertex.getNumberOfOutgoingArcs(); j < n; j++)
154       {
155         prepareVertex((AtomicVertex) vertex.getHeadVertex(j));
156       }
157     }
158   }
159
160   private void prepareVertex(AtomicVertex vertex)
161   {
162     vertex.reset();
163     vertex.setOrder(Integer.MAX_VALUE);
164     if (_startSetCondition.isFulfilled(vertex))
165     {
166       vertex.visit();
167     }
168   }
169
170   private int calculateShortestPath(AtomicVertex vertex, HashSet JavaDoc currentPath)
171   {
172     currentPath.add(vertex);
173     int shortestPath = Integer.MAX_VALUE;
174     for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
175     {
176       AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
177       prepareIfFinal(nextVertex);
178       int pathLength = _startSetCondition.isFulfilled(nextVertex)
179                           ? Integer.MAX_VALUE : nextVertex.getOrder();
180       if (!currentPath.contains(nextVertex) && !nextVertex.isVisited())
181       {
182         pathLength = calculateShortestPath(nextVertex, currentPath);
183         nextVertex.setOrder(pathLength);
184         nextVertex.visit();
185       }
186       shortestPath = Math.min(shortestPath, pathLength);
187     }
188     currentPath.remove(vertex);
189     if (shortestPath < Integer.MAX_VALUE)
190     {
191       shortestPath++;
192     }
193     return shortestPath;
194   }
195   
196   private void prepareIfFinal(AtomicVertex vertex)
197   {
198     if (_finalSetCondition.isFulfilled(vertex))
199     {
200       vertex.visit();
201       vertex.setOrder(0);
202     }
203   }
204
205   private void followPaths(AtomicVertex vertex, HashSet JavaDoc pathVertices)
206   {
207     pathVertices.add(vertex);
208     int shortestPathLength = vertex.getOrder() - 1;
209     for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
210     {
211       AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
212       int pathLength = nextVertex.getOrder();
213       if (pathLength < Integer.MAX_VALUE && !pathVertices.contains(nextVertex))
214       {
215         if (!_shortestPathsOnly || pathLength == shortestPathLength)
216         {
217           pathVertices.add(nextVertex);
218           if (pathLength > 0)
219           {
220             followPaths(nextVertex, pathVertices);
221           }
222         }
223       }
224     }
225   }
226
227 // private int search(AtomicVertex vertex, HashSet currentPath,
228
// HashSet pathVertices)
229
// {
230
// currentPath.add(vertex);
231
// boolean found = false;
232
// int shortestPath = Integer.MAX_VALUE;
233
// for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
234
// {
235
// AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
236
// int pathLength = nextVertex.getOrder();
237
// if (!nextVertex.isVisited() && !currentPath.contains(nextVertex))
238
// {
239
// pathLength = search(nextVertex, currentPath, pathVertices);
240
// nextVertex.setOrder(pathLength);
241
// nextVertex.visit();
242
// }
243
// shortestPath = Math.min(shortestPath, pathLength);
244
// }
245
// for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++)
246
// {
247
// AtomicVertex nextVertex = (AtomicVertex) vertex.getHeadVertex(i);
248
// int pathLength = nextVertex.getOrder();
249
// if (pathLength < Integer.MAX_VALUE)
250
// {
251
// if (!_shortestPathsOnly || pathLength == shortestPath)
252
// {
253
// pathVertices.add(nextVertex);
254
// }
255
// }
256
// }
257
// currentPath.remove(vertex);
258
// if (shortestPath < Integer.MAX_VALUE)
259
// {
260
// shortestPath++;
261
// }
262
// return shortestPath;
263
// }
264

265 }
266
Popular Tags