COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 1694:6d81e6f7a88d

Last change on this file since 1694:6d81e6f7a88d was 1694:6d81e6f7a88d, checked in by Balazs Dezso, 14 years ago

Fixing naming conventions
Temporarly bugfix with named-parameters
Removing dead codes

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