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.ArrayList; 035import java.util.Iterator; 036import java.util.List; 037import java.util.NoSuchElementException; 038import java.util.Stack; 039 040import org.graphstream.algorithm.util.FibonacciHeap; 041import org.graphstream.graph.Edge; 042import org.graphstream.graph.Graph; 043import org.graphstream.graph.Node; 044import org.graphstream.graph.Path; 045 046/** 047 * <p> 048 * Dijkstra's algorithm computes the shortest paths from a given node called 049 * source to all the other nodes in a graph. It produces a shortest path tree 050 * rooted in the source. <b>This algorithm works only for nonnegative 051 * lengths.</b> 052 * </p> 053 * 054 * <p> 055 * This implementation uses internally Fibonacci Heap, a data structure that 056 * makes it run faster for big graphs. 057 * </p> 058 * 059 * <h3>Length of a path</h3> 060 * 061 * <p> 062 * Traditionally the length of a path is defined as the sum of the lengths of 063 * its edges. This implementation allows to take into account also the "lengths" 064 * of the nodes. This is done by a parameter of type {@link Element} passed in 065 * the constructors. 066 * </p> 067 * 068 * <p> 069 * The lengths of individual elements (edges or/and nodes) are defined using 070 * another constructor parameter called {@code lengthAttribute}. If this 071 * parameter is {@code null}, the elements are considered to have unit lengths. 072 * In other words, the length of a path is the number of its edges or/and nodes. 073 * If the parameter is not null, the elements are supposed to have a numeric 074 * attribute named {@code lengthAttribute} used to store their lengths. 075 * </p> 076 * 077 * <h3>Solutions</h3> 078 * 079 * <p> 080 * Internal solution data is stored in attributes of the nodes of the underlying 081 * graph. The name of this attribute is another constructor parameter called 082 * {@code resultAttribute}. This name must be specified in order to avoid 083 * conflicts with existing attributes, but also to distinguish between solutions 084 * produced by different instances of this class working on the same graph (for 085 * example when computing shortest paths from two different sources). If not 086 * specified, a unique name is chosen automatically based on the hash code of 087 * the Dijkstra instance. The attributes store opaque internal objects and must 088 * not be accessed, modified or deleted. The only way to retrieve the solution 089 * is using different solution access methods. 090 * </p> 091 * 092 * <h3>Usage</h3> 093 * 094 * <p> 095 * A typical usage of this class involves the following steps: 096 * </p> 097 * <ul> 098 * <li>Instantiation using one of the constructors with appropriate parameters</li> 099 * <li>Initialization of the algorithm using {@link #init(Graph)}</li> 100 * <li>Computation of the shortest paths using {@link #compute()}</li> 101 * <li>Retrieving the solution using different solution access methods</li> 102 * <li>Cleaning up using {@link #clear()}</li> 103 * </ul> 104 * 105 * <p> 106 * Note that if the graph changes after the call of {@link #compute()} the 107 * computed solution is no longer valid. In this case the behavior of the 108 * different solution access methods is undefined. 109 * </p> 110 * 111 * <h3>Example</h3> 112 * 113 * <pre> 114 * Graph graph = ...; 115 * 116 * // Edge lengths are stored in an attribute called "length" 117 * // The length of a path is the sum of the lengths of its edges 118 * // The algorithm will store its results in attribute called "result" 119 * Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.edge, "result", "length"); 120 * 121 * // Compute the shortest paths in g from A to all nodes 122 * dijkstra.init(graph); 123 * dijkstra.setSource(graph.getNode("A")); 124 * dijkstra.compute(); 125 * 126 * // Print the lengths of all the shortest paths 127 * for (Node node : graph) 128 * System.out.printf("%s->%s:%6.2f%n", dijkstra.getSource(), node, dijkstra.getPathLength(node)); 129 * 130 * // Color in blue all the nodes on the shortest path form A to B 131 * for (Node node : dijkstra.getPathNodes(graph.getNode("B"))) 132 * node.addAttribute("ui.style", "fill-color: blue;"); 133 * 134 * // Color in red all the edges in the shortest path tree 135 * for (Edge edge : dijkstra.getTreeEdges()) 136 * edge.addAttribute("ui.style", "fill-color: red;"); 137 * 138 * // Print the shortest path from A to B 139 * System.out.println(dijkstra.getPath(graph.getNode("B")); 140 * 141 * // Build a list containing the nodes in the shortest path from A to B 142 * // Note that nodes are added at the beginning of the list 143 * // because the iterator traverses them in reverse order, from B to A 144 * List <Node> list1 = new ArrayList<Node>(); 145 * for (Node node : dijkstra.getPathNodes(graph.getNode("B"))) 146 * list1.add(0, node); 147 * 148 * // A shorter but less efficient way to do the same thing 149 * List<Node> list2 = dijkstra.getPath(graph.getNode("B")).getNodePath(); 150 * </pre> 151 * 152 * @author Stefan Balev 153 */ 154public class Dijkstra extends AbstractSpanningTree { 155 protected static class Data { 156 FibonacciHeap<Double, Node>.Node fn; 157 Edge edgeFromParent; 158 double distance; 159 } 160 161 /** 162 * This enumeration is used to specify how the length of a path is computed 163 * 164 * @author Stefan Balev 165 */ 166 public static enum Element { 167 /** 168 * The length of a path is the sum of the lengths of its edges. 169 */ 170 EDGE, 171 /** 172 * The length of a path is the sum of the lengths of its nodes. 173 */ 174 NODE, 175 /** 176 * The length of a path is the sum of the lengths of its edges and 177 * nodes. 178 */ 179 EDGE_AND_NODE; 180 } 181 182 protected Element element; 183 protected String resultAttribute; 184 protected String lengthAttribute; 185 protected Node source; 186 187 // *** Helpers *** 188 189 protected double getLength(Edge edge, Node dest) { 190 double lenght = 0; 191 if (element != Element.NODE) 192 lenght += lengthAttribute == null ? 1 : edge 193 .getNumber(lengthAttribute); 194 if (element != Element.EDGE) 195 lenght += lengthAttribute == null ? 1 : dest 196 .getNumber(lengthAttribute); 197 if (lenght < 0) 198 throw new IllegalStateException("Edge " + edge.getId() 199 + " has negative lenght " + lenght); 200 return lenght; 201 } 202 203 protected double getSourceLength() { 204 if (element == Element.EDGE) 205 return 0; 206 return lengthAttribute == null ? 1 : source.getNumber(lengthAttribute); 207 } 208 209 // *** Constructors *** 210 211 /** 212 * Constructs an instance with the specified parameters. The edges of the shortest path tree are not tagged. 213 * 214 * @param element 215 * Graph elements (edges or/and nodes) used to compute the path 216 * lengths. If {@code null}, the length of the path is computed 217 * using edges. 218 * @param resultAttribute 219 * Attribute name used to store internal solution data in the 220 * nodes of the graph. If {@code null}, a unique name is chosen 221 * automatically. 222 * @param lengthAttribute 223 * Attribute name used to define individual element lengths. If 224 * {@code null} the length of the elements is considered to be 225 * one. 226 */ 227 public Dijkstra(Element element, String resultAttribute, 228 String lengthAttribute) { 229 this(element, resultAttribute, lengthAttribute, null, null, null); 230 } 231 232 /** 233 * Constructs an instance in which the length of the path is considered to 234 * be the number of edges. Unique result attribute is chosen automatically. The edges of the shortest path tree are not tagged. 235 */ 236 public Dijkstra() { 237 this(null, null, null, null, null, null); 238 } 239 240 /** 241 * Constructs an instance with the specified parameters. 242 * 243 * @param element 244 * Graph elements (edges or/and nodes) used to compute the path 245 * lengths. If {@code null}, the length of the path is computed 246 * using edges. 247 * @param resultAttribute 248 * Attribute name used to store internal solution data in the 249 * nodes of the graph. If {@code null}, a unique name is chosen 250 * automatically. 251 * @param lengthAttribute 252 * Attribute name used to define individual element lengths. If 253 * {@code null} the length of the elements is considered to be 254 * one. 255 * @param flagAttribute 256 * attribute used to set if an edge is in the spanning tree 257 * @param flagOn 258 * value of the <i>flagAttribute</i> if edge is in the spanning 259 * tree 260 * @param flagOff 261 * value of the <i>flagAttribute</i> if edge is not in the 262 * spanning tree 263 */ 264 public Dijkstra(Element element, String resultAttribute, String lengthAttribute, String flagAttribute, Object flagOn, Object flagOff) { 265 super(flagAttribute, flagOn, flagOff); 266 this.element = element == null ? Element.EDGE : element; 267 this.resultAttribute = resultAttribute == null ? toString() 268 + "_result_" : resultAttribute; 269 this.lengthAttribute = lengthAttribute; 270 graph = null; 271 source = null; 272 } 273 274 // *** Some basic methods *** 275 276 /** 277 * Dijkstra's algorithm computes shortest paths from a given source node to 278 * all nodes in a graph. This method returns the source node. 279 * 280 * @return the source node 281 * @see #setSource(Node) 282 */ 283 @SuppressWarnings("unchecked") 284 public <T extends Node> T getSource() { 285 return (T) source; 286 } 287 288 /** 289 * Dijkstra's algorithm computes shortest paths from a given source node to 290 * all nodes in a graph. This method sets the source node. 291 * 292 * @param source 293 * The new source node. 294 * @see #getSource() 295 */ 296 public void setSource(Node source) { 297 this.source = source; 298 } 299 300 /** 301 * Removes the attributes used to store internal solution data in the nodes 302 * of the graph. Use this method to free memory. Solution access methods 303 * must not be used after calling this method. 304 */ 305 @Override 306 public void clear() { 307 super.clear(); 308 for (Node node : graph) { 309 Data data = node.getAttribute(resultAttribute); 310 if (data != null) { 311 data.fn = null; 312 data.edgeFromParent = null; 313 } 314 node.removeAttribute(resultAttribute); 315 } 316 } 317 318 // *** Methods of Algorithm interface *** 319 320 321 /** 322 * Computes the shortest paths from the source node to all nodes in the 323 * graph. 324 * 325 * @throws IllegalStateException 326 * if {@link #init(Graph)} or {@link #setSource(Node)} have not 327 * been called before or if elements with negative lengths are 328 * discovered. 329 * @see org.graphstream.algorithm.Algorithm#compute() 330 * @complexity O(<em>m</em> + <em>n</em>log<em>n</em>) where <em>m</em> is 331 * the number of edges and <em>n</em> is the number of nodes in 332 * the graph. 333 */ 334 @Override 335 public void compute() { 336 // check if computation can start 337 if (graph == null) 338 throw new IllegalStateException( 339 "No graph specified. Call init() first."); 340 if (source == null) 341 throw new IllegalStateException( 342 "No source specified. Call setSource() first."); 343 resetFlags(); 344 makeTree(); 345 } 346 347 @Override 348 protected void makeTree() { 349 // initialization 350 FibonacciHeap<Double, Node> heap = new FibonacciHeap<Double, Node>(); 351 for (Node node : graph) { 352 Data data = new Data(); 353 double v = node == source ? getSourceLength() 354 : Double.POSITIVE_INFINITY; 355 data.fn = heap.add(v, node); 356 data.edgeFromParent = null; 357 node.addAttribute(resultAttribute, data); 358 } 359 360 // main loop 361 while (!heap.isEmpty()) { 362 Node u = heap.extractMin(); 363 Data dataU = u.getAttribute(resultAttribute); 364 dataU.distance = dataU.fn.getKey(); 365 dataU.fn = null; 366 if (dataU.edgeFromParent != null) 367 edgeOn(dataU.edgeFromParent); 368 for (Edge e : u.getEachLeavingEdge()) { 369 Node v = e.getOpposite(u); 370 Data dataV = v.getAttribute(resultAttribute); 371 if (dataV.fn == null) 372 continue; 373 double tryDist = dataU.distance + getLength(e, v); 374 if (tryDist < dataV.fn.getKey()) { 375 dataV.edgeFromParent = e; 376 heap.decreaseKey(dataV.fn, tryDist); 377 } 378 } 379 } 380 } 381 382 // *** Iterators *** 383 384 protected class NodeIterator<T extends Node> implements Iterator<T> { 385 protected Node nextNode; 386 387 protected NodeIterator(Node target) { 388 nextNode = Double.isInfinite(getPathLength(target)) ? null : target; 389 } 390 391 public boolean hasNext() { 392 return nextNode != null; 393 } 394 395 @SuppressWarnings("unchecked") 396 public T next() { 397 if (nextNode == null) 398 throw new NoSuchElementException(); 399 Node node = nextNode; 400 nextNode = getParent(nextNode); 401 return (T) node; 402 } 403 404 public void remove() { 405 throw new UnsupportedOperationException( 406 "remove is not supported by this iterator"); 407 } 408 } 409 410 protected class EdgeIterator<T extends Edge> implements Iterator<T> { 411 protected Node nextNode; 412 protected T nextEdge; 413 414 protected EdgeIterator(Node target) { 415 nextNode = target; 416 nextEdge = getEdgeFromParent(nextNode); 417 } 418 419 public boolean hasNext() { 420 return nextEdge != null; 421 } 422 423 public T next() { 424 if (nextEdge == null) 425 throw new NoSuchElementException(); 426 T edge = nextEdge; 427 nextNode = getParent(nextNode); 428 nextEdge = getEdgeFromParent(nextNode); 429 return edge; 430 } 431 432 public void remove() { 433 throw new UnsupportedOperationException( 434 "remove is not supported by this iterator"); 435 } 436 } 437 438 protected class PathIterator implements Iterator<Path> { 439 protected List<Node> nodes; 440 protected List<Iterator<Edge>> iterators; 441 protected Path nextPath; 442 443 protected void extendPathStep() { 444 int last = nodes.size() - 1; 445 Node v = nodes.get(last); 446 double lengthV = getPathLength(v); 447 Iterator<Edge> it = iterators.get(last); 448 while (it.hasNext()) { 449 Edge e = it.next(); 450 Node u = e.getOpposite(v); 451 if (getPathLength(u) + getLength(e, v) == lengthV) { 452 nodes.add(u); 453 iterators.add(u.getEnteringEdgeIterator()); 454 return; 455 } 456 } 457 nodes.remove(last); 458 iterators.remove(last); 459 } 460 461 protected void extendPath() { 462 while (!nodes.isEmpty() && nodes.get(nodes.size() - 1) != source) 463 extendPathStep(); 464 } 465 466 protected void constructNextPath() { 467 if (nodes.isEmpty()) { 468 nextPath = null; 469 return; 470 } 471 nextPath = new Path(); 472 nextPath.setRoot(source); 473 for (int i = nodes.size() - 1; i > 0; i--) 474 nextPath.add(nodes.get(i).getEdgeToward( 475 nodes.get(i - 1).getId())); 476 } 477 478 public PathIterator(Node target) { 479 nodes = new ArrayList<Node>(); 480 iterators = new ArrayList<Iterator<Edge>>(); 481 if (Double.isInfinite(getPathLength(target))) { 482 nextPath = null; 483 return; 484 } 485 nodes.add(target); 486 iterators.add(target.getEnteringEdgeIterator()); 487 extendPath(); 488 constructNextPath(); 489 } 490 491 public boolean hasNext() { 492 return nextPath != null; 493 } 494 495 public Path next() { 496 if (nextPath == null) 497 throw new NoSuchElementException(); 498 nodes.remove(nodes.size() - 1); 499 iterators.remove(iterators.size() - 1); 500 extendPath(); 501 Path path = nextPath; 502 constructNextPath(); 503 return path; 504 } 505 506 public void remove() { 507 throw new UnsupportedOperationException( 508 "remove is not supported by this iterator"); 509 } 510 } 511 512 protected class TreeIterator<T extends Edge> implements Iterator<T> { 513 Iterator<Node> nodeIt; 514 T nextEdge; 515 516 protected void findNextEdge() { 517 nextEdge = null; 518 while (nodeIt.hasNext() && nextEdge == null) 519 nextEdge = getEdgeFromParent(nodeIt.next()); 520 } 521 522 protected TreeIterator() { 523 nodeIt = graph.getNodeIterator(); 524 findNextEdge(); 525 } 526 527 public boolean hasNext() { 528 return nextEdge != null; 529 } 530 531 public T next() { 532 if (nextEdge == null) 533 throw new NoSuchElementException(); 534 T edge = nextEdge; 535 findNextEdge(); 536 return edge; 537 } 538 539 public void remove() { 540 throw new UnsupportedOperationException( 541 "remove is not supported by this iterator"); 542 } 543 } 544 545 // *** Methods to access the solution *** 546 547 /** 548 * Returns the length of the shortest path from the source node to a given 549 * target node. 550 * 551 * @param target 552 * A node 553 * @return the length of the shortest path or 554 * {@link java.lang.Double#POSITIVE_INFINITY} if there is no path 555 * from the source to the target 556 * @complexity O(1) 557 */ 558 public double getPathLength(Node target) { 559 return target.<Data> getAttribute(resultAttribute).distance; 560 } 561 562 /** 563 * Dijkstra's algorithm produces a shortest path tree rooted in the source 564 * node. This method returns the total length of the tree. 565 * 566 * @return the length of the shortest path tree 567 * @complexity O(<em>n</em>) where <em>n</em> is the number of nodes is the 568 * graph. 569 */ 570 public double getTreeLength() { 571 double length = getSourceLength(); 572 for (Edge edge : getTreeEdges()) { 573 Node node = edge.getNode0(); 574 if (getEdgeFromParent(node) != edge) 575 node = edge.getNode1(); 576 length += getLength(edge, node); 577 } 578 return length; 579 } 580 581 /** 582 * Returns the edge between the target node and the previous node in the 583 * shortest path from the source to the target. This is also the edge 584 * connecting the target to its parent in the shortest path tree. 585 * 586 * @param target 587 * a node 588 * @return the edge between the target and its predecessor in the shortest 589 * path, {@code null} if there is no path from the source to the 590 * target or if the target and the source are the same node. 591 * @see #getParent(Node) 592 * @complexity O(1) 593 */ 594 @SuppressWarnings("unchecked") 595 public <T extends Edge> T getEdgeFromParent(Node target) { 596 return (T) target.<Data> getAttribute(resultAttribute).edgeFromParent; 597 } 598 599 /** 600 * Returns the node preceding the target in the shortest path from the 601 * source to the target. This node is the parent of the target in the 602 * shortest path tree. 603 * 604 * @param target 605 * a node 606 * @return the predecessor of the target in the shortest path, {@code null} 607 * if there is no path from the source to the target or if the 608 * target and the source are the same node. 609 * @see #getEdgeFromParent(Node) 610 * @complexity O(1) 611 */ 612 public <T extends Node> T getParent(Node target) { 613 Edge edge = getEdgeFromParent(target); 614 if (edge == null) 615 return null; 616 return edge.getOpposite(target); 617 } 618 619 /** 620 * This iterator traverses the nodes on the shortest path from the source 621 * node to a given target node. The nodes are traversed in reverse order: 622 * the target node first, then its predecessor, ... and finally the source 623 * node. If there is no path from the source to the target, no nodes are 624 * traversed. This iterator does not support 625 * {@link java.util.Iterator#remove()}. 626 * 627 * @param target 628 * a node 629 * @return an iterator on the nodes of the shortest path from the source to 630 * the target 631 * @see #getPathNodes(Node) 632 * @complexity Each call of {@link java.util.Iterator#next()} of this 633 * iterator takes O(1) time 634 */ 635 public <T extends Node> Iterator<T> getPathNodesIterator(Node target) { 636 return new NodeIterator<T>(target); 637 } 638 639 /** 640 * An iterable view of the nodes on the shortest path from the source node 641 * to a given target node. Uses {@link #getPathNodesIterator(Node)}. 642 * 643 * @param target 644 * a node 645 * @return an iterable view of the nodes on the shortest path from the 646 * source to the target 647 * @see #getPathNodesIterator(Node) 648 */ 649 public <T extends Node> Iterable<T> getPathNodes(final Node target) { 650 return new Iterable<T>() { 651 public Iterator<T> iterator() { 652 return getPathNodesIterator(target); 653 } 654 }; 655 } 656 657 /** 658 * This iterator traverses the edges on the shortest path from the source 659 * node to a given target node. The edges are traversed in reverse order: 660 * first the edge between the target and its predecessor, ... and finally 661 * the edge between the source end its successor. If there is no path from 662 * the source to the target or if he source and the target are the same 663 * node, no edges are traversed. This iterator does not support 664 * {@link java.util.Iterator#remove()}. 665 * 666 * @param target 667 * a node 668 * @return an iterator on the edges of the shortest path from the source to 669 * the target 670 * @see #getPathEdges(Node) 671 * @complexity Each call of {@link java.util.Iterator#next()} of this 672 * iterator takes O(1) time 673 */ 674 public <T extends Edge> Iterator<T> getPathEdgesIterator(Node target) { 675 return new EdgeIterator<T>(target); 676 } 677 678 /** 679 * An iterable view of the edges on the shortest path from the source node 680 * to a given target node. Uses {@link #getPathEdgesIterator(Node)}. 681 * 682 * @param target 683 * a node 684 * @return an iterable view of the edges on the shortest path from the 685 * source to the target 686 * @see #getPathEdgesIterator(Node) 687 */ 688 public <T extends Edge> Iterable<T> getPathEdges(final Node target) { 689 return new Iterable<T>() { 690 public Iterator<T> iterator() { 691 return getPathEdgesIterator(target); 692 } 693 694 }; 695 } 696 697 /** 698 * This iterator traverses <em>all</em> the shortest paths from the source 699 * node to a given target node. If there is more than one shortest paths 700 * between the source and the target, other solution access methods choose 701 * one of them (the one from the shortest path tree). This iterator can be 702 * used if one needs to know all the paths. Each call to 703 * {@link java.util.Iterator#next()} method of this iterator returns a 704 * shortest path in the form of {@link org.graphstream.graph.Path} object. 705 * This iterator does not support {@link java.util.Iterator#remove()}. 706 * 707 * @param target 708 * a node 709 * @return an iterator on all the shortest paths from the source to the 710 * target 711 * @see #getAllPaths(Node) 712 * @complexity Each call of {@link java.util.Iterator#next()} of this 713 * iterator takes O(<em>m</em>) time in the worst case, where 714 * <em>m</em> is the number of edges in the graph 715 */ 716 public Iterator<Path> getAllPathsIterator(Node target) { 717 return new PathIterator(target); 718 } 719 720 /** 721 * An iterable view of of <em>all</em> the shortest paths from the source 722 * node to a given target node. Uses {@link #getAllPathsIterator(Node)} 723 * 724 * @param target 725 * a node 726 * @return an iterable view of all the shortest paths from the source to the 727 * target 728 * @see #getAllPathsIterator(Node) 729 */ 730 public Iterable<Path> getAllPaths(final Node target) { 731 return new Iterable<Path>() { 732 public Iterator<Path> iterator() { 733 return getAllPathsIterator(target); 734 } 735 }; 736 } 737 738 /** 739 * Dijkstra's algorithm produces a shortest path tree rooted in the source 740 * node. This iterator traverses the edges of this tree. The edges are 741 * traversed in no particular order. 742 * 743 * @return an iterator on the edges of the shortest path tree 744 * @see #getTreeEdges() 745 * @complexity Each call of {@link java.util.Iterator#next()} of this 746 * iterator takes O(1) time 747 */ 748 @Override 749 public <T extends Edge> Iterator<T> getTreeEdgesIterator() { 750 return new TreeIterator<T>(); 751 } 752 753 754 /** 755 * Returns the shortest path from the source node to a given target node. If 756 * there is no path from the source to the target returns an empty path. 757 * This method constructs a {@link org.graphstream.graph.Path} object which 758 * consumes heap memory proportional to the number of edges and nodes in the 759 * path. When possible, prefer using {@link #getPathNodes(Node)} and 760 * {@link #getPathEdges(Node)} which are more memory- and time-efficient. 761 * 762 * @param target 763 * a node 764 * @return the shortest path from the source to the target 765 * @complexity O(<em>p</em>) where <em>p</em> is the number of the nodes in 766 * the path 767 */ 768 public Path getPath(Node target) { 769 Path path = new Path(); 770 if (Double.isInfinite(getPathLength(target))) 771 return path; 772 Stack<Edge> stack = new Stack<Edge>(); 773 for (Edge e : getPathEdges(target)) 774 stack.push(e); 775 path.setRoot(source); 776 while (!stack.isEmpty()) 777 path.add(stack.pop()); 778 return path; 779 } 780}