Changeset 697:9496ed797f20 in lemon-main
- Timestamp:
- 08/02/09 13:24:46 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r696 r697 17 17 */ 18 18 19 #ifndef LEMON_BEL MANN_FORD_H20 #define LEMON_BEL MANN_FORD_H19 #ifndef LEMON_BELLMAN_FORD_H 20 #define LEMON_BELLMAN_FORD_H 21 21 22 22 /// \ingroup shortest_path 23 23 /// \file 24 24 /// \brief Bellman-Ford algorithm. 25 ///26 25 27 26 #include <lemon/bits/path_dump.h> … … 29 28 #include <lemon/error.h> 30 29 #include <lemon/maps.h> 30 #include <lemon/path.h> 31 31 32 32 #include <limits> … … 36 36 /// \brief Default OperationTraits for the BellmanFord algorithm class. 37 37 /// 38 /// It defines all computational operations and constants which are39 /// used in the Bellman-Ford algorithm. The default implementation40 /// is based on the numeric_limits class. If the numeric type does not41 /// have infinity value then the maximum value is used as extremal42 /// infinity value.38 /// This operation traits class defines all computational operations 39 /// and constants that are used in the Bellman-Ford algorithm. 40 /// The default implementation is based on the \c numeric_limits class. 41 /// If the numeric type does not have infinity value, then the maximum 42 /// value is used as extremal infinity value. 43 43 template < 44 typename V alue,45 bool has_inf inity = std::numeric_limits<Value>::has_infinity>44 typename V, 45 bool has_inf = std::numeric_limits<V>::has_infinity> 46 46 struct BellmanFordDefaultOperationTraits { 47 /// \e 48 typedef V Value; 47 49 /// \brief Gives back the zero value of the type. 48 50 static Value zero() { … … 57 59 return left + right; 58 60 } 59 /// \brief Gives back true only if the first value less than the second. 61 /// \brief Gives back \c true only if the first value is less than 62 /// the second. 60 63 static bool less(const Value& left, const Value& right) { 61 64 return left < right; … … 63 66 }; 64 67 65 template <typename Value> 66 struct BellmanFordDefaultOperationTraits<Value, false> { 68 template <typename V> 69 struct BellmanFordDefaultOperationTraits<V, false> { 70 typedef V Value; 67 71 static Value zero() { 68 72 return static_cast<Value>(0); … … 83 87 /// 84 88 /// Default traits class of BellmanFord class. 85 /// \param _Digraph Digraph type.86 /// \param _LegthMap Type oflength map.87 template< class _Digraph, class _LengthMap>89 /// \param GR The type of the digraph. 90 /// \param LEN The type of the length map. 91 template<typename GR, typename LEN> 88 92 struct BellmanFordDefaultTraits { 89 /// The digraph typethe algorithm runs on.90 typedef _DigraphDigraph;93 /// The type of the digraph the algorithm runs on. 94 typedef GR Digraph; 91 95 92 96 /// \brief The type of the map that stores the arc lengths. 93 97 /// 94 98 /// The type of the map that stores the arc lengths. 95 /// It must meetthe \ref concepts::ReadMap "ReadMap" concept.96 typedef _LengthMapLengthMap;97 98 // The type of the length of the arcs.99 typedef typename _LengthMap::Value Value;99 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 100 typedef LEN LengthMap; 101 102 /// The type of the arc lengths. 103 typedef typename LEN::Value Value; 100 104 101 105 /// \brief Operation traits for Bellman-Ford algorithm. 102 106 /// 103 /// It defines the infinity type on the given Value type104 /// and the used operation.107 /// It defines the used operations and the infinity value for the 108 /// given \c Value type. 105 109 /// \see BellmanFordDefaultOperationTraits 106 110 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; … … 111 115 /// The type of the map that stores the last 112 116 /// arcs of the shortest paths. 113 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 114 /// 115 typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap; 116 117 /// \brief Instantiates a PredMap. 117 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 118 typedef typename GR::template NodeMap<typename GR::Arc> PredMap; 119 120 /// \brief Instantiates a \c PredMap. 118 121 /// 119 122 /// This function instantiates a \ref PredMap. 120 /// \param digraph is the digraph, to which we would like to define the PredMap. 121 static PredMap *createPredMap(const _Digraph& digraph) { 122 return new PredMap(digraph); 123 } 124 125 /// \brief The type of the map that stores the dists of the nodes. 126 /// 127 /// The type of the map that stores the dists of the nodes. 128 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 129 /// 130 typedef typename Digraph::template NodeMap<typename _LengthMap::Value> 131 DistMap; 132 133 /// \brief Instantiates a DistMap. 123 /// \param g is the digraph to which we would like to define the 124 /// \ref PredMap. 125 static PredMap *createPredMap(const GR& g) { 126 return new PredMap(g); 127 } 128 129 /// \brief The type of the map that stores the distances of the nodes. 130 /// 131 /// The type of the map that stores the distances of the nodes. 132 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 133 typedef typename GR::template NodeMap<typename LEN::Value> DistMap; 134 135 /// \brief Instantiates a \c DistMap. 134 136 /// 135 137 /// This function instantiates a \ref DistMap. 136 /// \param digraph is the digraph,to which we would like to define the137 /// \ref DistMap 138 static DistMap *createDistMap(const _Digraph& digraph) {139 return new DistMap( digraph);138 /// \param g is the digraph to which we would like to define the 139 /// \ref DistMap. 140 static DistMap *createDistMap(const GR& g) { 141 return new DistMap(g); 140 142 } 141 143 … … 145 147 /// 146 148 /// \ingroup shortest_path 147 /// This class provides an efficient implementation of \c Bellman-Ford 148 /// algorithm. The arc lengths are passed to the algorithm using a 149 /// This class provides an efficient implementation of the Bellman-Ford 150 /// algorithm. The maximum time complexity of the algorithm is 151 /// <tt>O(ne)</tt>. 152 /// 153 /// The Bellman-Ford algorithm solves the single-source shortest path 154 /// problem when the arcs can have negative lengths, but the digraph 155 /// should not contain directed cycles with negative total length. 156 /// If all arc costs are non-negative, consider to use the Dijkstra 157 /// algorithm instead, since it is more efficient. 158 /// 159 /// The arc lengths are passed to the algorithm using a 149 160 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 150 /// kind of length. 151 /// 152 /// The Bellman-Ford algorithm solves the shortest path from one node 153 /// problem when the arcs can have negative length but the digraph should 154 /// not contain cycles with negative sum of length. If we can assume 155 /// that all arc is non-negative in the digraph then the dijkstra algorithm 156 /// should be used rather. 157 /// 158 /// The maximal time complexity of the algorithm is \f$ O(ne) \f$. 159 /// 160 /// The type of the length is determined by the 161 /// \ref concepts::ReadMap::Value "Value" of the length map. 162 /// 163 /// \param _Digraph The digraph type the algorithm runs on. The default value 164 /// is \ref ListDigraph. The value of _Digraph is not used directly by 165 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 166 /// \param _LengthMap This read-only ArcMap determines the lengths of the 167 /// arcs. The default map type is \ref concepts::Digraph::ArcMap 168 /// "Digraph::ArcMap<int>". The value of _LengthMap is not used directly 169 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 170 /// \param _Traits Traits class to set various data types used by the 171 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits 172 /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>". See \ref 173 /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits 174 /// class. 161 /// kind of length. The type of the length values is determined by the 162 /// \ref concepts::ReadMap::Value "Value" type of the length map. 163 /// 164 /// There is also a \ref bellmanFord() "function-type interface" for the 165 /// Bellman-Ford algorithm, which is convenient in the simplier cases and 166 /// it can be used easier. 167 /// 168 /// \tparam GR The type of the digraph the algorithm runs on. 169 /// The default type is \ref ListDigraph. 170 /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies 171 /// the lengths of the arcs. The default map type is 172 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 175 173 #ifdef DOXYGEN 176 template <typename _Digraph, typename _LengthMap, typename _Traits>174 template <typename GR, typename LEN, typename TR> 177 175 #else 178 template <typename _Digraph,179 typename _LengthMap=typename _Digraph::template ArcMap<int>,180 typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >176 template <typename GR=ListDigraph, 177 typename LEN=typename GR::template ArcMap<int>, 178 typename TR=BellmanFordDefaultTraits<GR,LEN> > 181 179 #endif 182 180 class BellmanFord { 183 181 public: 184 182 185 typedef _Traits Traits;186 183 ///The type of the underlying digraph. 187 typedef typename _Traits::Digraph Digraph; 184 typedef typename TR::Digraph Digraph; 185 186 /// \brief The type of the arc lengths. 187 typedef typename TR::LengthMap::Value Value; 188 /// \brief The type of the map that stores the arc lengths. 189 typedef typename TR::LengthMap LengthMap; 190 /// \brief The type of the map that stores the last 191 /// arcs of the shortest paths. 192 typedef typename TR::PredMap PredMap; 193 /// \brief The type of the map that stores the distances of the nodes. 194 typedef typename TR::DistMap DistMap; 195 /// The type of the paths. 196 typedef PredMapPath<Digraph, PredMap> Path; 197 ///\brief The \ref BellmanFordDefaultOperationTraits 198 /// "operation traits class" of the algorithm. 199 typedef typename TR::OperationTraits OperationTraits; 200 201 ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm. 202 typedef TR Traits; 203 204 private: 188 205 189 206 typedef typename Digraph::Node Node; … … 191 208 typedef typename Digraph::Arc Arc; 192 209 typedef typename Digraph::OutArcIt OutArcIt; 193 194 /// \brief The type of the length of the arcs. 195 typedef typename _Traits::LengthMap::Value Value; 196 /// \brief The type of the map that stores the arc lengths. 197 typedef typename _Traits::LengthMap LengthMap; 198 /// \brief The type of the map that stores the last 199 /// arcs of the shortest paths. 200 typedef typename _Traits::PredMap PredMap; 201 /// \brief The type of the map that stores the dists of the nodes. 202 typedef typename _Traits::DistMap DistMap; 203 /// \brief The operation traits. 204 typedef typename _Traits::OperationTraits OperationTraits; 205 private: 206 /// Pointer to the underlying digraph. 207 const Digraph *digraph; 208 /// Pointer to the length map 209 const LengthMap *length; 210 ///Pointer to the map of predecessors arcs. 210 211 // Pointer to the underlying digraph. 212 const Digraph *_gr; 213 // Pointer to the length map 214 const LengthMap *_length; 215 // Pointer to the map of predecessors arcs. 211 216 PredMap *_pred; 212 // /Indicates if \ref _pred is locally allocated (\ctrue) or not.213 bool local_pred;214 // /Pointer to the map of distances.217 // Indicates if _pred is locally allocated (true) or not. 218 bool _local_pred; 219 // Pointer to the map of distances. 215 220 DistMap *_dist; 216 // /Indicates if \ref _dist is locally allocated (\ctrue) or not.217 bool local_dist;221 // Indicates if _dist is locally allocated (true) or not. 222 bool _local_dist; 218 223 219 224 typedef typename Digraph::template NodeMap<bool> MaskMap; … … 222 227 std::vector<Node> _process; 223 228 224 // /Creates the maps if necessary.229 // Creates the maps if necessary. 225 230 void create_maps() { 226 231 if(!_pred) { 227 local_pred = true;228 _pred = Traits::createPredMap(* digraph);232 _local_pred = true; 233 _pred = Traits::createPredMap(*_gr); 229 234 } 230 235 if(!_dist) { 231 local_dist = true;232 _dist = Traits::createDistMap(* digraph);233 } 234 _mask = new MaskMap(* digraph, false);236 _local_dist = true; 237 _dist = Traits::createDistMap(*_gr); 238 } 239 _mask = new MaskMap(*_gr, false); 235 240 } 236 241 … … 239 244 typedef BellmanFord Create; 240 245 241 /// \name Named template parameters246 /// \name Named Template Parameters 242 247 243 248 ///@{ 244 249 245 250 template <class T> 246 struct DefPredMapTraits : public Traits {251 struct SetPredMapTraits : public Traits { 247 252 typedef T PredMap; 248 253 static PredMap *createPredMap(const Digraph&) { … … 252 257 }; 253 258 254 /// \brief \ref named-templ-param "Named parameter" for setting PredMap 255 /// type 256 /// \ref named-templ-param "Named parameter" for setting PredMap type 257 /// 259 /// \brief \ref named-templ-param "Named parameter" for setting 260 /// \c PredMap type. 261 /// 262 /// \ref named-templ-param "Named parameter" for setting 263 /// \c PredMap type. 264 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 258 265 template <class T> 259 266 struct SetPredMap 260 : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {261 typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;267 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { 268 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; 262 269 }; 263 270 264 271 template <class T> 265 struct DefDistMapTraits : public Traits {272 struct SetDistMapTraits : public Traits { 266 273 typedef T DistMap; 267 274 static DistMap *createDistMap(const Digraph&) { … … 271 278 }; 272 279 273 /// \brief \ref named-templ-param "Named parameter" for setting DistMap 274 /// type 275 /// 276 /// \ref named-templ-param "Named parameter" for setting DistMap type 277 /// 280 /// \brief \ref named-templ-param "Named parameter" for setting 281 /// \c DistMap type. 282 /// 283 /// \ref named-templ-param "Named parameter" for setting 284 /// \c DistMap type. 285 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 278 286 template <class T> 279 287 struct SetDistMap 280 : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {281 typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;288 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { 289 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; 282 290 }; 283 291 284 292 template <class T> 285 struct DefOperationTraitsTraits : public Traits {293 struct SetOperationTraitsTraits : public Traits { 286 294 typedef T OperationTraits; 287 295 }; 288 296 289 297 /// \brief \ref named-templ-param "Named parameter" for setting 290 /// OperationTraits type 291 /// 292 /// \ref named-templ-param "Named parameter" for setting OperationTraits 293 /// type 298 /// \c OperationTraits type. 299 /// 300 /// \ref named-templ-param "Named parameter" for setting 301 /// \c OperationTraits type. 302 /// For more information see \ref BellmanFordDefaultOperationTraits. 294 303 template <class T> 295 304 struct SetOperationTraits 296 : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {297 typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >305 : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > { 306 typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > 298 307 Create; 299 308 }; … … 309 318 /// \brief Constructor. 310 319 /// 311 /// \param _graph the digraph the algorithm will run on. 312 /// \param _length the length map used by the algorithm. 313 BellmanFord(const Digraph& _graph, const LengthMap& _length) : 314 digraph(&_graph), length(&_length), 315 _pred(0), local_pred(false), 316 _dist(0), local_dist(false), _mask(0) {} 320 /// Constructor. 321 /// \param g The digraph the algorithm runs on. 322 /// \param length The length map used by the algorithm. 323 BellmanFord(const Digraph& g, const LengthMap& length) : 324 _gr(&g), _length(&length), 325 _pred(0), _local_pred(false), 326 _dist(0), _local_dist(false), _mask(0) {} 317 327 318 328 ///Destructor. 319 329 ~BellmanFord() { 320 if( local_pred) delete _pred;321 if( local_dist) delete _dist;330 if(_local_pred) delete _pred; 331 if(_local_dist) delete _dist; 322 332 if(_mask) delete _mask; 323 333 } … … 326 336 /// 327 337 /// Sets the length map. 328 /// \return \c (*this)329 BellmanFord &lengthMap(const LengthMap &m ) {330 length = &m;338 /// \return <tt>(*this)</tt> 339 BellmanFord &lengthMap(const LengthMap &map) { 340 _length = ↦ 331 341 return *this; 332 342 } 333 343 334 /// \brief Sets the map storing the predecessor arcs. 335 /// 336 /// Sets the map storing the predecessor arcs. 337 /// If you don't use this function before calling \ref run(), 338 /// it will allocate one. The destuctor deallocates this 339 /// automatically allocated map, of course. 340 /// \return \c (*this) 341 BellmanFord &predMap(PredMap &m) { 342 if(local_pred) { 344 /// \brief Sets the map that stores the predecessor arcs. 345 /// 346 /// Sets the map that stores the predecessor arcs. 347 /// If you don't use this function before calling \ref run() 348 /// or \ref init(), an instance will be allocated automatically. 349 /// The destructor deallocates this automatically allocated map, 350 /// of course. 351 /// \return <tt>(*this)</tt> 352 BellmanFord &predMap(PredMap &map) { 353 if(_local_pred) { 343 354 delete _pred; 344 local_pred=false;345 } 346 _pred = &m ;355 _local_pred=false; 356 } 357 _pred = ↦ 347 358 return *this; 348 359 } 349 360 350 /// \brief Sets the map storing the distances calculated by the algorithm. 351 /// 352 /// Sets the map storing the distances calculated by the algorithm. 353 /// If you don't use this function before calling \ref run(), 354 /// it will allocate one. The destuctor deallocates this 355 /// automatically allocated map, of course. 356 /// \return \c (*this) 357 BellmanFord &distMap(DistMap &m) { 358 if(local_dist) { 361 /// \brief Sets the map that stores the distances of the nodes. 362 /// 363 /// Sets the map that stores the distances of the nodes calculated 364 /// by the algorithm. 365 /// If you don't use this function before calling \ref run() 366 /// or \ref init(), an instance will be allocated automatically. 367 /// The destructor deallocates this automatically allocated map, 368 /// of course. 369 /// \return <tt>(*this)</tt> 370 BellmanFord &distMap(DistMap &map) { 371 if(_local_dist) { 359 372 delete _dist; 360 local_dist=false;361 } 362 _dist = &m ;373 _local_dist=false; 374 } 375 _dist = ↦ 363 376 return *this; 364 377 } 365 378 366 /// \name Execution control 367 /// The simplest way to execute the algorithm is to use 368 /// one of the member functions called \c run(...). 369 /// \n 370 /// If you need more control on the execution, 371 /// first you must call \ref init(), then you can add several source nodes 372 /// with \ref addSource(). 373 /// Finally \ref start() will perform the actual path 374 /// computation. 379 /// \name Execution Control 380 /// The simplest way to execute the Bellman-Ford algorithm is to use 381 /// one of the member functions called \ref run().\n 382 /// If you need better control on the execution, you have to call 383 /// \ref init() first, then you can add several source nodes 384 /// with \ref addSource(). Finally the actual path computation can be 385 /// performed with \ref start(), \ref checkedStart() or 386 /// \ref limitedStart(). 375 387 376 388 ///@{ … … 378 390 /// \brief Initializes the internal data structures. 379 391 /// 380 /// Initializes the internal data structures. 392 /// Initializes the internal data structures. The optional parameter 393 /// is the initial distance of each node. 381 394 void init(const Value value = OperationTraits::infinity()) { 382 395 create_maps(); 383 for (NodeIt it(* digraph); it != INVALID; ++it) {396 for (NodeIt it(*_gr); it != INVALID; ++it) { 384 397 _pred->set(it, INVALID); 385 398 _dist->set(it, value); … … 387 400 _process.clear(); 388 401 if (OperationTraits::less(value, OperationTraits::infinity())) { 389 for (NodeIt it(* digraph); it != INVALID; ++it) {402 for (NodeIt it(*_gr); it != INVALID; ++it) { 390 403 _process.push_back(it); 391 404 _mask->set(it, true); … … 396 409 /// \brief Adds a new source node. 397 410 /// 398 /// Adds a new source node. The optional second parameter is the 399 /// initial distance of the node. It just sets the distance of the 400 /// node to the given value. 411 /// This function adds a new source node. The optional second parameter 412 /// is the initial distance of the node. 401 413 void addSource(Node source, Value dst = OperationTraits::zero()) { 402 414 _dist->set(source, dst); … … 410 422 /// 411 423 /// If the algoritm calculated the distances in the previous round 412 /// exactly for all at most \f$ k \f$ length path lengths then it will 413 /// calculate the distances exactly for all at most \f$ k + 1 \f$ 414 /// length path lengths. With \f$ k \f$ iteration this function 415 /// calculates the at most \f$ k \f$ length path lengths. 424 /// exactly for the paths of at most \c k arcs, then this function 425 /// will calculate the distances exactly for the paths of at most 426 /// <tt>k+1</tt> arcs. Performing \c k iterations using this function 427 /// calculates the shortest path distances exactly for the paths 428 /// consisting of at most \c k arcs. 416 429 /// 417 430 /// \warning The paths with limited arc number cannot be retrieved 418 /// easily with \ref path() or \ref predArc() functions. If you 419 /// need the shortest path and not just the distance you should store420 /// after each iteration the \ref predMap() map and manually build421 /// the path.431 /// easily with \ref path() or \ref predArc() functions. If you also 432 /// need the shortest paths and not only the distances, you should 433 /// store the \ref predMap() "predecessor map" after each iteration 434 /// and build the path manually. 422 435 /// 423 436 /// \return \c true when the algorithm have not found more shorter 424 437 /// paths. 438 /// 439 /// \see ActiveIt 425 440 bool processNextRound() { 426 441 for (int i = 0; i < int(_process.size()); ++i) { … … 433 448 } 434 449 for (int i = 0; i < int(_process.size()); ++i) { 435 for (OutArcIt it(* digraph, _process[i]); it != INVALID; ++it) {436 Node target = digraph->target(it);437 Value relaxed = OperationTraits::plus(values[i], (* length)[it]);450 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 451 Node target = _gr->target(it); 452 Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); 438 453 if (OperationTraits::less(relaxed, (*_dist)[target])) { 439 454 _pred->set(target, it); … … 452 467 /// \brief Executes one weak round from the Bellman-Ford algorithm. 453 468 /// 454 /// If the algorithm calculated the distances in the 455 /// previous round at least for all at most k length paths then it will 456 /// calculate the distances at least for all at most k + 1 length paths. 457 /// This function does not make it possible to calculate strictly the 458 /// at most k length minimal paths, this is why it is 459 /// called just weak round. 460 /// \return \c true when the algorithm have not found more shorter paths. 469 /// If the algorithm calculated the distances in the previous round 470 /// at least for the paths of at most \c k arcs, then this function 471 /// will calculate the distances at least for the paths of at most 472 /// <tt>k+1</tt> arcs. 473 /// This function does not make it possible to calculate the shortest 474 /// path distances exactly for paths consisting of at most \c k arcs, 475 /// this is why it is called weak round. 476 /// 477 /// \return \c true when the algorithm have not found more shorter 478 /// paths. 479 /// 480 /// \see ActiveIt 461 481 bool processNextWeakRound() { 462 482 for (int i = 0; i < int(_process.size()); ++i) { … … 465 485 std::vector<Node> nextProcess; 466 486 for (int i = 0; i < int(_process.size()); ++i) { 467 for (OutArcIt it(* digraph, _process[i]); it != INVALID; ++it) {468 Node target = digraph->target(it);487 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 488 Node target = _gr->target(it); 469 489 Value relaxed = 470 OperationTraits::plus((*_dist)[_process[i]], (* length)[it]);490 OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); 471 491 if (OperationTraits::less(relaxed, (*_dist)[target])) { 472 492 _pred->set(target, it); … … 485 505 /// \brief Executes the algorithm. 486 506 /// 487 /// \pre init() must be called and at least one node should be added 488 /// with addSource() before using this function. 489 /// 490 /// This method runs the %BellmanFord algorithm from the root node(s) 491 /// in order to compute the shortest path to each node. The algorithm 492 /// computes 493 /// - The shortest path tree. 494 /// - The distance of each node from the root(s). 507 /// Executes the algorithm. 508 /// 509 /// This method runs the Bellman-Ford algorithm from the root node(s) 510 /// in order to compute the shortest path to each node. 511 /// 512 /// The algorithm computes 513 /// - the shortest path tree (forest), 514 /// - the distance of each node from the root(s). 515 /// 516 /// \pre init() must be called and at least one root node should be 517 /// added with addSource() before using this function. 495 518 void start() { 496 int num = countNodes(* digraph) - 1;519 int num = countNodes(*_gr) - 1; 497 520 for (int i = 0; i < num; ++i) { 498 521 if (processNextWeakRound()) break; … … 502 525 /// \brief Executes the algorithm and checks the negative cycles. 503 526 /// 504 /// \pre init() must be called and at least one node should be added 505 /// with addSource() before using this function. 506 /// 507 /// This method runs the %BellmanFord algorithm from the root node(s) 508 /// in order to compute the shortest path to each node. The algorithm 509 /// computes 510 /// - The shortest path tree. 511 /// - The distance of each node from the root(s). 527 /// Executes the algorithm and checks the negative cycles. 528 /// 529 /// This method runs the Bellman-Ford algorithm from the root node(s) 530 /// in order to compute the shortest path to each node and also checks 531 /// if the digraph contains cycles with negative total length. 532 /// 533 /// The algorithm computes 534 /// - the shortest path tree (forest), 535 /// - the distance of each node from the root(s). 512 536 /// 513 537 /// \return \c false if there is a negative cycle in the digraph. 538 /// 539 /// \pre init() must be called and at least one root node should be 540 /// added with addSource() before using this function. 514 541 bool checkedStart() { 515 int num = countNodes(* digraph);542 int num = countNodes(*_gr); 516 543 for (int i = 0; i < num; ++i) { 517 544 if (processNextWeakRound()) return true; … … 520 547 } 521 548 522 /// \brief Executes the algorithm with path length limit. 523 /// 524 /// \pre init() must be called and at least one node should be added 525 /// with addSource() before using this function. 526 /// 527 /// This method runs the %BellmanFord algorithm from the root 528 /// node(s) in order to compute the shortest path lengths with at 529 /// most \c num arc. 549 /// \brief Executes the algorithm with arc number limit. 550 /// 551 /// Executes the algorithm with arc number limit. 552 /// 553 /// This method runs the Bellman-Ford algorithm from the root node(s) 554 /// in order to compute the shortest path distance for each node 555 /// using only the paths consisting of at most \c num arcs. 556 /// 557 /// The algorithm computes 558 /// - the limited distance of each node from the root(s), 559 /// - the predecessor arc for each node. 530 560 /// 531 561 /// \warning The paths with limited arc number cannot be retrieved 532 /// easily with \ref path() or \ref predArc() functions. If you 533 /// need the shortest path and not just the distance you should store 534 /// after each iteration the \ref predMap() map and manually build 535 /// the path. 536 /// 537 /// The algorithm computes 538 /// - The predecessor arc from each node. 539 /// - The limited distance of each node from the root(s). 562 /// easily with \ref path() or \ref predArc() functions. If you also 563 /// need the shortest paths and not only the distances, you should 564 /// store the \ref predMap() "predecessor map" after each iteration 565 /// and build the path manually. 566 /// 567 /// \pre init() must be called and at least one root node should be 568 /// added with addSource() before using this function. 540 569 void limitedStart(int num) { 541 570 for (int i = 0; i < num; ++i) { … … 544 573 } 545 574 546 /// \brief Runs %BellmanFord algorithm from node \c s.575 /// \brief Runs the algorithm from the given root node. 547 576 /// 548 /// This method runs the %BellmanFord algorithm from a root node \c s 549 /// in order to compute the shortest path to each node. The algorithm 550 /// computes 551 /// - The shortest path tree. 552 /// - The distance of each node from the root. 553 /// 554 /// \note d.run(s) is just a shortcut of the following code. 555 ///\code 556 /// d.init(); 557 /// d.addSource(s); 558 /// d.start(); 559 ///\endcode 577 /// This method runs the Bellman-Ford algorithm from the given root 578 /// node \c s in order to compute the shortest path to each node. 579 /// 580 /// The algorithm computes 581 /// - the shortest path tree (forest), 582 /// - the distance of each node from the root(s). 583 /// 584 /// \note bf.run(s) is just a shortcut of the following code. 585 /// \code 586 /// bf.init(); 587 /// bf.addSource(s); 588 /// bf.start(); 589 /// \endcode 560 590 void run(Node s) { 561 591 init(); … … 564 594 } 565 595 566 /// \brief Runs %BellmanFord algorithm with limited path length567 /// from node \c s.596 /// \brief Runs the algorithm from the given root node with arc 597 /// number limit. 568 598 /// 569 /// This method runs the %BellmanFord algorithm from a root node \c s 570 /// in order to compute the shortest path with at most \c len arcs 571 /// to each node. The algorithm computes 572 /// - The shortest path tree. 573 /// - The distance of each node from the root. 574 /// 575 /// \note d.run(s, num) is just a shortcut of the following code. 576 ///\code 577 /// d.init(); 578 /// d.addSource(s); 579 /// d.limitedStart(num); 580 ///\endcode 599 /// This method runs the Bellman-Ford algorithm from the given root 600 /// node \c s in order to compute the shortest path distance for each 601 /// node using only the paths consisting of at most \c num arcs. 602 /// 603 /// The algorithm computes 604 /// - the limited distance of each node from the root(s), 605 /// - the predecessor arc for each node. 606 /// 607 /// \warning The paths with limited arc number cannot be retrieved 608 /// easily with \ref path() or \ref predArc() functions. If you also 609 /// need the shortest paths and not only the distances, you should 610 /// store the \ref predMap() "predecessor map" after each iteration 611 /// and build the path manually. 612 /// 613 /// \note bf.run(s, num) is just a shortcut of the following code. 614 /// \code 615 /// bf.init(); 616 /// bf.addSource(s); 617 /// bf.limitedStart(num); 618 /// \endcode 581 619 void run(Node s, int num) { 582 620 init(); … … 587 625 ///@} 588 626 589 /// \name Query Functions 590 /// The result of the %BellmanFord algorithm can be obtained using these 591 /// functions.\n 592 /// Before the use of these functions, 593 /// either run() or start() must be called. 594 595 ///@{ 596 597 /// \brief Lemon iterator for get the active nodes. 598 /// 599 /// Lemon iterator for get the active nodes. This class provides a 600 /// common style lemon iterator which gives back a subset of the 601 /// nodes. The iterated nodes are active in the algorithm after 602 /// the last phase so these should be checked in the next phase to 603 /// find augmenting arcs from these. 627 /// \brief LEMON iterator for getting the active nodes. 628 /// 629 /// This class provides a common style LEMON iterator that traverses 630 /// the active nodes of the Bellman-Ford algorithm after the last 631 /// phase. These nodes should be checked in the next phase to 632 /// find augmenting arcs outgoing from them. 604 633 class ActiveIt { 605 634 public: … … 607 636 /// \brief Constructor. 608 637 /// 609 /// Constructor for get the nodeset of the variable. 638 /// Constructor for getting the active nodes of the given BellmanFord 639 /// instance. 610 640 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 611 641 { … … 618 648 ActiveIt(Invalid) : _algorithm(0), _index(-1) {} 619 649 620 /// \brief Conversion to node.650 /// \brief Conversion to \c Node. 621 651 /// 622 /// Conversion to node.652 /// Conversion to \c Node. 623 653 operator Node() const { 624 654 return _index >= 0 ? _algorithm->_process[_index] : INVALID; … … 647 677 int _index; 648 678 }; 649 650 typedef PredMapPath<Digraph, PredMap> Path; 651 652 /// \brief Gives back the shortest path. 679 680 /// \name Query Functions 681 /// The result of the Bellman-Ford algorithm can be obtained using these 682 /// functions.\n 683 /// Either \ref run() or \ref init() should be called before using them. 684 685 ///@{ 686 687 /// \brief The shortest path to the given node. 653 688 /// 654 /// Gives back the shortest path. 655 /// \pre The \c t should be reachable from the source. 656 Path path(Node t) 689 /// Gives back the shortest path to the given node from the root(s). 690 /// 691 /// \warning \c t should be reached from the root(s). 692 /// 693 /// \pre Either \ref run() or \ref init() must be called before 694 /// using this function. 695 Path path(Node t) const 657 696 { 658 return Path(*digraph, *_pred, t); 659 } 660 661 662 // TODO : implement negative cycle 663 // /// \brief Gives back a negative cycle. 664 // /// 665 // /// This function gives back a negative cycle. 666 // /// If the algorithm have not found yet negative cycle it will give back 667 // /// an empty path. 668 // Path negativeCycle() { 669 // typename Digraph::template NodeMap<int> state(*digraph, 0); 670 // for (ActiveIt it(*this); it != INVALID; ++it) { 671 // if (state[it] == 0) { 672 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { 673 // if (state[t] == 0) { 674 // state[t] = 1; 675 // } else if (state[t] == 2) { 676 // break; 677 // } else { 678 // p.clear(); 679 // typename Path::Builder b(p); 680 // b.setStartNode(t); 681 // b.pushFront(predArc(t)); 682 // for(Node s = predNode(t); s != t; s = predNode(s)) { 683 // b.pushFront(predArc(s)); 684 // } 685 // b.commit(); 686 // return true; 687 // } 688 // } 689 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { 690 // if (state[t] == 1) { 691 // state[t] = 2; 692 // } else { 693 // break; 694 // } 695 // } 696 // } 697 // } 698 // return false; 699 // } 697 return Path(*_gr, *_pred, t); 698 } 700 699 701 /// \brief The distance of a node from the root. 702 /// 703 /// Returns the distance of a node from the root. 704 /// \pre \ref run() must be called before using this function. 705 /// \warning If node \c v in unreachable from the root the return value 706 /// of this funcion is undefined. 700 /// \brief The distance of the given node from the root(s). 701 /// 702 /// Returns the distance of the given node from the root(s). 703 /// 704 /// \warning If node \c v is not reached from the root(s), then 705 /// the return value of this function is undefined. 706 /// 707 /// \pre Either \ref run() or \ref init() must be called before 708 /// using this function. 707 709 Value dist(Node v) const { return (*_dist)[v]; } 708 710 709 /// \brief Returns the 'previous arc' of the shortest path tree. 710 /// 711 /// For a node \c v it returns the 'previous arc' of the shortest path 712 /// tree, i.e. it returns the last arc of a shortest path from the root 713 /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 714 /// if \c v=s. The shortest path tree used here is equal to the shortest 715 /// path tree used in \ref predNode(). 716 /// \pre \ref run() must be called before using 717 /// this function. 711 /// \brief Returns the 'previous arc' of the shortest path tree for 712 /// the given node. 713 /// 714 /// This function returns the 'previous arc' of the shortest path 715 /// tree for node \c v, i.e. it returns the last arc of a 716 /// shortest path from a root to \c v. It is \c INVALID if \c v 717 /// is not reached from the root(s) or if \c v is a root. 718 /// 719 /// The shortest path tree used here is equal to the shortest path 720 /// tree used in \ref predNode() and \predMap(). 721 /// 722 /// \pre Either \ref run() or \ref init() must be called before 723 /// using this function. 718 724 Arc predArc(Node v) const { return (*_pred)[v]; } 719 725 720 /// \brief Returns the 'previous node' of the shortest path tree. 721 /// 722 /// For a node \c v it returns the 'previous node' of the shortest path 723 /// tree, i.e. it returns the last but one node from a shortest path from 724 /// the root to \c /v. It is INVALID if \c v is unreachable from the root 725 /// or if \c v=s. The shortest path tree used here is equal to the 726 /// shortest path tree used in \ref predArc(). \pre \ref run() must be 727 /// called before using this function. 726 /// \brief Returns the 'previous node' of the shortest path tree for 727 /// the given node. 728 /// 729 /// This function returns the 'previous node' of the shortest path 730 /// tree for node \c v, i.e. it returns the last but one node of 731 /// a shortest path from a root to \c v. It is \c INVALID if \c v 732 /// is not reached from the root(s) or if \c v is a root. 733 /// 734 /// The shortest path tree used here is equal to the shortest path 735 /// tree used in \ref predArc() and \predMap(). 736 /// 737 /// \pre Either \ref run() or \ref init() must be called before 738 /// using this function. 728 739 Node predNode(Node v) const { 729 return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]); 730 } 731 732 /// \brief Returns a reference to the NodeMap of distances. 733 /// 734 /// Returns a reference to the NodeMap of distances. \pre \ref run() must 735 /// be called before using this function. 740 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 741 } 742 743 /// \brief Returns a const reference to the node map that stores the 744 /// distances of the nodes. 745 /// 746 /// Returns a const reference to the node map that stores the distances 747 /// of the nodes calculated by the algorithm. 748 /// 749 /// \pre Either \ref run() or \ref init() must be called before 750 /// using this function. 736 751 const DistMap &distMap() const { return *_dist;} 737 752 738 /// \brief Returns a reference to the shortest path tree map. 739 /// 740 /// Returns a reference to the NodeMap of the arcs of the 741 /// shortest path tree. 742 /// \pre \ref run() must be called before using this function. 753 /// \brief Returns a const reference to the node map that stores the 754 /// predecessor arcs. 755 /// 756 /// Returns a const reference to the node map that stores the predecessor 757 /// arcs, which form the shortest path tree (forest). 758 /// 759 /// \pre Either \ref run() or \ref init() must be called before 760 /// using this function. 743 761 const PredMap &predMap() const { return *_pred; } 744 762 745 /// \brief Checks if a node is reachable from the root. 746 /// 747 /// Returns \c true if \c v is reachable from the root. 748 /// \pre \ref run() must be called before using this function. 749 /// 750 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); } 763 /// \brief Checks if a node is reached from the root(s). 764 /// 765 /// Returns \c true if \c v is reached from the root(s). 766 /// 767 /// \pre Either \ref run() or \ref init() must be called before 768 /// using this function. 769 bool reached(Node v) const { 770 return (*_dist)[v] != OperationTraits::infinity(); 771 } 772 773 // TODO: implement negative cycle 774 // /// \brief Gives back a negative cycle. 775 // /// 776 // /// This function gives back a negative cycle. 777 // /// If the algorithm have not found yet negative cycle it will give back 778 // /// an empty path. 779 // Path negativeCycle() { 780 // typename Digraph::template NodeMap<int> state(*digraph, 0); 781 // for (ActiveIt it(*this); it != INVALID; ++it) { 782 // if (state[it] == 0) { 783 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { 784 // if (state[t] == 0) { 785 // state[t] = 1; 786 // } else if (state[t] == 2) { 787 // break; 788 // } else { 789 // p.clear(); 790 // typename Path::Builder b(p); 791 // b.setStartNode(t); 792 // b.pushFront(predArc(t)); 793 // for(Node s = predNode(t); s != t; s = predNode(s)) { 794 // b.pushFront(predArc(s)); 795 // } 796 // b.commit(); 797 // return true; 798 // } 799 // } 800 // for (Node t = it; predArc(t) != INVALID; t = predNode(t)) { 801 // if (state[t] == 1) { 802 // state[t] = 2; 803 // } else { 804 // break; 805 // } 806 // } 807 // } 808 // } 809 // return false; 810 // } 751 811 752 812 ///@} 753 813 }; 754 814 755 /// \brief Default traits class of BellmanFordfunction.756 /// 757 /// Default traits class of BellmanFordfunction.758 /// \ param _Digraph Digraph type.759 /// \ param _LengthMap Type oflength map.760 template <typename _Digraph, typename _LengthMap>815 /// \brief Default traits class of bellmanFord() function. 816 /// 817 /// Default traits class of bellmanFord() function. 818 /// \tparam GR The type of the digraph. 819 /// \tparam LEN The type of the length map. 820 template <typename GR, typename LEN> 761 821 struct BellmanFordWizardDefaultTraits { 762 /// \brief The digraph typethe algorithm runs on.763 typedef _DigraphDigraph;822 /// The type of the digraph the algorithm runs on. 823 typedef GR Digraph; 764 824 765 825 /// \brief The type of the map that stores the arc lengths. … … 767 827 /// The type of the map that stores the arc lengths. 768 828 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 769 typedef _LengthMapLengthMap;770 771 /// \brief The value type of the length map.772 typedef typename _LengthMap::Value Value;829 typedef LEN LengthMap; 830 831 /// The type of the arc lengths. 832 typedef typename LEN::Value Value; 773 833 774 834 /// \brief Operation traits for Bellman-Ford algorithm. 775 835 /// 776 /// It defines the infinity type on the given Value type777 /// and the used operation.836 /// It defines the used operations and the infinity value for the 837 /// given \c Value type. 778 838 /// \see BellmanFordDefaultOperationTraits 779 839 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; … … 782 842 /// arcs of the shortest paths. 783 843 /// 784 /// The type of the map that stores the last 785 /// arcs of the shortest paths. 786 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 787 typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap; 788 789 /// \brief Instantiates a PredMap. 844 /// The type of the map that stores the last arcs of the shortest paths. 845 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 846 typedef typename GR::template NodeMap<typename GR::Arc> PredMap; 847 848 /// \brief Instantiates a \c PredMap. 790 849 /// 791 /// This function instantiates a \ref PredMap. 792 static PredMap *createPredMap(const _Digraph &) { 793 return new PredMap(); 794 } 795 /// \brief The type of the map that stores the dists of the nodes. 796 /// 797 /// The type of the map that stores the dists of the nodes. 798 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. 799 typedef NullMap<typename Digraph::Node, Value> DistMap; 800 /// \brief Instantiates a DistMap. 850 /// This function instantiates a \ref PredMap. 851 /// \param g is the digraph to which we would like to define the 852 /// \ref PredMap. 853 static PredMap *createPredMap(const GR &g) { 854 return new PredMap(g); 855 } 856 857 /// \brief The type of the map that stores the distances of the nodes. 858 /// 859 /// The type of the map that stores the distances of the nodes. 860 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 861 typedef typename GR::template NodeMap<Value> DistMap; 862 863 /// \brief Instantiates a \c DistMap. 801 864 /// 802 865 /// This function instantiates a \ref DistMap. 803 static DistMap *createDistMap(const _Digraph &) { 804 return new DistMap(); 805 } 866 /// \param g is the digraph to which we would like to define the 867 /// \ref DistMap. 868 static DistMap *createDistMap(const GR &g) { 869 return new DistMap(g); 870 } 871 872 ///The type of the shortest paths. 873 874 ///The type of the shortest paths. 875 ///It must meet the \ref concepts::Path "Path" concept. 876 typedef lemon::Path<Digraph> Path; 806 877 }; 807 878 808 /// \brief Default traits used by \ref BellmanFordWizard 809 /// 810 /// To make it easier to use BellmanFord algorithm 811 /// we have created a wizard class. 812 /// This \ref BellmanFordWizard class needs default traits, 813 /// as well as the \ref BellmanFord class. 814 /// The \ref BellmanFordWizardBase is a class to be the default traits of the 815 /// \ref BellmanFordWizard class. 816 /// \todo More named parameters are required... 817 template<class _Digraph,class _LengthMap> 879 /// \brief Default traits class used by BellmanFordWizard. 880 /// 881 /// Default traits class used by BellmanFordWizard. 882 /// \tparam GR The type of the digraph. 883 /// \tparam LEN The type of the length map. 884 template <typename GR, typename LEN> 818 885 class BellmanFordWizardBase 819 : public BellmanFordWizardDefaultTraits< _Digraph,_LengthMap> {820 821 typedef BellmanFordWizardDefaultTraits< _Digraph,_LengthMap> Base;886 : public BellmanFordWizardDefaultTraits<GR, LEN> { 887 888 typedef BellmanFordWizardDefaultTraits<GR, LEN> Base; 822 889 protected: 823 // /Type of the nodes in the digraph.890 // Type of the nodes in the digraph. 824 891 typedef typename Base::Digraph::Node Node; 825 892 826 // /Pointer to the underlying digraph.893 // Pointer to the underlying digraph. 827 894 void *_graph; 828 // /Pointer to the length map895 // Pointer to the length map 829 896 void *_length; 830 // /Pointer to the map of predecessors arcs.897 // Pointer to the map of predecessors arcs. 831 898 void *_pred; 832 // /Pointer to the map of distances.899 // Pointer to the map of distances. 833 900 void *_dist; 834 ///Pointer to the source node. 835 Node _source; 901 //Pointer to the shortest path to the target node. 902 void *_path; 903 //Pointer to the distance of the target node. 904 void *_di; 836 905 837 906 public: 838 907 /// Constructor. 839 908 840 /// This constructor does not require parameters, thereforeit initiates841 /// all of the attributes to default values (0, INVALID).842 BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),843 _dist(0), _source(INVALID) {}909 /// This constructor does not require parameters, it initiates 910 /// all of the attributes to default values \c 0. 911 BellmanFordWizardBase() : 912 _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {} 844 913 845 914 /// Constructor. 846 915 847 /// This constructor requires some parameters, 848 /// listed in the parameters list. 849 /// Others are initiated to 0. 850 /// \param digraph is the initial value of \ref _graph 851 /// \param length is the initial value of \ref _length 852 /// \param source is the initial value of \ref _source 853 BellmanFordWizardBase(const _Digraph& digraph, 854 const _LengthMap& length, 855 Node source = INVALID) : 856 _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))), 857 _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 858 _pred(0), _dist(0), _source(source) {} 916 /// This constructor requires two parameters, 917 /// others are initiated to \c 0. 918 /// \param gr The digraph the algorithm runs on. 919 /// \param len The length map. 920 BellmanFordWizardBase(const GR& gr, 921 const LEN& len) : 922 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 923 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 924 _pred(0), _dist(0), _path(0), _di(0) {} 859 925 860 926 }; 861 927 862 /// A class to make the usage of BellmanFord algorithm easier 863 864 /// This class is created to make it easier to use BellmanFord algorithm. 865 /// It uses the functions and features of the plain \ref BellmanFord, 866 /// but it is much simpler to use it. 867 /// 868 /// Simplicity means that the way to change the types defined 869 /// in the traits class is based on functions that returns the new class 870 /// and not on templatable built-in classes. 871 /// When using the plain \ref BellmanFord 872 /// the new class with the modified type comes from 873 /// the original class by using the :: 874 /// operator. In the case of \ref BellmanFordWizard only 875 /// a function have to be called and it will 876 /// return the needed class. 877 /// 878 /// It does not have own \ref run method. When its \ref run method is called 879 /// it initiates a plain \ref BellmanFord class, and calls the \ref 880 /// BellmanFord::run method of it. 881 template<class _Traits> 882 class BellmanFordWizard : public _Traits { 883 typedef _Traits Base; 884 885 ///The type of the underlying digraph. 886 typedef typename _Traits::Digraph Digraph; 928 /// \brief Auxiliary class for the function-type interface of the 929 /// \ref BellmanFord "Bellman-Ford" algorithm. 930 /// 931 /// This auxiliary class is created to implement the 932 /// \ref bellmanFord() "function-type interface" of the 933 /// \ref BellmanFord "Bellman-Ford" algorithm. 934 /// It does not have own \ref run() method, it uses the 935 /// functions and features of the plain \ref BellmanFord. 936 /// 937 /// This class should only be used through the \ref bellmanFord() 938 /// function, which makes it easier to use the algorithm. 939 template<class TR> 940 class BellmanFordWizard : public TR { 941 typedef TR Base; 942 943 typedef typename TR::Digraph Digraph; 887 944 888 945 typedef typename Digraph::Node Node; … … 891 948 typedef typename Digraph::OutArcIt ArcIt; 892 949 893 ///The type of the map that stores the arc lengths. 894 typedef typename _Traits::LengthMap LengthMap; 895 896 ///The type of the length of the arcs. 950 typedef typename TR::LengthMap LengthMap; 897 951 typedef typename LengthMap::Value Value; 898 899 ///\brief The type of the map that stores the last 900 ///arcs of the shortest paths. 901 typedef typename _Traits::PredMap PredMap; 902 903 ///The type of the map that stores the dists of the nodes. 904 typedef typename _Traits::DistMap DistMap; 952 typedef typename TR::PredMap PredMap; 953 typedef typename TR::DistMap DistMap; 954 typedef typename TR::Path Path; 905 955 906 956 public: 907 957 /// Constructor. 908 BellmanFordWizard() : _Traits() {}958 BellmanFordWizard() : TR() {} 909 959 910 960 /// \brief Constructor that requires parameters. … … 912 962 /// Constructor that requires parameters. 913 963 /// These parameters will be the default values for the traits class. 914 BellmanFordWizard(const Digraph& digraph, const LengthMap& length, 915 Node src = INVALID) 916 : _Traits(digraph, length, src) {} 964 /// \param gr The digraph the algorithm runs on. 965 /// \param len The length map. 966 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 967 : TR(gr, len) {} 917 968 918 969 /// \brief Copy constructor 919 BellmanFordWizard(const _Traits &b) : _Traits(b) {}970 BellmanFordWizard(const TR &b) : TR(b) {} 920 971 921 972 ~BellmanFordWizard() {} 922 973 923 /// \brief Runs BellmanFord algorithm from a givennode.974 /// \brief Runs the Bellman-Ford algorithm from the given source node. 924 975 /// 925 /// Runs BellmanFord algorithm from a given node. 926 /// The node can be given by the \ref source function. 927 void run() { 928 LEMON_ASSERT(Base::_source != INVALID, "Source node is not given"); 929 BellmanFord<Digraph,LengthMap,_Traits> 976 /// This method runs the Bellman-Ford algorithm from the given source 977 /// node in order to compute the shortest path to each node. 978 void run(Node s) { 979 BellmanFord<Digraph,LengthMap,TR> 930 980 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 931 981 *reinterpret_cast<const LengthMap*>(Base::_length)); 932 982 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 933 983 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 934 bf.run(Base::_source); 935 } 936 937 /// \brief Runs BellmanFord algorithm from the given node. 938 /// 939 /// Runs BellmanFord algorithm from the given node. 940 /// \param src is the given source. 941 void run(Node src) { 942 Base::_source = src; 943 run(); 984 bf.run(s); 985 } 986 987 /// \brief Runs the Bellman-Ford algorithm to find the shortest path 988 /// between \c s and \c t. 989 /// 990 /// This method runs the Bellman-Ford algorithm from node \c s 991 /// in order to compute the shortest path to node \c t. 992 /// Actually, it computes the shortest path to each node, but using 993 /// this function you can retrieve the distance and the shortest path 994 /// for a single target node easier. 995 /// 996 /// \return \c true if \c t is reachable form \c s. 997 bool run(Node s, Node t) { 998 BellmanFord<Digraph,LengthMap,TR> 999 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 1000 *reinterpret_cast<const LengthMap*>(Base::_length)); 1001 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1002 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1003 bf.run(s); 1004 if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t); 1005 if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t); 1006 return bf.reached(t); 944 1007 } 945 1008 946 1009 template<class T> 947 struct DefPredMapBase : public Base {1010 struct SetPredMapBase : public Base { 948 1011 typedef T PredMap; 949 1012 static PredMap *createPredMap(const Digraph &) { return 0; }; 950 DefPredMapBase(const _Traits &b) : _Traits(b) {}1013 SetPredMapBase(const TR &b) : TR(b) {} 951 1014 }; 952 1015 953 ///\brief \ref named-templ-param "Named parameter" 954 ///function for setting PredMap type 955 /// 956 /// \ref named-templ-param "Named parameter" 957 ///function for setting PredMap type 958 /// 1016 /// \brief \ref named-templ-param "Named parameter" for setting 1017 /// the predecessor map. 1018 /// 1019 /// \ref named-templ-param "Named parameter" for setting 1020 /// the map that stores the predecessor arcs of the nodes. 959 1021 template<class T> 960 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 961 { 1022 BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) { 962 1023 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 963 return BellmanFordWizard< DefPredMapBase<T> >(*this);1024 return BellmanFordWizard<SetPredMapBase<T> >(*this); 964 1025 } 965 1026 966 1027 template<class T> 967 struct DefDistMapBase : public Base {1028 struct SetDistMapBase : public Base { 968 1029 typedef T DistMap; 969 1030 static DistMap *createDistMap(const Digraph &) { return 0; }; 970 DefDistMapBase(const _Traits &b) : _Traits(b) {}1031 SetDistMapBase(const TR &b) : TR(b) {} 971 1032 }; 972 1033 973 /// \brief \ref named-templ-param "Named parameter"974 /// function for setting DistMap type975 /// 976 /// \ref named-templ-param "Named parameter" 977 /// function for setting DistMap type978 /// 1034 /// \brief \ref named-templ-param "Named parameter" for setting 1035 /// the distance map. 1036 /// 1037 /// \ref named-templ-param "Named parameter" for setting 1038 /// the map that stores the distances of the nodes calculated 1039 /// by the algorithm. 979 1040 template<class T> 980 BellmanFordWizard< DefDistMapBase<T> > distMap(const T &t) {1041 BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) { 981 1042 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 982 return BellmanFordWizard< DefDistMapBase<T> >(*this);1043 return BellmanFordWizard<SetDistMapBase<T> >(*this); 983 1044 } 984 1045 985 1046 template<class T> 986 struct DefOperationTraitsBase : public Base {987 typedef T OperationTraits;988 DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}1047 struct SetPathBase : public Base { 1048 typedef T Path; 1049 SetPathBase(const TR &b) : TR(b) {} 989 1050 }; 990 991 ///\brief \ref named-templ-param "Named parameter" 992 ///function for setting OperationTraits type 993 /// 994 /// \ref named-templ-param "Named parameter" 995 ///function for setting OperationTraits type 996 /// 1051 1052 /// \brief \ref named-func-param "Named parameter" for getting 1053 /// the shortest path to the target node. 1054 /// 1055 /// \ref named-func-param "Named parameter" for getting 1056 /// the shortest path to the target node. 997 1057 template<class T> 998 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() { 999 return BellmanFordWizard<DefDistMapBase<T> >(*this); 1000 } 1001 1002 /// \brief Sets the source node, from which the BellmanFord algorithm runs. 1003 /// 1004 /// Sets the source node, from which the BellmanFord algorithm runs. 1005 /// \param src is the source node. 1006 BellmanFordWizard<_Traits>& source(Node src) { 1007 Base::_source = src; 1058 BellmanFordWizard<SetPathBase<T> > path(const T &t) 1059 { 1060 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1061 return BellmanFordWizard<SetPathBase<T> >(*this); 1062 } 1063 1064 /// \brief \ref named-func-param "Named parameter" for getting 1065 /// the distance of the target node. 1066 /// 1067 /// \ref named-func-param "Named parameter" for getting 1068 /// the distance of the target node. 1069 BellmanFordWizard dist(const Value &d) 1070 { 1071 Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d)); 1008 1072 return *this; 1009 1073 } … … 1011 1075 }; 1012 1076 1013 /// \brief Function type interface for BellmanFord algorithm. 1077 /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" 1078 /// algorithm. 1014 1079 /// 1015 1080 /// \ingroup shortest_path 1016 /// Function type interface for BellmanFord algorithm. 1081 /// Function type interface for the \ref BellmanFord "Bellman-Ford" 1082 /// algorithm. 1017 1083 /// 1018 1084 /// This function also has several \ref named-templ-func-param 1019 1085 /// "named parameters", they are declared as the members of class 1020 1086 /// \ref BellmanFordWizard. 1021 /// The following 1022 /// example shows how to use these parameters. 1023 ///\code 1024 /// bellmanford(g,length,source).predMap(preds).run(); 1025 ///\endcode 1087 /// The following examples show how to use these parameters. 1088 /// \code 1089 /// // Compute shortest path from node s to each node 1090 /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s); 1091 /// 1092 /// // Compute shortest path from s to t 1093 /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t); 1094 /// \endcode 1026 1095 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()" 1027 1096 /// to the end of the parameter list. 1028 1097 /// \sa BellmanFordWizard 1029 1098 /// \sa BellmanFord 1030 template<class _Digraph, class _LengthMap> 1031 BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> > 1032 bellmanFord(const _Digraph& digraph, 1033 const _LengthMap& length, 1034 typename _Digraph::Node source = INVALID) { 1035 return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> > 1036 (digraph, length, source); 1099 template<typename GR, typename LEN> 1100 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > 1101 bellmanFord(const GR& digraph, 1102 const LEN& length) 1103 { 1104 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length); 1037 1105 } 1038 1106
Note: See TracChangeset
for help on using the changeset viewer.