1 /** 2 * Copyright (c) 2011-2012, JGraph Ltd 3 */ 4 package com.mxgraph.analysis; 5 6 import java.util.ArrayList; 7 import java.util.Arrays; 8 import java.util.HashMap; 9 import java.util.HashSet; 10 import java.util.LinkedList; 11 import java.util.List; 12 import java.util.Map; 13 import java.util.Set; 14 15 import com.mxgraph.costfunction.mxCostFunction; 16 import com.mxgraph.view.mxCellState; 17 import com.mxgraph.view.mxGraph; 18 import com.mxgraph.view.mxGraph.mxICellVisitor; 19 import com.mxgraph.view.mxGraphView; 20 21 /** 22 * Implements a collection of utility methods for traversing the 23 * graph structure. This does not include tree traversal methods. 24 */ 25 public class mxTraversal 26 { 27 28 /** 29 * Implements a recursive depth first search starting from the specified 30 * cell. Process on the cell is performing by the visitor class passed in. 31 * The visitor has access to the current cell and the edge traversed to 32 * find this cell. Every cell is processed once only. 33 * <pre> 34 * mxTraversal.bfs(analysisGraph, startVertex, new mxICellVisitor() 35 * { 36 * public boolean visit(Object vertex, Object edge) 37 * { 38 * // perform your processing on each cell here 39 * return false; 40 * } 41 * }); 42 * </pre> 43 * @param aGraph the graph 44 * @param startVertex 45 * @param visitor 46 */ dfs(mxAnalysisGraph aGraph, Object startVertex, mxICellVisitor visitor)47 public static void dfs(mxAnalysisGraph aGraph, Object startVertex, mxICellVisitor visitor) 48 { 49 dfsRec(aGraph, startVertex, null, new HashSet<Object>(), visitor); 50 } 51 52 /** 53 * Core recursive DFS - for internal use 54 * @param aGraph 55 * @param cell 56 * @param edge 57 * @param seen 58 * @param visitor 59 */ dfsRec(mxAnalysisGraph aGraph, Object cell, Object edge, Set<Object> seen, mxICellVisitor visitor)60 private static void dfsRec(mxAnalysisGraph aGraph, Object cell, Object edge, Set<Object> seen, mxICellVisitor visitor) 61 { 62 if (cell != null) 63 { 64 if (!seen.contains(cell)) 65 { 66 visitor.visit(cell, edge); 67 seen.add(cell); 68 69 final Object[] edges = aGraph.getEdges(cell, null, false, true); 70 final Object[] opposites = aGraph.getOpposites(edges, cell); 71 72 for (int i = 0; i < opposites.length; i++) 73 { 74 dfsRec(aGraph, opposites[i], edges[i], seen, visitor); 75 } 76 } 77 } 78 } 79 80 /** 81 * Implements a recursive breadth first search starting from the specified 82 * cell. Process on the cell is performing by the visitor class passed in. 83 * The visitor has access to the current cell and the edge traversed to 84 * find this cell. Every cell is processed once only. 85 * <pre> 86 * mxTraversal.bfs(analysisGraph, startVertex, new mxICellVisitor() 87 * { 88 * public boolean visit(Object vertex, Object edge) 89 * { 90 * // perform your processing on each cell here 91 * return false; 92 * } 93 * }); 94 * </pre> 95 * @param aGraph the graph 96 * @param startVertex 97 * @param visitor 98 */ bfs(mxAnalysisGraph aGraph, Object startVertex, mxICellVisitor visitor)99 public static void bfs(mxAnalysisGraph aGraph, Object startVertex, mxICellVisitor visitor) 100 { 101 if (aGraph != null && startVertex != null && visitor != null) 102 { 103 Set<Object> queued = new HashSet<Object>(); 104 LinkedList<Object[]> queue = new LinkedList<Object[]>(); 105 Object[] q = { startVertex, null }; 106 queue.addLast(q); 107 queued.add(startVertex); 108 109 bfsRec(aGraph, queued, queue, visitor); 110 } 111 }; 112 113 /** 114 * Core recursive BFS - for internal use 115 * @param aGraph 116 * @param queued 117 * @param queue 118 * @param visitor 119 */ bfsRec(mxAnalysisGraph aGraph, Set<Object> queued, LinkedList<Object[]> queue, mxICellVisitor visitor)120 private static void bfsRec(mxAnalysisGraph aGraph, Set<Object> queued, LinkedList<Object[]> queue, mxICellVisitor visitor) 121 { 122 if (queue.size() > 0) 123 { 124 Object[] q = queue.removeFirst(); 125 Object cell = q[0]; 126 Object incomingEdge = q[1]; 127 128 visitor.visit(cell, incomingEdge); 129 130 final Object[] edges = aGraph.getEdges(cell, null, false, false); 131 132 for (int i = 0; i < edges.length; i++) 133 { 134 Object[] currEdge = { edges[i] }; 135 Object opposite = aGraph.getOpposites(currEdge, cell)[0]; 136 137 if (!queued.contains(opposite)) 138 { 139 Object[] current = { opposite, edges[i] }; 140 queue.addLast(current); 141 queued.add(opposite); 142 } 143 } 144 145 bfsRec(aGraph, queued, queue, visitor); 146 } 147 }; 148 149 /** 150 * Implements the Dijkstra's shortest path from startVertex to endVertex. 151 * Process on the cell is performing by the visitor class passed in. 152 * The visitor has access to the current cell and the edge traversed to 153 * find this cell. Every cell is processed once only. 154 * <pre> 155 * mxTraversal.dijkstra(analysisGraph, startVertex, endVertex, new mxICellVisitor() 156 * { 157 * public boolean visit(Object vertex, Object edge) 158 * { 159 * // perform your processing on each cell here 160 * return false; 161 * } 162 * }); 163 * </pre> 164 * 165 * @param aGraph 166 * @param startVertex 167 * @param endVertex 168 * @param visitor 169 * @throws StructuralException - The current Dijkstra algorithm only works for connected graphs 170 */ dijkstra(mxAnalysisGraph aGraph, Object startVertex, Object endVertex, mxICellVisitor visitor)171 public static void dijkstra(mxAnalysisGraph aGraph, Object startVertex, Object endVertex, mxICellVisitor visitor) 172 throws StructuralException 173 { 174 if (!mxGraphStructure.isConnected(aGraph)) 175 { 176 throw new StructuralException("The current Dijkstra algorithm only works for connected graphs and this graph isn't connected"); 177 } 178 179 Object parent = aGraph.getGraph().getDefaultParent(); 180 Object[] vertexes = aGraph.getChildVertices(parent); 181 int vertexCount = vertexes.length; 182 double[] distances = new double[vertexCount]; 183 // parents[][0] is the traveled vertex 184 // parents[][1] is the traveled outgoing edge 185 Object[][] parents = new Object[vertexCount][2]; 186 ArrayList<Object> vertexList = new ArrayList<Object>(); 187 ArrayList<Object> vertexListStatic = new ArrayList<Object>(); 188 189 for (int i = 0; i < vertexCount; i++) 190 { 191 distances[i] = Integer.MAX_VALUE; 192 vertexList.add((Object) vertexes[i]); 193 vertexListStatic.add((Object) vertexes[i]); 194 } 195 196 distances[vertexListStatic.indexOf(startVertex)] = 0; 197 mxCostFunction costFunction = aGraph.getGenerator().getCostFunction(); 198 mxGraphView view = aGraph.getGraph().getView(); 199 200 while (vertexList.size() > 0) 201 { 202 //find closest vertex 203 double minDistance; 204 Object currVertex; 205 Object closestVertex; 206 currVertex = vertexList.get(0); 207 int currIndex = vertexListStatic.indexOf(currVertex); 208 double currDistance = distances[currIndex]; 209 minDistance = currDistance; 210 closestVertex = currVertex; 211 212 if (vertexList.size() > 1) 213 { 214 for (int i = 1; i < vertexList.size(); i++) 215 { 216 currVertex = vertexList.get(i); 217 currIndex = vertexListStatic.indexOf(currVertex); 218 currDistance = distances[currIndex]; 219 220 if (currDistance < minDistance) 221 { 222 minDistance = currDistance; 223 closestVertex = currVertex; 224 } 225 } 226 } 227 228 // we found the closest vertex 229 vertexList.remove(closestVertex); 230 231 Object currEdge = new Object(); 232 Object[] neighborVertices = aGraph.getOpposites(aGraph.getEdges(closestVertex, null, true, true, false, true), closestVertex, 233 true, true); 234 235 for (int j = 0; j < neighborVertices.length; j++) 236 { 237 Object currNeighbor = neighborVertices[j]; 238 239 if (vertexList.contains(currNeighbor)) 240 { 241 //find edge that connects to the current vertex 242 Object[] neighborEdges = aGraph.getEdges(currNeighbor, null, true, true, false, true); 243 Object connectingEdge = null; 244 245 for (int k = 0; k < neighborEdges.length; k++) 246 { 247 currEdge = neighborEdges[k]; 248 249 if (aGraph.getTerminal(currEdge, true).equals(closestVertex) 250 || aGraph.getTerminal(currEdge, false).equals(closestVertex)) 251 { 252 connectingEdge = currEdge; 253 } 254 } 255 256 // check for new distance 257 int neighborIndex = vertexListStatic.indexOf(currNeighbor); 258 double oldDistance = distances[neighborIndex]; 259 double currEdgeWeight; 260 261 currEdgeWeight = costFunction.getCost(new mxCellState(view, connectingEdge, null)); 262 263 double newDistance = minDistance + currEdgeWeight; 264 265 //final part - updating the structure 266 if (newDistance < oldDistance) 267 { 268 distances[neighborIndex] = newDistance; 269 parents[neighborIndex][0] = closestVertex; 270 parents[neighborIndex][1] = connectingEdge; 271 } 272 } 273 } 274 } 275 276 ArrayList<Object[]> resultList = new ArrayList<Object[]>(); 277 Object currVertex = endVertex; 278 279 while (currVertex != startVertex) 280 { 281 int currIndex = vertexListStatic.indexOf(currVertex); 282 currVertex = parents[currIndex][0]; 283 resultList.add(0, parents[currIndex]); 284 } 285 286 resultList.add(resultList.size(), new Object[] { endVertex, null }); 287 288 for (int i = 0; i < resultList.size(); i++) 289 { 290 visitor.visit(resultList.get(i)[0], resultList.get(i)[1]); 291 } 292 }; 293 294 /** 295 * Implements the Bellman-Ford shortest path from startVertex to all vertices. 296 * 297 * @param aGraph 298 * @param startVertex 299 * @return a List where List(0) is the distance map and List(1) is the parent map. See the example in GraphConfigDialog.java 300 * @throws StructuralException - The Bellman-Ford algorithm only works for graphs without negative cycles 301 */ bellmanFord(mxAnalysisGraph aGraph, Object startVertex)302 public static List<Map<Object, Object>> bellmanFord(mxAnalysisGraph aGraph, Object startVertex) throws StructuralException 303 { 304 mxGraph graph = aGraph.getGraph(); 305 Object[] vertices = aGraph.getChildVertices(graph.getDefaultParent()); 306 Object[] edges = aGraph.getChildEdges(graph.getDefaultParent()); 307 int vertexNum = vertices.length; 308 int edgeNum = edges.length; 309 Map<Object, Object> distanceMap = new HashMap<Object, Object>(); 310 Map<Object, Object> parentMap = new HashMap<Object, Object>(); 311 mxCostFunction costFunction = aGraph.getGenerator().getCostFunction(); 312 mxGraphView view = graph.getView(); 313 314 for (int i = 0; i < vertexNum; i++) 315 { 316 Object currVertex = vertices[i]; 317 distanceMap.put(currVertex, Double.MAX_VALUE); 318 } 319 320 distanceMap.put(startVertex, 0.0); 321 parentMap.put(startVertex, startVertex); 322 323 for (int i = 0; i < vertexNum; i++) 324 { 325 for (int j = 0; j < edgeNum; j++) 326 { 327 Object currEdge = edges[j]; 328 Object source = aGraph.getTerminal(currEdge, true); 329 Object target = aGraph.getTerminal(currEdge, false); 330 331 double dist = (Double) distanceMap.get(source) + costFunction.getCost(new mxCellState(view, currEdge, null)); 332 333 if (dist < (Double) distanceMap.get(target)) 334 { 335 distanceMap.put(target, dist); 336 parentMap.put(target, source); 337 } 338 339 //for undirected graphs, check the reverse direction too 340 if (!mxGraphProperties.isDirected(aGraph.getProperties(), mxGraphProperties.DEFAULT_DIRECTED)) 341 { 342 dist = (Double) distanceMap.get(target) + costFunction.getCost(new mxCellState(view, currEdge, null)); 343 344 if (dist < (Double) distanceMap.get(source)) 345 { 346 distanceMap.put(source, dist); 347 parentMap.put(source, target); 348 } 349 } 350 351 } 352 } 353 354 for (int i = 0; i < edgeNum; i++) 355 { 356 Object currEdge = edges[i]; 357 Object source = aGraph.getTerminal(currEdge, true); 358 Object target = aGraph.getTerminal(currEdge, false); 359 360 double dist = (Double) distanceMap.get(source) + costFunction.getCost(new mxCellState(view, currEdge, null)); 361 362 if (dist < (Double) distanceMap.get(target)) 363 { 364 throw new StructuralException("The graph contains a negative cycle, so Bellman-Ford can't be completed."); 365 } 366 } 367 368 List<Map<Object, Object>> result = new ArrayList<Map<Object, Object>>(); 369 result.add(distanceMap); 370 result.add(parentMap); 371 372 return result; 373 }; 374 375 /** 376 * Implements the Floyd-Roy-Warshall (aka WFI) shortest path algorithm between all vertices. 377 * 378 * @param aGraph 379 * @return an ArrayList where ArrayList(0) is the distance map and List(1) is the path map. See the example in GraphConfigDialog.java 380 * @throws StructuralException - The Floyd-Roy-Warshall algorithm only works for graphs without negative cycles 381 */ floydRoyWarshall(mxAnalysisGraph aGraph)382 public static ArrayList<Object[][]> floydRoyWarshall(mxAnalysisGraph aGraph) throws StructuralException 383 { 384 385 Object[] vertices = aGraph.getChildVertices(aGraph.getGraph().getDefaultParent()); 386 Double[][] dist = new Double[vertices.length][vertices.length]; 387 Object[][] paths = new Object[vertices.length][vertices.length]; 388 Map<Object, Integer> indexMap = new HashMap<Object, Integer>(); 389 390 for (int i = 0; i < vertices.length; i++) 391 { 392 indexMap.put(vertices[i], i); 393 } 394 395 Object[] edges = aGraph.getChildEdges(aGraph.getGraph().getDefaultParent()); 396 dist = initializeWeight(aGraph, vertices, edges, indexMap); 397 398 for (int k = 0; k < vertices.length; k++) 399 { 400 for (int i = 0; i < vertices.length; i++) 401 { 402 for (int j = 0; j < vertices.length; j++) 403 { 404 if (dist[i][j] > dist[i][k] + dist[k][j]) 405 { 406 paths[i][j] = mxGraphStructure.getVertexWithValue(aGraph, k); 407 dist[i][j] = dist[i][k] + dist[k][j]; 408 } 409 } 410 } 411 } 412 413 for (int i = 0; i < dist[0].length; i++) 414 { 415 if ((Double) dist[i][i] < 0) 416 { 417 throw new StructuralException("The graph has negative cycles"); 418 } 419 } 420 421 ArrayList<Object[][]> result = new ArrayList<Object[][]>(); 422 result.add(dist); 423 result.add(paths); 424 return result; 425 }; 426 427 /** 428 * A helper function for the Floyd-Roy-Warshall algorithm - for internal use 429 * @param aGraph 430 * @param nodes 431 * @param edges 432 * @param indexMap 433 * @return 434 */ initializeWeight(mxAnalysisGraph aGraph, Object[] nodes, Object[] edges, Map<Object, Integer> indexMap)435 private static Double[][] initializeWeight(mxAnalysisGraph aGraph, Object[] nodes, Object[] edges, Map<Object, Integer> indexMap) 436 { 437 Double[][] weight = new Double[nodes.length][nodes.length]; 438 439 for (int i = 0; i < nodes.length; i++) 440 { 441 Arrays.fill(weight[i], Double.MAX_VALUE); 442 } 443 444 boolean isDirected = mxGraphProperties.isDirected(aGraph.getProperties(), mxGraphProperties.DEFAULT_DIRECTED); 445 mxCostFunction costFunction = aGraph.getGenerator().getCostFunction(); 446 mxGraphView view = aGraph.getGraph().getView(); 447 448 for (Object currEdge : edges) 449 { 450 Object source = aGraph.getTerminal(currEdge, true); 451 Object target = aGraph.getTerminal(currEdge, false); 452 453 weight[indexMap.get(source)][indexMap.get(target)] = costFunction.getCost(view.getState(currEdge)); 454 455 if (!isDirected) 456 { 457 weight[indexMap.get(target)][indexMap.get(source)] = costFunction.getCost(view.getState(currEdge)); 458 } 459 } 460 461 for (int i = 0; i < nodes.length; i++) 462 { 463 weight[i][i] = 0.0; 464 } 465 466 return weight; 467 }; 468 469 /** 470 * This method helps the user to get the desired data from the result of the Floyd-Roy-Warshall algorithm. 471 * @param aGraph 472 * @param FWIresult - the result of the Floyd-Roy-Warhall algorithm 473 * @param startVertex 474 * @param targetVertex 475 * @return returns the shortest path from <b>startVertex</b> to <b>endVertex</b> 476 * @throws StructuralException - The Floyd-Roy-Warshall algorithm only works for graphs without negative cycles 477 */ getWFIPath(mxAnalysisGraph aGraph, ArrayList<Object[][]> FWIresult, Object startVertex, Object targetVertex)478 public static Object[] getWFIPath(mxAnalysisGraph aGraph, ArrayList<Object[][]> FWIresult, Object startVertex, Object targetVertex) 479 throws StructuralException 480 { 481 Object[][] dist = FWIresult.get(0); 482 Object[][] paths = FWIresult.get(1); 483 ArrayList<Object> result = null; 484 485 if (aGraph == null || paths == null || startVertex == null || targetVertex == null) 486 { 487 throw new IllegalArgumentException(); 488 } 489 490 for (int i = 0; i < dist[0].length; i++) 491 { 492 if ((Double) dist[i][i] < 0) 493 { 494 throw new StructuralException("The graph has negative cycles"); 495 } 496 } 497 498 if (startVertex != targetVertex) 499 { 500 mxCostFunction cf = aGraph.getGenerator().getCostFunction(); 501 mxGraphView view = aGraph.getGraph().getView(); 502 ArrayList<Object> currPath = new ArrayList<Object>(); 503 currPath.add(startVertex); 504 505 while (startVertex != targetVertex) 506 { 507 result = getWFIPathRec(aGraph, paths, startVertex, targetVertex, currPath, cf, view); 508 startVertex = result.get(result.size() - 1); 509 } 510 } 511 512 if (result == null) 513 { 514 result = new ArrayList<Object>(); 515 } 516 517 return result.toArray(); 518 }; 519 520 /** 521 * Helper method for getWFIPath - for internal use 522 * @param aGraph 523 * @param paths 524 * @param startVertex 525 * @param targetVertex 526 * @param currPath 527 * @param cf 528 * @param view 529 * @return 530 * @throws StructuralException 531 */ getWFIPathRec(mxAnalysisGraph aGraph, Object[][] paths, Object startVertex, Object targetVertex, ArrayList<Object> currPath, mxCostFunction cf, mxGraphView view)532 private static ArrayList<Object> getWFIPathRec(mxAnalysisGraph aGraph, Object[][] paths, Object startVertex, Object targetVertex, 533 ArrayList<Object> currPath, mxCostFunction cf, mxGraphView view) throws StructuralException 534 { 535 Double sourceIndexD = (Double) cf.getCost(view.getState(startVertex)); 536 Object[] parents = paths[sourceIndexD.intValue()]; 537 Double targetIndexD = (Double) cf.getCost(view.getState(targetVertex)); 538 int tIndex = targetIndexD.intValue(); 539 540 if (parents[tIndex] != null) 541 { 542 currPath = getWFIPathRec(aGraph, paths, startVertex, parents[tIndex], currPath, cf, view); 543 } 544 else 545 { 546 if (mxGraphStructure.areConnected(aGraph, startVertex, targetVertex) || startVertex == targetVertex) 547 { 548 currPath.add(targetVertex); 549 } 550 else 551 { 552 throw new StructuralException("The two vertices aren't connected"); 553 } 554 } 555 556 return currPath; 557 } 558 }; 559