001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm; 033 034import java.util.*; 035 036import org.graphstream.graph.Edge; 037import org.graphstream.graph.Graph; 038import org.graphstream.graph.Node; 039import org.graphstream.graph.Path; 040import org.graphstream.stream.SinkAdapter; 041 042/** 043 * All-pair shortest paths lengths. 044 * 045 * <p> 046 * This class implements the Floyd-Warshall all pair shortest path algorithm 047 * where the shortest path from any node to any destination in a given weighted 048 * graph (with positive or negative edge weights) is performed. 049 * </p> 050 * <p> 051 * The computational complexity is O(n^3), this may seems a very large, however 052 * this algorithm may perform better than running several Dijkstra on all node 053 * pairs of the graph (that would be of complexity O(n^2 log(n))) when the graph 054 * becomes dense. 055 * </p> 056 * <p> 057 * Note that all the possible paths are not explicitly computed and stored. 058 * Instead, the weight is computed and a data structure similar to network 059 * routing tables is created directly on the graph. This allows a linear 060 * reconstruction of the wanted paths, on demand, minimizing the memory 061 * consumption. 062 * </p> 063 * <p> 064 * For each node of the graph, a {@link org.graphstream.algorithm.APSP.APSPInfo} attribute is stored. The name of 065 * this attribute is {@link org.graphstream.algorithm.APSP.APSPInfo#ATTRIBUTE_NAME}. 066 * </p> 067 * <h2>Usage</h2> 068 * <p> 069 * The implementation of this algorithm is made with two main classes that 070 * reflect the two main steps of the algorithm that are: 071 * </p> 072 * <ol> 073 * <li>compute pairwise weights for all nodes;</li> 074 * <li>retrieve actual paths from some given sources to some given destinations. 075 * </li> 076 * </ol> 077 * 078 * <p> 079 * For the first step (the real shortest path computation) you need to create an 080 * APSP object with 3 parameters: 081 * </p> 082 * 083 * <ul> 084 * <li>a reference to the graph to be computed;</li> 085 * <li>a string that indicates the name of the attribute to consider for the 086 * weighting;</li> 087 * <li>a boolean that indicates whether the computation considers edges 088 * direction or not.</li> 089 * </ul> 090 * 091 * <p> 092 * Those 3 parameters can be set in a ran in the constructor 093 * {@link #APSP(Graph,String,boolean)} or by using separated setters (see example 094 * below). 095 * </p> 096 * <p> 097 * Then the actual computation takes place by calling the {@link #compute()} method 098 * which is implemented from the "Algorithm" interface. This method actually 099 * does the computation. 100 * </p> 101 * <p> 102 * Secondly, when the weights are computed, one can retrieve paths with the help 103 * of another class: "APSPInfo". Such object are stored in each node and hold 104 * routing tables that can help rebuild shortest paths. 105 * </p> 106 * <p> 107 * Retrieving an "APSPInfo" instance from a node is done for instance for a 108 * node of id "F", like this:: 109 * </p> 110 * 111 * <pre> 112 * APSPInfo info = graph.getNode("F").getAttribute(APSPInfo.ATTRIBUTE_NAME); 113 * </pre> 114 * <p> 115 * then the shortest path from a "F" to another node (say "A") is given by:: 116 * </p> 117 * 118 * <pre> 119 * info.getShortestPathTo("A") 120 * </pre> 121 * 122 * 123 * <h2>Example</h2> 124 * 125 * <pre> 126 * import java.io.ByteArrayInputStream; 127 * import java.io.IOException; 128 * 129 * import org.graphstream.algorithm.APSP; 130 * import org.graphstream.algorithm.APSP.APSPInfo; 131 * import org.graphstream.graph.Graph; 132 * import org.graphstream.graph.implementations.DefaultGraph; 133 * import org.graphstream.stream.file.FileSourceDGS; 134 * 135 * public class APSPTest { 136 * 137 * // B-(1)-C 138 * // / \ 139 * // (1) (10) 140 * // / \ 141 * // A F 142 * // \ / 143 * // (1) (1) 144 * // \ / 145 * // D-(1)-E 146 * 147 * static String my_graph = "DGS004\n" 148 * + "my 0 0\n" 149 * + "an A \n" 150 * + "an B \n" 151 * + "an C \n" 152 * + "an D \n" 153 * + "an E \n" 154 * + "an F \n" 155 * + "ae AB A B weight:1 \n" 156 * + "ae AD A D weight:1 \n" 157 * + "ae BC B C weight:1 \n" 158 * + "ae CF C F weight:10 \n" 159 * + "ae DE D E weight:1 \n" 160 * + "ae EF E F weight:1 \n"; 161 * 162 * public static void main(String[] args) throws IOException { 163 * Graph graph = new DefaultGraph("APSP Test"); 164 * ByteArrayInputStream bs = new ByteArrayInputStream(my_graph.getBytes()); 165 * 166 * FileSourceDGS source = new FileSourceDGS(); 167 * source.addSink(graph); 168 * source.readAll(bs); 169 * 170 * APSP apsp = new APSP(); 171 * apsp.init(graph); // registering apsp as a sink for the graph 172 * apsp.setDirected(false); // undirected graph 173 * apsp.setWeightAttributeName("weight"); // ensure that the attribute name 174 * // used is "weight" 175 * apsp.compute(); // the method that actually computes shortest paths 176 * 177 * APSPInfo info = graph.getNode("F") 178 * .getAttribute(APSPInfo.ATTRIBUTE_NAME); 179 * System.out.println(info.getShortestPathTo("A")); 180 * } 181 * } 182 * </pre> 183 * 184 * <h2>Other Features</h2> 185 * 186 * <h3>Digraphs</h3> 187 * <p> 188 * This algorithm can use directed graphs and only compute paths according to 189 * this direction. You can choose to ignore edge orientation by calling 190 * {@link #setDirected(boolean)} method with "false" as value (or use the 191 * appropriate constructor). 192 * </p> 193 * 194 * 195 * <h2>Shortest Paths with weighted edges</2> 196 * <p> 197 * You can also specify that edges have "weights" or "importance" that value 198 * them. You store these values as attributes on the edges. The default name for 199 * these attributes is "weight" but you can specify it using the 200 * {@link #setWeightAttributeName(String)} method (or by using the appropriate 201 * constructor). The weight attribute must contain an object that implements 202 * java.lang.Number. 203 * </p> 204 * 205 * <h2>How shortest paths are stored in the graph?</h2> 206 * <p> 207 * All the shortest paths are not literally stored in the graph because it would 208 * require to much memory to do so. Instead, only useful data, allowing the fast 209 * reconstruction of any path, is stored. The storage approach is alike network 210 * routing tables where each node maintains a list of all possible targets 211 * linked with the next hop neighbor to go through. 212 * </p> 213 * <p> 214 * Technically, on each node, for each target, we only store the target node 215 * name and if the path is made of more than one edge, one "pass-by" node. As 216 * all shortest path that is made of more than one edge is necessarily made of 217 * two other shortest paths, it is easy to reconstruct a shortest path between 218 * two arbitrary nodes knowing only a pass-by node. This approach still stores a 219 * lot of data on the graph, however far less than if we stored complete paths. 220 * </p> 221 * 222 * @complexity O(n^3) with n the number of nodes. 223 * 224 * @reference Floyd, Robert W. "Algorithm 97: Shortest Path". Communications of 225 * the ACM 5 (6): 345. doi:10.1145/367766.368168. 1962. 226 * @reference Warshall, Stephen. "A theorem on Boolean matrices". Journal of the 227 * ACM 9 (1): 11–12. doi:10.1145/321105.321107. 1962. 228 * 229 */ 230public class APSP extends SinkAdapter implements Algorithm { 231 // Attribute 232 233 /** 234 * The graph to use. 235 */ 236 protected Graph graph; 237 238 /** 239 * Does the graph changed between two calls to {@link #compute()}?. 240 */ 241 protected boolean graphChanged = false; 242 243 /** 244 * If false, do not take edge orientation into account. 245 */ 246 protected boolean directed = true; 247 248 /** 249 * Name of the attribute on each edge indicating the weight of the edge. 250 * This attribute must contain a descendant of Number. 251 */ 252 protected String weightAttributeName; 253 254 protected Progress progress = null; 255 256 // Construction 257 258 public APSP() { 259 this(null); 260 } 261 262 /** 263 * New APSP algorithm working on the given graph. The edge weight attribute 264 * name by default is "weight" and edge orientation is taken into account. 265 * 266 * @param graph 267 * The graph to use. 268 */ 269 public APSP(Graph graph) { 270 this(graph, "weight", true); 271 } 272 273 /** 274 * New APSP algorithm working on the given graph. To fetch edges importance, 275 * the algorithm use the given string as attribute name for edge weights. 276 * Weights must be a descendant of Number. 277 * 278 * @param graph 279 * The graph to use. 280 * @param weightAttributeName 281 * The edge weight attribute name. 282 * @param directed 283 * If false, edge orientation is ignored. 284 */ 285 public APSP(Graph graph, String weightAttributeName, boolean directed) { 286 this.graph = graph; 287 this.weightAttributeName = weightAttributeName; 288 this.directed = directed; 289 290 init(graph); 291 } 292 293 // Access 294 295 /** 296 * True if the algorithm must take edge orientation into account. 297 * 298 * @return True if directed. 299 */ 300 public boolean isDirected() { 301 return directed; 302 } 303 304 /** 305 * The name of the attribute to use for retrieving edge weights. 306 * 307 * @return An attribute name. 308 */ 309 public String getWeightAttributeName() { 310 return weightAttributeName; 311 } 312 313 /** 314 * Access to the working graph. 315 * 316 * @return graph being used 317 */ 318 public Graph getGraph() { 319 return graph; 320 } 321 322 // Commands 323 324 /** 325 * Choose to use or ignore edge orientation. 326 * 327 * @param on 328 * If true edge orientation is used.b 329 */ 330 public void setDirected(boolean on) { 331 directed = on; 332 } 333 334 /** 335 * Specify an interface to call in order to indicate the algorithm progress. 336 * Pass null to remove the progress indicator. The progress indicator will 337 * be called regularly to indicate the computation progress. 338 */ 339 public void registerProgressIndicator(Progress progress) { 340 this.progress = progress; 341 } 342 343 /** 344 * Choose the name of the attribute used to retrieve edge weights. Edge 345 * weights attribute must contain a value that inherit Number. 346 * 347 * @param name 348 * The attribute name. 349 */ 350 public void setWeightAttributeName(String name) { 351 weightAttributeName = name; 352 } 353 354 /** 355 * @see Algorithm#init(Graph) 356 */ 357 public void init(Graph graph) { 358 if (this.graph != null) 359 this.graph.removeSink(this); 360 361 this.graph = graph; 362 363 if (this.graph != null){ 364 graphChanged = true; 365 this.graph.addSink(this); 366 } 367 } 368 369 /** 370 * Run the APSP computation. When finished, the graph is equipped with 371 * specific attributes of type 372 * {@link org.graphstream.algorithm.APSP.APSPInfo}. These attributes contain 373 * a map of length toward each other attainable node. The attribute name is 374 * given by {@link org.graphstream.algorithm.APSP.APSPInfo#ATTRIBUTE_NAME}. 375 * 376 * @complexity O(n^3) where n is the number of nodes in the graph. 377 */ 378 public void compute() { 379 if (graphChanged) { 380 // Make a list of all nodes, and equip them with APSP informations. 381 // The APSPInfo constructor add in each info item all the paths from 382 // the node to all its neighbour. It set the distance to 1 if there 383 // are no weights on edges. 384 385 ArrayList<Node> nodeList = new ArrayList<Node>(); 386 387 for (Node node : graph) { 388 node.addAttribute(APSPInfo.ATTRIBUTE_NAME, new APSPInfo(node, 389 weightAttributeName, directed)); 390 nodeList.add(node); 391 } 392 393 // The Floyd-Warshall algorithm. You can easily see it is in O(n^3).. 394 395 // int z = 0; 396 double prog = 0; 397 double max = nodeList.size(); 398 max *= max; 399 400 for (Node k : nodeList) { 401 for (Node i : nodeList) { 402 for (Node j : nodeList) { 403 APSPInfo I = (APSPInfo) i.getAttribute( 404 APSPInfo.ATTRIBUTE_NAME, APSPInfo.class); 405 APSPInfo J = (APSPInfo) j.getAttribute( 406 APSPInfo.ATTRIBUTE_NAME, APSPInfo.class); 407 APSPInfo K = (APSPInfo) k.getAttribute( 408 APSPInfo.ATTRIBUTE_NAME, APSPInfo.class); 409 410 double Dij = I.getLengthTo(J.source.getId()); 411 double Dik = I.getLengthTo(K.source.getId()); 412 double Dkj = K.getLengthTo(J.source.getId()); 413 414 // Take into account non-existing paths. 415 416 if (Dik >= 0 && Dkj >= 0) { 417 double sum = Dik + Dkj; 418 419 if (Dij >= 0) { 420 if (sum < Dij) { 421 I.setLengthTo(J, sum, K); 422 } 423 } else { 424 I.setLengthTo(J, sum, K); 425 } 426 } 427 } 428 429 if (progress != null) 430 progress.progress(prog / max); 431 432 prog += 1; 433 } 434 435 // z++; 436 // System.err.printf( "%3.2f%%%n", (z/((double)n))*100 ); 437 } 438 } 439 440 graphChanged = false; 441 } 442 443 /** 444 * Information stored on each node of the graph giving the length of the 445 * shortest paths toward each other node. 446 */ 447 public static class APSPInfo { 448 public static final String ATTRIBUTE_NAME = "APSPInfo"; 449 450 /** 451 * The start node name. This information is stored inside this node. 452 */ 453 public Node source; 454 455 /** 456 * Maximum number of hops to attain another node in the graph from the 457 * "from" node. 458 * XXX this is the maximum value seen during compute not the maximum shortest path XXX 459 */ 460 public double maxLength = Double.MIN_VALUE; 461 462 /** 463 * Minimum number of hops to attain another node in the graph from the 464 * "from" node. 465 * XXX this is the minimum value seen during compute not the minimum shortest path XXX 466 */ 467 public double minLength = Double.MAX_VALUE; 468 469 /** 470 * Shortest paths toward all other accessible nodes. 471 */ 472 public HashMap<String, TargetPath> targets = new HashMap<String, TargetPath>(); 473 474 /** 475 * Create the new information and put in it all the paths between this 476 * node and all its direct neighbours. 477 * 478 * @param node 479 * The node to start from. 480 * @param weightAttributeName 481 * The key used to retrieve the weight attributes of edges. 482 * This attribute but store a value that inherit Number. 483 * @param directed 484 * If false, the edge orientation is not taken into account. 485 */ 486 public APSPInfo(Node node, String weightAttributeName, boolean directed) { 487 double weight = 1; 488 Iterable<? extends Edge> edges = node.getLeavingEdgeSet(); 489 490 source = node; 491 492 if (!directed) 493 edges = node.getEdgeSet(); 494 495 for (Edge edge : edges) { 496 Node other = edge.getOpposite(node); 497 498 if (edge.hasAttribute(weightAttributeName)) 499 weight = edge.getNumber(weightAttributeName); 500 501 targets.put(other.getId(), new TargetPath(other, weight, null)); 502 } 503 } 504 505 /** 506 * The node represented by this APSP information. 507 * 508 * @return A node identifier. 509 */ 510 public String getNodeId() { 511 return source.getId(); 512 } 513 514 /** 515 * Minimum distance between this node and another. This returns -1 if 516 * there is no path stored yet between these two nodes. 517 * 518 * @param other 519 * The other node identifier. 520 * @return The distance or -1 if no path is stored yet between the two 521 * nodes. 522 */ 523 public double getLengthTo(String other) { 524 if (targets.containsKey(other)) 525 return targets.get(other).distance; 526 527 return -1; 528 } 529 530 /** 531 * The minimum distance between this node and another. 532 * XXX this is the minimum value seen during compute not the minimum shortest path XXX 533 * 534 * @return A distance. 535 */ 536 public double getMinimumLength() { 537 return minLength; 538 } 539 540 /** 541 * The maximum distance between this node and another. 542 * XXX this is the maximum value seen during compute not the maximum shortest path XXX 543 * 544 * @return A distance. 545 */ 546 public double getMaximumLength() { 547 return maxLength; 548 } 549 550 /** 551 * Add or change the length between this node and another and update the 552 * minimum and maximum lengths seen so far. 553 * 554 * @param other 555 * The other node APSP info. 556 * @param length 557 * The new minimum path lengths between these nodes. 558 */ 559 public void setLengthTo(APSPInfo other, double length, APSPInfo passBy) { 560 targets.put(other.source.getId(), new TargetPath(other.source, 561 length, passBy)); 562 563 if (length < minLength) 564 minLength = length; 565 566 if (length > maxLength) 567 maxLength = length; 568 } 569 570 public Path getShortestPathTo(String other) { 571 TargetPath tpath = targets.get(other); 572 573 // XXX Probably a bug here in the Path class usage. 574 // TODO update this to create an edge path to be compatible with 575 // multi-graphs. 576 577 if (tpath != null) { 578 Path path = new Path(); // XXX use the Path object directly. 579 ArrayList<Node> nodePath = new ArrayList<Node>(); 580 581 nodePath.add(source); 582 nodePath.add(tpath.target); 583 584 // Recursively build the path between the source and target node 585 // by exploring pass-by nodes. 586 587 expandPath(1, this, tpath, nodePath); 588 589 // Build a Path object. 590 591 for (int i = 0; i < nodePath.size() - 1; ++i) { 592 // XXX XXX complicated ? 593 594 path.add( 595 nodePath.get(i), 596 nodePath.get(i).getEdgeToward( 597 nodePath.get(i + 1).getId())); 598 } 599 600 return path; 601 } 602 603 return null; 604 } 605 606 protected int expandPath(int pos, APSPInfo source, TargetPath path, 607 ArrayList<Node> nodePath) { 608 // result = will contain the expanded path. 609 // source = A. 610 // path.passBy = X. 611 // path.target = B. 612 // pos = position of insertion of X inside result. 613 614 if (path.passBy != null) { 615 // We want to insert X between A and B. 616 617 nodePath.add(pos, path.passBy.source); 618 619 // We build paths between A and X and between X and B. 620 621 TargetPath path1 = source.targets.get(path.passBy.source 622 .getId()); // path from A -> X 623 TargetPath path2 = path.passBy.targets.get(path.target.getId()); 624 // path from X -> B 625 626 // Now we recurse the path expansion. 627 628 int added1 = expandPath(pos, source, path1, nodePath); 629 int added2 = expandPath(pos + 1 + added1, path.passBy, path2, 630 nodePath); 631 632 // Return the number of elements added at pos. 633 634 return added1 + added2 + 1; 635 } else { 636 // These is no more intermediary node X, stop the recursion. 637 638 return 0; 639 } 640 } 641 } 642 643 /** 644 * Description of a path to a target node. 645 * 646 * <p> 647 * This class is made to be used by the APSPInfo class, which references a 648 * source node. This class describes a target node, the length of the 649 * shortest path to it and, if the path is made of more than only one edge, 650 * an intermediary node (pass-by), used to reconstruct recursively the 651 * shortest path. 652 * </p> 653 * 654 * <p> 655 * This representation avoids to store each node of each shortest path, 656 * since this would consume a too large memory area. This way, a shortest 657 * path is stored at constant size (this is possible since we computed all 658 * the shortest paths and, knowing that a path of more than one edge is 659 * always made of the sum of two shortest paths, and knowing only one 660 * "pass-by" node in the shortest path, it is possible to rebuild it). 661 * </p> 662 */ 663 public static class TargetPath { 664 /** 665 * A distant other node. 666 */ 667 public Node target; 668 669 /** 670 * The distance to this other node. 671 */ 672 public double distance; 673 674 /** 675 * An intermediary other node on the minimum path to the other node. 676 * Used to reconstruct the path between two nodes. 677 */ 678 public APSPInfo passBy; 679 680 public TargetPath(Node other, double distance, APSPInfo passBy) { 681 this.target = other; 682 this.distance = distance; 683 this.passBy = passBy; 684 } 685 } 686 687 // Sink implementation 688 689 @Override 690 public void nodeAdded(String graphId, long timeId, String nodeId) { 691 graphChanged = true; 692 } 693 694 @Override 695 public void nodeRemoved(String graphId, long timeId, String nodeId) { 696 graphChanged = true; 697 } 698 699 @Override 700 public void edgeAdded(String graphId, long timeId, String edgeId, 701 String fromNodeId, String toNodeId, boolean directed) { 702 graphChanged = true; 703 } 704 705 @Override 706 public void edgeRemoved(String graphId, long timeId, String edgeId) { 707 graphChanged = true; 708 } 709 710 @Override 711 public void graphCleared(String graphId, long timeId) { 712 graphChanged = true; 713 } 714 715 @Override 716 public void edgeAttributeAdded(String graphId, long timeId, String edgeId, 717 String attribute, Object value) { 718 if (attribute.equals(weightAttributeName)) { 719 graphChanged = true; 720 } 721 } 722 723 @Override 724 public void edgeAttributeChanged(String graphId, long timeId, 725 String edgeId, String attribute, Object oldValue, Object value) { 726 if (attribute.equals(weightAttributeName)) { 727 graphChanged = true; 728 } 729 } 730 731 /** 732 * Interface allowing to be notified of the algorithm progress. 733 */ 734 public interface Progress { 735 /** 736 * Progress of the algorithm. 737 * 738 * @param percent 739 * a value between 0 and 1, 0 meaning 0% and 1 meaning 100%. 740 */ 741 void progress(double percent); 742 } 743}