173 return new DistMap(graph); |
173 return new DistMap(graph); |
174 } |
174 } |
175 |
175 |
176 }; |
176 }; |
177 |
177 |
178 /// \brief Johnson algorithm class. |
178 /// \brief %Johnson algorithm class. |
179 /// |
179 /// |
180 /// \ingroup flowalgs |
180 /// \ingroup flowalgs |
181 /// This class provides an efficient implementation of \c Johnson |
181 /// This class provides an efficient implementation of \c %Johnson |
182 /// algorithm. The edge lengths are passed to the algorithm using a |
182 /// algorithm. The edge lengths are passed to the algorithm using a |
183 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
183 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any |
184 /// kind of length. |
184 /// kind of length. |
185 /// |
185 /// |
186 /// The algorithm solves the shortest path problem for each pairs |
186 /// The algorithm solves the shortest path problem for each pairs |
187 /// of node when the edges can have negative length but the graph should |
187 /// of node when the edges can have negative length but the graph should |
188 /// not contain circle with negative sum of length. If we can assume |
188 /// not contain cycles with negative sum of length. If we can assume |
189 /// that all edge is non-negative in the graph then the dijkstra algorithm |
189 /// that all edge is non-negative in the graph then the dijkstra algorithm |
190 /// should be used from each node. |
190 /// should be used from each node. |
191 /// |
191 /// |
192 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or |
192 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or |
193 /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap |
193 /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap |
375 static Heap *createHeap(HeapCrossRef &) |
375 static Heap *createHeap(HeapCrossRef &) |
376 { |
376 { |
377 throw UninitializedParameter(); |
377 throw UninitializedParameter(); |
378 } |
378 } |
379 }; |
379 }; |
380 ///\ref named-templ-param "Named parameter" for setting heap and cross |
380 ///\brief \ref named-templ-param "Named parameter" for setting heap and |
381 ///reference type |
381 ///cross reference type |
382 |
382 |
383 ///\ref named-templ-param "Named parameter" for setting heap and cross |
383 ///\ref named-templ-param "Named parameter" for setting heap and cross |
384 ///reference type |
384 ///reference type |
385 /// |
385 /// |
386 template <class H, class CR = typename Graph::template NodeMap<int> > |
386 template <class H, class CR = typename Graph::template NodeMap<int> > |
485 return *this; |
485 return *this; |
486 } |
486 } |
487 |
487 |
488 protected: |
488 protected: |
489 |
489 |
490 typedef typename BelmannFord<Graph, LengthMap>:: |
490 template <typename PotentialMap> |
491 template DefOperationTraits<OperationTraits>:: |
491 void shiftedRun(const PotentialMap& potential) { |
492 template DefPredMap<NullMap<Node, Edge> >:: |
|
493 Create BelmannFordType; |
|
494 |
|
495 void shiftedRun(const BelmannFordType& belmannford) { |
|
496 |
492 |
497 typename Graph::template EdgeMap<Value> shiftlen(*graph); |
493 typename Graph::template EdgeMap<Value> shiftlen(*graph); |
498 for (EdgeIt it(*graph); it != INVALID; ++it) { |
494 for (EdgeIt it(*graph); it != INVALID; ++it) { |
499 shiftlen[it] = (*length)[it] |
495 shiftlen[it] = (*length)[it] |
500 + belmannford.dist(graph->source(it)) |
496 + potential[graph->source(it)] |
501 - belmannford.dist(graph->target(it)); |
497 - potential[graph->target(it)]; |
502 } |
498 } |
503 |
499 |
504 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >:: |
500 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >:: |
505 template DefHeap<Heap, HeapCrossRef>:: |
501 template DefHeap<Heap, HeapCrossRef>:: |
506 Create dijkstra(*graph, shiftlen); |
502 Create dijkstra(*graph, shiftlen); |
510 for (NodeIt it(*graph); it != INVALID; ++it) { |
506 for (NodeIt it(*graph); it != INVALID; ++it) { |
511 dijkstra.run(it); |
507 dijkstra.run(it); |
512 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
508 for (NodeIt jt(*graph); jt != INVALID; ++jt) { |
513 if (dijkstra.reached(jt)) { |
509 if (dijkstra.reached(jt)) { |
514 _dist->set(it, jt, dijkstra.dist(jt) + |
510 _dist->set(it, jt, dijkstra.dist(jt) + |
515 belmannford.dist(jt) - belmannford.dist(it)); |
511 potential[jt] - potential[it]); |
516 _pred->set(it, jt, dijkstra.pred(jt)); |
512 _pred->set(it, jt, dijkstra.pred(jt)); |
517 } else { |
513 } else { |
518 _dist->set(it, jt, OperationTraits::infinity()); |
514 _dist->set(it, jt, OperationTraits::infinity()); |
519 _pred->set(it, jt, INVALID); |
515 _pred->set(it, jt, INVALID); |
520 } |
516 } |
548 /// computes |
544 /// computes |
549 /// - The shortest path tree for each node. |
545 /// - The shortest path tree for each node. |
550 /// - The distance between each node pairs. |
546 /// - The distance between each node pairs. |
551 void start() { |
547 void start() { |
552 |
548 |
|
549 typedef typename BelmannFord<Graph, LengthMap>:: |
|
550 template DefOperationTraits<OperationTraits>:: |
|
551 template DefPredMap<NullMap<Node, Edge> >:: |
|
552 Create BelmannFordType; |
|
553 |
553 BelmannFordType belmannford(*graph, *length); |
554 BelmannFordType belmannford(*graph, *length); |
554 |
555 |
555 NullMap<Node, Edge> predMap; |
556 NullMap<Node, Edge> predMap; |
556 |
557 |
557 belmannford.predMap(predMap); |
558 belmannford.predMap(predMap); |
558 |
559 |
559 belmannford.init(OperationTraits::zero()); |
560 belmannford.init(OperationTraits::zero()); |
560 belmannford.start(); |
561 belmannford.start(); |
561 |
562 |
562 shiftedRun(belmannford); |
563 shiftedRun(belmannford.distMap()); |
563 } |
564 } |
564 |
565 |
565 /// \brief Executes the algorithm and checks the negatvie circles. |
566 /// \brief Executes the algorithm and checks the negatvie cycles. |
566 /// |
567 /// |
567 /// This method runs the %Johnson algorithm in order to compute |
568 /// This method runs the %Johnson algorithm in order to compute |
568 /// the shortest path to each node pairs. If the graph contains |
569 /// the shortest path to each node pairs. If the graph contains |
569 /// negative circle it gives back false. The algorithm |
570 /// negative cycle it gives back false. The algorithm |
570 /// computes |
571 /// computes |
571 /// - The shortest path tree for each node. |
572 /// - The shortest path tree for each node. |
572 /// - The distance between each node pairs. |
573 /// - The distance between each node pairs. |
573 bool checkedStart() { |
574 bool checkedStart() { |
|
575 |
|
576 typedef typename BelmannFord<Graph, LengthMap>:: |
|
577 template DefOperationTraits<OperationTraits>:: |
|
578 template DefPredMap<NullMap<Node, Edge> >:: |
|
579 Create BelmannFordType; |
574 |
580 |
575 BelmannFordType belmannford(*graph, *length); |
581 BelmannFordType belmannford(*graph, *length); |
576 |
582 |
577 NullMap<Node, Edge> predMap; |
583 NullMap<Node, Edge> predMap; |
578 |
584 |
579 belmannford.predMap(predMap); |
585 belmannford.predMap(predMap); |
580 |
586 |
581 belmannford.init(OperationTraits::zero()); |
587 belmannford.init(OperationTraits::zero()); |
582 if (!belmannford.checkedStart()) return false; |
588 if (!belmannford.checkedStart()) return false; |
583 |
589 |
584 shiftedRun(belmannford); |
590 shiftedRun(belmannford.distMap()); |
585 return true; |
591 return true; |
586 } |
592 } |
587 |
593 |
588 |
594 |
589 /// \brief Runs %Johnson algorithm. |
595 /// \brief Runs %Johnson algorithm. |