1.1 --- a/lemon/bellman_ford.h Fri Jan 05 10:59:18 2007 +0000
1.2 +++ b/lemon/bellman_ford.h Mon Jan 08 10:39:59 2007 +0000
1.3 @@ -25,6 +25,7 @@
1.4 ///
1.5
1.6 #include <lemon/list_graph.h>
1.7 +#include <lemon/bits/path_dump.h>
1.8 #include <lemon/bits/invalid.h>
1.9 #include <lemon/error.h>
1.10 #include <lemon/maps.h>
1.11 @@ -427,7 +428,7 @@
1.12 /// calculates the at most \f$ k \f$ length path lengths.
1.13 ///
1.14 /// \warning The paths with limited edge number cannot be retrieved
1.15 - /// easily with \ref getPath() or \ref predEdge() functions. If you
1.16 + /// easily with \ref path() or \ref predEdge() functions. If you
1.17 /// need the shortest path and not just the distance you should store
1.18 /// after each iteration the \ref predEdgeMap() map and manually build
1.19 /// the path.
1.20 @@ -540,7 +541,7 @@
1.21 /// most \c num edge.
1.22 ///
1.23 /// \warning The paths with limited edge number cannot be retrieved
1.24 - /// easily with \ref getPath() or \ref predEdge() functions. If you
1.25 + /// easily with \ref path() or \ref predEdge() functions. If you
1.26 /// need the shortest path and not just the distance you should store
1.27 /// after each iteration the \ref predEdgeMap() map and manually build
1.28 /// the path.
1.29 @@ -658,70 +659,56 @@
1.30 int _index;
1.31 };
1.32
1.33 - /// \brief Copies the shortest path to \c t into \c p
1.34 + typedef PredMapPath<Graph, PredMap> Path;
1.35 +
1.36 + /// \brief Gives back the shortest path.
1.37 ///
1.38 - /// This function copies the shortest path to \c t into \c p.
1.39 - /// If it \c t is a source itself or unreachable, then it does not
1.40 - /// alter \c p.
1.41 - ///
1.42 - /// \return Returns \c true if a path to \c t was actually copied to \c p,
1.43 - /// \c false otherwise.
1.44 - /// \sa DirPath
1.45 - template <typename Path>
1.46 - bool getPath(Path &p, Node t) {
1.47 - if(reached(t)) {
1.48 - p.clear();
1.49 - typename Path::Builder b(p);
1.50 - for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
1.51 - b.pushFront(predEdge(t));
1.52 - b.commit();
1.53 - return true;
1.54 - }
1.55 - return false;
1.56 + /// Gives back the shortest path.
1.57 + /// \pre The \c t should be reachable from the source.
1.58 + Path path(Node t)
1.59 + {
1.60 + return Path(*graph, *_pred, t);
1.61 }
1.62
1.63 - /// \brief Copies a negative cycle into path \c p.
1.64 - ///
1.65 - /// This function copies a negative cycle into path \c p.
1.66 - /// If the algorithm have not found yet negative cycle it will not change
1.67 - /// the given path and gives back false.
1.68 - ///
1.69 - /// \return Returns \c true if a cycle was actually copied to \c p,
1.70 - /// \c false otherwise.
1.71 - /// \sa DirPath
1.72 - template <typename Path>
1.73 - bool getNegativeCycle(Path& p) {
1.74 - typename Graph::template NodeMap<int> state(*graph, 0);
1.75 - for (ActiveIt it(*this); it != INVALID; ++it) {
1.76 - if (state[it] == 0) {
1.77 - for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
1.78 - if (state[t] == 0) {
1.79 - state[t] = 1;
1.80 - } else if (state[t] == 2) {
1.81 - break;
1.82 - } else {
1.83 - p.clear();
1.84 - typename Path::Builder b(p);
1.85 - b.setStartNode(t);
1.86 - b.pushFront(predEdge(t));
1.87 - for(Node s = predNode(t); s != t; s = predNode(s)) {
1.88 - b.pushFront(predEdge(s));
1.89 - }
1.90 - b.commit();
1.91 - return true;
1.92 - }
1.93 - }
1.94 - for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
1.95 - if (state[t] == 1) {
1.96 - state[t] = 2;
1.97 - } else {
1.98 - break;
1.99 - }
1.100 - }
1.101 - }
1.102 - }
1.103 - return false;
1.104 - }
1.105 +
1.106 + // TODO : implement negative cycle
1.107 +// /// \brief Gives back a negative cycle.
1.108 +// ///
1.109 +// /// This function gives back a negative cycle.
1.110 +// /// If the algorithm have not found yet negative cycle it will give back
1.111 +// /// an empty path.
1.112 +// Path negativeCycle() {
1.113 +// typename Graph::template NodeMap<int> state(*graph, 0);
1.114 +// for (ActiveIt it(*this); it != INVALID; ++it) {
1.115 +// if (state[it] == 0) {
1.116 +// for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
1.117 +// if (state[t] == 0) {
1.118 +// state[t] = 1;
1.119 +// } else if (state[t] == 2) {
1.120 +// break;
1.121 +// } else {
1.122 +// p.clear();
1.123 +// typename Path::Builder b(p);
1.124 +// b.setStartNode(t);
1.125 +// b.pushFront(predEdge(t));
1.126 +// for(Node s = predNode(t); s != t; s = predNode(s)) {
1.127 +// b.pushFront(predEdge(s));
1.128 +// }
1.129 +// b.commit();
1.130 +// return true;
1.131 +// }
1.132 +// }
1.133 +// for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
1.134 +// if (state[t] == 1) {
1.135 +// state[t] = 2;
1.136 +// } else {
1.137 +// break;
1.138 +// }
1.139 +// }
1.140 +// }
1.141 +// }
1.142 +// return false;
1.143 +// }
1.144
1.145 /// \brief The distance of a node from the root.
1.146 ///