486 template <typename Path> |
486 template <typename Path> |
487 bool getPath(Path &p, Node source, Node target) { |
487 bool getPath(Path &p, Node source, Node target) { |
488 if (connected(source, target)) { |
488 if (connected(source, target)) { |
489 p.clear(); |
489 p.clear(); |
490 typename Path::Builder b(target); |
490 typename Path::Builder b(target); |
491 for(b.setStartNode(target); pred(source, target) != INVALID; |
491 for(b.setStartNode(target); predEdge(source, target) != INVALID; |
492 target = predNode(target)) { |
492 target = predNode(target)) { |
493 b.pushFront(pred(source, target)); |
493 b.pushFront(predEdge(source, target)); |
494 } |
494 } |
495 b.commit(); |
495 b.commit(); |
496 return true; |
496 return true; |
497 } |
497 } |
498 return false; |
498 return false; |
516 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
516 /// to \c node. It is \ref INVALID if \c node is unreachable from the root |
517 /// or if \c node=root. The shortest path tree used here is equal to the |
517 /// or if \c node=root. The shortest path tree used here is equal to the |
518 /// shortest path tree used in \ref predNode(). |
518 /// shortest path tree used in \ref predNode(). |
519 /// \pre \ref run() must be called before using this function. |
519 /// \pre \ref run() must be called before using this function. |
520 /// \todo predEdge could be a better name. |
520 /// \todo predEdge could be a better name. |
521 Edge pred(Node root, Node node) const { |
521 Edge predEdge(Node root, Node node) const { |
522 return (*_pred)(root, node); |
522 return (*_pred)(root, node); |
523 } |
523 } |
524 |
524 |
525 /// \brief Returns the 'previous node' of the shortest path tree. |
525 /// \brief Returns the 'previous node' of the shortest path tree. |
526 /// |
526 /// |
527 /// For a node \c node it returns the 'previous node' of the shortest path |
527 /// For a node \c node it returns the 'previous node' of the shortest path |
528 /// tree to direction of the node \c root, i.e. it returns the last but |
528 /// tree to direction of the node \c root, i.e. it returns the last but |
529 /// one node from a shortest path from the \c root to \c node. It is |
529 /// one node from a shortest path from the \c root to \c node. It is |
530 /// INVALID if \c node is unreachable from the root or if \c node=root. |
530 /// INVALID if \c node is unreachable from the root or if \c node=root. |
531 /// The shortest path tree used here is equal to the |
531 /// The shortest path tree used here is equal to the |
532 /// shortest path tree used in \ref pred(). |
532 /// shortest path tree used in \ref predEdge(). |
533 /// \pre \ref run() must be called before using this function. |
533 /// \pre \ref run() must be called before using this function. |
534 Node predNode(Node root, Node node) const { |
534 Node predNode(Node root, Node node) const { |
535 return (*_pred)(root, node) == INVALID ? |
535 return (*_pred)(root, node) == INVALID ? |
536 INVALID : graph->source((*_pred)(root, node)); |
536 INVALID : graph->source((*_pred)(root, node)); |
537 } |
537 } |