1 25 package classycle.graph; 26 27 import java.util.HashSet ; 28 29 30 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 50 public PathsFinder(VertexCondition startSetCondition, 51 VertexCondition finalSetCondition, 52 boolean shortestPathsOnly) 53 { 54 this(startSetCondition, finalSetCondition, shortestPathsOnly, false); 55 } 56 57 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 99 public AtomicVertex[] findPaths(AtomicVertex[] graph) 100 { 101 prepareGraph(graph); 102 HashSet pathVertices = new HashSet (); 103 HashSet currentPath = new HashSet (); 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 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 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 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 265 } 266 | Popular Tags |