The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_JOHNSON_H
20 #define LEMON_JOHNSON_H
24 /// \brief Johnson algorithm.
27 #include <lemon/list_graph.h>
28 #include <lemon/graph_utils.h>
29 #include <lemon/dijkstra.h>
30 #include <lemon/bellman_ford.h>
31 #include <lemon/invalid.h>
32 #include <lemon/error.h>
33 #include <lemon/maps.h>
34 #include <lemon/matrix_maps.h>
40 /// \brief Default OperationTraits for the Johnson algorithm class.
42 /// It defines all computational operations and constants which are
43 /// used in the Floyd-Warshall algorithm. The default implementation
44 /// is based on the numeric_limits class. If the numeric type does not
45 /// have infinity value then the maximum value is used as extremal
49 bool has_infinity = std::numeric_limits<Value>::has_infinity>
50 struct JohnsonDefaultOperationTraits {
51 /// \brief Gives back the zero value of the type.
53 return static_cast<Value>(0);
55 /// \brief Gives back the positive infinity value of the type.
56 static Value infinity() {
57 return std::numeric_limits<Value>::infinity();
59 /// \brief Gives back the sum of the given two elements.
60 static Value plus(const Value& left, const Value& right) {
63 /// \brief Gives back true only if the first value less than the second.
64 static bool less(const Value& left, const Value& right) {
69 template <typename Value>
70 struct JohnsonDefaultOperationTraits<Value, false> {
72 return static_cast<Value>(0);
74 static Value infinity() {
75 return std::numeric_limits<Value>::max();
77 static Value plus(const Value& left, const Value& right) {
78 if (left == infinity() || right == infinity()) return infinity();
81 static bool less(const Value& left, const Value& right) {
86 /// \brief Default traits class of Johnson class.
88 /// Default traits class of Johnson class.
89 /// \param _Graph Graph type.
90 /// \param _LegthMap Type of length map.
91 template<class _Graph, class _LengthMap>
92 struct JohnsonDefaultTraits {
93 /// The graph type the algorithm runs on.
96 /// \brief The type of the map that stores the edge lengths.
98 /// The type of the map that stores the edge lengths.
99 /// It must meet the \ref concept::ReadMap "ReadMap" concept.
100 typedef _LengthMap LengthMap;
102 // The type of the length of the edges.
103 typedef typename _LengthMap::Value Value;
105 /// \brief Operation traits for bellman-ford algorithm.
107 /// It defines the infinity type on the given Value type
108 /// and the used operation.
109 /// \see JohnsonDefaultOperationTraits
110 typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
112 /// The cross reference type used by heap.
114 /// The cross reference type used by heap.
115 /// Usually it is \c Graph::NodeMap<int>.
116 typedef typename Graph::template NodeMap<int> HeapCrossRef;
118 ///Instantiates a HeapCrossRef.
120 ///This function instantiates a \ref HeapCrossRef.
121 /// \param graph is the graph, to which we would like to define the
123 static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
124 return new HeapCrossRef(graph);
127 ///The heap type used by Dijkstra algorithm.
129 ///The heap type used by Dijkstra algorithm.
133 typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
134 HeapCrossRef, std::less<Value> > Heap;
136 ///Instantiates a Heap.
138 ///This function instantiates a \ref Heap.
139 /// \param crossRef The cross reference for the heap.
140 static Heap *createHeap(HeapCrossRef& crossRef) {
141 return new Heap(crossRef);
144 /// \brief The type of the matrix map that stores the last edges of the
147 /// The type of the map that stores the last edges of the shortest paths.
148 /// It must be a matrix map with \c Graph::Edge value type.
150 typedef DynamicMatrixMap<Graph, typename Graph::Node,
151 typename Graph::Edge> PredMap;
153 /// \brief Instantiates a PredMap.
155 /// This function instantiates a \ref PredMap.
156 /// \param graph is the graph, to which we would like to define the PredMap.
157 /// \todo The graph alone may be insufficient for the initialization
158 static PredMap *createPredMap(const Graph& graph) {
159 return new PredMap(graph);
162 /// \brief The type of the matrix map that stores the dists of the nodes.
164 /// The type of the matrix map that stores the dists of the nodes.
165 /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
167 typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
169 /// \brief Instantiates a DistMap.
171 /// This function instantiates a \ref DistMap.
172 /// \param graph is the graph, to which we would like to define the
174 static DistMap *createDistMap(const _Graph& graph) {
175 return new DistMap(graph);
180 /// \brief %Johnson algorithm class.
182 /// \ingroup flowalgs
183 /// This class provides an efficient implementation of \c %Johnson
184 /// algorithm. The edge lengths are passed to the algorithm using a
185 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
188 /// The algorithm solves the shortest path problem for each pair
189 /// of node when the edges can have negative length but the graph should
190 /// not contain cycles with negative sum of length. If we can assume
191 /// that all edge is non-negative in the graph then the dijkstra algorithm
192 /// should be used from each node.
194 /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
195 /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
196 /// implementation is slower than either binary heap implementation or the
197 /// Floyd-Warshall algorithm.
199 /// The type of the length is determined by the
200 /// \ref concept::ReadMap::Value "Value" of the length map.
202 /// \param _Graph The graph type the algorithm runs on. The default value
203 /// is \ref ListGraph. The value of _Graph is not used directly by
204 /// Johnson, it is only passed to \ref JohnsonDefaultTraits.
205 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
206 /// edges. It is read once for each edge, so the map may involve in
207 /// relatively time consuming process to compute the edge length if
208 /// it is necessary. The default map type is \ref
209 /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
210 /// of _LengthMap is not used directly by Johnson, it is only passed
211 /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set
212 /// various data types used by the algorithm. The default traits
213 /// class is \ref JohnsonDefaultTraits
214 /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref
215 /// JohnsonDefaultTraits for the documentation of a Johnson traits
218 /// \author Balazs Dezso
221 template <typename _Graph, typename _LengthMap, typename _Traits>
223 template <typename _Graph=ListGraph,
224 typename _LengthMap=typename _Graph::template EdgeMap<int>,
225 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
230 /// \brief \ref Exception for uninitialized parameters.
232 /// This error represents problems in the initialization
233 /// of the parameters of the algorithms.
235 class UninitializedParameter : public lemon::UninitializedParameter {
237 virtual const char* exceptionName() const {
238 return "lemon::Johnson::UninitializedParameter";
242 typedef _Traits Traits;
243 ///The type of the underlying graph.
244 typedef typename _Traits::Graph Graph;
246 typedef typename Graph::Node Node;
247 typedef typename Graph::NodeIt NodeIt;
248 typedef typename Graph::Edge Edge;
249 typedef typename Graph::EdgeIt EdgeIt;
251 /// \brief The type of the length of the edges.
252 typedef typename _Traits::LengthMap::Value Value;
253 /// \brief The type of the map that stores the edge lengths.
254 typedef typename _Traits::LengthMap LengthMap;
255 /// \brief The type of the map that stores the last
256 /// edges of the shortest paths. The type of the PredMap
257 /// is a matrix map for Edges
258 typedef typename _Traits::PredMap PredMap;
259 /// \brief The type of the map that stores the dists of the nodes.
260 /// The type of the DistMap is a matrix map for Values
261 typedef typename _Traits::DistMap DistMap;
262 /// \brief The operation traits.
263 typedef typename _Traits::OperationTraits OperationTraits;
264 ///The cross reference type used for the current heap.
265 typedef typename _Traits::HeapCrossRef HeapCrossRef;
266 ///The heap type used by the dijkstra algorithm.
267 typedef typename _Traits::Heap Heap;
269 /// Pointer to the underlying graph.
271 /// Pointer to the length map
272 const LengthMap *length;
273 ///Pointer to the map of predecessors edges.
275 ///Indicates if \ref _pred is locally allocated (\c true) or not.
277 ///Pointer to the map of distances.
279 ///Indicates if \ref _dist is locally allocated (\c true) or not.
281 ///Pointer to the heap cross references.
282 HeapCrossRef *_heap_cross_ref;
283 ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
284 bool local_heap_cross_ref;
285 ///Pointer to the heap.
287 ///Indicates if \ref _heap is locally allocated (\c true) or not.
290 /// Creates the maps if necessary.
294 _pred = Traits::createPredMap(*graph);
298 _dist = Traits::createDistMap(*graph);
300 if (!_heap_cross_ref) {
301 local_heap_cross_ref = true;
302 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
306 _heap = Traits::createHeap(*_heap_cross_ref);
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 ///\name Execution control
491 /// The simplest way to execute the algorithm is to use
492 /// one of the member functions called \c run(...).
494 /// If you need more control on the execution,
495 /// Finally \ref start() will perform the actual path
500 /// \brief Initializes the internal data structures.
502 /// Initializes the internal data structures.
507 /// \brief Executes the algorithm with own potential map.
509 /// This method runs the %Johnson algorithm in order to compute
510 /// the shortest path to each node pairs. The potential map
511 /// can be given for this algorithm which usually calculated
512 /// by the Bellman-Ford algorithm. If the graph does not have
513 /// negative length edge then this start function can be used
514 /// with constMap<Node, int>(0) parameter to omit the running time of
515 /// the Bellman-Ford.
516 /// The algorithm computes
517 /// - The shortest path tree for each node.
518 /// - The distance between each node pairs.
519 template <typename PotentialMap>
520 void shiftedStart(const PotentialMap& potential) {
521 typename Graph::template EdgeMap<Value> shiftlen(*graph);
522 for (EdgeIt it(*graph); it != INVALID; ++it) {
523 shiftlen[it] = (*length)[it]
524 + potential[graph->source(it)]
525 - potential[graph->target(it)];
528 typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
529 template DefHeap<Heap, HeapCrossRef>::
530 Create dijkstra(*graph, shiftlen);
532 dijkstra.heap(*_heap, *_heap_cross_ref);
534 for (NodeIt it(*graph); it != INVALID; ++it) {
536 for (NodeIt jt(*graph); jt != INVALID; ++jt) {
537 if (dijkstra.reached(jt)) {
538 _dist->set(it, jt, dijkstra.dist(jt) +
539 potential[jt] - potential[it]);
540 _pred->set(it, jt, dijkstra.predEdge(jt));
542 _dist->set(it, jt, OperationTraits::infinity());
543 _pred->set(it, jt, INVALID);
549 /// \brief Executes the algorithm.
551 /// This method runs the %Johnson algorithm in order to compute
552 /// the shortest path to each node pairs. The algorithm
554 /// - The shortest path tree for each node.
555 /// - The distance between each node pairs.
558 typedef typename BellmanFord<Graph, LengthMap>::
559 template DefOperationTraits<OperationTraits>::
560 template DefPredMap<NullMap<Node, Edge> >::
561 Create BellmanFordType;
563 BellmanFordType bellmanford(*graph, *length);
565 NullMap<Node, Edge> predMap;
567 bellmanford.predMap(predMap);
569 bellmanford.init(OperationTraits::zero());
572 shiftedStart(bellmanford.distMap());
575 /// \brief Executes the algorithm and checks the negatvie cycles.
577 /// This method runs the %Johnson algorithm in order to compute
578 /// the shortest path to each node pairs. If the graph contains
579 /// negative cycle it gives back false. The algorithm
581 /// - The shortest path tree for each node.
582 /// - The distance between each node pairs.
583 bool checkedStart() {
585 typedef typename BellmanFord<Graph, LengthMap>::
586 template DefOperationTraits<OperationTraits>::
587 template DefPredMap<NullMap<Node, Edge> >::
588 Create BellmanFordType;
590 BellmanFordType bellmanford(*graph, *length);
592 NullMap<Node, Edge> predMap;
594 bellmanford.predMap(predMap);
596 bellmanford.init(OperationTraits::zero());
597 if (!bellmanford.checkedStart()) return false;
599 shiftedStart(bellmanford.distMap());
604 /// \brief Runs %Johnson algorithm.
606 /// This method runs the %Johnson algorithm from a each node
607 /// in order to compute the shortest path to each node pairs.
608 /// The algorithm computes
609 /// - The shortest path tree for each node.
610 /// - The distance between each node pairs.
612 /// \note d.run(s) is just a shortcut of the following code.
624 /// \name Query Functions
625 /// The result of the %Johnson algorithm can be obtained using these
627 /// Before the use of these functions,
628 /// either run() or start() must be called.
632 /// \brief Copies the shortest path to \c t into \c p
634 /// This function copies the shortest path to \c t into \c p.
635 /// If it \c t is a source itself or unreachable, then it does not
637 /// \return Returns \c true if a path to \c t was actually copied to \c p,
638 /// \c false otherwise.
640 template <typename Path>
641 bool getPath(Path &p, Node source, Node target) {
642 if (connected(source, target)) {
644 typename Path::Builder b(target);
645 for(b.setStartNode(target); predEdge(source, target) != INVALID;
646 target = predNode(target)) {
647 b.pushFront(predEdge(source, target));
655 /// \brief The distance between two nodes.
657 /// Returns the distance between two nodes.
658 /// \pre \ref run() must be called before using this function.
659 /// \warning If node \c v in unreachable from the root the return value
660 /// of this funcion is undefined.
661 Value dist(Node source, Node target) const {
662 return (*_dist)(source, target);
665 /// \brief Returns the 'previous edge' of the shortest path tree.
667 /// For the node \c node it returns the 'previous edge' of the shortest
668 /// path tree to direction of the node \c root
669 /// i.e. it returns the last edge of a shortest path from the node \c root
670 /// to \c node. It is \ref INVALID if \c node is unreachable from the root
671 /// or if \c node=root. The shortest path tree used here is equal to the
672 /// shortest path tree used in \ref predNode().
673 /// \pre \ref run() must be called before using this function.
674 Edge predEdge(Node root, Node node) const {
675 return (*_pred)(root, node);
678 /// \brief Returns the 'previous node' of the shortest path tree.
680 /// For a node \c node it returns the 'previous node' of the shortest path
681 /// tree to direction of the node \c root, i.e. it returns the last but
682 /// one node from a shortest path from the \c root to \c node. It is
683 /// INVALID if \c node is unreachable from the root or if \c node=root.
684 /// The shortest path tree used here is equal to the
685 /// shortest path tree used in \ref predEdge().
686 /// \pre \ref run() must be called before using this function.
687 Node predNode(Node root, Node node) const {
688 return (*_pred)(root, node) == INVALID ?
689 INVALID : graph->source((*_pred)(root, node));
692 /// \brief Returns a reference to the matrix node map of distances.
694 /// Returns a reference to the matrix node map of distances.
696 /// \pre \ref run() must be called before using this function.
697 const DistMap &distMap() const { return *_dist;}
699 /// \brief Returns a reference to the shortest path tree map.
701 /// Returns a reference to the matrix node map of the edges of the
702 /// shortest path tree.
703 /// \pre \ref run() must be called before using this function.
704 const PredMap &predMap() const { return *_pred;}
706 /// \brief Checks if a node is reachable from the root.
708 /// Returns \c true if \c v is reachable from the root.
709 /// \pre \ref run() must be called before using this function.
711 bool connected(Node source, Node target) {
712 return (*_dist)(source, target) != OperationTraits::infinity();
718 } //END OF NAMESPACE LEMON