507 dijkstra.run(it); |
507 dijkstra.run(it); |
508 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
508 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
509 if (dijkstra.reached(jt)) { |
509 if (dijkstra.reached(jt)) { |
510 _dist->set(it, jt, dijkstra.dist(jt) + |
510 _dist->set(it, jt, dijkstra.dist(jt) + |
511 potential[jt] - potential[it]); |
511 potential[jt] - potential[it]); |
512 _pred->set(it, jt, dijkstra.pred(jt)); |
512 _pred->set(it, jt, dijkstra.predEdge(jt)); |
513 } else { |
513 } else { |
514 _dist->set(it, jt, OperationTraits::infinity()); |
514 _dist->set(it, jt, OperationTraits::infinity()); |
515 _pred->set(it, jt, INVALID); |
515 _pred->set(it, jt, INVALID); |
516 } |
516 } |
517 } |
517 } |
632 template <typename Path> |
632 template <typename Path> |
633 bool getPath(Path &p, Node source, Node target) { |
633 bool getPath(Path &p, Node source, Node target) { |
634 if (connected(source, target)) { |
634 if (connected(source, target)) { |
635 p.clear(); |
635 p.clear(); |
636 typename Path::Builder b(target); |
636 typename Path::Builder b(target); |
637 for(b.setStartNode(target); pred(source, target) != INVALID; |
637 for(b.setStartNode(target); predEdge(source, target) != INVALID; |
638 target = predNode(target)) { |
638 target = predNode(target)) { |
639 b.pushFront(pred(source, target)); |
639 b.pushFront(predEdge(source, target)); |
640 } |
640 } |
641 b.commit(); |
641 b.commit(); |
642 return true; |
642 return true; |
643 } |
643 } |
644 return false; |
644 return false; |
662 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
662 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
663 /// or if \c node=root. The shortest path tree used here is equal to the |
663 /// or if \c node=root. The shortest path tree used here is equal to the |
664 /// shortest path tree used in \ref predNode(). |
664 /// shortest path tree used in \ref predNode(). |
665 /// \pre \ref run() must be called before using this function. |
665 /// \pre \ref run() must be called before using this function. |
666 /// \todo predEdge could be a better name. |
666 /// \todo predEdge could be a better name. |
667 Edge pred(Node root, Node node) const { |
667 Edge predEdge(Node root, Node node) const { |
668 return (*_pred)(root, node); |
668 return (*_pred)(root, node); |
669 } |
669 } |
670 |
670 |
671 /// \brief Returns the 'previous node' of the shortest path tree. |
671 /// \brief Returns the 'previous node' of the shortest path tree. |
672 /// |
672 /// |
673 /// For a node \c node it returns the 'previous node' of the shortest path |
673 /// For a node \c node it returns the 'previous node' of the shortest path |
674 /// tree to direction of the node \c root, i.e. it returns the last but |
674 /// tree to direction of the node \c root, i.e. it returns the last but |
675 /// one node from a shortest path from the \c root to \c node. It is |
675 /// one node from a shortest path from the \c root to \c node. It is |
676 /// INVALID if \c node is unreachable from the root or if \c node=root. |
676 /// INVALID if \c node is unreachable from the root or if \c node=root. |
677 /// The shortest path tree used here is equal to the |
677 /// The shortest path tree used here is equal to the |
678 /// shortest path tree used in \ref pred(). |
678 /// shortest path tree used in \ref predEdge(). |
679 /// \pre \ref run() must be called before using this function. |
679 /// \pre \ref run() must be called before using this function. |
680 Node predNode(Node root, Node node) const { |
680 Node predNode(Node root, Node node) const { |
681 return (*_pred)(root, node) == INVALID ? |
681 return (*_pred)(root, node) == INVALID ? |
682 INVALID : graph->source((*_pred)(root, node)); |
682 INVALID : graph->source((*_pred)(root, node)); |
683 } |
683 } |