2 * lemon/johnson.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_JOHNSON_H
18 #define LEMON_JOHNSON_H
22 /// \brief Johnson algorithm.
25 #include <lemon/list_graph.h>
26 #include <lemon/graph_utils.h>
27 #include <lemon/dijkstra.h>
28 #include <lemon/belmann_ford.h>
29 #include <lemon/invalid.h>
30 #include <lemon/error.h>
31 #include <lemon/maps.h>
32 #include <lemon/matrix_maps.h>
38 /// \brief Default OperationTraits for the Johnson algorithm class.
40 /// It defines all computational operations and constants which are
41 /// used in the Floyd-Warshall algorithm. The default implementation
42 /// is based on the numeric_limits class. If the numeric type does not
43 /// have infinity value then the maximum value is used as extremal
47 bool has_infinity = std::numeric_limits<Value>::has_infinity>
48 struct JohnsonDefaultOperationTraits {
49 /// \brief Gives back the zero value of the type.
51 return static_cast<Value>(0);
53 /// \brief Gives back the positive infinity value of the type.
54 static Value infinity() {
55 return std::numeric_limits<Value>::infinity();
57 /// \brief Gives back the sum of the given two elements.
58 static Value plus(const Value& left, const Value& right) {
61 /// \brief Gives back true only if the first value less than the second.
62 static bool less(const Value& left, const Value& right) {
67 template <typename Value>
68 struct JohnsonDefaultOperationTraits<Value, false> {
70 return static_cast<Value>(0);
72 static Value infinity() {
73 return std::numeric_limits<Value>::max();
75 static Value plus(const Value& left, const Value& right) {
76 if (left == infinity() || right == infinity()) return infinity();
79 static bool less(const Value& left, const Value& right) {
84 /// \brief Default traits class of Johnson class.
86 /// Default traits class of Johnson class.
87 /// \param _Graph Graph type.
88 /// \param _LegthMap Type of length map.
89 template<class _Graph, class _LengthMap>
90 struct JohnsonDefaultTraits {
91 /// The graph type the algorithm runs on.
94 /// \brief The type of the map that stores the edge lengths.
96 /// The type of the map that stores the edge lengths.
97 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
98 typedef _LengthMap LengthMap;
100 // The type of the length of the edges.
101 typedef typename _LengthMap::Value Value;
103 /// \brief Operation traits for belmann-ford algorithm.
105 /// It defines the infinity type on the given Value type
106 /// and the used operation.
107 /// \see JohnsonDefaultOperationTraits
108 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
110 /// The cross reference type used by heap.
112 /// The cross reference type used by heap.
113 /// Usually it is \c Graph::NodeMap<int>.
114 typedef typename Graph::template NodeMap<int> HeapCrossRef;
116 ///Instantiates a HeapCrossRef.
118 ///This function instantiates a \ref HeapCrossRef.
119 /// \param graph is the graph, to which we would like to define the
121 static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
122 return new HeapCrossRef(graph);
125 ///The heap type used by Dijkstra algorithm.
127 ///The heap type used by Dijkstra algorithm.
131 typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
132 HeapCrossRef, std::less<Value> > Heap;
134 ///Instantiates a Heap.
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);
142 /// \brief The type of the matrix map that stores the last edges of the
145 /// The type of the map that stores the last edges of the shortest paths.
146 /// It must be a matrix map with \c Graph::Edge value type.
148 typedef DynamicMatrixMap<Graph, typename Graph::Node,
149 typename Graph::Edge> PredMap;
151 /// \brief Instantiates a PredMap.
153 /// This function instantiates a \ref PredMap.
154 /// \param G is the graph, to which we would like to define the PredMap.
155 /// \todo The graph alone may be insufficient for the initialization
156 static PredMap *createPredMap(const Graph& graph) {
157 return new PredMap(graph);
160 /// \brief The type of the matrix map that stores the dists of the nodes.
162 /// The type of the matrix map that stores the dists of the nodes.
163 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
165 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
167 /// \brief Instantiates a DistMap.
169 /// This function instantiates a \ref DistMap.
170 /// \param G is the graph, to which we would like to define the
172 static DistMap *createDistMap(const _Graph& graph) {
173 return new DistMap(graph);
178 /// \brief %Johnson algorithm class.
180 /// \ingroup flowalgs
181 /// This class provides an efficient implementation of \c %Johnson
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
186 /// The algorithm solves the shortest path problem for each pair
187 /// of node when the edges can have negative length but the graph should
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
190 /// should be used from each node.
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
194 /// implementation is slower than either binary heap implementation or the
195 /// Floyd-Warshall algorithm.
197 /// The type of the length is determined by the
198 /// \ref concept::ReadMap::Value "Value" of the length map.
200 /// \param _Graph The graph type the algorithm runs on. The default value
201 /// is \ref ListGraph. The value of _Graph is not used directly by
202 /// Johnson, it is only passed to \ref JohnsonDefaultTraits.
203 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
204 /// edges. It is read once for each edge, so the map may involve in
205 /// relatively time consuming process to compute the edge length if
206 /// it is necessary. The default map type is \ref
207 /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
208 /// of _LengthMap is not used directly by Johnson, it is only passed
209 /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set
210 /// various data types used by the algorithm. The default traits
211 /// class is \ref JohnsonDefaultTraits
212 /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref
213 /// JohnsonDefaultTraits for the documentation of a Johnson traits
216 /// \author Balazs Dezso
219 template <typename _Graph, typename _LengthMap, typename _Traits>
221 template <typename _Graph=ListGraph,
222 typename _LengthMap=typename _Graph::template EdgeMap<int>,
223 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
228 /// \brief \ref Exception for uninitialized parameters.
230 /// This error represents problems in the initialization
231 /// of the parameters of the algorithms.
233 class UninitializedParameter : public lemon::UninitializedParameter {
235 virtual const char* exceptionName() const {
236 return "lemon::Johnson::UninitializedParameter";
240 typedef _Traits Traits;
241 ///The type of the underlying graph.
242 typedef typename _Traits::Graph Graph;
244 typedef typename Graph::Node Node;
245 typedef typename Graph::NodeIt NodeIt;
246 typedef typename Graph::Edge Edge;
247 typedef typename Graph::EdgeIt EdgeIt;
249 /// \brief The type of the length of the edges.
250 typedef typename _Traits::LengthMap::Value Value;
251 /// \brief The type of the map that stores the edge lengths.
252 typedef typename _Traits::LengthMap LengthMap;
253 /// \brief The type of the map that stores the last
254 /// edges of the shortest paths. The type of the PredMap
255 /// is a matrix map for Edges
256 typedef typename _Traits::PredMap PredMap;
257 /// \brief The type of the map that stores the dists of the nodes.
258 /// The type of the DistMap is a matrix map for Values
259 typedef typename _Traits::DistMap DistMap;
260 /// \brief The operation traits.
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;
267 /// Pointer to the underlying graph.
269 /// Pointer to the length map
270 const LengthMap *length;
271 ///Pointer to the map of predecessors edges.
273 ///Indicates if \ref _pred is locally allocated (\c true) or not.
275 ///Pointer to the map of distances.
277 ///Indicates if \ref _dist is locally allocated (\c true) or not.
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.
285 ///Indicates if \ref _heap is locally allocated (\c true) or not.
288 /// Creates the maps if necessary.
292 _pred = Traits::createPredMap(*graph);
296 _dist = Traits::createDistMap(*graph);
298 if (!_heap_cross_ref) {
299 local_heap_cross_ref = true;
300 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
304 _heap = Traits::createHeap(*_heap_cross_ref);
310 typedef Johnson Create;
312 /// \name Named template parameters
317 struct DefPredMapTraits : public Traits {
319 static PredMap *createPredMap(const Graph& graph) {
320 throw UninitializedParameter();
324 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
326 /// \ref named-templ-param "Named parameter" for setting PredMap type
330 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
331 typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
335 struct DefDistMapTraits : public Traits {
337 static DistMap *createDistMap(const Graph& graph) {
338 throw UninitializedParameter();
341 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
344 /// \ref named-templ-param "Named parameter" for setting DistMap type
348 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
349 typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
353 struct DefOperationTraitsTraits : public Traits {
354 typedef T OperationTraits;
357 /// \brief \ref named-templ-param "Named parameter" for setting
358 /// OperationTraits type
360 /// \ref named-templ-param "Named parameter" for setting
361 /// OperationTraits type
363 struct DefOperationTraits
364 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
365 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
368 template <class H, class CR>
369 struct DefHeapTraits : public Traits {
370 typedef CR HeapCrossRef;
372 static HeapCrossRef *createHeapCrossRef(const Graph &) {
373 throw UninitializedParameter();
375 static Heap *createHeap(HeapCrossRef &)
377 throw UninitializedParameter();
380 ///\brief \ref named-templ-param "Named parameter" for setting heap and
381 ///cross reference type
383 ///\ref named-templ-param "Named parameter" for setting heap and cross
386 template <class H, class CR = typename Graph::template NodeMap<int> >
388 : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
389 typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
392 template <class H, class CR>
393 struct DefStandardHeapTraits : public Traits {
394 typedef CR HeapCrossRef;
396 static HeapCrossRef *createHeapCrossRef(const Graph &G) {
397 return new HeapCrossRef(G);
399 static Heap *createHeap(HeapCrossRef &R)
404 ///\ref named-templ-param "Named parameter" for setting heap and cross
405 ///reference type with automatic allocation
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> >
426 typedef Johnson Create;
428 /// \brief Constructor.
430 /// \param _graph the graph the algorithm will run on.
431 /// \param _length the length map used by the algorithm.
432 Johnson(const Graph& _graph, const LengthMap& _length) :
433 graph(&_graph), length(&_length),
434 _pred(0), local_pred(false),
435 _dist(0), local_dist(false),
436 _heap_cross_ref(0), local_heap_cross_ref(false),
437 _heap(0), local_heap(false) {}
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;
447 /// \brief Sets the length map.
449 /// Sets the length map.
450 /// \return \c (*this)
451 Johnson &lengthMap(const LengthMap &m) {
456 /// \brief Sets the map storing the predecessor edges.
458 /// Sets the map storing the predecessor edges.
459 /// If you don't use this function before calling \ref run(),
460 /// it will allocate one. The destuctor deallocates this
461 /// automatically allocated map, of course.
462 /// \return \c (*this)
463 Johnson &predMap(PredMap &m) {
472 /// \brief Sets the map storing the distances calculated by the algorithm.
474 /// Sets the map storing the distances calculated by the algorithm.
475 /// If you don't use this function before calling \ref run(),
476 /// it will allocate one. The destuctor deallocates this
477 /// automatically allocated map, of course.
478 /// \return \c (*this)
479 Johnson &distMap(DistMap &m) {
490 template <typename PotentialMap>
491 void shiftedRun(const PotentialMap& potential) {
493 typename Graph::template EdgeMap<Value> shiftlen(*graph);
494 for (EdgeIt it(*graph); it != INVALID; ++it) {
495 shiftlen[it] = (*length)[it]
496 + potential[graph->source(it)]
497 - potential[graph->target(it)];
500 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
501 template DefHeap<Heap, HeapCrossRef>::
502 Create dijkstra(*graph, shiftlen);
504 dijkstra.heap(*_heap, *_heap_cross_ref);
506 for (NodeIt it(*graph); it != INVALID; ++it) {
508 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
509 if (dijkstra.reached(jt)) {
510 _dist->set(it, jt, dijkstra.dist(jt) +
511 potential[jt] - potential[it]);
512 _pred->set(it, jt, dijkstra.predEdge(jt));
514 _dist->set(it, jt, OperationTraits::infinity());
515 _pred->set(it, jt, INVALID);
523 ///\name Execution control
524 /// The simplest way to execute the algorithm is to use
525 /// one of the member functions called \c run(...).
527 /// If you need more control on the execution,
528 /// Finally \ref start() will perform the actual path
533 /// \brief Initializes the internal data structures.
535 /// Initializes the internal data structures.
540 /// \brief Executes the algorithm.
542 /// This method runs the %Johnson algorithm in order to compute
543 /// the shortest path to each node pairs. The algorithm
545 /// - The shortest path tree for each node.
546 /// - The distance between each node pairs.
549 typedef typename BelmannFord<Graph, LengthMap>::
550 template DefOperationTraits<OperationTraits>::
551 template DefPredMap<NullMap<Node, Edge> >::
552 Create BelmannFordType;
554 BelmannFordType belmannford(*graph, *length);
556 NullMap<Node, Edge> predMap;
558 belmannford.predMap(predMap);
560 belmannford.init(OperationTraits::zero());
563 shiftedRun(belmannford.distMap());
566 /// \brief Executes the algorithm and checks the negatvie cycles.
568 /// This method runs the %Johnson algorithm in order to compute
569 /// the shortest path to each node pairs. If the graph contains
570 /// negative cycle it gives back false. The algorithm
572 /// - The shortest path tree for each node.
573 /// - The distance between each node pairs.
574 bool checkedStart() {
576 typedef typename BelmannFord<Graph, LengthMap>::
577 template DefOperationTraits<OperationTraits>::
578 template DefPredMap<NullMap<Node, Edge> >::
579 Create BelmannFordType;
581 BelmannFordType belmannford(*graph, *length);
583 NullMap<Node, Edge> predMap;
585 belmannford.predMap(predMap);
587 belmannford.init(OperationTraits::zero());
588 if (!belmannford.checkedStart()) return false;
590 shiftedRun(belmannford.distMap());
595 /// \brief Runs %Johnson algorithm.
597 /// This method runs the %Johnson algorithm from a each node
598 /// in order to compute the shortest path to each node pairs.
599 /// The algorithm computes
600 /// - The shortest path tree for each node.
601 /// - The distance between each node pairs.
603 /// \note d.run(s) is just a shortcut of the following code.
615 /// \name Query Functions
616 /// The result of the %Johnson algorithm can be obtained using these
618 /// Before the use of these functions,
619 /// either run() or start() must be called.
623 /// \brief Copies the shortest path to \c t into \c p
625 /// This function copies the shortest path to \c t into \c p.
626 /// If it \c t is a source itself or unreachable, then it does not
628 /// \return Returns \c true if a path to \c t was actually copied to \c p,
629 /// \c false otherwise.
631 template <typename Path>
632 bool getPath(Path &p, Node source, Node target) {
633 if (connected(source, target)) {
635 typename Path::Builder b(target);
636 for(b.setStartNode(target); predEdge(source, target) != INVALID;
637 target = predNode(target)) {
638 b.pushFront(predEdge(source, target));
646 /// \brief The distance between two nodes.
648 /// Returns the distance between two nodes.
649 /// \pre \ref run() must be called before using this function.
650 /// \warning If node \c v in unreachable from the root the return value
651 /// of this funcion is undefined.
652 Value dist(Node source, Node target) const {
653 return (*_dist)(source, target);
656 /// \brief Returns the 'previous edge' of the shortest path tree.
658 /// For the node \c node it returns the 'previous edge' of the shortest
659 /// path tree to direction of the node \c root
660 /// i.e. it returns the last edge of a shortest path from the node \c root
661 /// to \c node. It is \ref INVALID if \c node is unreachable from the root
662 /// or if \c node=root. The shortest path tree used here is equal to the
663 /// shortest path tree used in \ref predNode().
664 /// \pre \ref run() must be called before using this function.
665 Edge predEdge(Node root, Node node) const {
666 return (*_pred)(root, node);
669 /// \brief Returns the 'previous node' of the shortest path tree.
671 /// For a node \c node it returns the 'previous node' of the shortest path
672 /// tree to direction of the node \c root, i.e. it returns the last but
673 /// one node from a shortest path from the \c root to \c node. It is
674 /// INVALID if \c node is unreachable from the root or if \c node=root.
675 /// The shortest path tree used here is equal to the
676 /// shortest path tree used in \ref predEdge().
677 /// \pre \ref run() must be called before using this function.
678 Node predNode(Node root, Node node) const {
679 return (*_pred)(root, node) == INVALID ?
680 INVALID : graph->source((*_pred)(root, node));
683 /// \brief Returns a reference to the matrix node map of distances.
685 /// Returns a reference to the matrix node map of distances.
687 /// \pre \ref run() must be called before using this function.
688 const DistMap &distMap() const { return *_dist;}
690 /// \brief Returns a reference to the shortest path tree map.
692 /// Returns a reference to the matrix node map of the edges of the
693 /// shortest path tree.
694 /// \pre \ref run() must be called before using this function.
695 const PredMap &predMap() const { return *_pred;}
697 /// \brief Checks if a node is reachable from the root.
699 /// Returns \c true if \c v is reachable from the root.
700 /// \pre \ref run() must be called before using this function.
702 bool connected(Node source, Node target) {
703 return (*_dist)(source, target) != OperationTraits::infinity();
709 } //END OF NAMESPACE LEMON