COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dag_shortest_path.h @ 2347:0aaa7ada5395

Last change on this file since 2347:0aaa7ada5395 was 2335:27aa03cd3121, checked in by Balazs Dezso, 17 years ago

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File size: 37.1 KB
Line 
1/* -*- C++ -*-
2 *
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
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_DAG_SHORTEST_PATH_H
20#define LEMON_DAG_SHORTEST_PATH_H
21
22///\ingroup flowalgs
23/// \file
24/// \brief DagShortestPath algorithm.
25///
26
27#include <lemon/list_graph.h>
28#include <lemon/bits/invalid.h>
29#include <lemon/error.h>
30#include <lemon/maps.h>
31#include <lemon/topology.h>
32
33#include <limits>
34
35namespace lemon {
36
37  /// \brief Default OperationTraits for the DagShortestPath algorithm class.
38  /// 
39  /// It defines all computational operations and constants which are
40  /// used in the dag shortest path algorithm. The default implementation
41  /// is based on the numeric_limits class. If the numeric type does not
42  /// have infinity value then the maximum value is used as extremal
43  /// infinity value.
44  template <
45    typename Value,
46    bool has_infinity = std::numeric_limits<Value>::has_infinity>
47  struct DagShortestPathDefaultOperationTraits {
48    /// \brief Gives back the zero value of the type.
49    static Value zero() {
50      return static_cast<Value>(0);
51    }
52    /// \brief Gives back the positive infinity value of the type.
53    static Value infinity() {
54      return std::numeric_limits<Value>::infinity();
55    }
56    /// \brief Gives back the sum of the given two elements.
57    static Value plus(const Value& left, const Value& right) {
58      return left + right;
59    }
60    /// \brief Gives back true only if the first value less than the second.
61    static bool less(const Value& left, const Value& right) {
62      return left < right;
63    }
64  };
65
66  template <typename Value>
67  struct DagShortestPathDefaultOperationTraits<Value, false> {
68    static Value zero() {
69      return static_cast<Value>(0);
70    }
71    static Value infinity() {
72      return std::numeric_limits<Value>::max();
73    }
74    static Value plus(const Value& left, const Value& right) {
75      if (left == infinity() || right == infinity()) return infinity();
76      return left + right;
77    }
78    static bool less(const Value& left, const Value& right) {
79      return left < right;
80    }
81  };
82 
83  /// \brief Default traits class of DagShortestPath class.
84  ///
85  /// Default traits class of DagShortestPath class.
86  /// \param _Graph Graph type.
87  /// \param _LegthMap Type of length map.
88  template<class _Graph, class _LengthMap>
89  struct DagShortestPathDefaultTraits {
90    /// The graph type the algorithm runs on.
91    typedef _Graph Graph;
92
93    /// \brief The type of the map that stores the edge lengths.
94    ///
95    /// The type of the map that stores the edge lengths.
96    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
97    typedef _LengthMap LengthMap;
98
99    // The type of the length of the edges.
100    typedef typename _LengthMap::Value Value;
101
102    /// \brief Operation traits for dag shortest path algorithm.
103    ///
104    /// It defines the infinity type on the given Value type
105    /// and the used operation.
106    /// \see DagShortestPathDefaultOperationTraits
107    typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
108 
109    /// \brief The type of the map that stores the last edges of the
110    /// shortest paths.
111    ///
112    /// The type of the map that stores the last
113    /// edges of the shortest paths.
114    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
115    ///
116    typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
117
118    /// \brief Instantiates a PredMap.
119    ///
120    /// This function instantiates a \ref PredMap.
121    /// \param graph is the graph, to which we would
122    /// like to define the PredMap.
123    /// \todo The graph alone may be insufficient for the initialization
124    static PredMap *createPredMap(const _Graph& graph) {
125      return new PredMap(graph);
126    }
127
128    /// \brief The type of the map that stores the dists of the nodes.
129    ///
130    /// The type of the map that stores the dists of the nodes.
131    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
132    ///
133    typedef typename Graph::template NodeMap<typename _LengthMap::Value>
134    DistMap;
135
136    /// \brief Instantiates a DistMap.
137    ///
138    /// This function instantiates a \ref DistMap.
139    /// \param graph is the graph, to which we would like to define the
140    /// \ref DistMap
141    static DistMap *createDistMap(const _Graph& graph) {
142      return new DistMap(graph);
143    }
144
145  };
146 
147  /// \brief Inverse OperationTraits for the DagShortestPath algorithm class.
148  ///
149  /// It defines all computational operations and constants which are
150  /// used in the dag shortest path algorithm. It is the inverse of
151  /// \ref DagShortestPathDefaultOperationTraits, so it can be used to
152  /// calculate the longest path. The default implementation
153  /// is based on the numeric_limits class. If the numeric type does not
154  /// have infinity value then the minimum value is used as extremal
155  /// infinity value.
156  template <
157    typename Value,
158    bool has_infinity = std::numeric_limits<Value>::has_infinity>
159  struct DagLongestPathOperationTraits {
160    /// \brief Gives back the zero value of the type.
161    static Value zero() {
162      return static_cast<Value>(0);
163    }
164    /// \brief Gives back the negative infinity value of the type.
165    static Value infinity() {
166      return -(std::numeric_limits<Value>::infinity());
167    }
168    /// \brief Gives back the sum of the given two elements.
169    static Value plus(const Value& left, const Value& right) {
170      return left + right;
171    }
172    /// \brief Gives back true only if the first value less than the second.
173    static bool less(const Value& left, const Value& right) {
174      return left > right;
175    }
176  };
177
178  template <typename Value>
179  struct DagLongestPathOperationTraits<Value, false> {
180    static Value zero() {
181      return static_cast<Value>(0);
182    }
183    static Value infinity() {
184      return std::numeric_limits<Value>::min();
185    }
186    static Value plus(const Value& left, const Value& right) {
187      if (left == infinity() || right == infinity()) return infinity();
188      return left + right;
189    }
190    static bool less(const Value& left, const Value& right) {
191      return left > right;
192    }
193  };
194
195  /// \brief Inverse traits class of DagShortestPath class.
196  ///
197  /// Inverse traits class of DagShortestPath class.
198  /// \param _Graph Graph type.
199  /// \param _LegthMap Type of length map.
200  template<class _Graph, class _LengthMap>
201  struct DagLongestPathTraits {
202    /// The graph type the algorithm runs on.
203    typedef _Graph Graph;
204
205    /// \brief The type of the map that stores the edge lengths.
206    ///
207    /// The type of the map that stores the edge lengths.
208    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
209    typedef _LengthMap LengthMap;
210
211    // The type of the length of the edges.
212    typedef typename _LengthMap::Value Value;
213
214    /// \brief Inverse operation traits for dag shortest path algorithm.
215    ///
216    /// It defines the infinity type on the given Value type
217    /// and the used operation.
218    /// \see DagLongestPathOperationTraits
219    typedef DagLongestPathOperationTraits<Value> OperationTraits;
220 
221    /// \brief The type of the map that stores the last edges of the
222    /// longest paths.
223    ///
224    /// The type of the map that stores the last
225    /// edges of the longest paths.
226    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
227    ///
228    typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
229
230    /// \brief Instantiates a PredMap.
231    ///
232    /// This function instantiates a \ref PredMap.
233    /// \param graph is the graph,
234    /// to which we would like to define the PredMap.
235    /// \todo The graph alone may be insufficient for the initialization
236    static PredMap *createPredMap(const _Graph& graph) {
237      return new PredMap(graph);
238    }
239
240    /// \brief The type of the map that stores the dists of the nodes.
241    ///
242    /// The type of the map that stores the dists of the nodes.
243    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
244    ///
245    typedef typename Graph::template NodeMap<typename _LengthMap::Value>
246    DistMap;
247
248    /// \brief Instantiates a DistMap.
249    ///
250    /// This function instantiates a \ref DistMap.
251    /// \param graph is the graph, to which we would like to define the
252    /// \ref DistMap
253    static DistMap *createDistMap(const _Graph& graph) {
254      return new DistMap(graph);
255    }
256
257  };
258 
259
260  /// \brief %DagShortestPath algorithm class.
261  ///
262  /// \ingroup flowalgs
263  /// This class provides an efficient implementation of a Dag sortest path
264  /// searching algorithm. The edge lengths are passed to the algorithm
265  /// using a \ref concepts::ReadMap "ReadMap", so it is easy to change it
266  /// to any kind of length.
267  ///
268  /// The complexity of the algorithm is O(n + e).
269  ///
270  /// The type of the length is determined by the
271  /// \ref concepts::ReadMap::Value "Value" of the length map.
272  ///
273  /// \param _Graph The graph type the algorithm runs on. The default value
274  /// is \ref ListGraph. The value of _Graph is not used directly by
275  /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
276  /// \param _LengthMap This read-only EdgeMap determines the lengths of the
277  /// edges. The default map type is \ref concepts::Graph::EdgeMap
278  /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly
279  /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits. 
280  /// \param _Traits Traits class to set various data types used by the
281  /// algorithm.  The default traits class is \ref DagShortestPathDefaultTraits
282  /// "DagShortestPathDefaultTraits<_Graph,_LengthMap>".  See \ref
283  /// DagShortestPathDefaultTraits for the documentation of a DagShortestPath traits
284  /// class.
285  ///
286  /// \author Balazs Attila Mihaly (based on Balazs Dezso's work)
287
288#ifdef DOXYGEN
289  template <typename _Graph, typename _LengthMap, typename _Traits>
290#else
291  template <typename _Graph=ListGraph,
292            typename _LengthMap=typename _Graph::template EdgeMap<int>,
293            typename _Traits=DagShortestPathDefaultTraits<_Graph,_LengthMap> >
294#endif
295  class DagShortestPath {
296  public:
297   
298    /// \brief \ref Exception for uninitialized parameters.
299    ///
300    /// This error represents problems in the initialization
301    /// of the parameters of the algorithms.
302
303    class UninitializedParameter : public lemon::UninitializedParameter {
304    public:
305      virtual const char* what() const throw() {
306        return "lemon::DagShortestPath::UninitializedParameter";
307      }
308    };
309
310    typedef _Traits Traits;
311    ///The type of the underlying graph.
312    typedef typename _Traits::Graph Graph;
313
314    typedef typename Graph::Node Node;
315    typedef typename Graph::NodeIt NodeIt;
316    typedef typename Graph::Edge Edge;
317    typedef typename Graph::EdgeIt EdgeIt;
318    typedef typename Graph::OutEdgeIt OutEdgeIt;
319   
320    /// \brief The type of the length of the edges.
321    typedef typename _Traits::LengthMap::Value Value;
322    /// \brief The type of the map that stores the edge lengths.
323    typedef typename _Traits::LengthMap LengthMap;
324    /// \brief The type of the map that stores the last
325    /// edges of the shortest paths.
326    typedef typename _Traits::PredMap PredMap;
327    /// \brief The type of the map that stores the dists of the nodes.
328    typedef typename _Traits::DistMap DistMap;
329    /// \brief The operation traits.
330    typedef typename _Traits::OperationTraits OperationTraits;
331    /// \brief The Node weight map.
332    typedef typename Graph::template NodeMap<Value> WeightMap;
333  private:
334    /// Pointer to the underlying graph
335    const Graph *graph;
336    /// Pointer to the length map
337    const LengthMap *length;
338    ///Pointer to the map of predecessors edges
339    PredMap *_pred;
340    ///Indicates if \ref _pred is locally allocated (\c true) or not
341    bool local_pred;
342    ///Pointer to the map of distances
343    DistMap *_dist;
344    ///Indicates if \ref _dist is locally allocated (\c true) or not
345    bool local_dist;
346    ///Process step counter
347    unsigned int _process_step;
348
349    std::vector<Node> _node_order;
350
351    /// Creates the maps if necessary.
352    void create_maps() {
353      if(!_pred) {
354        local_pred = true;
355        _pred = Traits::createPredMap(*graph);
356      }
357      if(!_dist) {
358        local_dist = true;
359        _dist = Traits::createDistMap(*graph);
360      }
361    }
362   
363  public :
364 
365    typedef DagShortestPath Create;
366
367    /// \name Named template parameters
368
369    ///@{
370
371    template <class T>
372    struct DefPredMapTraits : public Traits {
373      typedef T PredMap;
374      static PredMap *createPredMap(const Graph&) {
375        throw UninitializedParameter();
376      }
377    };
378
379    /// \brief \ref named-templ-param "Named parameter" for setting PredMap
380    /// type
381    /// \ref named-templ-param "Named parameter" for setting PredMap type
382    ///
383    template <class T>
384    struct DefPredMap {
385      typedef DagShortestPath< Graph, LengthMap, DefPredMapTraits<T> > Create;
386    };
387   
388    template <class T>
389    struct DefDistMapTraits : public Traits {
390      typedef T DistMap;
391      static DistMap *createDistMap(const Graph& graph) {
392        throw UninitializedParameter();
393      }
394    };
395
396    /// \brief \ref named-templ-param "Named parameter" for setting DistMap
397    /// type
398    ///
399    /// \ref named-templ-param "Named parameter" for setting DistMap type
400    ///
401    template <class T>
402    struct DefDistMap
403      : public DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > {
404      typedef DagShortestPath< Graph, LengthMap, DefDistMapTraits<T> > Create;
405    };
406   
407    template <class T>
408    struct DefOperationTraitsTraits : public Traits {
409      typedef T OperationTraits;
410    };
411   
412    /// \brief \ref named-templ-param "Named parameter" for setting
413    /// OperationTraits type
414    ///
415    /// \ref named-templ-param "Named parameter" for setting OperationTraits
416    /// type
417    template <class T>
418    struct DefOperationTraits
419      : public DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> > {
420      typedef DagShortestPath< Graph, LengthMap, DefOperationTraitsTraits<T> >
421      Create;
422    };
423   
424    ///@}
425
426  protected:
427   
428    DagShortestPath() {}
429
430  public:     
431   
432    /// \brief Constructor.
433    ///
434    /// \param _graph the graph the algorithm will run on.
435    /// \param _length the length map used by the algorithm.
436    DagShortestPath(const Graph& _graph, const LengthMap& _length) :
437      graph(&_graph), length(&_length),
438      _pred(0), local_pred(false),
439      _dist(0), local_dist(false){}
440
441    /// \brief Constructor with node weight map.
442    ///
443    /// \param _graph the graph the algorithm will run on.
444    /// \param _length the length map used by the algorithm.
445    /// The NodeMap _length will be used as the weight map.
446    /// Each edge will have the weight of its target node.
447    DagShortestPath(const Graph& _graph, const WeightMap& _length) :
448      graph(&_graph),
449      _pred(0), local_pred(false),
450      _dist(0), local_dist(false){
451      length=new LengthMap(_graph);
452      _dist=new DistMap(_graph);
453      for(EdgeIt eit(_graph);eit!=INVALID;++eit)
454        (const_cast<LengthMap*>(length))->set(eit,_length[_graph.target(eit)]);
455      }
456
457    ///Destructor.
458    ~DagShortestPath() {
459      if(local_pred) delete _pred;
460      if(local_dist) delete _dist;
461    }
462
463    /// \brief Sets the length map.
464    ///
465    /// Sets the length map.
466    /// \return \c (*this)
467    DagShortestPath &lengthMap(const LengthMap &m) {
468      length = &m;
469      return *this;
470    }
471
472    /// \brief Sets the map storing the predecessor edges.
473    ///
474    /// Sets the map storing the predecessor edges.
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    DagShortestPath &predMap(PredMap &m) {
480      if(local_pred) {
481        delete _pred;
482        local_pred=false;
483      }
484      _pred = &m;
485      return *this;
486    }
487
488    /// \brief Sets the map storing the distances calculated by the algorithm.
489    ///
490    /// Sets the map storing the distances calculated by the algorithm.
491    /// If you don't use this function before calling \ref run(),
492    /// it will allocate one. The destuctor deallocates this
493    /// automatically allocated map, of course.
494    /// \return \c (*this)
495    DagShortestPath &distMap(DistMap &m) {
496      if(local_dist) {
497        delete _dist;
498        local_dist=false;
499      }
500      _dist = &m;
501      return *this;
502    }
503
504    /// \name Execution control
505    /// The simplest way to execute the algorithm is to use
506    /// one of the member functions called \c run(...)
507    /// \n
508    /// If you need more control on the execution,
509    /// first you must call \ref init(...), then you can add several source
510    /// nodes with \ref addSource().
511    /// Finally \ref start() will perform the actual path computation.
512    /// Some functions have an alternative form (\ref checkedInit(...),
513    /// \ref checkedRun(...)) which also verifies if the graph given in the
514    /// constructor is a dag.
515
516    ///@{
517
518    /// \brief Initializes the internal data structures.
519    ///
520    /// Initializes the internal data structures.
521    void init(const Value value = OperationTraits::infinity()) {
522      typedef typename Graph::template NodeMap<int> NodeOrderMap;
523      _process_step=0;
524      NodeOrderMap node_order(*graph);
525      topologicalSort(*graph,node_order);
526      _node_order.resize(countNodes(*graph),INVALID);
527      create_maps();
528      for (NodeIt it(*graph); it != INVALID; ++it) {
529        _node_order[node_order[it]]=it;
530        _pred->set(it, INVALID);
531        _dist->set(it, value);
532      }
533    }
534
535    /// \brief Initializes the internal data structures
536    /// with a given topological sort (NodeMap).
537    ///
538    /// Initializes the internal data structures
539    /// with a given topological sort (NodeMap).
540    void init(const typename Graph::template NodeMap<int>& node_order,
541         const Value value = OperationTraits::infinity()) {
542      _process_step=0;
543      _node_order.resize(countNodes(*graph),INVALID);
544      create_maps();
545      for (NodeIt it(*graph); it != INVALID; ++it) {
546        _node_order[node_order[it]]=it;
547        _pred->set(it, INVALID);
548        _dist->set(it, value);
549      }
550    }
551
552    /// \brief Initializes the internal data structures
553    /// with a given topological sort (std::vector).
554    ///
555    /// Initializes the internal data structures
556    /// with a given topological sort (std::vector).
557    void init(const std::vector<Node>& node_order,
558        const Value value = OperationTraits::infinity()) {
559      _process_step=0;
560      _node_order=node_order;
561      create_maps();
562      for (NodeIt it(*graph); it != INVALID; ++it) {
563        _pred->set(it, INVALID);
564        _dist->set(it, value);
565      }
566    }
567
568    /// \brief Initializes the internal data structures. It also checks if the graph is dag.
569    ///
570    /// Initializes the internal data structures. It also checks if the graph is dag.
571    /// \return true if the graph (given in the constructor) is dag, false otherwise.
572    bool checkedInit(const Value value = OperationTraits::infinity()) {
573      typedef typename Graph::template NodeMap<int> NodeOrderMap;
574      NodeOrderMap node_order(*graph);
575      if(!checkedTopologicalSort(*graph,node_order))return false;
576      init(node_order,value);
577      return true;
578    }
579
580    /// \brief Initializes the internal data structures with a given
581    /// topological sort (NodeMap). It also checks if the graph is dag.
582    ///
583    /// Initializes the internal data structures with a given
584    /// topological sort (NodeMap). It also checks if the graph is dag.
585    /// \return true if the graph (given in the constructor) is dag, false otherwise.
586    bool checkedInit(const typename Graph::template NodeMap<int>& node_order,
587                     const Value value = OperationTraits::infinity()) {
588      for(NodeIt it(*graph);it!=INVALID;++it){
589        for(OutEdgeIt oeit(*graph,it);oeit!=INVALID;++oeit){
590          if(node_order[graph->target(oeit)]<node_order[it])return false;
591        }
592      }
593      init(node_order,value);
594      return true;
595    }
596
597    /// \brief Initializes the internal data structures with a given
598    /// topological sort (std::vector). It also checks if the graph is dag.
599    ///
600    /// Initializes the internal data structures with a given
601    /// topological sort (std::vector). It also checks if the graph is dag.
602    /// \return true if the graph (given in the constructor) is dag, false otherwise.
603    bool checkedInit(const std::vector<Node>& node_order,
604                     const Value value = OperationTraits::infinity()) {
605      typedef typename Graph::template NodeMap<bool> BoolNodeMap;
606      BoolNodeMap _processed(*graph,false);
607      for(unsigned int i=0;i<_node_order.size();++i){
608        _processed[node_order[i]]=true;
609        for(OutEdgeIt oeit(*graph,node_order[i]);oeit!=INVALID;++oeit){
610          if(_processed[graph->target(oeit)])return false;
611        }
612      }
613      init(node_order,value);
614      return true;
615    }
616
617    /// \brief Adds a new source node.
618    ///
619    /// The optional second parameter is the initial distance of the node.
620    /// It just sets the distance of the node to the given value.
621    void addSource(Node source, Value dst = OperationTraits::zero()) {
622      if((*_dist)[source] != dst){
623        _dist->set(source, dst);
624      }
625    }
626
627    /// \brief Executes one step from the dag shortest path algorithm.
628    ///
629    /// If the algoritm calculated the distances in the previous step
630    /// strictly for all at most k length paths then it will calculate the
631    /// distances strictly for all at most k + 1 length paths. With k
632    /// iteration this function calculates the at most k length paths.
633    ///\pre the queue is not empty
634    ///\return the currently processed node
635    Node processNextNode() {
636      if(reached(_node_order[_process_step])){
637        for (OutEdgeIt it(*graph, _node_order[_process_step]); it != INVALID; ++it) {
638          Node target = graph->target(it);
639          Value relaxed =
640            OperationTraits::plus((*_dist)[_node_order[_process_step]], (*length)[it]);
641          if (OperationTraits::less(relaxed, (*_dist)[target])) {
642            _pred->set(target, it);
643            _dist->set(target, relaxed);
644          }
645        }
646      }
647      ++_process_step;
648      return _node_order[_process_step-1];
649    }
650
651    ///\brief Returns \c false if there are nodes
652    ///to be processed in the queue
653    ///
654    ///Returns \c false if there are nodes
655    ///to be processed in the queue
656    bool emptyQueue() { return _node_order.size()-1==_process_step; }
657
658    ///\brief Returns the number of the nodes to be processed.
659    ///
660    ///Returns the number of the nodes to be processed in the queue.
661    int queueSize() { return _node_order.size()-1-_process_step; }
662
663    /// \brief Executes the algorithm.
664    ///
665    /// \pre init() must be called and at least one node should be added
666    /// with addSource() before using this function.
667    ///
668    /// This method runs the %DagShortestPath algorithm from the root node(s)
669    /// in order to compute the shortest path to each node. The algorithm
670    /// computes
671    /// - The shortest path tree.
672    /// - The distance of each node from the root(s).
673    void start() {
674      while(!emptyQueue()) {
675        processNextNode();
676      }
677    }
678
679    /// \brief Runs %DagShortestPath algorithm from node \c s.
680    ///   
681    /// This method runs the %DagShortestPath algorithm from a root node \c s
682    /// in order to compute the shortest path to each node. The algorithm
683    /// computes
684    /// - The shortest path tree.
685    /// - The distance of each node from the root.
686    ///
687    /// \note d.run(s) is just a shortcut of the following code.
688    ///\code
689    ///  d.init();
690    ///  d.addSource(s);
691    ///  d.start();
692    ///\endcode
693    void run(Node s) {
694      init();
695      addSource(s);
696      start();
697    }
698   
699    /// \brief Runs %DagShortestPath algorithm from node \c s.
700    /// It also checks if the graph is a dag.
701    ///   
702    /// This method runs the %DagShortestPath algorithm from a root node \c s
703    /// in order to compute the shortest path to each node. The algorithm
704    /// computes
705    /// - The shortest path tree.
706    /// - The distance of each node from the root.
707    /// The algorithm checks if the graph given int the constructor is a dag.
708    bool checkedRun(Node s) {
709      if(!checkedInit())return false;
710      addSource(s);
711      start();
712      return true;
713    }
714   
715    ///@}
716
717    /// \name Query Functions
718    /// The result of the %DagShortestPath algorithm can be obtained using these
719    /// functions.\n
720    /// Before the use of these functions,
721    /// either run() or start() must be called.
722   
723    ///@{
724
725    typedef PredMapPath<Graph, PredMap> Path;
726
727    ///Gives back the shortest path.
728   
729    ///Gives back the shortest path.
730    ///\pre The \c t should be reachable from the source.
731    Path path(Node t)
732    {
733      return Path(*graph, *_pred, t);
734    }
735         
736    /// \brief The distance of a node from the root.
737    ///
738    /// Returns the distance of a node from the root.
739    /// \pre \ref run() must be called before using this function.
740    /// \warning If node \c v in unreachable from the root the return value
741    /// of this funcion is undefined.
742    Value dist(Node v) const { return (*_dist)[v]; }
743
744    /// \brief Returns the 'previous edge' of the shortest path tree.
745    ///
746    /// For a node \c v it returns the 'previous edge' of the shortest path
747    /// tree, i.e. it returns the last edge of a shortest path from the root
748    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
749    /// if \c v=s. The shortest path tree used here is equal to the shortest
750    /// path tree used in \ref predNode().
751    /// \pre \ref run() must be called before using
752    /// this function.
753    Edge predEdge(Node v) const { return (*_pred)[v]; }
754
755    /// \brief Returns the 'previous node' of the shortest path tree.
756    ///
757    /// For a node \c v it returns the 'previous node' of the shortest path
758    /// tree, i.e. it returns the last but one node from a shortest path from
759    /// the root to \c /v. It is INVALID if \c v is unreachable from the root
760    /// or if \c v=s. The shortest path tree used here is equal to the
761    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be
762    /// called before using this function.
763    Node predNode(Node v) const {
764      return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
765    }
766   
767    /// \brief Returns a reference to the NodeMap of distances.
768    ///
769    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
770    /// be called before using this function.
771    const DistMap &distMap() const { return *_dist;}
772 
773    /// \brief Returns a reference to the shortest path tree map.
774    ///
775    /// Returns a reference to the NodeMap of the edges of the
776    /// shortest path tree.
777    /// \pre \ref run() must be called before using this function.
778    const PredMap &predMap() const { return *_pred; }
779 
780    /// \brief Checks if a node is reachable from the root.
781    ///
782    /// Returns \c true if \c v is reachable from the root.
783    /// \pre \ref run() must be called before using this function.
784    ///
785    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
786   
787    ///@}
788  };
789 
790  /// \brief Default traits class of DagShortestPath function.
791  ///
792  /// Default traits class of DagShortestPath function.
793  /// \param _Graph Graph type.
794  /// \param _LengthMap Type of length map.
795  template <typename _Graph, typename _LengthMap>
796  struct DagShortestPathWizardDefaultTraits {
797    /// \brief The graph type the algorithm runs on.
798    typedef _Graph Graph;
799
800    /// \brief The type of the map that stores the edge lengths.
801    ///
802    /// The type of the map that stores the edge lengths.
803    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
804    typedef _LengthMap LengthMap;
805
806    /// \brief The value type of the length map.
807    typedef typename _LengthMap::Value Value;
808
809    /// \brief Operation traits for dag shortest path algorithm.
810    ///
811    /// It defines the infinity type on the given Value type
812    /// and the used operation.
813    /// \see DagShortestPathDefaultOperationTraits
814    typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
815
816    /// \brief The type of the map that stores the last
817    /// edges of the shortest paths.
818    ///
819    /// The type of the map that stores the last
820    /// edges of the shortest paths.
821    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
822    typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
823
824    /// \brief Instantiates a PredMap.
825    ///
826    /// This function instantiates a \ref PredMap.
827    static PredMap *createPredMap(const _Graph &) {
828      return new PredMap();
829    }
830    /// \brief The type of the map that stores the dists of the nodes.
831    ///
832    /// The type of the map that stores the dists of the nodes.
833    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
834    typedef NullMap<typename Graph::Node, Value> DistMap;
835    /// \brief Instantiates a DistMap.
836    ///
837    /// This function instantiates a \ref DistMap.
838    static DistMap *createDistMap(const _Graph &) {
839      return new DistMap();
840    }
841  };
842 
843  /// \brief Default traits used by \ref DagShortestPathWizard
844  ///
845  /// To make it easier to use DagShortestPath algorithm
846  /// we have created a wizard class.
847  /// This \ref DagShortestPathWizard class needs default traits,
848  /// as well as the \ref DagShortestPath class.
849  /// The \ref DagShortestPathWizardBase is a class to be the default traits of the
850  /// \ref DagShortestPathWizard class.
851  /// \todo More named parameters are required...
852  template<class _Graph,class _LengthMap>
853  class DagShortestPathWizardBase
854    : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
855
856    typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
857  protected:
858    /// Type of the nodes in the graph.
859    typedef typename Base::Graph::Node Node;
860
861    /// Pointer to the underlying graph.
862    void *_graph;
863    /// Pointer to the length map
864    void *_length;
865    ///Pointer to the map of predecessors edges.
866    void *_pred;
867    ///Pointer to the map of distances.
868    void *_dist;
869    ///Pointer to the source node.
870    Node _source;
871
872    public:
873    /// Constructor.
874   
875    /// This constructor does not require parameters, therefore it initiates
876    /// all of the attributes to default values (0, INVALID).
877    DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
878                           _dist(0), _source(INVALID) {}
879
880    /// Constructor.
881   
882    /// This constructor requires some parameters,
883    /// listed in the parameters list.
884    /// Others are initiated to 0.
885    /// \param graph is the initial value of  \ref _graph
886    /// \param length is the initial value of  \ref _length
887    /// \param source is the initial value of  \ref _source
888    DagShortestPathWizardBase(const _Graph& graph,
889                          const _LengthMap& length,
890                          Node source = INVALID) :
891      _graph((void *)&graph), _length((void *)&length), _pred(0),
892      _dist(0), _source(source) {}
893
894  };
895 
896  /// A class to make the usage of DagShortestPath algorithm easier
897
898  /// This class is created to make it easier to use DagShortestPath algorithm.
899  /// It uses the functions and features of the plain \ref DagShortestPath,
900  /// but it is much simpler to use it.
901  ///
902  /// Simplicity means that the way to change the types defined
903  /// in the traits class is based on functions that returns the new class
904  /// and not on templatable built-in classes.
905  /// When using the plain \ref DagShortestPath
906  /// the new class with the modified type comes from
907  /// the original class by using the ::
908  /// operator. In the case of \ref DagShortestPathWizard only
909  /// a function have to be called and it will
910  /// return the needed class.
911  ///
912  /// It does not have own \ref run method. When its \ref run method is called
913  /// it initiates a plain \ref DagShortestPath class, and calls the \ref
914  /// DagShortestPath::run() method of it.
915  template<class _Traits>
916  class DagShortestPathWizard : public _Traits {
917    typedef _Traits Base;
918
919    ///The type of the underlying graph.
920    typedef typename _Traits::Graph Graph;
921
922    typedef typename Graph::Node Node;
923    typedef typename Graph::NodeIt NodeIt;
924    typedef typename Graph::Edge Edge;
925    typedef typename Graph::OutEdgeIt EdgeIt;
926   
927    ///The type of the map that stores the edge lengths.
928    typedef typename _Traits::LengthMap LengthMap;
929
930    ///The type of the length of the edges.
931    typedef typename LengthMap::Value Value;
932
933    ///\brief The type of the map that stores the last
934    ///edges of the shortest paths.
935    typedef typename _Traits::PredMap PredMap;
936
937    ///The type of the map that stores the dists of the nodes.
938    typedef typename _Traits::DistMap DistMap;
939
940  public:
941    /// Constructor.
942    DagShortestPathWizard() : _Traits() {}
943
944    /// \brief Constructor that requires parameters.
945    ///
946    /// Constructor that requires parameters.
947    /// These parameters will be the default values for the traits class.
948    DagShortestPathWizard(const Graph& graph, const LengthMap& length,
949                      Node source = INVALID)
950      : _Traits(graph, length, source) {}
951
952    /// \brief Copy constructor
953    DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
954
955    ~DagShortestPathWizard() {}
956
957    /// \brief Runs DagShortestPath algorithm from a given node.
958    ///   
959    /// Runs DagShortestPath algorithm from a given node.
960    /// The node can be given by the \ref source function.
961    void run() {
962      if(Base::_source == INVALID) throw UninitializedParameter();
963      DagShortestPath<Graph,LengthMap,_Traits>
964        bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
965      if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
966      if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
967      bf.run(Base::_source);
968    }
969
970    /// \brief Runs DagShortestPath algorithm from the given node.
971    ///
972    /// Runs DagShortestPath algorithm from the given node.
973    /// \param source is the given source.
974    void run(Node source) {
975      Base::_source = source;
976      run();
977    }
978
979    template<class T>
980    struct DefPredMapBase : public Base {
981      typedef T PredMap;
982      static PredMap *createPredMap(const Graph &) { return 0; };
983      DefPredMapBase(const _Traits &b) : _Traits(b) {}
984    };
985   
986    ///\brief \ref named-templ-param "Named parameter"
987    ///function for setting PredMap type
988    ///
989    /// \ref named-templ-param "Named parameter"
990    ///function for setting PredMap type
991    ///
992    template<class T>
993    DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t)
994    {
995      Base::_pred=(void *)&t;
996      return DagShortestPathWizard<DefPredMapBase<T> >(*this);
997    }
998   
999    template<class T>
1000    struct DefDistMapBase : public Base {
1001      typedef T DistMap;
1002      static DistMap *createDistMap(const Graph &) { return 0; };
1003      DefDistMapBase(const _Traits &b) : _Traits(b) {}
1004    };
1005   
1006    ///\brief \ref named-templ-param "Named parameter"
1007    ///function for setting DistMap type
1008    ///
1009    /// \ref named-templ-param "Named parameter"
1010    ///function for setting DistMap type
1011    ///
1012    template<class T>
1013    DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
1014      Base::_dist=(void *)&t;
1015      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1016    }
1017
1018    template<class T>
1019    struct DefOperationTraitsBase : public Base {
1020      typedef T OperationTraits;
1021      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1022    };
1023   
1024    ///\brief \ref named-templ-param "Named parameter"
1025    ///function for setting OperationTraits type
1026    ///
1027    /// \ref named-templ-param "Named parameter"
1028    ///function for setting OperationTraits type
1029    ///
1030    template<class T>
1031    DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
1032      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1033    }
1034   
1035    /// \brief Sets the source node, from which the DagShortestPath algorithm runs.
1036    ///
1037    /// Sets the source node, from which the DagShortestPath algorithm runs.
1038    /// \param source is the source node.
1039    DagShortestPathWizard<_Traits>& source(Node source) {
1040      Base::_source = source;
1041      return *this;
1042    }
1043   
1044  };
1045 
1046  /// \brief Function type interface for DagShortestPath algorithm.
1047  ///
1048  /// \ingroup flowalgs
1049  /// Function type interface for DagShortestPath algorithm.
1050  ///
1051  /// This function also has several \ref named-templ-func-param
1052  /// "named parameters", they are declared as the members of class
1053  /// \ref DagShortestPathWizard.
1054  /// The following
1055  /// example shows how to use these parameters.
1056  ///\code
1057  /// dagShortestPath(g,length,source).predMap(preds).run();
1058  ///\endcode
1059  /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()"
1060  /// to the end of the parameter list.
1061  /// \sa DagShortestPathWizard
1062  /// \sa DagShortestPath
1063  template<class _Graph, class _LengthMap>
1064  DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1065  dagShortestPath(const _Graph& graph,
1066              const _LengthMap& length,
1067              typename _Graph::Node source = INVALID) {
1068    return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1069      (graph, length, source);
1070  }
1071
1072} //END OF NAMESPACE LEMON
1073
1074#endif
1075
Note: See TracBrowser for help on using the repository browser.