In algorithm window maps can be selected and reated through MapSelector widget.
2 * lemon/johnson.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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/bellman_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 bellman-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 /// \name Named template parameters
315 struct DefPredMapTraits : public Traits {
317 static PredMap *createPredMap(const Graph& graph) {
318 throw UninitializedParameter();
322 /// \brief \ref named-templ-param "Named parameter" for setting PredMap
324 /// \ref named-templ-param "Named parameter" for setting PredMap type
328 : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
329 typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
333 struct DefDistMapTraits : public Traits {
335 static DistMap *createDistMap(const Graph& graph) {
336 throw UninitializedParameter();
339 /// \brief \ref named-templ-param "Named parameter" for setting DistMap
342 /// \ref named-templ-param "Named parameter" for setting DistMap type
346 : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
347 typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
351 struct DefOperationTraitsTraits : public Traits {
352 typedef T OperationTraits;
355 /// \brief \ref named-templ-param "Named parameter" for setting
356 /// OperationTraits type
358 /// \ref named-templ-param "Named parameter" for setting
359 /// OperationTraits type
361 struct DefOperationTraits
362 : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
363 typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
366 template <class H, class CR>
367 struct DefHeapTraits : public Traits {
368 typedef CR HeapCrossRef;
370 static HeapCrossRef *createHeapCrossRef(const Graph &) {
371 throw UninitializedParameter();
373 static Heap *createHeap(HeapCrossRef &)
375 throw UninitializedParameter();
378 ///\brief \ref named-templ-param "Named parameter" for setting heap and
379 ///cross reference type
381 ///\ref named-templ-param "Named parameter" for setting heap and cross
384 template <class H, class CR = typename Graph::template NodeMap<int> >
386 : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
387 typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
390 template <class H, class CR>
391 struct DefStandardHeapTraits : public Traits {
392 typedef CR HeapCrossRef;
394 static HeapCrossRef *createHeapCrossRef(const Graph &G) {
395 return new HeapCrossRef(G);
397 static Heap *createHeap(HeapCrossRef &R)
402 ///\ref named-templ-param "Named parameter" for setting heap and cross
403 ///reference type with automatic allocation
405 ///\ref named-templ-param "Named parameter" for setting heap and cross
406 ///reference type. It can allocate the heap and the cross reference
407 ///object if the cross reference's constructor waits for the graph as
408 ///parameter and the heap's constructor waits for the cross reference.
409 template <class H, class CR = typename Graph::template NodeMap<int> >
410 struct DefStandardHeap
411 : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
412 typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
424 typedef Johnson Create;
426 /// \brief Constructor.
428 /// \param _graph the graph the algorithm will run on.
429 /// \param _length the length map used by the algorithm.
430 Johnson(const Graph& _graph, const LengthMap& _length) :
431 graph(&_graph), length(&_length),
432 _pred(0), local_pred(false),
433 _dist(0), local_dist(false),
434 _heap_cross_ref(0), local_heap_cross_ref(false),
435 _heap(0), local_heap(false) {}
439 if (local_pred) delete _pred;
440 if (local_dist) delete _dist;
441 if (local_heap_cross_ref) delete _heap_cross_ref;
442 if (local_heap) delete _heap;
445 /// \brief Sets the length map.
447 /// Sets the length map.
448 /// \return \c (*this)
449 Johnson &lengthMap(const LengthMap &m) {
454 /// \brief Sets the map storing the predecessor edges.
456 /// Sets the map storing the predecessor edges.
457 /// If you don't use this function before calling \ref run(),
458 /// it will allocate one. The destuctor deallocates this
459 /// automatically allocated map, of course.
460 /// \return \c (*this)
461 Johnson &predMap(PredMap &m) {
470 /// \brief Sets the map storing the distances calculated by the algorithm.
472 /// Sets the map storing the distances calculated by the algorithm.
473 /// If you don't use this function before calling \ref run(),
474 /// it will allocate one. The destuctor deallocates this
475 /// automatically allocated map, of course.
476 /// \return \c (*this)
477 Johnson &distMap(DistMap &m) {
488 template <typename PotentialMap>
489 void shiftedRun(const PotentialMap& potential) {
491 typename Graph::template EdgeMap<Value> shiftlen(*graph);
492 for (EdgeIt it(*graph); it != INVALID; ++it) {
493 shiftlen[it] = (*length)[it]
494 + potential[graph->source(it)]
495 - potential[graph->target(it)];
498 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
499 template DefHeap<Heap, HeapCrossRef>::
500 Create dijkstra(*graph, shiftlen);
502 dijkstra.heap(*_heap, *_heap_cross_ref);
504 for (NodeIt it(*graph); it != INVALID; ++it) {
506 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
507 if (dijkstra.reached(jt)) {
508 _dist->set(it, jt, dijkstra.dist(jt) +
509 potential[jt] - potential[it]);
510 _pred->set(it, jt, dijkstra.predEdge(jt));
512 _dist->set(it, jt, OperationTraits::infinity());
513 _pred->set(it, jt, INVALID);
521 ///\name Execution control
522 /// The simplest way to execute the algorithm is to use
523 /// one of the member functions called \c run(...).
525 /// If you need more control on the execution,
526 /// Finally \ref start() will perform the actual path
531 /// \brief Initializes the internal data structures.
533 /// Initializes the internal data structures.
538 /// \brief Executes the algorithm.
540 /// This method runs the %Johnson algorithm in order to compute
541 /// the shortest path to each node pairs. The algorithm
543 /// - The shortest path tree for each node.
544 /// - The distance between each node pairs.
547 typedef typename BellmanFord<Graph, LengthMap>::
548 template DefOperationTraits<OperationTraits>::
549 template DefPredMap<NullMap<Node, Edge> >::
550 Create BellmanFordType;
552 BellmanFordType bellmanford(*graph, *length);
554 NullMap<Node, Edge> predMap;
556 bellmanford.predMap(predMap);
558 bellmanford.init(OperationTraits::zero());
561 shiftedRun(bellmanford.distMap());
564 /// \brief Executes the algorithm and checks the negatvie cycles.
566 /// This method runs the %Johnson algorithm in order to compute
567 /// the shortest path to each node pairs. If the graph contains
568 /// negative cycle it gives back false. The algorithm
570 /// - The shortest path tree for each node.
571 /// - The distance between each node pairs.
572 bool checkedStart() {
574 typedef typename BellmanFord<Graph, LengthMap>::
575 template DefOperationTraits<OperationTraits>::
576 template DefPredMap<NullMap<Node, Edge> >::
577 Create BellmanFordType;
579 BellmanFordType bellmanford(*graph, *length);
581 NullMap<Node, Edge> predMap;
583 bellmanford.predMap(predMap);
585 bellmanford.init(OperationTraits::zero());
586 if (!bellmanford.checkedStart()) return false;
588 shiftedRun(bellmanford.distMap());
593 /// \brief Runs %Johnson algorithm.
595 /// This method runs the %Johnson algorithm from a each node
596 /// in order to compute the shortest path to each node pairs.
597 /// The algorithm computes
598 /// - The shortest path tree for each node.
599 /// - The distance between each node pairs.
601 /// \note d.run(s) is just a shortcut of the following code.
613 /// \name Query Functions
614 /// The result of the %Johnson algorithm can be obtained using these
616 /// Before the use of these functions,
617 /// either run() or start() must be called.
621 /// \brief Copies the shortest path to \c t into \c p
623 /// This function copies the shortest path to \c t into \c p.
624 /// If it \c t is a source itself or unreachable, then it does not
626 /// \return Returns \c true if a path to \c t was actually copied to \c p,
627 /// \c false otherwise.
629 template <typename Path>
630 bool getPath(Path &p, Node source, Node target) {
631 if (connected(source, target)) {
633 typename Path::Builder b(target);
634 for(b.setStartNode(target); predEdge(source, target) != INVALID;
635 target = predNode(target)) {
636 b.pushFront(predEdge(source, target));
644 /// \brief The distance between two nodes.
646 /// Returns the distance between two nodes.
647 /// \pre \ref run() must be called before using this function.
648 /// \warning If node \c v in unreachable from the root the return value
649 /// of this funcion is undefined.
650 Value dist(Node source, Node target) const {
651 return (*_dist)(source, target);
654 /// \brief Returns the 'previous edge' of the shortest path tree.
656 /// For the node \c node it returns the 'previous edge' of the shortest
657 /// path tree to direction of the node \c root
658 /// i.e. it returns the last edge of a shortest path from the node \c root
659 /// to \c node. It is \ref INVALID if \c node is unreachable from the root
660 /// or if \c node=root. The shortest path tree used here is equal to the
661 /// shortest path tree used in \ref predNode().
662 /// \pre \ref run() must be called before using this function.
663 Edge predEdge(Node root, Node node) const {
664 return (*_pred)(root, node);
667 /// \brief Returns the 'previous node' of the shortest path tree.
669 /// For a node \c node it returns the 'previous node' of the shortest path
670 /// tree to direction of the node \c root, i.e. it returns the last but
671 /// one node from a shortest path from the \c root to \c node. It is
672 /// INVALID if \c node is unreachable from the root or if \c node=root.
673 /// The shortest path tree used here is equal to the
674 /// shortest path tree used in \ref predEdge().
675 /// \pre \ref run() must be called before using this function.
676 Node predNode(Node root, Node node) const {
677 return (*_pred)(root, node) == INVALID ?
678 INVALID : graph->source((*_pred)(root, node));
681 /// \brief Returns a reference to the matrix node map of distances.
683 /// Returns a reference to the matrix node map of distances.
685 /// \pre \ref run() must be called before using this function.
686 const DistMap &distMap() const { return *_dist;}
688 /// \brief Returns a reference to the shortest path tree map.
690 /// Returns a reference to the matrix node map of the edges of the
691 /// shortest path tree.
692 /// \pre \ref run() must be called before using this function.
693 const PredMap &predMap() const { return *_pred;}
695 /// \brief Checks if a node is reachable from the root.
697 /// Returns \c true if \c v is reachable from the root.
698 /// \pre \ref run() must be called before using this function.
700 bool connected(Node source, Node target) {
701 return (*_dist)(source, target) != OperationTraits::infinity();
707 } //END OF NAMESPACE LEMON