Changeset 1741:7a98fe2ed989 in lemon-0.x
- Timestamp:
- 10/26/05 12:50:47 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/belmann_ford.h
r1723 r1741 413 413 int num = countNodes(*graph) - 1; 414 414 for (int i = 0; i < num; ++i) { 415 bool ready= true;415 bool done = true; 416 416 for (EdgeIt it(*graph); it != INVALID; ++it) { 417 417 Node source = graph->source(it); … … 422 422 _pred->set(target, it); 423 423 _dist->set(target, relaxed); 424 ready= false;424 done = false; 425 425 } 426 426 } 427 if ( ready) return;428 } 429 } 430 431 /// \brief Executes the algorithm and check the negative circles.427 if (done) return; 428 } 429 } 430 431 /// \brief Executes the algorithm and checks the negative circles. 432 432 /// 433 433 /// \pre init() must be called and at least one node should be added … … 443 443 int num = countNodes(*graph); 444 444 for (int i = 0; i < num; ++i) { 445 bool ready= true;445 bool done = true; 446 446 for (EdgeIt it(*graph); it != INVALID; ++it) { 447 447 Node source = graph->source(it); … … 452 452 _pred->set(target, it); 453 453 _dist->set(target, relaxed); 454 ready= false;454 done = false; 455 455 } 456 456 } 457 if ( ready) return true;457 if (done) return true; 458 458 } 459 459 return false; -
lemon/dijkstra.h
r1734 r1741 62 62 /// \param G is the graph, to which we would like to define the 63 63 /// HeapCrossRef. 64 /// \todo The graph alone may be insufficient for the initialization65 64 static HeapCrossRef *createHeapCrossRef(const GR &G) 66 65 { … … 75 74 ///\sa Dijkstra 76 75 typedef BinHeap<typename Graph::Node, typename LM::Value, 77 typename GR::template NodeMap<int>, 78 std::less<Value> > Heap; 76 HeapCrossRef, std::less<Value> > Heap; 79 77 80 78 static Heap *createHeap(HeapCrossRef& R) … … 361 359 typedef CR HeapCrossRef; 362 360 typedef H Heap; 363 static HeapCrossRef *createHeapCrossRef(const Graph & G) {364 return new HeapCrossRef(G);365 } 366 static Heap *createHeap(HeapCrossRef & R)361 static HeapCrossRef *createHeapCrossRef(const Graph &) { 362 throw UninitializedParameter(); 363 } 364 static Heap *createHeap(HeapCrossRef &) 367 365 { 368 return new Heap(R);366 throw UninitializedParameter(); 369 367 } 370 368 }; … … 379 377 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { 380 378 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create; 379 }; 380 381 template <class H, class CR> 382 struct DefStandardHeapTraits : public Traits { 383 typedef CR HeapCrossRef; 384 typedef H Heap; 385 static HeapCrossRef *createHeapCrossRef(const Graph &G) { 386 return new HeapCrossRef(G); 387 } 388 static Heap *createHeap(HeapCrossRef &R) 389 { 390 return new Heap(R); 391 } 392 }; 393 ///\ref named-templ-param "Named parameter" for setting heap and cross 394 ///reference type with automatic allocation 395 396 ///\ref named-templ-param "Named parameter" for setting heap and cross 397 ///reference type. It can allocate the heap and the cross reference 398 ///object if the cross reference's constructor waits for the graph as 399 ///parameter and the heap's constructor waits for the cross reference. 400 template <class H, class CR = typename Graph::template NodeMap<int> > 401 struct DefStandardHeap 402 : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 403 typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > 404 Create; 381 405 }; 382 406 … … 454 478 } 455 479 _dist = &m; 480 return *this; 481 } 482 483 ///Sets the heap and the cross reference used by algorithm. 484 485 ///Sets the heap and the cross reference used by algorithm. 486 ///If you don't use this function before calling \ref run(), 487 ///it will allocate one. The destuctor deallocates this 488 ///automatically allocated map, of course. 489 ///\return <tt> (*this) </tt> 490 Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef) 491 { 492 if(local_heap_cross_ref) { 493 delete _heap_cross_ref; 494 local_heap_cross_ref=false; 495 } 496 _heap_cross_ref = &crossRef; 497 if(local_heap) { 498 delete _heap; 499 local_heap=false; 500 } 501 _heap = &heap; 456 502 return *this; 457 503 } -
lemon/floyd_warshall.h
r1723 r1741 393 393 for (NodeIt jt(*graph); jt != INVALID; ++jt) { 394 394 _pred->set(it, jt, INVALID); 395 _dist->set(it, jt, it == jt ? 396 OperationTraits::zero() : OperationTraits::infinity()); 395 _dist->set(it, jt, OperationTraits::infinity()); 397 396 } 397 _dist->set(it, it, OperationTraits::zero()); 398 398 } 399 399 for (EdgeIt it(*graph); it != INVALID; ++it) { … … 427 427 } 428 428 } 429 } 430 431 /// \brief Executes the algorithm and checks the negative circles. 432 /// 433 /// This method runs the %FloydWarshall algorithm in order to compute 434 /// the shortest path to each node pairs. If there is a negative circle 435 /// in the graph it gives back false. 436 /// The algorithm computes 437 /// - The shortest path tree for each node. 438 /// - The distance between each node pairs. 439 bool checkedStart() { 440 start(); 441 for (NodeIt it(*graph); it != INVALID; ++it) { 442 if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) { 443 return false; 444 } 445 } 446 return true; 429 447 } 430 448 -
lemon/johnson.h
r1723 r1741 107 107 /// \see JohnsonDefaultOperationTraits 108 108 typedef JohnsonDefaultOperationTraits<Value> OperationTraits; 109 110 /// The cross reference type used by heap. 111 112 /// The cross reference type used by heap. 113 /// Usually it is \c Graph::NodeMap<int>. 114 typedef typename Graph::template NodeMap<int> HeapCrossRef; 115 116 ///Instantiates a HeapCrossRef. 117 118 ///This function instantiates a \ref HeapCrossRef. 119 /// \param graph is the graph, to which we would like to define the 120 /// HeapCrossRef. 121 static HeapCrossRef *createHeapCrossRef(const Graph& graph) { 122 return new HeapCrossRef(graph); 123 } 124 125 ///The heap type used by Dijkstra algorithm. 126 127 ///The heap type used by Dijkstra algorithm. 128 /// 129 ///\sa BinHeap 130 ///\sa Dijkstra 131 typedef BinHeap<typename Graph::Node, typename LengthMap::Value, 132 HeapCrossRef, std::less<Value> > Heap; 133 134 ///Instantiates a Heap. 135 136 ///This function instantiates a \ref Heap. 137 /// \param crossRef The cross reference for the heap. 138 static Heap *createHeap(HeapCrossRef& crossRef) { 139 return new Heap(crossRef); 140 } 109 141 110 142 /// \brief The type of the matrix map that stores the last edges of the … … 122 154 /// \param G is the graph, to which we would like to define the PredMap. 123 155 /// \todo The graph alone may be insufficient for the initialization 124 static PredMap *createPredMap(const _Graph& graph) {156 static PredMap *createPredMap(const Graph& graph) { 125 157 return new PredMap(graph); 126 158 } … … 159 191 /// 160 192 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or 161 /// with fibonacci heap O(n^2 * log(n) + n * e). 193 /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap 194 /// implementation is slower than either binary heap implementation or the 195 /// Floyd-Warshall algorithm. 162 196 /// 163 197 /// The type of the length is determined by the … … 226 260 /// \brief The operation traits. 227 261 typedef typename _Traits::OperationTraits OperationTraits; 262 ///The cross reference type used for the current heap. 263 typedef typename _Traits::HeapCrossRef HeapCrossRef; 264 ///The heap type used by the dijkstra algorithm. 265 typedef typename _Traits::Heap Heap; 228 266 private: 229 267 /// Pointer to the underlying graph. … … 239 277 ///Indicates if \ref _dist is locally allocated (\c true) or not. 240 278 bool local_dist; 279 ///Pointer to the heap cross references. 280 HeapCrossRef *_heap_cross_ref; 281 ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. 282 bool local_heap_cross_ref; 283 ///Pointer to the heap. 284 Heap *_heap; 285 ///Indicates if \ref _heap is locally allocated (\c true) or not. 286 bool local_heap; 241 287 242 288 /// Creates the maps if necessary. … … 250 296 _dist = Traits::createDistMap(*graph); 251 297 } 252 } 253 298 if (!_heap_cross_ref) { 299 local_heap_cross_ref = true; 300 _heap_cross_ref = Traits::createHeapCrossRef(*graph); 301 } 302 if (!_heap) { 303 local_heap = true; 304 _heap = Traits::createHeap(*_heap_cross_ref); 305 } 306 } 307 254 308 public : 309 310 typedef Johnson Create; 255 311 256 312 /// \name Named template parameters … … 309 365 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create; 310 366 }; 367 368 template <class H, class CR> 369 struct DefHeapTraits : public Traits { 370 typedef CR HeapCrossRef; 371 typedef H Heap; 372 static HeapCrossRef *createHeapCrossRef(const Graph &) { 373 throw UninitializedParameter(); 374 } 375 static Heap *createHeap(HeapCrossRef &) 376 { 377 throw UninitializedParameter(); 378 } 379 }; 380 ///\ref named-templ-param "Named parameter" for setting heap and cross 381 ///reference type 382 383 ///\ref named-templ-param "Named parameter" for setting heap and cross 384 ///reference type 385 /// 386 template <class H, class CR = typename Graph::template NodeMap<int> > 387 struct DefHeap 388 : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > { 389 typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create; 390 }; 391 392 template <class H, class CR> 393 struct DefStandardHeapTraits : public Traits { 394 typedef CR HeapCrossRef; 395 typedef H Heap; 396 static HeapCrossRef *createHeapCrossRef(const Graph &G) { 397 return new HeapCrossRef(G); 398 } 399 static Heap *createHeap(HeapCrossRef &R) 400 { 401 return new Heap(R); 402 } 403 }; 404 ///\ref named-templ-param "Named parameter" for setting heap and cross 405 ///reference type with automatic allocation 406 407 ///\ref named-templ-param "Named parameter" for setting heap and cross 408 ///reference type. It can allocate the heap and the cross reference 409 ///object if the cross reference's constructor waits for the graph as 410 ///parameter and the heap's constructor waits for the cross reference. 411 template <class H, class CR = typename Graph::template NodeMap<int> > 412 struct DefStandardHeap 413 : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 414 typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > 415 Create; 416 }; 311 417 312 418 ///@} … … 317 423 318 424 public: 425 426 typedef Johnson Create; 319 427 320 428 /// \brief Constructor. … … 325 433 graph(&_graph), length(&_length), 326 434 _pred(0), local_pred(false), 327 _dist(0), local_dist(false) {} 435 _dist(0), local_dist(false), 436 _heap_cross_ref(0), local_heap_cross_ref(false), 437 _heap(0), local_heap(false) {} 328 438 329 439 ///Destructor. 330 440 ~Johnson() { 331 if(local_pred) delete _pred; 332 if(local_dist) delete _dist; 441 if (local_pred) delete _pred; 442 if (local_dist) delete _dist; 443 if (local_heap_cross_ref) delete _heap_cross_ref; 444 if (local_heap) delete _heap; 333 445 } 334 446 … … 374 486 } 375 487 376 ///\name Execution control 377 /// The simplest way to execute the algorithm is to use 378 /// one of the member functions called \c run(...). 379 /// \n 380 /// If you need more control on the execution, 381 /// Finally \ref start() will perform the actual path 382 /// computation. 383 384 ///@{ 385 386 /// \brief Initializes the internal data structures. 387 /// 388 /// Initializes the internal data structures. 389 void init() { 390 create_maps(); 391 } 392 393 /// \brief Executes the algorithm. 394 /// 395 /// This method runs the %Johnson algorithm in order to compute 396 /// the shortest path to each node pairs. The algorithm 397 /// computes 398 /// - The shortest path tree for each node. 399 /// - The distance between each node pairs. 400 void start() { 401 typedef typename BelmannFord<Graph, LengthMap>:: 402 template DefOperationTraits<OperationTraits>:: 403 template DefPredMap<NullMap<Node, Edge> >:: 404 Create BelmannFordType; 405 406 BelmannFordType belmannford(*graph, *length); 407 408 NullMap<Node, Edge> predMap; 409 410 belmannford.predMap(predMap); 488 protected: 489 490 typedef typename BelmannFord<Graph, LengthMap>:: 491 template DefOperationTraits<OperationTraits>:: 492 template DefPredMap<NullMap<Node, Edge> >:: 493 Create BelmannFordType; 494 495 void shiftedRun(const BelmannFordType& belmannford) { 411 496 412 belmannford.init(OperationTraits::zero()); 413 belmannford.start(); 414 497 typedef PotentialDifferenceMap<Graph, 498 typename BelmannFordType::DistMap> PotDiffMap; 499 PotDiffMap potdiff(*graph, belmannford.distMap()); 500 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap; 501 ShiftLengthMap shiftlen(*length, potdiff); 502 503 typename Dijkstra<Graph, ShiftLengthMap>:: 504 template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen); 505 506 dijkstra.heap(*_heap, *_heap_cross_ref); 507 415 508 for (NodeIt it(*graph); it != INVALID; ++it) { 416 typedef PotentialDifferenceMap<Graph,417 typename BelmannFordType::DistMap> PotDiffMap;418 PotDiffMap potdiff(*graph, belmannford.distMap());419 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;420 ShiftLengthMap shiftlen(*length, potdiff);421 Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen);422 509 dijkstra.run(it); 423 510 for (NodeIt jt(*graph); jt != INVALID; ++jt) { … … 433 520 } 434 521 } 522 523 public: 524 525 ///\name Execution control 526 /// The simplest way to execute the algorithm is to use 527 /// one of the member functions called \c run(...). 528 /// \n 529 /// If you need more control on the execution, 530 /// Finally \ref start() will perform the actual path 531 /// computation. 532 533 ///@{ 534 535 /// \brief Initializes the internal data structures. 536 /// 537 /// Initializes the internal data structures. 538 void init() { 539 create_maps(); 540 } 541 542 /// \brief Executes the algorithm. 543 /// 544 /// This method runs the %Johnson algorithm in order to compute 545 /// the shortest path to each node pairs. The algorithm 546 /// computes 547 /// - The shortest path tree for each node. 548 /// - The distance between each node pairs. 549 void start() { 550 551 BelmannFordType belmannford(*graph, *length); 552 553 NullMap<Node, Edge> predMap; 554 555 belmannford.predMap(predMap); 556 557 belmannford.init(OperationTraits::zero()); 558 belmannford.start(); 559 560 shiftedRun(belmannford); 561 } 562 563 /// \brief Executes the algorithm and checks the negatvie circles. 564 /// 565 /// This method runs the %Johnson algorithm in order to compute 566 /// the shortest path to each node pairs. If the graph contains 567 /// negative circle it gives back false. The algorithm 568 /// computes 569 /// - The shortest path tree for each node. 570 /// - The distance between each node pairs. 571 bool checkedStart() { 572 573 BelmannFordType belmannford(*graph, *length); 574 575 NullMap<Node, Edge> predMap; 576 577 belmannford.predMap(predMap); 578 579 belmannford.init(OperationTraits::zero()); 580 if (!belmannford.checkedStart()) return false; 581 582 shiftedRun(belmannford); 583 return true; 584 } 585 435 586 436 587 /// \brief Runs %Johnson algorithm.
Note: See TracChangeset
for help on using the changeset viewer.