NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
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 /// \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 BelmannFord<Graph, LengthMap>::
548 template DefOperationTraits<OperationTraits>::
549 template DefPredMap<NullMap<Node, Edge> >::
550 Create BelmannFordType;
552 BelmannFordType belmannford(*graph, *length);
554 NullMap<Node, Edge> predMap;
556 belmannford.predMap(predMap);
558 belmannford.init(OperationTraits::zero());
561 shiftedRun(belmannford.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 BelmannFord<Graph, LengthMap>::
575 template DefOperationTraits<OperationTraits>::
576 template DefPredMap<NullMap<Node, Edge> >::
577 Create BelmannFordType;
579 BelmannFordType belmannford(*graph, *length);
581 NullMap<Node, Edge> predMap;
583 belmannford.predMap(predMap);
585 belmannford.init(OperationTraits::zero());
586 if (!belmannford.checkedStart()) return false;
588 shiftedRun(belmannford.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