1.1 --- a/lemon/bellman_ford.h Wed Mar 17 12:35:52 2010 +0100
1.2 +++ b/lemon/bellman_ford.h Sat Mar 06 14:35:12 2010 +0000
1.3 @@ -1,8 +1,8 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 - * Copyright (C) 2003-2008
1.11 + * Copyright (C) 2003-2010
1.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.14 *
1.15 @@ -36,7 +36,7 @@
1.16 namespace lemon {
1.17
1.18 /// \brief Default operation traits for the BellmanFord algorithm class.
1.19 - ///
1.20 + ///
1.21 /// This operation traits class defines all computational operations
1.22 /// and constants that are used in the Bellman-Ford algorithm.
1.23 /// The default implementation is based on the \c numeric_limits class.
1.24 @@ -45,7 +45,7 @@
1.25 ///
1.26 /// \see BellmanFordToleranceOperationTraits
1.27 template <
1.28 - typename V,
1.29 + typename V,
1.30 bool has_inf = std::numeric_limits<V>::has_infinity>
1.31 struct BellmanFordDefaultOperationTraits {
1.32 /// \brief Value type for the algorithm.
1.33 @@ -86,7 +86,7 @@
1.34 return left < right;
1.35 }
1.36 };
1.37 -
1.38 +
1.39 /// \brief Operation traits for the BellmanFord algorithm class
1.40 /// using tolerance.
1.41 ///
1.42 @@ -139,7 +139,7 @@
1.43 /// \param LEN The type of the length map.
1.44 template<typename GR, typename LEN>
1.45 struct BellmanFordDefaultTraits {
1.46 - /// The type of the digraph the algorithm runs on.
1.47 + /// The type of the digraph the algorithm runs on.
1.48 typedef GR Digraph;
1.49
1.50 /// \brief The type of the map that stores the arc lengths.
1.51 @@ -158,18 +158,18 @@
1.52 /// \see BellmanFordDefaultOperationTraits,
1.53 /// BellmanFordToleranceOperationTraits
1.54 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.55 -
1.56 - /// \brief The type of the map that stores the last arcs of the
1.57 +
1.58 + /// \brief The type of the map that stores the last arcs of the
1.59 /// shortest paths.
1.60 - ///
1.61 + ///
1.62 /// The type of the map that stores the last
1.63 /// arcs of the shortest paths.
1.64 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.65 typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.66
1.67 /// \brief Instantiates a \c PredMap.
1.68 - ///
1.69 - /// This function instantiates a \ref PredMap.
1.70 + ///
1.71 + /// This function instantiates a \ref PredMap.
1.72 /// \param g is the digraph to which we would like to define the
1.73 /// \ref PredMap.
1.74 static PredMap *createPredMap(const GR& g) {
1.75 @@ -184,19 +184,19 @@
1.76
1.77 /// \brief Instantiates a \c DistMap.
1.78 ///
1.79 - /// This function instantiates a \ref DistMap.
1.80 - /// \param g is the digraph to which we would like to define the
1.81 + /// This function instantiates a \ref DistMap.
1.82 + /// \param g is the digraph to which we would like to define the
1.83 /// \ref DistMap.
1.84 static DistMap *createDistMap(const GR& g) {
1.85 return new DistMap(g);
1.86 }
1.87
1.88 };
1.89 -
1.90 +
1.91 /// \brief %BellmanFord algorithm class.
1.92 ///
1.93 /// \ingroup shortest_path
1.94 - /// This class provides an efficient implementation of the Bellman-Ford
1.95 + /// This class provides an efficient implementation of the Bellman-Ford
1.96 /// algorithm. The maximum time complexity of the algorithm is
1.97 /// <tt>O(ne)</tt>.
1.98 ///
1.99 @@ -207,7 +207,7 @@
1.100 /// algorithm instead, since it is more efficient.
1.101 ///
1.102 /// The arc lengths are passed to the algorithm using a
1.103 - /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
1.104 + /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
1.105 /// kind of length. The type of the length values is determined by the
1.106 /// \ref concepts::ReadMap::Value "Value" type of the length map.
1.107 ///
1.108 @@ -237,7 +237,7 @@
1.109
1.110 ///The type of the underlying digraph.
1.111 typedef typename TR::Digraph Digraph;
1.112 -
1.113 +
1.114 /// \brief The type of the arc lengths.
1.115 typedef typename TR::LengthMap::Value Value;
1.116 /// \brief The type of the map that stores the arc lengths.
1.117 @@ -284,20 +284,20 @@
1.118 // Creates the maps if necessary.
1.119 void create_maps() {
1.120 if(!_pred) {
1.121 - _local_pred = true;
1.122 - _pred = Traits::createPredMap(*_gr);
1.123 + _local_pred = true;
1.124 + _pred = Traits::createPredMap(*_gr);
1.125 }
1.126 if(!_dist) {
1.127 - _local_dist = true;
1.128 - _dist = Traits::createDistMap(*_gr);
1.129 + _local_dist = true;
1.130 + _dist = Traits::createDistMap(*_gr);
1.131 }
1.132 if(!_mask) {
1.133 _mask = new MaskMap(*_gr);
1.134 }
1.135 }
1.136 -
1.137 +
1.138 public :
1.139 -
1.140 +
1.141 typedef BellmanFord Create;
1.142
1.143 /// \name Named Template Parameters
1.144 @@ -320,11 +320,11 @@
1.145 /// \c PredMap type.
1.146 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.147 template <class T>
1.148 - struct SetPredMap
1.149 + struct SetPredMap
1.150 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
1.151 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
1.152 };
1.153 -
1.154 +
1.155 template <class T>
1.156 struct SetDistMapTraits : public Traits {
1.157 typedef T DistMap;
1.158 @@ -341,7 +341,7 @@
1.159 /// \c DistMap type.
1.160 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.161 template <class T>
1.162 - struct SetDistMap
1.163 + struct SetDistMap
1.164 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
1.165 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
1.166 };
1.167 @@ -350,8 +350,8 @@
1.168 struct SetOperationTraitsTraits : public Traits {
1.169 typedef T OperationTraits;
1.170 };
1.171 -
1.172 - /// \brief \ref named-templ-param "Named parameter" for setting
1.173 +
1.174 + /// \brief \ref named-templ-param "Named parameter" for setting
1.175 /// \c OperationTraits type.
1.176 ///
1.177 /// \ref named-templ-param "Named parameter" for setting
1.178 @@ -363,15 +363,15 @@
1.179 typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
1.180 Create;
1.181 };
1.182 -
1.183 +
1.184 ///@}
1.185
1.186 protected:
1.187 -
1.188 +
1.189 BellmanFord() {}
1.190
1.191 - public:
1.192 -
1.193 + public:
1.194 +
1.195 /// \brief Constructor.
1.196 ///
1.197 /// Constructor.
1.198 @@ -381,7 +381,7 @@
1.199 _gr(&g), _length(&length),
1.200 _pred(0), _local_pred(false),
1.201 _dist(0), _local_dist(false), _mask(0) {}
1.202 -
1.203 +
1.204 ///Destructor.
1.205 ~BellmanFord() {
1.206 if(_local_pred) delete _pred;
1.207 @@ -408,8 +408,8 @@
1.208 /// \return <tt>(*this)</tt>
1.209 BellmanFord &predMap(PredMap &map) {
1.210 if(_local_pred) {
1.211 - delete _pred;
1.212 - _local_pred=false;
1.213 + delete _pred;
1.214 + _local_pred=false;
1.215 }
1.216 _pred = ↦
1.217 return *this;
1.218 @@ -426,8 +426,8 @@
1.219 /// \return <tt>(*this)</tt>
1.220 BellmanFord &distMap(DistMap &map) {
1.221 if(_local_dist) {
1.222 - delete _dist;
1.223 - _local_dist=false;
1.224 + delete _dist;
1.225 + _local_dist=false;
1.226 }
1.227 _dist = ↦
1.228 return *this;
1.229 @@ -445,28 +445,28 @@
1.230 ///@{
1.231
1.232 /// \brief Initializes the internal data structures.
1.233 - ///
1.234 + ///
1.235 /// Initializes the internal data structures. The optional parameter
1.236 /// is the initial distance of each node.
1.237 void init(const Value value = OperationTraits::infinity()) {
1.238 create_maps();
1.239 for (NodeIt it(*_gr); it != INVALID; ++it) {
1.240 - _pred->set(it, INVALID);
1.241 - _dist->set(it, value);
1.242 + _pred->set(it, INVALID);
1.243 + _dist->set(it, value);
1.244 }
1.245 _process.clear();
1.246 if (OperationTraits::less(value, OperationTraits::infinity())) {
1.247 - for (NodeIt it(*_gr); it != INVALID; ++it) {
1.248 - _process.push_back(it);
1.249 - _mask->set(it, true);
1.250 - }
1.251 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.252 + _process.push_back(it);
1.253 + _mask->set(it, true);
1.254 + }
1.255 } else {
1.256 - for (NodeIt it(*_gr); it != INVALID; ++it) {
1.257 - _mask->set(it, false);
1.258 - }
1.259 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.260 + _mask->set(it, false);
1.261 + }
1.262 }
1.263 }
1.264 -
1.265 +
1.266 /// \brief Adds a new source node.
1.267 ///
1.268 /// This function adds a new source node. The optional second parameter
1.269 @@ -474,8 +474,8 @@
1.270 void addSource(Node source, Value dst = OperationTraits::zero()) {
1.271 _dist->set(source, dst);
1.272 if (!(*_mask)[source]) {
1.273 - _process.push_back(source);
1.274 - _mask->set(source, true);
1.275 + _process.push_back(source);
1.276 + _mask->set(source, true);
1.277 }
1.278 }
1.279
1.280 @@ -500,26 +500,26 @@
1.281 /// \see ActiveIt
1.282 bool processNextRound() {
1.283 for (int i = 0; i < int(_process.size()); ++i) {
1.284 - _mask->set(_process[i], false);
1.285 + _mask->set(_process[i], false);
1.286 }
1.287 std::vector<Node> nextProcess;
1.288 std::vector<Value> values(_process.size());
1.289 for (int i = 0; i < int(_process.size()); ++i) {
1.290 - values[i] = (*_dist)[_process[i]];
1.291 + values[i] = (*_dist)[_process[i]];
1.292 }
1.293 for (int i = 0; i < int(_process.size()); ++i) {
1.294 - for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.295 - Node target = _gr->target(it);
1.296 - Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
1.297 - if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.298 - _pred->set(target, it);
1.299 - _dist->set(target, relaxed);
1.300 - if (!(*_mask)[target]) {
1.301 - _mask->set(target, true);
1.302 - nextProcess.push_back(target);
1.303 - }
1.304 - }
1.305 - }
1.306 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.307 + Node target = _gr->target(it);
1.308 + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
1.309 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.310 + _pred->set(target, it);
1.311 + _dist->set(target, relaxed);
1.312 + if (!(*_mask)[target]) {
1.313 + _mask->set(target, true);
1.314 + nextProcess.push_back(target);
1.315 + }
1.316 + }
1.317 + }
1.318 }
1.319 _process.swap(nextProcess);
1.320 return _process.empty();
1.321 @@ -541,23 +541,23 @@
1.322 /// \see ActiveIt
1.323 bool processNextWeakRound() {
1.324 for (int i = 0; i < int(_process.size()); ++i) {
1.325 - _mask->set(_process[i], false);
1.326 + _mask->set(_process[i], false);
1.327 }
1.328 std::vector<Node> nextProcess;
1.329 for (int i = 0; i < int(_process.size()); ++i) {
1.330 - for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.331 - Node target = _gr->target(it);
1.332 - Value relaxed =
1.333 - OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
1.334 - if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.335 - _pred->set(target, it);
1.336 - _dist->set(target, relaxed);
1.337 - if (!(*_mask)[target]) {
1.338 - _mask->set(target, true);
1.339 - nextProcess.push_back(target);
1.340 - }
1.341 - }
1.342 - }
1.343 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.344 + Node target = _gr->target(it);
1.345 + Value relaxed =
1.346 + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
1.347 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.348 + _pred->set(target, it);
1.349 + _dist->set(target, relaxed);
1.350 + if (!(*_mask)[target]) {
1.351 + _mask->set(target, true);
1.352 + nextProcess.push_back(target);
1.353 + }
1.354 + }
1.355 + }
1.356 }
1.357 _process.swap(nextProcess);
1.358 return _process.empty();
1.359 @@ -579,7 +579,7 @@
1.360 void start() {
1.361 int num = countNodes(*_gr) - 1;
1.362 for (int i = 0; i < num; ++i) {
1.363 - if (processNextWeakRound()) break;
1.364 + if (processNextWeakRound()) break;
1.365 }
1.366 }
1.367
1.368 @@ -591,18 +591,18 @@
1.369 /// in order to compute the shortest path to each node and also checks
1.370 /// if the digraph contains cycles with negative total length.
1.371 ///
1.372 - /// The algorithm computes
1.373 + /// The algorithm computes
1.374 /// - the shortest path tree (forest),
1.375 /// - the distance of each node from the root(s).
1.376 - ///
1.377 + ///
1.378 /// \return \c false if there is a negative cycle in the digraph.
1.379 ///
1.380 /// \pre init() must be called and at least one root node should be
1.381 - /// added with addSource() before using this function.
1.382 + /// added with addSource() before using this function.
1.383 bool checkedStart() {
1.384 int num = countNodes(*_gr);
1.385 for (int i = 0; i < num; ++i) {
1.386 - if (processNextWeakRound()) return true;
1.387 + if (processNextWeakRound()) return true;
1.388 }
1.389 return _process.empty();
1.390 }
1.391 @@ -626,15 +626,15 @@
1.392 /// and build the path manually.
1.393 ///
1.394 /// \pre init() must be called and at least one root node should be
1.395 - /// added with addSource() before using this function.
1.396 + /// added with addSource() before using this function.
1.397 void limitedStart(int num) {
1.398 for (int i = 0; i < num; ++i) {
1.399 - if (processNextRound()) break;
1.400 + if (processNextRound()) break;
1.401 }
1.402 }
1.403 -
1.404 +
1.405 /// \brief Runs the algorithm from the given root node.
1.406 - ///
1.407 + ///
1.408 /// This method runs the Bellman-Ford algorithm from the given root
1.409 /// node \c s in order to compute the shortest path to each node.
1.410 ///
1.411 @@ -653,10 +653,10 @@
1.412 addSource(s);
1.413 start();
1.414 }
1.415 -
1.416 +
1.417 /// \brief Runs the algorithm from the given root node with arc
1.418 /// number limit.
1.419 - ///
1.420 + ///
1.421 /// This method runs the Bellman-Ford algorithm from the given root
1.422 /// node \c s in order to compute the shortest path distance for each
1.423 /// node using only the paths consisting of at most \c num arcs.
1.424 @@ -682,7 +682,7 @@
1.425 addSource(s);
1.426 limitedStart(num);
1.427 }
1.428 -
1.429 +
1.430 ///@}
1.431
1.432 /// \brief LEMON iterator for getting the active nodes.
1.433 @@ -697,7 +697,7 @@
1.434 /// \brief Constructor.
1.435 ///
1.436 /// Constructor for getting the active nodes of the given BellmanFord
1.437 - /// instance.
1.438 + /// instance.
1.439 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
1.440 {
1.441 _index = _algorithm->_process.size() - 1;
1.442 @@ -711,7 +711,7 @@
1.443 /// \brief Conversion to \c Node.
1.444 ///
1.445 /// Conversion to \c Node.
1.446 - operator Node() const {
1.447 + operator Node() const {
1.448 return _index >= 0 ? _algorithm->_process[_index] : INVALID;
1.449 }
1.450
1.451 @@ -720,33 +720,33 @@
1.452 /// Increment operator.
1.453 ActiveIt& operator++() {
1.454 --_index;
1.455 - return *this;
1.456 + return *this;
1.457 }
1.458
1.459 - bool operator==(const ActiveIt& it) const {
1.460 - return static_cast<Node>(*this) == static_cast<Node>(it);
1.461 + bool operator==(const ActiveIt& it) const {
1.462 + return static_cast<Node>(*this) == static_cast<Node>(it);
1.463 }
1.464 - bool operator!=(const ActiveIt& it) const {
1.465 - return static_cast<Node>(*this) != static_cast<Node>(it);
1.466 + bool operator!=(const ActiveIt& it) const {
1.467 + return static_cast<Node>(*this) != static_cast<Node>(it);
1.468 }
1.469 - bool operator<(const ActiveIt& it) const {
1.470 - return static_cast<Node>(*this) < static_cast<Node>(it);
1.471 + bool operator<(const ActiveIt& it) const {
1.472 + return static_cast<Node>(*this) < static_cast<Node>(it);
1.473 }
1.474 -
1.475 +
1.476 private:
1.477 const BellmanFord* _algorithm;
1.478 int _index;
1.479 };
1.480 -
1.481 +
1.482 /// \name Query Functions
1.483 /// The result of the Bellman-Ford algorithm can be obtained using these
1.484 /// functions.\n
1.485 /// Either \ref run() or \ref init() should be called before using them.
1.486 -
1.487 +
1.488 ///@{
1.489
1.490 /// \brief The shortest path to the given node.
1.491 - ///
1.492 + ///
1.493 /// Gives back the shortest path to the given node from the root(s).
1.494 ///
1.495 /// \warning \c t should be reached from the root(s).
1.496 @@ -757,7 +757,7 @@
1.497 {
1.498 return Path(*_gr, *_pred, t);
1.499 }
1.500 -
1.501 +
1.502 /// \brief The distance of the given node from the root(s).
1.503 ///
1.504 /// Returns the distance of the given node from the root(s).
1.505 @@ -797,10 +797,10 @@
1.506 ///
1.507 /// \pre Either \ref run() or \ref init() must be called before
1.508 /// using this function.
1.509 - Node predNode(Node v) const {
1.510 - return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
1.511 + Node predNode(Node v) const {
1.512 + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
1.513 }
1.514 -
1.515 +
1.516 /// \brief Returns a const reference to the node map that stores the
1.517 /// distances of the nodes.
1.518 ///
1.519 @@ -810,7 +810,7 @@
1.520 /// \pre Either \ref run() or \ref init() must be called before
1.521 /// using this function.
1.522 const DistMap &distMap() const { return *_dist;}
1.523 -
1.524 +
1.525 /// \brief Returns a const reference to the node map that stores the
1.526 /// predecessor arcs.
1.527 ///
1.528 @@ -820,7 +820,7 @@
1.529 /// \pre Either \ref run() or \ref init() must be called before
1.530 /// using this function.
1.531 const PredMap &predMap() const { return *_pred; }
1.532 -
1.533 +
1.534 /// \brief Checks if a node is reached from the root(s).
1.535 ///
1.536 /// Returns \c true if \c v is reached from the root(s).
1.537 @@ -832,7 +832,7 @@
1.538 }
1.539
1.540 /// \brief Gives back a negative cycle.
1.541 - ///
1.542 + ///
1.543 /// This function gives back a directed cycle with negative total
1.544 /// length if the algorithm has already found one.
1.545 /// Otherwise it gives back an empty path.
1.546 @@ -859,10 +859,10 @@
1.547 }
1.548 return cycle;
1.549 }
1.550 -
1.551 +
1.552 ///@}
1.553 };
1.554 -
1.555 +
1.556 /// \brief Default traits class of bellmanFord() function.
1.557 ///
1.558 /// Default traits class of bellmanFord() function.
1.559 @@ -870,7 +870,7 @@
1.560 /// \tparam LEN The type of the length map.
1.561 template <typename GR, typename LEN>
1.562 struct BellmanFordWizardDefaultTraits {
1.563 - /// The type of the digraph the algorithm runs on.
1.564 + /// The type of the digraph the algorithm runs on.
1.565 typedef GR Digraph;
1.566
1.567 /// \brief The type of the map that stores the arc lengths.
1.568 @@ -892,13 +892,13 @@
1.569
1.570 /// \brief The type of the map that stores the last
1.571 /// arcs of the shortest paths.
1.572 - ///
1.573 + ///
1.574 /// The type of the map that stores the last arcs of the shortest paths.
1.575 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.576 typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.577
1.578 /// \brief Instantiates a \c PredMap.
1.579 - ///
1.580 + ///
1.581 /// This function instantiates a \ref PredMap.
1.582 /// \param g is the digraph to which we would like to define the
1.583 /// \ref PredMap.
1.584 @@ -914,7 +914,7 @@
1.585
1.586 /// \brief Instantiates a \c DistMap.
1.587 ///
1.588 - /// This function instantiates a \ref DistMap.
1.589 + /// This function instantiates a \ref DistMap.
1.590 /// \param g is the digraph to which we would like to define the
1.591 /// \ref DistMap.
1.592 static DistMap *createDistMap(const GR &g) {
1.593 @@ -927,14 +927,14 @@
1.594 ///It must meet the \ref concepts::Path "Path" concept.
1.595 typedef lemon::Path<Digraph> Path;
1.596 };
1.597 -
1.598 +
1.599 /// \brief Default traits class used by BellmanFordWizard.
1.600 ///
1.601 /// Default traits class used by BellmanFordWizard.
1.602 /// \tparam GR The type of the digraph.
1.603 /// \tparam LEN The type of the length map.
1.604 template <typename GR, typename LEN>
1.605 - class BellmanFordWizardBase
1.606 + class BellmanFordWizardBase
1.607 : public BellmanFordWizardDefaultTraits<GR, LEN> {
1.608
1.609 typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
1.610 @@ -957,26 +957,26 @@
1.611
1.612 public:
1.613 /// Constructor.
1.614 -
1.615 +
1.616 /// This constructor does not require parameters, it initiates
1.617 /// all of the attributes to default values \c 0.
1.618 BellmanFordWizardBase() :
1.619 _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.620
1.621 /// Constructor.
1.622 -
1.623 +
1.624 /// This constructor requires two parameters,
1.625 /// others are initiated to \c 0.
1.626 /// \param gr The digraph the algorithm runs on.
1.627 /// \param len The length map.
1.628 - BellmanFordWizardBase(const GR& gr,
1.629 - const LEN& len) :
1.630 - _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
1.631 - _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
1.632 + BellmanFordWizardBase(const GR& gr,
1.633 + const LEN& len) :
1.634 + _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
1.635 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
1.636 _pred(0), _dist(0), _path(0), _di(0) {}
1.637
1.638 };
1.639 -
1.640 +
1.641 /// \brief Auxiliary class for the function-type interface of the
1.642 /// \ref BellmanFord "Bellman-Ford" algorithm.
1.643 ///
1.644 @@ -1001,7 +1001,7 @@
1.645 typedef typename Digraph::NodeIt NodeIt;
1.646 typedef typename Digraph::Arc Arc;
1.647 typedef typename Digraph::OutArcIt ArcIt;
1.648 -
1.649 +
1.650 typedef typename TR::LengthMap LengthMap;
1.651 typedef typename LengthMap::Value Value;
1.652 typedef typename TR::PredMap PredMap;
1.653 @@ -1018,7 +1018,7 @@
1.654 /// These parameters will be the default values for the traits class.
1.655 /// \param gr The digraph the algorithm runs on.
1.656 /// \param len The length map.
1.657 - BellmanFordWizard(const Digraph& gr, const LengthMap& len)
1.658 + BellmanFordWizard(const Digraph& gr, const LengthMap& len)
1.659 : TR(gr, len) {}
1.660
1.661 /// \brief Copy constructor
1.662 @@ -1027,12 +1027,12 @@
1.663 ~BellmanFordWizard() {}
1.664
1.665 /// \brief Runs the Bellman-Ford algorithm from the given source node.
1.666 - ///
1.667 + ///
1.668 /// This method runs the Bellman-Ford algorithm from the given source
1.669 /// node in order to compute the shortest path to each node.
1.670 void run(Node s) {
1.671 - BellmanFord<Digraph,LengthMap,TR>
1.672 - bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.673 + BellmanFord<Digraph,LengthMap,TR>
1.674 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.675 *reinterpret_cast<const LengthMap*>(Base::_length));
1.676 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.677 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.678 @@ -1067,7 +1067,7 @@
1.679 static PredMap *createPredMap(const Digraph &) { return 0; };
1.680 SetPredMapBase(const TR &b) : TR(b) {}
1.681 };
1.682 -
1.683 +
1.684 /// \brief \ref named-templ-param "Named parameter" for setting
1.685 /// the predecessor map.
1.686 ///
1.687 @@ -1078,14 +1078,14 @@
1.688 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.689 return BellmanFordWizard<SetPredMapBase<T> >(*this);
1.690 }
1.691 -
1.692 +
1.693 template<class T>
1.694 struct SetDistMapBase : public Base {
1.695 typedef T DistMap;
1.696 static DistMap *createDistMap(const Digraph &) { return 0; };
1.697 SetDistMapBase(const TR &b) : TR(b) {}
1.698 };
1.699 -
1.700 +
1.701 /// \brief \ref named-templ-param "Named parameter" for setting
1.702 /// the distance map.
1.703 ///
1.704 @@ -1126,9 +1126,9 @@
1.705 Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1.706 return *this;
1.707 }
1.708 -
1.709 +
1.710 };
1.711 -
1.712 +
1.713 /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
1.714 /// algorithm.
1.715 ///
1.716 @@ -1136,8 +1136,8 @@
1.717 /// Function type interface for the \ref BellmanFord "Bellman-Ford"
1.718 /// algorithm.
1.719 ///
1.720 - /// This function also has several \ref named-templ-func-param
1.721 - /// "named parameters", they are declared as the members of class
1.722 + /// This function also has several \ref named-templ-func-param
1.723 + /// "named parameters", they are declared as the members of class
1.724 /// \ref BellmanFordWizard.
1.725 /// The following examples show how to use these parameters.
1.726 /// \code
1.727 @@ -1154,7 +1154,7 @@
1.728 template<typename GR, typename LEN>
1.729 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
1.730 bellmanFord(const GR& digraph,
1.731 - const LEN& length)
1.732 + const LEN& length)
1.733 {
1.734 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
1.735 }