COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dijkstra.h @ 2020:332245399dc6

Last change on this file since 2020:332245399dc6 was 2010:08464643a658, checked in by Mihaly Barasz, 14 years ago

unused parameters fix

File size: 35.4 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[921]19#ifndef LEMON_DIJKSTRA_H
20#define LEMON_DIJKSTRA_H
[255]21
[758]22///\ingroup flowalgs
[255]23///\file
24///\brief Dijkstra algorithm.
[1283]25///
[1734]26///\todo dijkstraZero() solution should be revised.
[255]27
[953]28#include <lemon/list_graph.h>
[921]29#include <lemon/bin_heap.h>
[1993]30#include <lemon/bits/invalid.h>
[1119]31#include <lemon/error.h>
32#include <lemon/maps.h>
[255]33
[921]34namespace lemon {
[385]35
[1734]36  template<class T> T dijkstraZero() {return 0;}
[1151]37 
[954]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.
[953]43  template<class GR, class LM>
44  struct DijkstraDefaultTraits
45  {
[954]46    ///The graph type the algorithm runs on.
[953]47    typedef GR Graph;
48    ///The type of the map that stores the edge lengths.
49
[1124]50    ///The type of the map that stores the edge lengths.
[967]51    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
[953]52    typedef LM LengthMap;
[954]53    //The type of the length of the edges.
[987]54    typedef typename LM::Value Value;
[1721]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   
[954]70    ///The heap type used by Dijkstra algorithm.
[967]71
72    ///The heap type used by Dijkstra algorithm.
73    ///
74    ///\sa BinHeap
75    ///\sa Dijkstra
[1709]76    typedef BinHeap<typename Graph::Node, typename LM::Value,
[1741]77                    HeapCrossRef, std::less<Value> > Heap;
[953]78
[1721]79    static Heap *createHeap(HeapCrossRef& R)
80    {
81      return new Heap(R);
82    }
83
[953]84    ///\brief The type of the map that stores the last
85    ///edges of the shortest paths.
86    ///
[1124]87    ///The type of the map that stores the last
88    ///edges of the shortest paths.
[967]89    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
[953]90    ///
[954]91    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
92    ///Instantiates a PredMap.
[953]93 
[1123]94    ///This function instantiates a \ref PredMap.
95    ///\param G is the graph, to which we would like to define the PredMap.
[1119]96    ///\todo The graph alone may be insufficient for the initialization
[954]97    static PredMap *createPredMap(const GR &G)
[953]98    {
99      return new PredMap(G);
100    }
[1119]101
[1218]102    ///The type of the map that stores whether a nodes is processed.
[1119]103 
[1218]104    ///The type of the map that stores whether a nodes is processed.
[1119]105    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
106    ///By default it is a NullMap.
[1218]107    ///\todo If it is set to a real map,
108    ///Dijkstra::processed() should read this.
[1119]109    ///\todo named parameter to set this type, function to read and write.
[1218]110    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
111    ///Instantiates a ProcessedMap.
[1119]112 
[1218]113    ///This function instantiates a \ref ProcessedMap.
[1536]114    ///\param g is the graph, to which
[1218]115    ///we would like to define the \ref ProcessedMap
[1536]116#ifdef DOXYGEN
117    static ProcessedMap *createProcessedMap(const GR &g)
118#else
[1366]119    static ProcessedMap *createProcessedMap(const GR &)
[1536]120#endif
[1119]121    {
[1218]122      return new ProcessedMap();
[1119]123    }
[953]124    ///The type of the map that stores the dists of the nodes.
125 
[1124]126    ///The type of the map that stores the dists of the nodes.
[967]127    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
[953]128    ///
[987]129    typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
[954]130    ///Instantiates a DistMap.
[953]131 
[1123]132    ///This function instantiates a \ref DistMap.
133    ///\param G is the graph, to which we would like to define the \ref DistMap
[954]134    static DistMap *createDistMap(const GR &G)
[953]135    {
136      return new DistMap(G);
137    }
138  };
139 
[255]140  ///%Dijkstra algorithm class.
[1125]141 
[1151]142  /// \ingroup flowalgs
[255]143  ///This class provides an efficient implementation of %Dijkstra algorithm.
144  ///The edge lengths are passed to the algorithm using a
[959]145  ///\ref concept::ReadMap "ReadMap",
[255]146  ///so it is easy to change it to any kind of length.
147  ///
[880]148  ///The type of the length is determined by the
[987]149  ///\ref concept::ReadMap::Value "Value" of the length map.
[255]150  ///
151  ///It is also possible to change the underlying priority heap.
152  ///
[1218]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.
[456]168  ///
[689]169  ///\author Jacint Szabo and Alpar Juttner
[584]170
[255]171#ifdef DOXYGEN
[584]172  template <typename GR,
173            typename LM,
[953]174            typename TR>
[255]175#else
[953]176  template <typename GR=ListGraph,
[584]177            typename LM=typename GR::template EdgeMap<int>,
[953]178            typename TR=DijkstraDefaultTraits<GR,LM> >
[255]179#endif
[1116]180  class Dijkstra {
[255]181  public:
[1125]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* exceptionName() const {
[1218]191        return "lemon::Dijkstra::UninitializedParameter";
[1125]192      }
193    };
[1119]194
[953]195    typedef TR Traits;
[584]196    ///The type of the underlying graph.
[954]197    typedef typename TR::Graph Graph;
[911]198    ///\e
[255]199    typedef typename Graph::Node Node;
[911]200    ///\e
[255]201    typedef typename Graph::NodeIt NodeIt;
[911]202    ///\e
[255]203    typedef typename Graph::Edge Edge;
[911]204    ///\e
[255]205    typedef typename Graph::OutEdgeIt OutEdgeIt;
206   
[584]207    ///The type of the length of the edges.
[987]208    typedef typename TR::LengthMap::Value Value;
[693]209    ///The type of the map that stores the edge lengths.
[954]210    typedef typename TR::LengthMap LengthMap;
[693]211    ///\brief The type of the map that stores the last
[584]212    ///edges of the shortest paths.
[953]213    typedef typename TR::PredMap PredMap;
[1218]214    ///The type of the map indicating if a node is processed.
215    typedef typename TR::ProcessedMap ProcessedMap;
[693]216    ///The type of the map that stores the dists of the nodes.
[953]217    typedef typename TR::DistMap DistMap;
[1721]218    ///The cross reference type used for the current heap.
219    typedef typename TR::HeapCrossRef HeapCrossRef;
[953]220    ///The heap type used by the dijkstra algorithm.
221    typedef typename TR::Heap Heap;
[255]222  private:
[802]223    /// Pointer to the underlying graph.
[688]224    const Graph *G;
[802]225    /// Pointer to the length map
[954]226    const LengthMap *length;
[802]227    ///Pointer to the map of predecessors edges.
[1119]228    PredMap *_pred;
229    ///Indicates if \ref _pred is locally allocated (\c true) or not.
230    bool local_pred;
[802]231    ///Pointer to the map of distances.
[1130]232    DistMap *_dist;
233    ///Indicates if \ref _dist is locally allocated (\c true) or not.
234    bool local_dist;
[1218]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;
[1721]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;
[688]247
[1128]248    ///Creates the maps if necessary.
[688]249   
250    ///\todo Better memory allocation (instead of new).
[1128]251    void create_maps()
[688]252    {
[1119]253      if(!_pred) {
254        local_pred = true;
255        _pred = Traits::createPredMap(*G);
[688]256      }
[1130]257      if(!_dist) {
258        local_dist = true;
259        _dist = Traits::createDistMap(*G);
[688]260      }
[1218]261      if(!_processed) {
262        local_processed = true;
263        _processed = Traits::createProcessedMap(*G);
[1119]264      }
[1721]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      }
[688]273    }
[255]274   
275  public :
[1710]276
277    typedef Dijkstra Create;
[1116]278 
[1128]279    ///\name Named template parameters
280
281    ///@{
282
[953]283    template <class T>
[1116]284    struct DefPredMapTraits : public Traits {
[953]285      typedef T PredMap;
[2010]286      static PredMap *createPredMap(const Graph &)
[953]287      {
[1126]288        throw UninitializedParameter();
[953]289      }
290    };
[954]291    ///\ref named-templ-param "Named parameter" for setting PredMap type
292
293    ///\ref named-templ-param "Named parameter" for setting PredMap type
[1043]294    ///
[953]295    template <class T>
[1709]296    struct DefPredMap
297      : public Dijkstra< Graph, LengthMap, DefPredMapTraits<T> > {
298      typedef Dijkstra< Graph,  LengthMap, DefPredMapTraits<T> > Create;
299    };
[953]300   
301    template <class T>
[1116]302    struct DefDistMapTraits : public Traits {
[953]303      typedef T DistMap;
[2010]304      static DistMap *createDistMap(const Graph &)
[953]305      {
[1126]306        throw UninitializedParameter();
[953]307      }
308    };
[954]309    ///\ref named-templ-param "Named parameter" for setting DistMap type
310
311    ///\ref named-templ-param "Named parameter" for setting DistMap type
[1043]312    ///
[953]313    template <class T>
[1709]314    struct DefDistMap
315      : public Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > {
316      typedef Dijkstra< Graph, LengthMap, DefDistMapTraits<T> > Create;
317    };
[953]318   
[1128]319    template <class T>
[1218]320    struct DefProcessedMapTraits : public Traits {
321      typedef T ProcessedMap;
322      static ProcessedMap *createProcessedMap(const Graph &G)
[1128]323      {
324        throw UninitializedParameter();
325      }
326    };
[1218]327    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
[1128]328
[1218]329    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
[1128]330    ///
331    template <class T>
[1709]332    struct DefProcessedMap
333      : public Dijkstra< Graph, LengthMap, DefProcessedMapTraits<T> > {
334      typedef Dijkstra< Graph,  LengthMap, DefProcessedMapTraits<T> > Create;
335    };
[1128]336   
[1218]337    struct DefGraphProcessedMapTraits : public Traits {
338      typedef typename Graph::template NodeMap<bool> ProcessedMap;
339      static ProcessedMap *createProcessedMap(const Graph &G)
[1128]340      {
[1218]341        return new ProcessedMap(G);
[1128]342      }
343    };
344    ///\brief \ref named-templ-param "Named parameter"
[1218]345    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
[1128]346    ///
347    ///\ref named-templ-param "Named parameter"
[1218]348    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
[1128]349    ///If you don't set it explicitely, it will be automatically allocated.
350    template <class T>
[1709]351    struct DefProcessedMapToBeDefaultMap
352      : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> {
353      typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
354    };
[1721]355
356    template <class H, class CR>
357    struct DefHeapTraits : public Traits {
358      typedef CR HeapCrossRef;
359      typedef H Heap;
[1741]360      static HeapCrossRef *createHeapCrossRef(const Graph &) {
361        throw UninitializedParameter();
[1721]362      }
[1741]363      static Heap *createHeap(HeapCrossRef &)
[1721]364      {
[1741]365        throw UninitializedParameter();
[1721]366      }
367    };
368    ///\ref named-templ-param "Named parameter" for setting heap and cross
369    ///reference type
370
371    ///\ref named-templ-param "Named parameter" for setting heap and cross
372    ///reference type
373    ///
374    template <class H, class CR = typename Graph::template NodeMap<int> >
375    struct DefHeap
376      : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
377      typedef Dijkstra< Graph,  LengthMap, DefHeapTraits<H, CR> > Create;
378    };
[1741]379
380    template <class H, class CR>
381    struct DefStandardHeapTraits : public Traits {
382      typedef CR HeapCrossRef;
383      typedef H Heap;
384      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
385        return new HeapCrossRef(G);
386      }
387      static Heap *createHeap(HeapCrossRef &R)
388      {
389        return new Heap(R);
390      }
391    };
392    ///\ref named-templ-param "Named parameter" for setting heap and cross
393    ///reference type with automatic allocation
394
395    ///\ref named-templ-param "Named parameter" for setting heap and cross
396    ///reference type. It can allocate the heap and the cross reference
397    ///object if the cross reference's constructor waits for the graph as
398    ///parameter and the heap's constructor waits for the cross reference.
399    template <class H, class CR = typename Graph::template NodeMap<int> >
400    struct DefStandardHeap
401      : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
402      typedef Dijkstra< Graph,  LengthMap, DefStandardHeapTraits<H, CR> >
403      Create;
404    };
[1128]405   
406    ///@}
407
408
[1710]409  protected:
410
411    Dijkstra() {}
412
[1128]413  public:     
414   
[802]415    ///Constructor.
[255]416   
[802]417    ///\param _G the graph the algorithm will run on.
418    ///\param _length the length map used by the algorithm.
[954]419    Dijkstra(const Graph& _G, const LengthMap& _length) :
[688]420      G(&_G), length(&_length),
[1119]421      _pred(NULL), local_pred(false),
[1130]422      _dist(NULL), local_dist(false),
[1218]423      _processed(NULL), local_processed(false),
[1721]424      _heap_cross_ref(NULL), local_heap_cross_ref(false),
425      _heap(NULL), local_heap(false)
[688]426    { }
427   
[802]428    ///Destructor.
[688]429    ~Dijkstra()
430    {
[1119]431      if(local_pred) delete _pred;
[1130]432      if(local_dist) delete _dist;
[1218]433      if(local_processed) delete _processed;
[1721]434      if(local_heap_cross_ref) delete _heap_cross_ref;
435      if(local_heap) delete _heap;
[688]436    }
437
438    ///Sets the length map.
439
440    ///Sets the length map.
441    ///\return <tt> (*this) </tt>
[1116]442    Dijkstra &lengthMap(const LengthMap &m)
[688]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>
[1116]455    Dijkstra &predMap(PredMap &m)
[688]456    {
[1119]457      if(local_pred) {
458        delete _pred;
459        local_pred=false;
[688]460      }
[1119]461      _pred = &m;
[688]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>
[1116]472    Dijkstra &distMap(DistMap &m)
[688]473    {
[1130]474      if(local_dist) {
475        delete _dist;
476        local_dist=false;
[688]477      }
[1130]478      _dist = &m;
[688]479      return *this;
480    }
[694]481
[1741]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
[1981]487    ///automatically allocated heap and cross reference, of course.
[1741]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
[1130]504  private:
505    void finalizeNodeData(Node v,Value dst)
506    {
[1218]507      _processed->set(v,true);
[1130]508      _dist->set(v, dst);
509    }
510
511  public:
[1218]512    ///\name Execution control
[1128]513    ///The simplest way to execute the algorithm is to use
[1156]514    ///one of the member functions called \c run(...).
[1128]515    ///\n
[1218]516    ///If you need more control on the execution,
[1128]517    ///first you must call \ref init(), then you can add several source nodes
[1218]518    ///with \ref addSource().
519    ///Finally \ref start() will perform the actual path
[1128]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();
[1721]531      _heap->clear();
[774]532      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
[1119]533        _pred->set(u,INVALID);
[1218]534        _processed->set(u,false);
[1721]535        _heap_cross_ref->set(u,Heap::PRE_HEAP);
[694]536      }
[1128]537    }
538   
539    ///Adds a new source node.
540
[1155]541    ///Adds a new source node to the priority heap.
[1128]542    ///
543    ///The optional second parameter is the initial distance of the node.
544    ///
[1155]545    ///It checks if the node has already been added to the heap and
[1988]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.
[1734]548    void addSource(Node s,Value dst=dijkstraZero<Value>())
[1128]549    {
[1721]550      if(_heap->state(s) != Heap::IN_HEAP) {
551        _heap->push(s,dst);
552      } else if((*_heap)[s]<dst) {
[1988]553        _heap->set(s,dst);
[1155]554        _pred->set(s,INVALID);
555      }
[1128]556    }
557   
[1155]558    ///Processes the next node in the priority heap
559
560    ///Processes the next node in the priority heap.
561    ///
[1516]562    ///\return The processed node.
563    ///
[1155]564    ///\warning The priority heap must not be empty!
[1516]565    Node processNextNode()
[1128]566    {
[1721]567      Node v=_heap->top();
568      Value oldvalue=_heap->prio();
569      _heap->pop();
[1130]570      finalizeNodeData(v,oldvalue);
[694]571     
[1128]572      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
573        Node w=G->target(e);
[1721]574        switch(_heap->state(w)) {
[1128]575        case Heap::PRE_HEAP:
[1721]576          _heap->push(w,oldvalue+(*length)[e]);
[1128]577          _pred->set(w,e);
578          break;
579        case Heap::IN_HEAP:
[1721]580          if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
581            _heap->decrease(w, oldvalue+(*length)[e]);
[1119]582            _pred->set(w,e);
[694]583          }
[1128]584          break;
585        case Heap::POST_HEAP:
586          break;
[694]587        }
588      }
[1516]589      return v;
[694]590    }
[1128]591
[1665]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.
[1694]598    Node nextNode()
[1665]599    {
[1721]600      return _heap->empty()?_heap->top():INVALID;
[1665]601    }
602 
[1218]603    ///\brief Returns \c false if there are nodes
604    ///to be processed in the priority heap
[1155]605    ///
[1218]606    ///Returns \c false if there are nodes
607    ///to be processed in the priority heap
[1721]608    bool emptyQueue() { return _heap->empty(); }
[1155]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    ///
[1721]613    int queueSize() { return _heap->size(); }
[1155]614   
[1130]615    ///Executes the algorithm.
[1128]616
[1130]617    ///Executes the algorithm.
[1128]618    ///
[1130]619    ///\pre init() must be called and at least one node should be added
620    ///with addSource() before using this function.
[1128]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    {
[1721]631      while ( !_heap->empty() ) processNextNode();
[1128]632    }
[255]633   
[1130]634    ///Executes the algorithm until \c dest is reached.
[1128]635
[1130]636    ///Executes the algorithm until \c dest is reached.
[1128]637    ///
[1130]638    ///\pre init() must be called and at least one node should be added
639    ///with addSource() before using this function.
[1128]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    {
[1721]650      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
651      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
[1130]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>.
[1345]663    template<class NodeBoolMap>
664    void start(const NodeBoolMap &nm)
[1130]665    {
[1721]666      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
667      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
[1128]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   
[1130]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);
[1734]708      return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
[1130]709    }
710   
[1128]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
[1283]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.
[1536]724    ///If it \c t is a source itself or unreachable, then it does not
[1283]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);
[1763]735        for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
736          b.pushFront(predEdge(t));
[1283]737        b.commit();
738        return true;
739      }
740      return false;
741    }
742         
[385]743    ///The distance of a node from the root.
[255]744
[385]745    ///Returns the distance of a node from the root.
[255]746    ///\pre \ref run() must be called before using this function.
[385]747    ///\warning If node \c v in unreachable from the root the return value
[255]748    ///of this funcion is undefined.
[1130]749    Value dist(Node v) const { return (*_dist)[v]; }
[373]750
[584]751    ///Returns the 'previous edge' of the shortest path tree.
[255]752
[584]753    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
[785]754    ///i.e. it returns the last edge of a shortest path from the root to \c
[688]755    ///v. It is \ref INVALID
756    ///if \c v is unreachable from the root or if \c v=s. The
[385]757    ///shortest path tree used here is equal to the shortest path tree used in
[1631]758    ///\ref predNode().  \pre \ref run() must be called before using
[385]759    ///this function.
[1763]760    Edge predEdge(Node v) const { return (*_pred)[v]; }
[373]761
[584]762    ///Returns the 'previous node' of the shortest path tree.
[255]763
[584]764    ///For a node \c v it returns the 'previous node' of the shortest path tree,
[385]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
[1763]768    ///tree used in \ref predEdge().  \pre \ref run() must be called before
[385]769    ///using this function.
[1130]770    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
771                                  G->source((*_pred)[v]); }
[255]772   
773    ///Returns a reference to the NodeMap of distances.
774
[385]775    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
776    ///be called before using this function.
[1130]777    const DistMap &distMap() const { return *_dist;}
[385]778 
[255]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.
[1119]784    const PredMap &predMap() const { return *_pred;}
[385]785 
786    ///Checks if a node is reachable from the root.
[255]787
[385]788    ///Returns \c true if \c v is reachable from the root.
[1218]789    ///\warning The source nodes are inditated as unreached.
[255]790    ///\pre \ref run() must be called before using this function.
[385]791    ///
[1721]792    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
[1734]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; }
[255]801   
[1128]802    ///@}
[255]803  };
[953]804
[1218]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 concept::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
[1721]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
[1218]846    ///The heap type used by Dijkstra algorithm.
847    ///
848    ///\sa BinHeap
849    ///\sa Dijkstra
[1721]850    typedef BinHeap<typename Graph::Node, typename LM::Value,
[1218]851                    typename GR::template NodeMap<int>,
852                    std::less<Value> > Heap;
853
[1721]854    static Heap *createHeap(HeapCrossRef& R)
855    {
856      return new Heap(R);
857    }
858
[1218]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 concept::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.
[1536]870    ///\param g is the graph, to which we would like to define the PredMap.
[1218]871    ///\todo The graph alone may be insufficient for the initialization
[1536]872#ifdef DOXYGEN
873    static PredMap *createPredMap(const GR &g)
874#else
[1367]875    static PredMap *createPredMap(const GR &)
[1536]876#endif
[1218]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 concept::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.
[1536]892    ///\param g is the graph, to which
[1218]893    ///we would like to define the \ref ProcessedMap
[1536]894#ifdef DOXYGEN
895    static ProcessedMap *createProcessedMap(const GR &g)
896#else
[1367]897    static ProcessedMap *createProcessedMap(const GR &)
[1536]898#endif
[1218]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 concept::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.
[1536]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
[1367]915    static DistMap *createDistMap(const GR &)
[1536]916#endif
[1218]917    {
918      return new DistMap();
919    }
920  };
921 
[1123]922  /// Default traits used by \ref DijkstraWizard
923
[1151]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.
[1123]928  /// The \ref DijkstraWizardBase is a class to be the default traits of the
929  /// \ref DijkstraWizard class.
[1220]930  /// \todo More named parameters are required...
[1116]931  template<class GR,class LM>
[1218]932  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
[1116]933  {
934
[1218]935    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
[1116]936  protected:
[1201]937    /// Type of the nodes in the graph.
938    typedef typename Base::Graph::Node Node;
939
[1116]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.
[1201]949    Node _source;
[1116]950
951    public:
[1123]952    /// Constructor.
953   
954    /// This constructor does not require parameters, therefore it initiates
955    /// all of the attributes to default values (0, INVALID).
[1218]956    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
957                           _dist(0), _source(INVALID) {}
[1116]958
[1123]959    /// Constructor.
960   
[1156]961    /// This constructor requires some parameters,
962    /// listed in the parameters list.
[1123]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
[1116]967    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
[1218]968      _g((void *)&g), _length((void *)&l), _pred(0),
969      _dist(0), _source(s) {}
[1116]970
971  };
972 
[1229]973  /// A class to make the usage of Dijkstra algorithm easier
[953]974
[1123]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,
[1151]977  /// but it is much simpler to use it.
[953]978  ///
[1123]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
[1151]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
[1123]987  /// return the needed class.
988  ///
989  /// It does not have own \ref run method. When its \ref run method is called
[1721]990  /// it initiates a plain \ref Dijkstra class, and calls the \ref
991  /// Dijkstra::run method of it.
[953]992  template<class TR>
[1116]993  class DijkstraWizard : public TR
[953]994  {
[1116]995    typedef TR Base;
[953]996
[1123]997    ///The type of the underlying graph.
[953]998    typedef typename TR::Graph Graph;
[1119]999    //\e
[953]1000    typedef typename Graph::Node Node;
[1119]1001    //\e
[953]1002    typedef typename Graph::NodeIt NodeIt;
[1119]1003    //\e
[953]1004    typedef typename Graph::Edge Edge;
[1119]1005    //\e
[953]1006    typedef typename Graph::OutEdgeIt OutEdgeIt;
1007   
[1123]1008    ///The type of the map that stores the edge lengths.
[953]1009    typedef typename TR::LengthMap LengthMap;
[1123]1010    ///The type of the length of the edges.
[987]1011    typedef typename LengthMap::Value Value;
[1123]1012    ///\brief The type of the map that stores the last
1013    ///edges of the shortest paths.
[953]1014    typedef typename TR::PredMap PredMap;
[1123]1015    ///The type of the map that stores the dists of the nodes.
[953]1016    typedef typename TR::DistMap DistMap;
[1123]1017    ///The heap type used by the dijkstra algorithm.
[953]1018    typedef typename TR::Heap Heap;
[1116]1019public:
[1123]1020    /// Constructor.
[1116]1021    DijkstraWizard() : TR() {}
[953]1022
[1123]1023    /// Constructor that requires parameters.
[1124]1024
1025    /// Constructor that requires parameters.
[1123]1026    /// These parameters will be the default values for the traits class.
[1116]1027    DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1028      TR(g,l,s) {}
[953]1029
[1123]1030    ///Copy constructor
[1116]1031    DijkstraWizard(const TR &b) : TR(b) {}
[953]1032
[1116]1033    ~DijkstraWizard() {}
1034
[1123]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.
[1116]1039    void run()
[953]1040    {
[1201]1041      if(Base::_source==INVALID) throw UninitializedParameter();
[1193]1042      Dijkstra<Graph,LengthMap,TR>
[1345]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);
[1116]1047    }
1048
[1124]1049    ///Runs Dijkstra algorithm from the given node.
[1123]1050
[1124]1051    ///Runs Dijkstra algorithm from the given node.
[1123]1052    ///\param s is the given source.
[1116]1053    void run(Node s)
1054    {
[1201]1055      Base::_source=s;
[1116]1056      run();
[953]1057    }
1058
1059    template<class T>
[1116]1060    struct DefPredMapBase : public Base {
1061      typedef T PredMap;
[1367]1062      static PredMap *createPredMap(const Graph &) { return 0; };
[1236]1063      DefPredMapBase(const TR &b) : TR(b) {}
[1116]1064    };
[953]1065   
[1156]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
[1124]1071    ///
[953]1072    template<class T>
[1116]1073    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
[953]1074    {
[1193]1075      Base::_pred=(void *)&t;
[1116]1076      return DijkstraWizard<DefPredMapBase<T> >(*this);
[953]1077    }
1078   
[1116]1079    template<class T>
1080    struct DefDistMapBase : public Base {
1081      typedef T DistMap;
[1367]1082      static DistMap *createDistMap(const Graph &) { return 0; };
[1236]1083      DefDistMapBase(const TR &b) : TR(b) {}
[1116]1084    };
[953]1085   
[1156]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
[1124]1091    ///
[953]1092    template<class T>
[1116]1093    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
[953]1094    {
[1193]1095      Base::_dist=(void *)&t;
[1116]1096      return DijkstraWizard<DefDistMapBase<T> >(*this);
[953]1097    }
[1117]1098   
[1123]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.
[1117]1103    DijkstraWizard<TR> &source(Node s)
[953]1104    {
[1201]1105      Base::_source=s;
[953]1106      return *this;
1107    }
1108   
1109  };
[255]1110 
[1218]1111  ///Function type interface for Dijkstra algorithm.
[953]1112
[1151]1113  /// \ingroup flowalgs
[1218]1114  ///Function type interface for Dijkstra algorithm.
[953]1115  ///
[1218]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
[953]1128  template<class GR, class LM>
[1116]1129  DijkstraWizard<DijkstraWizardBase<GR,LM> >
1130  dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
[953]1131  {
[1116]1132    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
[953]1133  }
1134
[921]1135} //END OF NAMESPACE LEMON
[255]1136
1137#endif
Note: See TracBrowser for help on using the repository browser.