lemon-0.x: comparison lemon/belmann

equal deleted inserted replaced

-:dbe59e50e971
+:76f2b184d9b3
 typedef typename _Traits::Graph Graph;
 typedef typename Graph::Node Node;
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
-typedef typename Graph::EdgeIt EdgeIt;
+typedef typename Graph::OutEdgeIt OutEdgeIt;
 /// \brief The type of the length of the edges.
 typedef typename _Traits::LengthMap::Value Value;
 /// \brief The type of the map that stores the edge lengths.
 typedef typename _Traits::LengthMap LengthMap;
 ///Pointer to the map of distances.
 DistMap *_dist;
 ///Indicates if \ref _dist is locally allocated (\c true) or not.
 bool local_dist;
+typedef typename Graph::template NodeMap<bool> MaskMap;
+MaskMap *_mask;
+std::vector<Node> _process;
 /// Creates the maps if necessary.
 void create_maps() {
 if(!_pred) {
 	local_pred = true;
 	_pred = Traits::createPredMap(*graph);
 }
 if(!_dist) {
 	local_dist = true;
 	_dist = Traits::createDistMap(*graph);
 }
+_mask = new MaskMap(*graph, false);
 }
 public :
 typedef BelmannFord Create;
 ///Destructor.
 ~BelmannFord() {
 if(local_pred) delete _pred;
 if(local_dist) delete _dist;
+delete _mask;
 }
 /// \brief Sets the length map.
 ///
 /// Sets the length map.
 create_maps();
 for (NodeIt it(*graph); it != INVALID; ++it) {
 	_pred->set(it, INVALID);
 	_dist->set(it, value);
 }
+_process.clear();
+if (OperationTraits::less(value, OperationTraits::infinity())) {
+	for (NodeIt it(*graph); it != INVALID; ++it) {
+	  _process.push_back(it);
+	}
+}
 }
 /// \brief Adds a new source node.
 ///
 /// The optional second parameter is the initial distance of the node.
 /// It just sets the distance of the node to the given value.
 void addSource(Node source, Value dst = OperationTraits::zero()) {
 _dist->set(source, dst);
+if (!(*_mask)[source]) {
+	_process.push_back(source);
+	_mask->set(source, true);
+}
+}
+/// \brief Executes one round from the belmann ford algorithm.
+///
+/// If the algoritm calculated the distances in the previous round
+/// strictly for all at most k length pathes then it will calculate the
+/// distances strictly for all at most k + 1 length pathes. With k
+/// iteration this function calculates the at most k length pathes.
+bool processNextRound() {
+for (int i = 0; i < (int)_process.size(); ++i) {
+	_mask->set(_process[i], false);
+}
+std::vector<Node> nextProcess;
+std::vector<Value> values(_process.size());
+for (int i = 0; i < (int)_process.size(); ++i) {
+	values[i] = _dist[_process[i]];
+}
+for (int i = 0; i < (int)_process.size(); ++i) {
+	for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
+	  Node target = graph->target(it);
+	  Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
+	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
+	    _pred->set(target, it);
+	    _dist->set(target, relaxed);
+	    if (!(*_mask)[target]) {
+	      _mask->set(target, true);
+	      nextProcess.push_back(target);
+	    }
+	  }
+	}
+}
+_process.swap(nextProcess);
+return _process.empty();
+}
+/// \brief Executes one weak round from the belmann ford algorithm.
+///
+/// If the algorithm calculated the distances in the
+/// previous round at least for all at most k length pathes then it will
+/// calculate the distances at least for all at most k + 1 length pathes.
+/// This function does not make possible to calculate strictly the
+/// at most k length minimal pathes, this way it called just weak round.
+bool processNextWeakRound() {
+for (int i = 0; i < (int)_process.size(); ++i) {
+	_mask->set(_process[i], false);
+}
+std::vector<Node> nextProcess;
+for (int i = 0; i < (int)_process.size(); ++i) {
+	for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
+	  Node target = graph->target(it);
+	  Value relaxed =
+	    OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
+	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
+	    _pred->set(target, it);
+	    _dist->set(target, relaxed);
+	    if (!(*_mask)[target]) {
+	      _mask->set(target, true);
+	      nextProcess.push_back(target);
+	    }
+	  }
+	}
+}
+for (int i = 0; i < (int)nextProcess.size(); ++i) {
+	_mask->set(nextProcess[i], false);
+}
+_process.swap(nextProcess);
+return _process.empty();
 }
 /// \brief Executes the algorithm.
 ///
 /// \pre init() must be called and at least one node should be added
 /// - The shortest path tree.
 /// - The distance of each node from the root(s).
 void start() {
 int num = countNodes(*graph) - 1;
 for (int i = 0; i < num; ++i) {
-	bool done = true;
+	if (processNextWeakRound()) break;
-	for (EdgeIt it(*graph); it != INVALID; ++it) {
-	  Node source = graph->source(it);
-	  Node target = graph->target(it);
-	  Value relaxed =
-	    OperationTraits::plus((*_dist)[source], (*length)[it]);
-	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
-	    _pred->set(target, it);
-	    _dist->set(target, relaxed);
-	    done = false;
-	  }
-	}
-	if (done) return;
 }
 }
 /// \brief Executes the algorithm and checks the negative cycles.
 ///
 /// - The shortest path tree.
 /// - The distance of each node from the root(s).
 bool checkedStart() {
 int num = countNodes(*graph);
 for (int i = 0; i < num; ++i) {
-	bool done = true;
+	if (processNextWeakRound()) return true;
-	for (EdgeIt it(*graph); it != INVALID; ++it) {
-	  Node source = graph->source(it);
-	  Node target = graph->target(it);
-	  Value relaxed =
-	    OperationTraits::plus((*_dist)[source], (*length)[it]);
-	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
-	    _pred->set(target, it);
-	    _dist->set(target, relaxed);
-	    done = false;
-	  }
-	}
-	if (done) return true;
 }
 return false;
+}
+/// \brief Executes the algorithm with path length limit.
+///
+/// \pre init() must be called and at least one node should be added
+/// with addSource() before using this function.
+///
+/// This method runs the %BelmannFord algorithm from the root node(s)
+/// in order to compute the shortest path with at most \c length edge
+/// long pathes to each node. The algorithm computes
+/// - The shortest path tree.
+/// - The limited distance of each node from the root(s).
+void limitedStart(int length) {
+for (int i = 0; i < length; ++i) {
+	if (processNextRound()) break;
+}
 }
 /// \brief Runs %BelmannFord algorithm from node \c s.
 ///
 /// This method runs the %BelmannFord algorithm from a root node \c s

changeset 1781	dca4c8a54e0a
parent 1765	f15b3c09481c
child 1782	cb405cda0205