COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 2260:4274224f8a7d

Last change on this file since 2260:4274224f8a7d was 2260:4274224f8a7d, checked in by Alpar Juttner, 18 years ago

concept -> concepts (namespace & directory)

File size: 35.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_DIJKSTRA_H
20#define LEMON_DIJKSTRA_H
21
22///\ingroup flowalgs
23///\file
24///\brief Dijkstra algorithm.
25///
26///\todo dijkstraZero() solution should be revised.
27
28#include <lemon/list_graph.h>
29#include <lemon/bin_heap.h>
30#include <lemon/bits/invalid.h>
31#include <lemon/error.h>
32#include <lemon/maps.h>
33
34namespace lemon {
35
36  template<class T> T dijkstraZero() {return 0;}
37 
38  ///Default traits class of Dijkstra class.
39
40  ///Default traits class of Dijkstra class.
41  ///\param GR Graph type.
42  ///\param LM Type of length map.
43  template<class GR, class LM>
44  struct DijkstraDefaultTraits
45  {
46    ///The graph type the algorithm runs on.
47    typedef GR Graph;
48    ///The type of the map that stores the edge lengths.
49
50    ///The type of the map that stores the edge lengths.
51    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
52    typedef LM LengthMap;
53    //The type of the length of the edges.
54    typedef typename LM::Value Value;
55    /// The cross reference type used by heap.
56
57    /// The cross reference type used by heap.
58    /// Usually it is \c Graph::NodeMap<int>.
59    typedef typename Graph::template NodeMap<int> HeapCrossRef;
60    ///Instantiates a HeapCrossRef.
61
62    ///This function instantiates a \ref HeapCrossRef.
63    /// \param G is the graph, to which we would like to define the
64    /// HeapCrossRef.
65    static HeapCrossRef *createHeapCrossRef(const GR &G)
66    {
67      return new HeapCrossRef(G);
68    }
69   
70    ///The heap type used by Dijkstra algorithm.
71
72    ///The heap type used by Dijkstra algorithm.
73    ///
74    ///\sa BinHeap
75    ///\sa Dijkstra
76    typedef BinHeap<typename Graph::Node, typename LM::Value,
77                    HeapCrossRef, std::less<Value> > Heap;
78
79    static Heap *createHeap(HeapCrossRef& R)
80    {
81      return new Heap(R);
82    }
83
84    ///\brief The type of the map that stores the last
85    ///edges of the shortest paths.
86    ///
87    ///The type of the map that stores the last
88    ///edges of the shortest paths.
89    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
90    ///
91    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
92    ///Instantiates a PredMap.
93 
94    ///This function instantiates a \ref PredMap.
95    ///\param G is the graph, to which we would like to define the PredMap.
96    ///\todo The graph alone may be insufficient for the initialization
97    static PredMap *createPredMap(const GR &G)
98    {
99      return new PredMap(G);
100    }
101
102    ///The type of the map that stores whether a nodes is processed.
103 
104    ///The type of the map that stores whether a nodes is processed.
105    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
106    ///By default it is a NullMap.
107    ///\todo If it is set to a real map,
108    ///Dijkstra::processed() should read this.
109    ///\todo named parameter to set this type, function to read and write.
110    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
111    ///Instantiates a ProcessedMap.
112 
113    ///This function instantiates a \ref ProcessedMap.
114    ///\param g is the graph, to which
115    ///we would like to define the \ref ProcessedMap
116#ifdef DOXYGEN
117    static ProcessedMap *createProcessedMap(const GR &g)
118#else
119    static ProcessedMap *createProcessedMap(const GR &)
120#endif
121    {
122      return new ProcessedMap();
123    }
124    ///The type of the map that stores the dists of the nodes.
125 
126    ///The type of the map that stores the dists of the nodes.
127    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
128    ///
129    typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
130    ///Instantiates a DistMap.
131 
132    ///This function instantiates a \ref DistMap.
133    ///\param G is the graph, to which we would like to define the \ref DistMap
134    static DistMap *createDistMap(const GR &G)
135    {
136      return new DistMap(G);
137    }
138  };
139 
140  ///%Dijkstra algorithm class.
141 
142  /// \ingroup flowalgs
143  ///This class provides an efficient implementation of %Dijkstra algorithm.
144  ///The edge lengths are passed to the algorithm using a
145  ///\ref concepts::ReadMap "ReadMap",
146  ///so it is easy to change it to any kind of length.
147  ///
148  ///The type of the length is determined by the
149  ///\ref concepts::ReadMap::Value "Value" of the length map.
150  ///
151  ///It is also possible to change the underlying priority heap.
152  ///
153  ///\param GR The graph type the algorithm runs on. The default value
154  ///is \ref ListGraph. The value of GR is not used directly by
155  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
156  ///\param LM This read-only EdgeMap determines the lengths of the
157  ///edges. It is read once for each edge, so the map may involve in
158  ///relatively time consuming process to compute the edge length if
159  ///it is necessary. The default map type is \ref
160  ///concepts::Graph::EdgeMap "Graph::EdgeMap<int>".  The value
161  ///of LM is not used directly by Dijkstra, it is only passed to \ref
162  ///DijkstraDefaultTraits.  \param TR Traits class to set
163  ///various data types used by the algorithm.  The default traits
164  ///class is \ref DijkstraDefaultTraits
165  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
166  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
167  ///class.
168  ///
169  ///\author Jacint Szabo and Alpar Juttner
170
171#ifdef DOXYGEN
172  template <typename GR,
173            typename LM,
174            typename TR>
175#else
176  template <typename GR=ListGraph,
177            typename LM=typename GR::template EdgeMap<int>,
178            typename TR=DijkstraDefaultTraits<GR,LM> >
179#endif
180  class Dijkstra {
181  public:
182    /**
183     * \brief \ref Exception for uninitialized parameters.
184     *
185     * This error represents problems in the initialization
186     * of the parameters of the algorithms.
187     */
188    class UninitializedParameter : public lemon::UninitializedParameter {
189    public:
190      virtual const char* what() const throw() {
191        return "lemon::Dijkstra::UninitializedParameter";
192      }
193    };
194
195    typedef TR Traits;
196    ///The type of the underlying graph.
197    typedef typename TR::Graph Graph;
198    ///\e
199    typedef typename Graph::Node Node;
200    ///\e
201    typedef typename Graph::NodeIt NodeIt;
202    ///\e
203    typedef typename Graph::Edge Edge;
204    ///\e
205    typedef typename Graph::OutEdgeIt OutEdgeIt;
206   
207    ///The type of the length of the edges.
208    typedef typename TR::LengthMap::Value Value;
209    ///The type of the map that stores the edge lengths.
210    typedef typename TR::LengthMap LengthMap;
211    ///\brief The type of the map that stores the last
212    ///edges of the shortest paths.
213    typedef typename TR::PredMap PredMap;
214    ///The type of the map indicating if a node is processed.
215    typedef typename TR::ProcessedMap ProcessedMap;
216    ///The type of the map that stores the dists of the nodes.
217    typedef typename TR::DistMap DistMap;
218    ///The cross reference type used for the current heap.
219    typedef typename TR::HeapCrossRef HeapCrossRef;
220    ///The heap type used by the dijkstra algorithm.
221    typedef typename TR::Heap Heap;
222  private:
223    /// Pointer to the underlying graph.
224    const Graph *G;
225    /// Pointer to the length map
226    const LengthMap *length;
227    ///Pointer to the map of predecessors edges.
228    PredMap *_pred;
229    ///Indicates if \ref _pred is locally allocated (\c true) or not.
230    bool local_pred;
231    ///Pointer to the map of distances.
232    DistMap *_dist;
233    ///Indicates if \ref _dist is locally allocated (\c true) or not.
234    bool local_dist;
235    ///Pointer to the map of processed status of the nodes.
236    ProcessedMap *_processed;
237    ///Indicates if \ref _processed is locally allocated (\c true) or not.
238    bool local_processed;
239    ///Pointer to the heap cross references.
240    HeapCrossRef *_heap_cross_ref;
241    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
242    bool local_heap_cross_ref;
243    ///Pointer to the heap.
244    Heap *_heap;
245    ///Indicates if \ref _heap is locally allocated (\c true) or not.
246    bool local_heap;
247
248    ///Creates the maps if necessary.
249   
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 &)
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 &)
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    ///\brief \ref named-templ-param "Named parameter" for setting
369    ///heap and cross 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    ///\brief \ref named-templ-param "Named parameter" for setting
393    ///heap and cross 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 heap and cross reference, 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 shorter than \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->set(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    ///\return Returns \c true if a path to \c t was actually copied to \c p,
727    ///\c false otherwise.
728    ///\sa DirPath
729    template<class P>
730    bool getPath(P &p,Node t)
731    {
732      if(reached(t)) {
733        p.clear();
734        typename P::Builder b(p);
735        for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
736          b.pushFront(predEdge(t));
737        b.commit();
738        return true;
739      }
740      return false;
741    }
742         
743    ///The distance of a node from the root.
744
745    ///Returns the distance of a node from the root.
746    ///\pre \ref run() must be called before using this function.
747    ///\warning If node \c v in unreachable from the root the return value
748    ///of this funcion is undefined.
749    Value dist(Node v) const { return (*_dist)[v]; }
750
751    ///Returns the 'previous edge' of the shortest path tree.
752
753    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
754    ///i.e. it returns the last edge of a shortest path from the root to \c
755    ///v. It is \ref INVALID
756    ///if \c v is unreachable from the root or if \c v=s. The
757    ///shortest path tree used here is equal to the shortest path tree used in
758    ///\ref predNode().  \pre \ref run() must be called before using
759    ///this function.
760    Edge predEdge(Node v) const { return (*_pred)[v]; }
761
762    ///Returns the 'previous node' of the shortest path tree.
763
764    ///For a node \c v it returns the 'previous node' of the shortest path tree,
765    ///i.e. it returns the last but one node from a shortest path from the
766    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
767    ///\c v=s. The shortest path tree used here is equal to the shortest path
768    ///tree used in \ref predEdge().  \pre \ref run() must be called before
769    ///using this function.
770    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
771                                  G->source((*_pred)[v]); }
772   
773    ///Returns a reference to the NodeMap of distances.
774
775    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
776    ///be called before using this function.
777    const DistMap &distMap() const { return *_dist;}
778 
779    ///Returns a reference to the shortest path tree map.
780
781    ///Returns a reference to the NodeMap of the edges of the
782    ///shortest path tree.
783    ///\pre \ref run() must be called before using this function.
784    const PredMap &predMap() const { return *_pred;}
785 
786    ///Checks if a node is reachable from the root.
787
788    ///Returns \c true if \c v is reachable from the root.
789    ///\warning The source nodes are inditated as unreached.
790    ///\pre \ref run() must be called before using this function.
791    ///
792    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
793
794    ///Checks if a node is processed.
795
796    ///Returns \c true if \c v is processed, i.e. the shortest
797    ///path to \c v has already found.
798    ///\pre \ref run() must be called before using this function.
799    ///
800    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
801   
802    ///@}
803  };
804
805
806
807
808 
809  ///Default traits class of Dijkstra function.
810
811  ///Default traits class of Dijkstra function.
812  ///\param GR Graph type.
813  ///\param LM Type of length map.
814  template<class GR, class LM>
815  struct DijkstraWizardDefaultTraits
816  {
817    ///The graph type the algorithm runs on.
818    typedef GR Graph;
819    ///The type of the map that stores the edge lengths.
820
821    ///The type of the map that stores the edge lengths.
822    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
823    typedef LM LengthMap;
824    //The type of the length of the edges.
825    typedef typename LM::Value Value;
826    ///The heap type used by Dijkstra algorithm.
827
828    /// The cross reference type used by heap.
829
830    /// The cross reference type used by heap.
831    /// Usually it is \c Graph::NodeMap<int>.
832    typedef typename Graph::template NodeMap<int> HeapCrossRef;
833    ///Instantiates a HeapCrossRef.
834
835    ///This function instantiates a \ref HeapCrossRef.
836    /// \param G is the graph, to which we would like to define the
837    /// HeapCrossRef.
838    /// \todo The graph alone may be insufficient for the initialization
839    static HeapCrossRef *createHeapCrossRef(const GR &G)
840    {
841      return new HeapCrossRef(G);
842    }
843   
844    ///The heap type used by Dijkstra algorithm.
845
846    ///The heap type used by Dijkstra algorithm.
847    ///
848    ///\sa BinHeap
849    ///\sa Dijkstra
850    typedef BinHeap<typename Graph::Node, typename LM::Value,
851                    typename GR::template NodeMap<int>,
852                    std::less<Value> > Heap;
853
854    static Heap *createHeap(HeapCrossRef& R)
855    {
856      return new Heap(R);
857    }
858
859    ///\brief The type of the map that stores the last
860    ///edges of the shortest paths.
861    ///
862    ///The type of the map that stores the last
863    ///edges of the shortest paths.
864    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
865    ///
866    typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
867    ///Instantiates a PredMap.
868 
869    ///This function instantiates a \ref PredMap.
870    ///\param g is the graph, to which we would like to define the PredMap.
871    ///\todo The graph alone may be insufficient for the initialization
872#ifdef DOXYGEN
873    static PredMap *createPredMap(const GR &g)
874#else
875    static PredMap *createPredMap(const GR &)
876#endif
877    {
878      return new PredMap();
879    }
880    ///The type of the map that stores whether a nodes is processed.
881 
882    ///The type of the map that stores whether a nodes is processed.
883    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
884    ///By default it is a NullMap.
885    ///\todo If it is set to a real map,
886    ///Dijkstra::processed() should read this.
887    ///\todo named parameter to set this type, function to read and write.
888    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
889    ///Instantiates a ProcessedMap.
890 
891    ///This function instantiates a \ref ProcessedMap.
892    ///\param g is the graph, to which
893    ///we would like to define the \ref ProcessedMap
894#ifdef DOXYGEN
895    static ProcessedMap *createProcessedMap(const GR &g)
896#else
897    static ProcessedMap *createProcessedMap(const GR &)
898#endif
899    {
900      return new ProcessedMap();
901    }
902    ///The type of the map that stores the dists of the nodes.
903 
904    ///The type of the map that stores the dists of the nodes.
905    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
906    ///
907    typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
908    ///Instantiates a DistMap.
909 
910    ///This function instantiates a \ref DistMap.
911    ///\param g is the graph, to which we would like to define the \ref DistMap
912#ifdef DOXYGEN
913    static DistMap *createDistMap(const GR &g)
914#else
915    static DistMap *createDistMap(const GR &)
916#endif
917    {
918      return new DistMap();
919    }
920  };
921 
922  /// Default traits used by \ref DijkstraWizard
923
924  /// To make it easier to use Dijkstra algorithm
925  ///we have created a wizard class.
926  /// This \ref DijkstraWizard class needs default traits,
927  ///as well as the \ref Dijkstra class.
928  /// The \ref DijkstraWizardBase is a class to be the default traits of the
929  /// \ref DijkstraWizard class.
930  /// \todo More named parameters are required...
931  template<class GR,class LM>
932  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
933  {
934
935    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
936  protected:
937    /// Type of the nodes in the graph.
938    typedef typename Base::Graph::Node Node;
939
940    /// Pointer to the underlying graph.
941    void *_g;
942    /// Pointer to the length map
943    void *_length;
944    ///Pointer to the map of predecessors edges.
945    void *_pred;
946    ///Pointer to the map of distances.
947    void *_dist;
948    ///Pointer to the source node.
949    Node _source;
950
951    public:
952    /// Constructor.
953   
954    /// This constructor does not require parameters, therefore it initiates
955    /// all of the attributes to default values (0, INVALID).
956    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
957                           _dist(0), _source(INVALID) {}
958
959    /// Constructor.
960   
961    /// This constructor requires some parameters,
962    /// listed in the parameters list.
963    /// Others are initiated to 0.
964    /// \param g is the initial value of  \ref _g
965    /// \param l is the initial value of  \ref _length
966    /// \param s is the initial value of  \ref _source
967    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
968      _g((void *)&g), _length((void *)&l), _pred(0),
969      _dist(0), _source(s) {}
970
971  };
972 
973  /// A class to make the usage of Dijkstra algorithm easier
974
975  /// This class is created to make it easier to use Dijkstra algorithm.
976  /// It uses the functions and features of the plain \ref Dijkstra,
977  /// but it is much simpler to use it.
978  ///
979  /// Simplicity means that the way to change the types defined
980  /// in the traits class is based on functions that returns the new class
981  /// and not on templatable built-in classes.
982  /// When using the plain \ref Dijkstra
983  /// the new class with the modified type comes from
984  /// the original class by using the ::
985  /// operator. In the case of \ref DijkstraWizard only
986  /// a function have to be called and it will
987  /// return the needed class.
988  ///
989  /// It does not have own \ref run method. When its \ref run method is called
990  /// it initiates a plain \ref Dijkstra class, and calls the \ref
991  /// Dijkstra::run method of it.
992  template<class TR>
993  class DijkstraWizard : public TR
994  {
995    typedef TR Base;
996
997    ///The type of the underlying graph.
998    typedef typename TR::Graph Graph;
999    //\e
1000    typedef typename Graph::Node Node;
1001    //\e
1002    typedef typename Graph::NodeIt NodeIt;
1003    //\e
1004    typedef typename Graph::Edge Edge;
1005    //\e
1006    typedef typename Graph::OutEdgeIt OutEdgeIt;
1007   
1008    ///The type of the map that stores the edge lengths.
1009    typedef typename TR::LengthMap LengthMap;
1010    ///The type of the length of the edges.
1011    typedef typename LengthMap::Value Value;
1012    ///\brief The type of the map that stores the last
1013    ///edges of the shortest paths.
1014    typedef typename TR::PredMap PredMap;
1015    ///The type of the map that stores the dists of the nodes.
1016    typedef typename TR::DistMap DistMap;
1017    ///The heap type used by the dijkstra algorithm.
1018    typedef typename TR::Heap Heap;
1019public:
1020    /// Constructor.
1021    DijkstraWizard() : TR() {}
1022
1023    /// Constructor that requires parameters.
1024
1025    /// Constructor that requires parameters.
1026    /// These parameters will be the default values for the traits class.
1027    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1028      TR(g,l,s) {}
1029
1030    ///Copy constructor
1031    DijkstraWizard(const TR &b) : TR(b) {}
1032
1033    ~DijkstraWizard() {}
1034
1035    ///Runs Dijkstra algorithm from a given node.
1036   
1037    ///Runs Dijkstra algorithm from a given node.
1038    ///The node can be given by the \ref source function.
1039    void run()
1040    {
1041      if(Base::_source==INVALID) throw UninitializedParameter();
1042      Dijkstra<Graph,LengthMap,TR>
1043        dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
1044      if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
1045      if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
1046      dij.run(Base::_source);
1047    }
1048
1049    ///Runs Dijkstra algorithm from the given node.
1050
1051    ///Runs Dijkstra algorithm from the given node.
1052    ///\param s is the given source.
1053    void run(Node s)
1054    {
1055      Base::_source=s;
1056      run();
1057    }
1058
1059    template<class T>
1060    struct DefPredMapBase : public Base {
1061      typedef T PredMap;
1062      static PredMap *createPredMap(const Graph &) { return 0; };
1063      DefPredMapBase(const TR &b) : TR(b) {}
1064    };
1065   
1066    ///\brief \ref named-templ-param "Named parameter"
1067    ///function for setting PredMap type
1068    ///
1069    /// \ref named-templ-param "Named parameter"
1070    ///function for setting PredMap type
1071    ///
1072    template<class T>
1073    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1074    {
1075      Base::_pred=(void *)&t;
1076      return DijkstraWizard<DefPredMapBase<T> >(*this);
1077    }
1078   
1079    template<class T>
1080    struct DefDistMapBase : public Base {
1081      typedef T DistMap;
1082      static DistMap *createDistMap(const Graph &) { return 0; };
1083      DefDistMapBase(const TR &b) : TR(b) {}
1084    };
1085   
1086    ///\brief \ref named-templ-param "Named parameter"
1087    ///function for setting DistMap type
1088    ///
1089    /// \ref named-templ-param "Named parameter"
1090    ///function for setting DistMap type
1091    ///
1092    template<class T>
1093    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1094    {
1095      Base::_dist=(void *)&t;
1096      return DijkstraWizard<DefDistMapBase<T> >(*this);
1097    }
1098   
1099    /// Sets the source node, from which the Dijkstra algorithm runs.
1100
1101    /// Sets the source node, from which the Dijkstra algorithm runs.
1102    /// \param s is the source node.
1103    DijkstraWizard<TR> &source(Node s)
1104    {
1105      Base::_source=s;
1106      return *this;
1107    }
1108   
1109  };
1110 
1111  ///Function type interface for Dijkstra algorithm.
1112
1113  /// \ingroup flowalgs
1114  ///Function type interface for Dijkstra algorithm.
1115  ///
1116  ///This function also has several
1117  ///\ref named-templ-func-param "named parameters",
1118  ///they are declared as the members of class \ref DijkstraWizard.
1119  ///The following
1120  ///example shows how to use these parameters.
1121  ///\code
1122  ///  dijkstra(g,length,source).predMap(preds).run();
1123  ///\endcode
1124  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1125  ///to the end of the parameter list.
1126  ///\sa DijkstraWizard
1127  ///\sa Dijkstra
1128  template<class GR, class LM>
1129  DijkstraWizard<DijkstraWizardBase<GR,LM> >
1130  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1131  {
1132    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1133  }
1134
1135} //END OF NAMESPACE LEMON
1136
1137#endif
Note: See TracBrowser for help on using the repository browser.