COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 2618:6aa6fcaeaea5

Last change on this file since 2618:6aa6fcaeaea5 was 2618:6aa6fcaeaea5, checked in by Balazs Dezso, 11 years ago

G++-4.3 compatibility changes

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