1.1 --- a/lemon/belmann_ford.h Tue Nov 08 10:12:45 2005 +0000
1.2 +++ b/lemon/belmann_ford.h Wed Nov 09 12:07:00 2005 +0000
1.3 @@ -203,7 +203,7 @@
1.4 typedef typename Graph::Node Node;
1.5 typedef typename Graph::NodeIt NodeIt;
1.6 typedef typename Graph::Edge Edge;
1.7 - typedef typename Graph::EdgeIt EdgeIt;
1.8 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.9
1.10 /// \brief The type of the length of the edges.
1.11 typedef typename _Traits::LengthMap::Value Value;
1.12 @@ -230,6 +230,11 @@
1.13 ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.14 bool local_dist;
1.15
1.16 + typedef typename Graph::template NodeMap<bool> MaskMap;
1.17 + MaskMap *_mask;
1.18 +
1.19 + std::vector<Node> _process;
1.20 +
1.21 /// Creates the maps if necessary.
1.22 void create_maps() {
1.23 if(!_pred) {
1.24 @@ -240,6 +245,7 @@
1.25 local_dist = true;
1.26 _dist = Traits::createDistMap(*graph);
1.27 }
1.28 + _mask = new MaskMap(*graph, false);
1.29 }
1.30
1.31 public :
1.32 @@ -324,6 +330,7 @@
1.33 ~BelmannFord() {
1.34 if(local_pred) delete _pred;
1.35 if(local_dist) delete _dist;
1.36 + delete _mask;
1.37 }
1.38
1.39 /// \brief Sets the length map.
1.40 @@ -388,6 +395,12 @@
1.41 _pred->set(it, INVALID);
1.42 _dist->set(it, value);
1.43 }
1.44 + _process.clear();
1.45 + if (OperationTraits::less(value, OperationTraits::infinity())) {
1.46 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.47 + _process.push_back(it);
1.48 + }
1.49 + }
1.50 }
1.51
1.52 /// \brief Adds a new source node.
1.53 @@ -396,6 +409,77 @@
1.54 /// It just sets the distance of the node to the given value.
1.55 void addSource(Node source, Value dst = OperationTraits::zero()) {
1.56 _dist->set(source, dst);
1.57 + if (!(*_mask)[source]) {
1.58 + _process.push_back(source);
1.59 + _mask->set(source, true);
1.60 + }
1.61 + }
1.62 +
1.63 + /// \brief Executes one round from the belmann ford algorithm.
1.64 + ///
1.65 + /// If the algoritm calculated the distances in the previous round
1.66 + /// strictly for all at most k length pathes then it will calculate the
1.67 + /// distances strictly for all at most k + 1 length pathes. With k
1.68 + /// iteration this function calculates the at most k length pathes.
1.69 + bool processNextRound() {
1.70 + for (int i = 0; i < (int)_process.size(); ++i) {
1.71 + _mask->set(_process[i], false);
1.72 + }
1.73 + std::vector<Node> nextProcess;
1.74 + std::vector<Value> values(_process.size());
1.75 + for (int i = 0; i < (int)_process.size(); ++i) {
1.76 + values[i] = _dist[_process[i]];
1.77 + }
1.78 + for (int i = 0; i < (int)_process.size(); ++i) {
1.79 + for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
1.80 + Node target = graph->target(it);
1.81 + Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
1.82 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.83 + _pred->set(target, it);
1.84 + _dist->set(target, relaxed);
1.85 + if (!(*_mask)[target]) {
1.86 + _mask->set(target, true);
1.87 + nextProcess.push_back(target);
1.88 + }
1.89 + }
1.90 + }
1.91 + }
1.92 + _process.swap(nextProcess);
1.93 + return _process.empty();
1.94 + }
1.95 +
1.96 + /// \brief Executes one weak round from the belmann ford algorithm.
1.97 + ///
1.98 + /// If the algorithm calculated the distances in the
1.99 + /// previous round at least for all at most k length pathes then it will
1.100 + /// calculate the distances at least for all at most k + 1 length pathes.
1.101 + /// This function does not make possible to calculate strictly the
1.102 + /// at most k length minimal pathes, this way it called just weak round.
1.103 + bool processNextWeakRound() {
1.104 + for (int i = 0; i < (int)_process.size(); ++i) {
1.105 + _mask->set(_process[i], false);
1.106 + }
1.107 + std::vector<Node> nextProcess;
1.108 + for (int i = 0; i < (int)_process.size(); ++i) {
1.109 + for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
1.110 + Node target = graph->target(it);
1.111 + Value relaxed =
1.112 + OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
1.113 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.114 + _pred->set(target, it);
1.115 + _dist->set(target, relaxed);
1.116 + if (!(*_mask)[target]) {
1.117 + _mask->set(target, true);
1.118 + nextProcess.push_back(target);
1.119 + }
1.120 + }
1.121 + }
1.122 + }
1.123 + for (int i = 0; i < (int)nextProcess.size(); ++i) {
1.124 + _mask->set(nextProcess[i], false);
1.125 + }
1.126 + _process.swap(nextProcess);
1.127 + return _process.empty();
1.128 }
1.129
1.130 /// \brief Executes the algorithm.
1.131 @@ -411,19 +495,7 @@
1.132 void start() {
1.133 int num = countNodes(*graph) - 1;
1.134 for (int i = 0; i < num; ++i) {
1.135 - bool done = true;
1.136 - for (EdgeIt it(*graph); it != INVALID; ++it) {
1.137 - Node source = graph->source(it);
1.138 - Node target = graph->target(it);
1.139 - Value relaxed =
1.140 - OperationTraits::plus((*_dist)[source], (*length)[it]);
1.141 - if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.142 - _pred->set(target, it);
1.143 - _dist->set(target, relaxed);
1.144 - done = false;
1.145 - }
1.146 - }
1.147 - if (done) return;
1.148 + if (processNextWeakRound()) break;
1.149 }
1.150 }
1.151
1.152 @@ -441,22 +513,26 @@
1.153 bool checkedStart() {
1.154 int num = countNodes(*graph);
1.155 for (int i = 0; i < num; ++i) {
1.156 - bool done = true;
1.157 - for (EdgeIt it(*graph); it != INVALID; ++it) {
1.158 - Node source = graph->source(it);
1.159 - Node target = graph->target(it);
1.160 - Value relaxed =
1.161 - OperationTraits::plus((*_dist)[source], (*length)[it]);
1.162 - if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.163 - _pred->set(target, it);
1.164 - _dist->set(target, relaxed);
1.165 - done = false;
1.166 - }
1.167 - }
1.168 - if (done) return true;
1.169 + if (processNextWeakRound()) return true;
1.170 }
1.171 return false;
1.172 }
1.173 +
1.174 + /// \brief Executes the algorithm with path length limit.
1.175 + ///
1.176 + /// \pre init() must be called and at least one node should be added
1.177 + /// with addSource() before using this function.
1.178 + ///
1.179 + /// This method runs the %BelmannFord algorithm from the root node(s)
1.180 + /// in order to compute the shortest path with at most \c length edge
1.181 + /// long pathes to each node. The algorithm computes
1.182 + /// - The shortest path tree.
1.183 + /// - The limited distance of each node from the root(s).
1.184 + void limitedStart(int length) {
1.185 + for (int i = 0; i < length; ++i) {
1.186 + if (processNextRound()) break;
1.187 + }
1.188 + }
1.189
1.190 /// \brief Runs %BelmannFord algorithm from node \c s.
1.191 ///