COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 1721:c0f5e8401373

Last change on this file since 1721:c0f5e8401373 was 1721:c0f5e8401373, checked in by Balazs Dezso, 15 years ago

Named parameter for heap and cross ref
It needs some redesign

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