COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dag_shortest_path.h @ 1999:2ff283124dfc

Last change on this file since 1999:2ff283124dfc was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

File size: 37.5 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 concept::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 concept::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 concept::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 concept::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 concept::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 concept::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 concept::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 concept::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 concept::StaticGraph::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* exceptionName() const {
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    /// \brief Copies the shortest path to \c t into \c p
726    ///   
727    /// This function copies the shortest path to \c t into \c p.
728    /// If it \c t is a source itself or unreachable, then it does not
729    /// alter \c p.
730    ///
731    /// \return Returns \c true if a path to \c t was actually copied to \c p,
732    /// \c false otherwise.
733    /// \sa DirPath
734    template <typename Path>
735    bool getPath(Path &p, Node t) {
736      if(reached(t)) {
737        p.clear();
738        typename Path::Builder b(p);
739        for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
740          b.pushFront(predEdge(t));
741        b.commit();
742        return true;
743      }
744      return false;
745    }
746         
747    /// \brief The distance of a node from the root.
748    ///
749    /// Returns the distance of a node from the root.
750    /// \pre \ref run() must be called before using this function.
751    /// \warning If node \c v in unreachable from the root the return value
752    /// of this funcion is undefined.
753    Value dist(Node v) const { return (*_dist)[v]; }
754
755    /// \brief Returns the 'previous edge' of the shortest path tree.
756    ///
757    /// For a node \c v it returns the 'previous edge' of the shortest path
758    /// tree, i.e. it returns the last edge of a shortest path from the root
759    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
760    /// if \c v=s. The shortest path tree used here is equal to the shortest
761    /// path tree used in \ref predNode().
762    /// \pre \ref run() must be called before using
763    /// this function.
764    Edge predEdge(Node v) const { return (*_pred)[v]; }
765
766    /// \brief Returns the 'previous node' of the shortest path tree.
767    ///
768    /// For a node \c v it returns the 'previous node' of the shortest path
769    /// tree, i.e. it returns the last but one node from a shortest path from
770    /// the root to \c /v. It is INVALID if \c v is unreachable from the root
771    /// or if \c v=s. The shortest path tree used here is equal to the
772    /// shortest path tree used in \ref predEdge().  \pre \ref run() must be
773    /// called before using this function.
774    Node predNode(Node v) const {
775      return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
776    }
777   
778    /// \brief Returns a reference to the NodeMap of distances.
779    ///
780    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
781    /// be called before using this function.
782    const DistMap &distMap() const { return *_dist;}
783 
784    /// \brief Returns a reference to the shortest path tree map.
785    ///
786    /// Returns a reference to the NodeMap of the edges of the
787    /// shortest path tree.
788    /// \pre \ref run() must be called before using this function.
789    const PredMap &predMap() const { return *_pred; }
790 
791    /// \brief Checks if a node is reachable from the root.
792    ///
793    /// Returns \c true if \c v is reachable from the root.
794    /// \pre \ref run() must be called before using this function.
795    ///
796    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
797   
798    ///@}
799  };
800 
801  /// \brief Default traits class of DagShortestPath function.
802  ///
803  /// Default traits class of DagShortestPath function.
804  /// \param _Graph Graph type.
805  /// \param _LengthMap Type of length map.
806  template <typename _Graph, typename _LengthMap>
807  struct DagShortestPathWizardDefaultTraits {
808    /// \brief The graph type the algorithm runs on.
809    typedef _Graph Graph;
810
811    /// \brief The type of the map that stores the edge lengths.
812    ///
813    /// The type of the map that stores the edge lengths.
814    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
815    typedef _LengthMap LengthMap;
816
817    /// \brief The value type of the length map.
818    typedef typename _LengthMap::Value Value;
819
820    /// \brief Operation traits for dag shortest path algorithm.
821    ///
822    /// It defines the infinity type on the given Value type
823    /// and the used operation.
824    /// \see DagShortestPathDefaultOperationTraits
825    typedef DagShortestPathDefaultOperationTraits<Value> OperationTraits;
826
827    /// \brief The type of the map that stores the last
828    /// edges of the shortest paths.
829    ///
830    /// The type of the map that stores the last
831    /// edges of the shortest paths.
832    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
833    typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
834
835    /// \brief Instantiates a PredMap.
836    ///
837    /// This function instantiates a \ref PredMap.
838    static PredMap *createPredMap(const _Graph &) {
839      return new PredMap();
840    }
841    /// \brief The type of the map that stores the dists of the nodes.
842    ///
843    /// The type of the map that stores the dists of the nodes.
844    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
845    typedef NullMap<typename Graph::Node, Value> DistMap;
846    /// \brief Instantiates a DistMap.
847    ///
848    /// This function instantiates a \ref DistMap.
849    static DistMap *createDistMap(const _Graph &) {
850      return new DistMap();
851    }
852  };
853 
854  /// \brief Default traits used by \ref DagShortestPathWizard
855  ///
856  /// To make it easier to use DagShortestPath algorithm
857  /// we have created a wizard class.
858  /// This \ref DagShortestPathWizard class needs default traits,
859  /// as well as the \ref DagShortestPath class.
860  /// The \ref DagShortestPathWizardBase is a class to be the default traits of the
861  /// \ref DagShortestPathWizard class.
862  /// \todo More named parameters are required...
863  template<class _Graph,class _LengthMap>
864  class DagShortestPathWizardBase
865    : public DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> {
866
867    typedef DagShortestPathWizardDefaultTraits<_Graph,_LengthMap> Base;
868  protected:
869    /// Type of the nodes in the graph.
870    typedef typename Base::Graph::Node Node;
871
872    /// Pointer to the underlying graph.
873    void *_graph;
874    /// Pointer to the length map
875    void *_length;
876    ///Pointer to the map of predecessors edges.
877    void *_pred;
878    ///Pointer to the map of distances.
879    void *_dist;
880    ///Pointer to the source node.
881    Node _source;
882
883    public:
884    /// Constructor.
885   
886    /// This constructor does not require parameters, therefore it initiates
887    /// all of the attributes to default values (0, INVALID).
888    DagShortestPathWizardBase() : _graph(0), _length(0), _pred(0),
889                           _dist(0), _source(INVALID) {}
890
891    /// Constructor.
892   
893    /// This constructor requires some parameters,
894    /// listed in the parameters list.
895    /// Others are initiated to 0.
896    /// \param graph is the initial value of  \ref _graph
897    /// \param length is the initial value of  \ref _length
898    /// \param source is the initial value of  \ref _source
899    DagShortestPathWizardBase(const _Graph& graph,
900                          const _LengthMap& length,
901                          Node source = INVALID) :
902      _graph((void *)&graph), _length((void *)&length), _pred(0),
903      _dist(0), _source(source) {}
904
905  };
906 
907  /// A class to make the usage of DagShortestPath algorithm easier
908
909  /// This class is created to make it easier to use DagShortestPath algorithm.
910  /// It uses the functions and features of the plain \ref DagShortestPath,
911  /// but it is much simpler to use it.
912  ///
913  /// Simplicity means that the way to change the types defined
914  /// in the traits class is based on functions that returns the new class
915  /// and not on templatable built-in classes.
916  /// When using the plain \ref DagShortestPath
917  /// the new class with the modified type comes from
918  /// the original class by using the ::
919  /// operator. In the case of \ref DagShortestPathWizard only
920  /// a function have to be called and it will
921  /// return the needed class.
922  ///
923  /// It does not have own \ref run method. When its \ref run method is called
924  /// it initiates a plain \ref DagShortestPath class, and calls the \ref
925  /// DagShortestPath::run() method of it.
926  template<class _Traits>
927  class DagShortestPathWizard : public _Traits {
928    typedef _Traits Base;
929
930    ///The type of the underlying graph.
931    typedef typename _Traits::Graph Graph;
932
933    typedef typename Graph::Node Node;
934    typedef typename Graph::NodeIt NodeIt;
935    typedef typename Graph::Edge Edge;
936    typedef typename Graph::OutEdgeIt EdgeIt;
937   
938    ///The type of the map that stores the edge lengths.
939    typedef typename _Traits::LengthMap LengthMap;
940
941    ///The type of the length of the edges.
942    typedef typename LengthMap::Value Value;
943
944    ///\brief The type of the map that stores the last
945    ///edges of the shortest paths.
946    typedef typename _Traits::PredMap PredMap;
947
948    ///The type of the map that stores the dists of the nodes.
949    typedef typename _Traits::DistMap DistMap;
950
951  public:
952    /// Constructor.
953    DagShortestPathWizard() : _Traits() {}
954
955    /// \brief Constructor that requires parameters.
956    ///
957    /// Constructor that requires parameters.
958    /// These parameters will be the default values for the traits class.
959    DagShortestPathWizard(const Graph& graph, const LengthMap& length,
960                      Node source = INVALID)
961      : _Traits(graph, length, source) {}
962
963    /// \brief Copy constructor
964    DagShortestPathWizard(const _Traits &b) : _Traits(b) {}
965
966    ~DagShortestPathWizard() {}
967
968    /// \brief Runs DagShortestPath algorithm from a given node.
969    ///   
970    /// Runs DagShortestPath algorithm from a given node.
971    /// The node can be given by the \ref source function.
972    void run() {
973      if(Base::_source == INVALID) throw UninitializedParameter();
974      DagShortestPath<Graph,LengthMap,_Traits>
975        bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
976      if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
977      if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
978      bf.run(Base::_source);
979    }
980
981    /// \brief Runs DagShortestPath algorithm from the given node.
982    ///
983    /// Runs DagShortestPath algorithm from the given node.
984    /// \param source is the given source.
985    void run(Node source) {
986      Base::_source = source;
987      run();
988    }
989
990    template<class T>
991    struct DefPredMapBase : public Base {
992      typedef T PredMap;
993      static PredMap *createPredMap(const Graph &) { return 0; };
994      DefPredMapBase(const _Traits &b) : _Traits(b) {}
995    };
996   
997    ///\brief \ref named-templ-param "Named parameter"
998    ///function for setting PredMap type
999    ///
1000    /// \ref named-templ-param "Named parameter"
1001    ///function for setting PredMap type
1002    ///
1003    template<class T>
1004    DagShortestPathWizard<DefPredMapBase<T> > predMap(const T &t)
1005    {
1006      Base::_pred=(void *)&t;
1007      return DagShortestPathWizard<DefPredMapBase<T> >(*this);
1008    }
1009   
1010    template<class T>
1011    struct DefDistMapBase : public Base {
1012      typedef T DistMap;
1013      static DistMap *createDistMap(const Graph &) { return 0; };
1014      DefDistMapBase(const _Traits &b) : _Traits(b) {}
1015    };
1016   
1017    ///\brief \ref named-templ-param "Named parameter"
1018    ///function for setting DistMap type
1019    ///
1020    /// \ref named-templ-param "Named parameter"
1021    ///function for setting DistMap type
1022    ///
1023    template<class T>
1024    DagShortestPathWizard<DefDistMapBase<T> > distMap(const T &t) {
1025      Base::_dist=(void *)&t;
1026      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1027    }
1028
1029    template<class T>
1030    struct DefOperationTraitsBase : public Base {
1031      typedef T OperationTraits;
1032      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1033    };
1034   
1035    ///\brief \ref named-templ-param "Named parameter"
1036    ///function for setting OperationTraits type
1037    ///
1038    /// \ref named-templ-param "Named parameter"
1039    ///function for setting OperationTraits type
1040    ///
1041    template<class T>
1042    DagShortestPathWizard<DefOperationTraitsBase<T> > distMap() {
1043      return DagShortestPathWizard<DefDistMapBase<T> >(*this);
1044    }
1045   
1046    /// \brief Sets the source node, from which the DagShortestPath algorithm runs.
1047    ///
1048    /// Sets the source node, from which the DagShortestPath algorithm runs.
1049    /// \param source is the source node.
1050    DagShortestPathWizard<_Traits>& source(Node source) {
1051      Base::_source = source;
1052      return *this;
1053    }
1054   
1055  };
1056 
1057  /// \brief Function type interface for DagShortestPath algorithm.
1058  ///
1059  /// \ingroup flowalgs
1060  /// Function type interface for DagShortestPath algorithm.
1061  ///
1062  /// This function also has several \ref named-templ-func-param
1063  /// "named parameters", they are declared as the members of class
1064  /// \ref DagShortestPathWizard.
1065  /// The following
1066  /// example shows how to use these parameters.
1067  ///\code
1068  /// dagShortestPath(g,length,source).predMap(preds).run();
1069  ///\endcode
1070  /// \warning Don't forget to put the \ref DagShortestPathWizard::run() "run()"
1071  /// to the end of the parameter list.
1072  /// \sa DagShortestPathWizard
1073  /// \sa DagShortestPath
1074  template<class _Graph, class _LengthMap>
1075  DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1076  dagShortestPath(const _Graph& graph,
1077              const _LengthMap& length,
1078              typename _Graph::Node source = INVALID) {
1079    return DagShortestPathWizard<DagShortestPathWizardBase<_Graph,_LengthMap> >
1080      (graph, length, source);
1081  }
1082
1083} //END OF NAMESPACE LEMON
1084
1085#endif
1086
Note: See TracBrowser for help on using the repository browser.