COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/dijkstra.h @ 118:407c08a0eae9

Last change on this file since 118:407c08a0eae9 was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 17 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

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