COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 1763:49045f2d28d4

Last change on this file since 1763:49045f2d28d4 was 1763:49045f2d28d4, checked in by Balazs Dezso, 14 years ago

pred => predEdge rename

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