COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/johnson.h @ 2335:27aa03cd3121

Last change on this file since 2335:27aa03cd3121 was 2335:27aa03cd3121, checked in by Balazs Dezso, 13 years ago

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File size: 23.4 KB
RevLine 
[1699]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1699]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_JOHNSON_H
20#define LEMON_JOHNSON_H
21
22///\ingroup flowalgs
23/// \file
24/// \brief Johnson algorithm.
25///
26
27#include <lemon/list_graph.h>
28#include <lemon/graph_utils.h>
29#include <lemon/dijkstra.h>
[1864]30#include <lemon/bellman_ford.h>
[2335]31#include <lemon/bits/path_dump.h>
[1993]32#include <lemon/bits/invalid.h>
[1699]33#include <lemon/error.h>
34#include <lemon/maps.h>
[1723]35#include <lemon/matrix_maps.h>
[1699]36
37#include <limits>
38
39namespace lemon {
40
41  /// \brief Default OperationTraits for the Johnson algorithm class.
42  /// 
43  /// It defines all computational operations and constants which are
44  /// used in the Floyd-Warshall algorithm. The default implementation
45  /// is based on the numeric_limits class. If the numeric type does not
46  /// have infinity value then the maximum value is used as extremal
47  /// infinity value.
48  template <
49    typename Value,
50    bool has_infinity = std::numeric_limits<Value>::has_infinity>
51  struct JohnsonDefaultOperationTraits {
52    /// \brief Gives back the zero value of the type.
53    static Value zero() {
54      return static_cast<Value>(0);
55    }
56    /// \brief Gives back the positive infinity value of the type.
57    static Value infinity() {
58      return std::numeric_limits<Value>::infinity();
59    }
60    /// \brief Gives back the sum of the given two elements.
61    static Value plus(const Value& left, const Value& right) {
62      return left + right;
63    }
64    /// \brief Gives back true only if the first value less than the second.
65    static bool less(const Value& left, const Value& right) {
66      return left < right;
67    }
68  };
69
70  template <typename Value>
71  struct JohnsonDefaultOperationTraits<Value, false> {
72    static Value zero() {
73      return static_cast<Value>(0);
74    }
75    static Value infinity() {
76      return std::numeric_limits<Value>::max();
77    }
78    static Value plus(const Value& left, const Value& right) {
79      if (left == infinity() || right == infinity()) return infinity();
80      return left + right;
81    }
82    static bool less(const Value& left, const Value& right) {
83      return left < right;
84    }
85  };
86 
87  /// \brief Default traits class of Johnson class.
88  ///
89  /// Default traits class of Johnson class.
90  /// \param _Graph Graph type.
91  /// \param _LegthMap Type of length map.
92  template<class _Graph, class _LengthMap>
93  struct JohnsonDefaultTraits {
94    /// The graph type the algorithm runs on.
95    typedef _Graph Graph;
96
97    /// \brief The type of the map that stores the edge lengths.
98    ///
99    /// The type of the map that stores the edge lengths.
[2260]100    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
[1699]101    typedef _LengthMap LengthMap;
102
103    // The type of the length of the edges.
104    typedef typename _LengthMap::Value Value;
105
[1864]106    /// \brief Operation traits for bellman-ford algorithm.
[1699]107    ///
108    /// It defines the infinity type on the given Value type
109    /// and the used operation.
110    /// \see JohnsonDefaultOperationTraits
111    typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
[1741]112
113    /// The cross reference type used by heap.
114
115    /// The cross reference type used by heap.
116    /// Usually it is \c Graph::NodeMap<int>.
117    typedef typename Graph::template NodeMap<int> HeapCrossRef;
118
119    ///Instantiates a HeapCrossRef.
120
121    ///This function instantiates a \ref HeapCrossRef.
122    /// \param graph is the graph, to which we would like to define the
123    /// HeapCrossRef.
124    static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
125      return new HeapCrossRef(graph);
126    }
127   
128    ///The heap type used by Dijkstra algorithm.
129
130    ///The heap type used by Dijkstra algorithm.
131    ///
132    ///\sa BinHeap
133    ///\sa Dijkstra
[2263]134    typedef BinHeap<typename LengthMap::Value,
[1741]135                    HeapCrossRef, std::less<Value> > Heap;
136
137    ///Instantiates a Heap.
138
139    ///This function instantiates a \ref Heap.
140    /// \param crossRef The cross reference for the heap.
141    static Heap *createHeap(HeapCrossRef& crossRef) {
142      return new Heap(crossRef);
143    }
[1699]144 
[1723]145    /// \brief The type of the matrix map that stores the last edges of the
[1699]146    /// shortest paths.
147    ///
[1723]148    /// The type of the map that stores the last edges of the shortest paths.
[1699]149    /// It must be a matrix map with \c Graph::Edge value type.
150    ///
[1723]151    typedef DynamicMatrixMap<Graph, typename Graph::Node,
152                             typename Graph::Edge> PredMap;
[1699]153
154    /// \brief Instantiates a PredMap.
155    ///
156    /// This function instantiates a \ref PredMap.
[1953]157    /// \param graph is the graph, to which we would like to define the PredMap.
[1699]158    /// \todo The graph alone may be insufficient for the initialization
[1741]159    static PredMap *createPredMap(const Graph& graph) {
[1699]160      return new PredMap(graph);
161    }
162
[1723]163    /// \brief The type of the matrix map that stores the dists of the nodes.
[1699]164    ///
[1723]165    /// The type of the matrix map that stores the dists of the nodes.
[2260]166    /// It must meet the \ref concepts::WriteMatrixMap "WriteMatrixMap" concept.
[1699]167    ///
[1723]168    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
169   
[1699]170    /// \brief Instantiates a DistMap.
171    ///
172    /// This function instantiates a \ref DistMap.
[1953]173    /// \param graph is the graph, to which we would like to define the
[1699]174    /// \ref DistMap
175    static DistMap *createDistMap(const _Graph& graph) {
176      return new DistMap(graph);
177    }
178
179  };
180
[1754]181  /// \brief %Johnson algorithm class.
[1699]182  ///
183  /// \ingroup flowalgs
[1754]184  /// This class provides an efficient implementation of \c %Johnson
[1699]185  /// algorithm. The edge lengths are passed to the algorithm using a
[2260]186  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
[1699]187  /// kind of length.
188  ///
[1757]189  /// The algorithm solves the shortest path problem for each pair
[1723]190  /// of node when the edges can have negative length but the graph should
[1754]191  /// not contain cycles with negative sum of length. If we can assume
[1723]192  /// that all edge is non-negative in the graph then the dijkstra algorithm
193  /// should be used from each node.
194  ///
[2042]195  /// The complexity of this algorithm is \f$ O(n^2\log(n)+n\log(n)e) \f$ or
196  /// with fibonacci heap \f$ O(n^2\log(n)+ne) \f$. Usually the fibonacci heap
[1741]197  /// implementation is slower than either binary heap implementation or the
198  /// Floyd-Warshall algorithm.
[1723]199  ///
[1699]200  /// The type of the length is determined by the
[2260]201  /// \ref concepts::ReadMap::Value "Value" of the length map.
[1699]202  ///
203  /// \param _Graph The graph type the algorithm runs on. The default value
204  /// is \ref ListGraph. The value of _Graph is not used directly by
205  /// Johnson, it is only passed to \ref JohnsonDefaultTraits.
206  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
207  /// edges. It is read once for each edge, so the map may involve in
208  /// relatively time consuming process to compute the edge length if
209  /// it is necessary. The default map type is \ref
[2260]210  /// concepts::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
[1699]211  /// of _LengthMap is not used directly by Johnson, it is only passed
212  /// to \ref JohnsonDefaultTraits.  \param _Traits Traits class to set
213  /// various data types used by the algorithm.  The default traits
214  /// class is \ref JohnsonDefaultTraits
215  /// "JohnsonDefaultTraits<_Graph,_LengthMap>".  See \ref
216  /// JohnsonDefaultTraits for the documentation of a Johnson traits
217  /// class.
218  ///
219  /// \author Balazs Dezso
220
[1710]221#ifdef DOXYGEN
222  template <typename _Graph, typename _LengthMap, typename _Traits>
223#else
[1699]224  template <typename _Graph=ListGraph,
225            typename _LengthMap=typename _Graph::template EdgeMap<int>,
226            typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
[1710]227#endif
[1699]228  class Johnson {
229  public:
230   
231    /// \brief \ref Exception for uninitialized parameters.
232    ///
233    /// This error represents problems in the initialization
234    /// of the parameters of the algorithms.
235
236    class UninitializedParameter : public lemon::UninitializedParameter {
237    public:
[2151]238      virtual const char* what() const throw() {
[1699]239        return "lemon::Johnson::UninitializedParameter";
240      }
241    };
242
243    typedef _Traits Traits;
244    ///The type of the underlying graph.
245    typedef typename _Traits::Graph Graph;
246
247    typedef typename Graph::Node Node;
248    typedef typename Graph::NodeIt NodeIt;
249    typedef typename Graph::Edge Edge;
250    typedef typename Graph::EdgeIt EdgeIt;
251   
252    /// \brief The type of the length of the edges.
253    typedef typename _Traits::LengthMap::Value Value;
254    /// \brief The type of the map that stores the edge lengths.
255    typedef typename _Traits::LengthMap LengthMap;
256    /// \brief The type of the map that stores the last
257    /// edges of the shortest paths. The type of the PredMap
258    /// is a matrix map for Edges
259    typedef typename _Traits::PredMap PredMap;
260    /// \brief The type of the map that stores the dists of the nodes.
261    /// The type of the DistMap is a matrix map for Values
262    typedef typename _Traits::DistMap DistMap;
263    /// \brief The operation traits.
264    typedef typename _Traits::OperationTraits OperationTraits;
[1741]265    ///The cross reference type used for the current heap.
266    typedef typename _Traits::HeapCrossRef HeapCrossRef;
267    ///The heap type used by the dijkstra algorithm.
268    typedef typename _Traits::Heap Heap;
[1699]269  private:
270    /// Pointer to the underlying graph.
271    const Graph *graph;
272    /// Pointer to the length map
273    const LengthMap *length;
274    ///Pointer to the map of predecessors edges.
275    PredMap *_pred;
276    ///Indicates if \ref _pred is locally allocated (\c true) or not.
277    bool local_pred;
278    ///Pointer to the map of distances.
279    DistMap *_dist;
280    ///Indicates if \ref _dist is locally allocated (\c true) or not.
281    bool local_dist;
[1741]282    ///Pointer to the heap cross references.
283    HeapCrossRef *_heap_cross_ref;
284    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
285    bool local_heap_cross_ref;
286    ///Pointer to the heap.
287    Heap *_heap;
288    ///Indicates if \ref _heap is locally allocated (\c true) or not.
289    bool local_heap;
[1699]290
291    /// Creates the maps if necessary.
292    void create_maps() {
293      if(!_pred) {
294        local_pred = true;
295        _pred = Traits::createPredMap(*graph);
296      }
297      if(!_dist) {
298        local_dist = true;
299        _dist = Traits::createDistMap(*graph);
300      }
[1741]301      if (!_heap_cross_ref) {
302        local_heap_cross_ref = true;
303        _heap_cross_ref = Traits::createHeapCrossRef(*graph);
304      }
305      if (!_heap) {
306        local_heap = true;
307        _heap = Traits::createHeap(*_heap_cross_ref);
308      }
[1699]309    }
[1741]310
[1699]311  public :
[1741]312
[1699]313    /// \name Named template parameters
314
315    ///@{
316
317    template <class T>
318    struct DefPredMapTraits : public Traits {
319      typedef T PredMap;
320      static PredMap *createPredMap(const Graph& graph) {
321        throw UninitializedParameter();
322      }
323    };
324
325    /// \brief \ref named-templ-param "Named parameter" for setting PredMap
326    /// type
327    /// \ref named-templ-param "Named parameter" for setting PredMap type
328    ///
329    template <class T>
[1710]330    struct DefPredMap
331      : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
332      typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
333    };
[1699]334   
335    template <class T>
336    struct DefDistMapTraits : public Traits {
337      typedef T DistMap;
338      static DistMap *createDistMap(const Graph& graph) {
339        throw UninitializedParameter();
340      }
341    };
342    /// \brief \ref named-templ-param "Named parameter" for setting DistMap
343    /// type
344    ///
345    /// \ref named-templ-param "Named parameter" for setting DistMap type
346    ///
347    template <class T>
[1710]348    struct DefDistMap
349      : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
350      typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
351    };
[1699]352   
353    template <class T>
354    struct DefOperationTraitsTraits : public Traits {
355      typedef T OperationTraits;
356    };
357   
358    /// \brief \ref named-templ-param "Named parameter" for setting
359    /// OperationTraits type
360    ///
[1710]361    /// \ref named-templ-param "Named parameter" for setting
362    /// OperationTraits type
[1699]363    template <class T>
[1710]364    struct DefOperationTraits
365      : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
366      typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
367    };
[1741]368
369    template <class H, class CR>
370    struct DefHeapTraits : public Traits {
371      typedef CR HeapCrossRef;
372      typedef H Heap;
373      static HeapCrossRef *createHeapCrossRef(const Graph &) {
374        throw UninitializedParameter();
375      }
376      static Heap *createHeap(HeapCrossRef &)
377      {
378        throw UninitializedParameter();
379      }
380    };
[1754]381    ///\brief \ref named-templ-param "Named parameter" for setting heap and
382    ///cross reference type
[2230]383    ///
[1741]384    ///\ref named-templ-param "Named parameter" for setting heap and cross
385    ///reference type
386    ///
387    template <class H, class CR = typename Graph::template NodeMap<int> >
388    struct DefHeap
389      : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
390      typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
391    };
392
393    template <class H, class CR>
394    struct DefStandardHeapTraits : public Traits {
395      typedef CR HeapCrossRef;
396      typedef H Heap;
397      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
398        return new HeapCrossRef(G);
399      }
400      static Heap *createHeap(HeapCrossRef &R)
401      {
402        return new Heap(R);
403      }
404    };
[2230]405    ///\brief \ref named-templ-param "Named parameter" for setting
406    ///heap and cross reference type with automatic allocation
407    ///
[1741]408    ///\ref named-templ-param "Named parameter" for setting heap and cross
409    ///reference type. It can allocate the heap and the cross reference
410    ///object if the cross reference's constructor waits for the graph as
411    ///parameter and the heap's constructor waits for the cross reference.
412    template <class H, class CR = typename Graph::template NodeMap<int> >
413    struct DefStandardHeap
414      : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
415      typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
416      Create;
417    };
[1699]418   
419    ///@}
420
[1710]421  protected:
422
423    Johnson() {}
424
[1699]425  public:     
[1741]426
427    typedef Johnson Create;
[1699]428   
429    /// \brief Constructor.
430    ///
431    /// \param _graph the graph the algorithm will run on.
432    /// \param _length the length map used by the algorithm.
433    Johnson(const Graph& _graph, const LengthMap& _length) :
434      graph(&_graph), length(&_length),
435      _pred(0), local_pred(false),
[1741]436      _dist(0), local_dist(false),
437      _heap_cross_ref(0), local_heap_cross_ref(false),
438      _heap(0), local_heap(false) {}
[1699]439   
440    ///Destructor.
441    ~Johnson() {
[1741]442      if (local_pred) delete _pred;
443      if (local_dist) delete _dist;
444      if (local_heap_cross_ref) delete _heap_cross_ref;
445      if (local_heap) delete _heap;
[1699]446    }
447
448    /// \brief Sets the length map.
449    ///
450    /// Sets the length map.
451    /// \return \c (*this)
452    Johnson &lengthMap(const LengthMap &m) {
453      length = &m;
454      return *this;
455    }
456
457    /// \brief Sets the map storing the predecessor edges.
458    ///
459    /// Sets the map storing the predecessor edges.
460    /// If you don't use this function before calling \ref run(),
461    /// it will allocate one. The destuctor deallocates this
462    /// automatically allocated map, of course.
463    /// \return \c (*this)
464    Johnson &predMap(PredMap &m) {
465      if(local_pred) {
466        delete _pred;
467        local_pred=false;
468      }
469      _pred = &m;
470      return *this;
471    }
472
473    /// \brief Sets the map storing the distances calculated by the algorithm.
474    ///
475    /// Sets the map storing the distances calculated by the algorithm.
476    /// If you don't use this function before calling \ref run(),
477    /// it will allocate one. The destuctor deallocates this
478    /// automatically allocated map, of course.
479    /// \return \c (*this)
480    Johnson &distMap(DistMap &m) {
481      if(local_dist) {
482        delete _dist;
483        local_dist=false;
484      }
485      _dist = &m;
486      return *this;
487    }
488
[1916]489  public:   
490
491    ///\name Execution control
492    /// The simplest way to execute the algorithm is to use
493    /// one of the member functions called \c run(...).
494    /// \n
495    /// If you need more control on the execution,
496    /// Finally \ref start() will perform the actual path
497    /// computation.
498
499    ///@{
500
501    /// \brief Initializes the internal data structures.
502    ///
503    /// Initializes the internal data structures.
504    void init() {
505      create_maps();
506    }
507
508    /// \brief Executes the algorithm with own potential map.
509    ///
510    /// This method runs the %Johnson algorithm in order to compute
511    /// the shortest path to each node pairs. The potential map
512    /// can be given for this algorithm which usually calculated
513    /// by the Bellman-Ford algorithm. If the graph does not have
514    /// negative length edge then this start function can be used
515    /// with constMap<Node, int>(0) parameter to omit the running time of
516    /// the Bellman-Ford.
517    /// The algorithm computes
518    /// - The shortest path tree for each node.
519    /// - The distance between each node pairs.
[1754]520    template <typename PotentialMap>
[1916]521    void shiftedStart(const PotentialMap& potential) {     
[1747]522      typename Graph::template EdgeMap<Value> shiftlen(*graph);
523      for (EdgeIt it(*graph);  it != INVALID; ++it) {
524        shiftlen[it] = (*length)[it]
[1754]525          + potential[graph->source(it)]
526          - potential[graph->target(it)];
[1747]527      }
528     
529      typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
530        template DefHeap<Heap, HeapCrossRef>::
531        Create dijkstra(*graph, shiftlen);
[1741]532
533      dijkstra.heap(*_heap, *_heap_cross_ref);
534     
535      for (NodeIt it(*graph); it != INVALID; ++it) {
536        dijkstra.run(it);
537        for (NodeIt jt(*graph); jt != INVALID; ++jt) {
538          if (dijkstra.reached(jt)) {
539            _dist->set(it, jt, dijkstra.dist(jt) +
[1754]540                       potential[jt] - potential[it]);
[1763]541            _pred->set(it, jt, dijkstra.predEdge(jt));
[1741]542          } else {
543            _dist->set(it, jt, OperationTraits::infinity());
544            _pred->set(it, jt, INVALID);
545          }
546        }
547      }
548    }
549
[1699]550    /// \brief Executes the algorithm.
551    ///
552    /// This method runs the %Johnson algorithm in order to compute
553    /// the shortest path to each node pairs. The algorithm
554    /// computes
555    /// - The shortest path tree for each node.
556    /// - The distance between each node pairs.
557    void start() {
[1710]558
[1864]559      typedef typename BellmanFord<Graph, LengthMap>::
[1754]560      template DefOperationTraits<OperationTraits>::
561      template DefPredMap<NullMap<Node, Edge> >::
[1864]562      Create BellmanFordType;
[1754]563     
[1864]564      BellmanFordType bellmanford(*graph, *length);
[1710]565
566      NullMap<Node, Edge> predMap;
567
[1864]568      bellmanford.predMap(predMap);
[1699]569     
[1864]570      bellmanford.init(OperationTraits::zero());
571      bellmanford.start();
[1699]572
[1916]573      shiftedStart(bellmanford.distMap());
[1699]574    }
[1741]575
[1754]576    /// \brief Executes the algorithm and checks the negatvie cycles.
[1741]577    ///
578    /// This method runs the %Johnson algorithm in order to compute
579    /// the shortest path to each node pairs. If the graph contains
[1754]580    /// negative cycle it gives back false. The algorithm
[1741]581    /// computes
582    /// - The shortest path tree for each node.
583    /// - The distance between each node pairs.
584    bool checkedStart() {
[1754]585     
[1864]586      typedef typename BellmanFord<Graph, LengthMap>::
[1754]587      template DefOperationTraits<OperationTraits>::
588      template DefPredMap<NullMap<Node, Edge> >::
[1864]589      Create BellmanFordType;
[1741]590
[1864]591      BellmanFordType bellmanford(*graph, *length);
[1741]592
593      NullMap<Node, Edge> predMap;
594
[1864]595      bellmanford.predMap(predMap);
[1741]596     
[1864]597      bellmanford.init(OperationTraits::zero());
598      if (!bellmanford.checkedStart()) return false;
[1741]599
[1916]600      shiftedStart(bellmanford.distMap());
[1741]601      return true;
602    }
603
[1699]604   
605    /// \brief Runs %Johnson algorithm.
606    ///   
607    /// This method runs the %Johnson algorithm from a each node
608    /// in order to compute the shortest path to each node pairs.
609    /// The algorithm computes
610    /// - The shortest path tree for each node.
611    /// - The distance between each node pairs.
612    ///
613    /// \note d.run(s) is just a shortcut of the following code.
[1946]614    ///\code
[1699]615    ///  d.init();
616    ///  d.start();
[1946]617    ///\endcode
[1699]618    void run() {
619      init();
620      start();
621    }
622   
623    ///@}
624
625    /// \name Query Functions
626    /// The result of the %Johnson algorithm can be obtained using these
627    /// functions.\n
628    /// Before the use of these functions,
629    /// either run() or start() must be called.
630   
631    ///@{
632
[2335]633    typedef PredMatrixMapPath<Graph, PredMap> Path;
634
635    ///Gives back the shortest path.
636   
637    ///Gives back the shortest path.
638    ///\pre The \c t should be reachable from the \c t.
639    Path path(Node s, Node t)
640    {
641      return Path(*graph, *_pred, s, t);
[1699]642    }
643         
644    /// \brief The distance between two nodes.
645    ///
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);
652    }
653
654    /// \brief Returns the 'previous edge' of the shortest path tree.
655    ///
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.
[1763]663    Edge predEdge(Node root, Node node) const {
[1699]664      return (*_pred)(root, node);
665    }
666
667    /// \brief Returns the 'previous node' of the shortest path tree.
668    ///
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
[1763]674    /// shortest path tree used in \ref predEdge(). 
[1699]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));
679    }
680   
681    /// \brief Returns a reference to the matrix node map of distances.
682    ///
683    /// Returns a reference to the matrix node map of distances.
684    ///
685    /// \pre \ref run() must be called before using this function.
686    const DistMap &distMap() const { return *_dist;}
687 
688    /// \brief Returns a reference to the shortest path tree map.
689    ///
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;}
694 
695    /// \brief Checks if a node is reachable from the root.
696    ///
697    /// Returns \c true if \c v is reachable from the root.
698    /// \pre \ref run() must be called before using this function.
699    ///
700    bool connected(Node source, Node target) {
701      return (*_dist)(source, target) != OperationTraits::infinity();
702    }
703   
704    ///@}
705  };
706 
707} //END OF NAMESPACE LEMON
708
709#endif
Note: See TracBrowser for help on using the repository browser.