COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 2334:c1e936e6a46b

Last change on this file since 2334:c1e936e6a46b was 2269:fb1c634fff29, checked in by Balazs Dezso, 17 years ago

Bug fix for removing heap Item from template parameter list

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