COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.0 for lemon/dijkstra.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r184 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    3535
    3636  /// \brief Default OperationTraits for the Dijkstra algorithm class.
    37   /// 
     37  ///
    3838  /// It defines all computational operations and constants which are
    3939  /// used in the Dijkstra algorithm.
     
    5555
    5656  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
    57   /// 
     57  ///
    5858  /// It defines all computational operations and constants which are
    5959  /// used in the Dijkstra algorithm for widest path computation.
     
    7373    }
    7474  };
    75  
     75
    7676  ///Default traits class of Dijkstra class.
    7777
     
    8282  struct DijkstraDefaultTraits
    8383  {
    84     ///The digraph type the algorithm runs on. 
     84    ///The digraph type the algorithm runs on.
    8585    typedef GR Digraph;
    8686    ///The type of the map that stores the arc lengths.
     
    104104    ///Instantiates a HeapCrossRef.
    105105
    106     ///This function instantiates a \c HeapCrossRef. 
    107     /// \param G is the digraph, to which we would like to define the 
     106    ///This function instantiates a \c HeapCrossRef.
     107    /// \param G is the digraph, to which we would like to define the
    108108    /// HeapCrossRef.
    109     static HeapCrossRef *createHeapCrossRef(const GR &G) 
     109    static HeapCrossRef *createHeapCrossRef(const GR &G)
    110110    {
    111111      return new HeapCrossRef(G);
    112112    }
    113    
     113
    114114    ///The heap type used by Dijkstra algorithm.
    115115
     
    120120    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    121121
    122     static Heap *createHeap(HeapCrossRef& R) 
     122    static Heap *createHeap(HeapCrossRef& R)
    123123    {
    124124      return new Heap(R);
     
    127127    ///\brief The type of the map that stores the last
    128128    ///arcs of the shortest paths.
    129     /// 
     129    ///
    130130    ///The type of the map that stores the last
    131131    ///arcs of the shortest paths.
     
    134134    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    135135    ///Instantiates a PredMap.
    136  
    137     ///This function instantiates a \c PredMap. 
     136
     137    ///This function instantiates a \c PredMap.
    138138    ///\param G is the digraph, to which we would like to define the PredMap.
    139139    ///\todo The digraph alone may be insufficient for the initialization
    140     static PredMap *createPredMap(const GR &G) 
     140    static PredMap *createPredMap(const GR &G)
    141141    {
    142142      return new PredMap(G);
     
    144144
    145145    ///The type of the map that stores whether a nodes is processed.
    146  
     146
    147147    ///The type of the map that stores whether a nodes is processed.
    148148    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    153153    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    154154    ///Instantiates a ProcessedMap.
    155  
    156     ///This function instantiates a \c ProcessedMap. 
     155
     156    ///This function instantiates a \c ProcessedMap.
    157157    ///\param g is the digraph, to which
    158158    ///we would like to define the \c ProcessedMap
     
    166166    }
    167167    ///The type of the map that stores the dists of the nodes.
    168  
     168
    169169    ///The type of the map that stores the dists of the nodes.
    170170    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    172172    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    173173    ///Instantiates a DistMap.
    174  
    175     ///This function instantiates a \ref DistMap. 
     174
     175    ///This function instantiates a \ref DistMap.
    176176    ///\param G is the digraph, to which we would like to define the \ref DistMap
    177177    static DistMap *createDistMap(const GR &G)
     
    180180    }
    181181  };
    182  
     182
    183183  ///%Dijkstra algorithm class.
    184  
     184
    185185  /// \ingroup shortest_path
    186186  ///This class provides an efficient implementation of %Dijkstra algorithm.
     
    203203  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
    204204  ///of LM is not used directly by Dijkstra, it is only passed to \ref
    205   ///DijkstraDefaultTraits. 
     205  ///DijkstraDefaultTraits.
    206206  ///\tparam TR Traits class to set
    207207  ///various data types used by the algorithm.  The default traits
     
    215215#else
    216216  template <typename GR=ListDigraph,
    217             typename LM=typename GR::template ArcMap<int>,
    218             typename TR=DijkstraDefaultTraits<GR,LM> >
     217            typename LM=typename GR::template ArcMap<int>,
     218            typename TR=DijkstraDefaultTraits<GR,LM> >
    219219#endif
    220220  class Dijkstra {
     
    229229    public:
    230230      virtual const char* what() const throw() {
    231         return "lemon::Dijkstra::UninitializedParameter";
     231        return "lemon::Dijkstra::UninitializedParameter";
    232232      }
    233233    };
     
    244244    ///\e
    245245    typedef typename Digraph::OutArcIt OutArcIt;
    246    
     246
    247247    ///The type of the length of the arcs.
    248248    typedef typename TR::LengthMap::Value Value;
     
    289289
    290290    ///Creates the maps if necessary.
    291    
     291
    292292    ///\todo Better memory allocation (instead of new).
    293     void create_maps() 
     293    void create_maps()
    294294    {
    295295      if(!_pred) {
    296         local_pred = true;
    297         _pred = Traits::createPredMap(*G);
     296        local_pred = true;
     297        _pred = Traits::createPredMap(*G);
    298298      }
    299299      if(!_dist) {
    300         local_dist = true;
    301         _dist = Traits::createDistMap(*G);
     300        local_dist = true;
     301        _dist = Traits::createDistMap(*G);
    302302      }
    303303      if(!_processed) {
    304         local_processed = true;
    305         _processed = Traits::createProcessedMap(*G);
     304        local_processed = true;
     305        _processed = Traits::createProcessedMap(*G);
    306306      }
    307307      if (!_heap_cross_ref) {
    308         local_heap_cross_ref = true;
    309         _heap_cross_ref = Traits::createHeapCrossRef(*G);
     308        local_heap_cross_ref = true;
     309        _heap_cross_ref = Traits::createHeapCrossRef(*G);
    310310      }
    311311      if (!_heap) {
    312         local_heap = true;
    313         _heap = Traits::createHeap(*_heap_cross_ref);
    314       }
    315     }
    316    
     312        local_heap = true;
     313        _heap = Traits::createHeap(*_heap_cross_ref);
     314      }
     315    }
     316
    317317  public :
    318318
    319319    typedef Dijkstra Create;
    320  
     320
    321321    ///\name Named template parameters
    322322
     
    328328      static PredMap *createPredMap(const Digraph &)
    329329      {
    330         throw UninitializedParameter();
     330        throw UninitializedParameter();
    331331      }
    332332    };
     
    336336    ///
    337337    template <class T>
    338     struct DefPredMap 
    339       : public Dijkstra< Digraph,       LengthMap, DefPredMapTraits<T> > {
    340       typedef Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > Create;
    341     };
    342    
     338    struct DefPredMap
     339      : public Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > {
     340      typedef Dijkstra< Digraph,        LengthMap, DefPredMapTraits<T> > Create;
     341    };
     342
    343343    template <class T>
    344344    struct DefDistMapTraits : public Traits {
     
    346346      static DistMap *createDistMap(const Digraph &)
    347347      {
    348         throw UninitializedParameter();
     348        throw UninitializedParameter();
    349349      }
    350350    };
     
    354354    ///
    355355    template <class T>
    356     struct DefDistMap 
    357       : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { 
     356    struct DefDistMap
     357      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
    358358      typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
    359359    };
    360    
     360
    361361    template <class T>
    362362    struct DefProcessedMapTraits : public Traits {
    363363      typedef T ProcessedMap;
    364       static ProcessedMap *createProcessedMap(const Digraph &G) 
     364      static ProcessedMap *createProcessedMap(const Digraph &G)
    365365      {
    366         throw UninitializedParameter();
     366        throw UninitializedParameter();
    367367      }
    368368    };
     
    372372    ///
    373373    template <class T>
    374     struct DefProcessedMap 
    375       : public Dijkstra< Digraph,       LengthMap, DefProcessedMapTraits<T> > {
    376       typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;
    377     };
    378    
     374    struct DefProcessedMap
     375      : public Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > {
     376      typedef Dijkstra< Digraph,        LengthMap, DefProcessedMapTraits<T> > Create;
     377    };
     378
    379379    struct DefDigraphProcessedMapTraits : public Traits {
    380380      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    381       static ProcessedMap *createProcessedMap(const Digraph &G) 
     381      static ProcessedMap *createProcessedMap(const Digraph &G)
    382382      {
    383         return new ProcessedMap(G);
     383        return new ProcessedMap(G);
    384384      }
    385385    };
     
    391391    ///If you don't set it explicitely, it will be automatically allocated.
    392392    template <class T>
    393     struct DefProcessedMapToBeDefaultMap 
     393    struct DefProcessedMapToBeDefaultMap
    394394      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
    395395      typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
     
    401401      typedef H Heap;
    402402      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
    403         throw UninitializedParameter();
    404       }
    405       static Heap *createHeap(HeapCrossRef &) 
     403        throw UninitializedParameter();
     404      }
     405      static Heap *createHeap(HeapCrossRef &)
    406406      {
    407         throw UninitializedParameter();
     407        throw UninitializedParameter();
    408408      }
    409409    };
     
    411411    ///heap and cross reference type
    412412    ///
    413     ///\ref named-templ-param "Named parameter" for setting heap and cross 
     413    ///\ref named-templ-param "Named parameter" for setting heap and cross
    414414    ///reference type
    415415    ///
    416416    template <class H, class CR = typename Digraph::template NodeMap<int> >
    417417    struct DefHeap
    418       : public Dijkstra< Digraph,       LengthMap, DefHeapTraits<H, CR> > {
    419       typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;
     418      : public Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > {
     419      typedef Dijkstra< Digraph,        LengthMap, DefHeapTraits<H, CR> > Create;
    420420    };
    421421
     
    425425      typedef H Heap;
    426426      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
    427         return new HeapCrossRef(G);
    428       }
    429       static Heap *createHeap(HeapCrossRef &R) 
     427        return new HeapCrossRef(G);
     428      }
     429      static Heap *createHeap(HeapCrossRef &R)
    430430      {
    431         return new Heap(R);
     431        return new Heap(R);
    432432      }
    433433    };
     
    435435    ///heap and cross reference type with automatic allocation
    436436    ///
    437     ///\ref named-templ-param "Named parameter" for setting heap and cross 
    438     ///reference type. It can allocate the heap and the cross reference 
    439     ///object if the cross reference's constructor waits for the digraph as 
     437    ///\ref named-templ-param "Named parameter" for setting heap and cross
     438    ///reference type. It can allocate the heap and the cross reference
     439    ///object if the cross reference's constructor waits for the digraph as
    440440    ///parameter and the heap's constructor waits for the cross reference.
    441441    template <class H, class CR = typename Digraph::template NodeMap<int> >
    442442    struct DefStandardHeap
    443       : public Dijkstra< Digraph,       LengthMap, DefStandardHeapTraits<H, CR> > {
    444       typedef Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> >
     443      : public Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> > {
     444      typedef Dijkstra< Digraph,        LengthMap, DefStandardHeapTraits<H, CR> >
    445445      Create;
    446446    };
     
    450450      typedef T OperationTraits;
    451451    };
    452    
    453     /// \brief \ref named-templ-param "Named parameter" for setting 
     452
     453    /// \brief \ref named-templ-param "Named parameter" for setting
    454454    /// OperationTraits type
    455455    ///
     
    462462      Create;
    463463    };
    464    
     464
    465465    ///@}
    466466
     
    470470    Dijkstra() {}
    471471
    472   public:     
    473    
     472  public:
     473
    474474    ///Constructor.
    475    
     475
    476476    ///\param _G the digraph the algorithm will run on.
    477477    ///\param _length the length map used by the algorithm.
     
    484484      _heap(NULL), local_heap(false)
    485485    { }
    486    
     486
    487487    ///Destructor.
    488     ~Dijkstra() 
     488    ~Dijkstra()
    489489    {
    490490      if(local_pred) delete _pred;
     
    499499    ///Sets the length map.
    500500    ///\return <tt> (*this) </tt>
    501     Dijkstra &lengthMap(const LengthMap &m) 
     501    Dijkstra &lengthMap(const LengthMap &m)
    502502    {
    503503      length = &m;
     
    512512    ///automatically allocated map, of course.
    513513    ///\return <tt> (*this) </tt>
    514     Dijkstra &predMap(PredMap &m) 
     514    Dijkstra &predMap(PredMap &m)
    515515    {
    516516      if(local_pred) {
    517         delete _pred;
    518         local_pred=false;
     517        delete _pred;
     518        local_pred=false;
    519519      }
    520520      _pred = &m;
     
    529529    ///automatically allocated map, of course.
    530530    ///\return <tt> (*this) </tt>
    531     Dijkstra &distMap(DistMap &m) 
     531    Dijkstra &distMap(DistMap &m)
    532532    {
    533533      if(local_dist) {
    534         delete _dist;
    535         local_dist=false;
     534        delete _dist;
     535        local_dist=false;
    536536      }
    537537      _dist = &m;
     
    549549    {
    550550      if(local_heap_cross_ref) {
    551         delete _heap_cross_ref;
    552         local_heap_cross_ref=false;
     551        delete _heap_cross_ref;
     552        local_heap_cross_ref=false;
    553553      }
    554554      _heap_cross_ref = &cr;
    555555      if(local_heap) {
    556         delete _heap;
    557         local_heap=false;
     556        delete _heap;
     557        local_heap=false;
    558558      }
    559559      _heap = &hp;
     
    593593      _heap->clear();
    594594      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    595         _pred->set(u,INVALID);
    596         _processed->set(u,false);
    597         _heap_cross_ref->set(u,Heap::PRE_HEAP);
    598       }
    599     }
    600    
     595        _pred->set(u,INVALID);
     596        _processed->set(u,false);
     597        _heap_cross_ref->set(u,Heap::PRE_HEAP);
     598      }
     599    }
     600
    601601    ///Adds a new source node.
    602602
     
    611611    {
    612612      if(_heap->state(s) != Heap::IN_HEAP) {
    613         _heap->push(s,dst);
     613        _heap->push(s,dst);
    614614      } else if(OperationTraits::less((*_heap)[s], dst)) {
    615         _heap->set(s,dst);
    616         _pred->set(s,INVALID);
    617       }
    618     }
    619    
     615        _heap->set(s,dst);
     616        _pred->set(s,INVALID);
     617      }
     618    }
     619
    620620    ///Processes the next node in the priority heap
    621621
     
    627627    Node processNextNode()
    628628    {
    629       Node v=_heap->top(); 
     629      Node v=_heap->top();
    630630      Value oldvalue=_heap->prio();
    631631      _heap->pop();
    632632      finalizeNodeData(v,oldvalue);
    633      
     633
    634634      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
    635         Node w=G->target(e);
    636         switch(_heap->state(w)) {
    637         case Heap::PRE_HEAP:
    638           _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
    639           _pred->set(w,e);
    640           break;
    641         case Heap::IN_HEAP:
    642           {
    643             Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
    644             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
    645               _heap->decrease(w, newvalue);
    646               _pred->set(w,e);
    647             }
    648           }
    649           break;
    650         case Heap::POST_HEAP:
    651           break;
    652         }
     635        Node w=G->target(e);
     636        switch(_heap->state(w)) {
     637        case Heap::PRE_HEAP:
     638          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
     639          _pred->set(w,e);
     640          break;
     641        case Heap::IN_HEAP:
     642          {
     643            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
     644            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
     645              _heap->decrease(w, newvalue);
     646              _pred->set(w,e);
     647            }
     648          }
     649          break;
     650        case Heap::POST_HEAP:
     651          break;
     652        }
    653653      }
    654654      return v;
     
    656656
    657657    ///Next node to be processed.
    658    
     658
    659659    ///Next node to be processed.
    660660    ///
     
    662662    /// is empty.
    663663    Node nextNode()
    664     { 
     664    {
    665665      return !_heap->empty()?_heap->top():INVALID;
    666666    }
    667  
     667
    668668    ///\brief Returns \c false if there are nodes
    669669    ///to be processed in the priority heap
     
    677677    ///
    678678    int queueSize() { return _heap->size(); }
    679    
     679
    680680    ///Executes the algorithm.
    681681
     
    696696      while ( !_heap->empty() ) processNextNode();
    697697    }
    698    
     698
    699699    ///Executes the algorithm until \c dest is reached.
    700700
     
    716716      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    717717    }
    718    
     718
    719719    ///Executes the algorithm until a condition is met.
    720720
     
    737737      return _heap->top();
    738738    }
    739    
     739
    740740    ///Runs %Dijkstra algorithm from node \c s.
    741    
     741
    742742    ///This method runs the %Dijkstra algorithm from a root node \c s
    743743    ///in order to
     
    758758      start();
    759759    }
    760    
     760
    761761    ///Finds the shortest path between \c s and \c t.
    762    
     762
    763763    ///Finds the shortest path between \c s and \c t.
    764764    ///
     
    778778      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
    779779    }
    780    
     780
    781781    ///@}
    782782
     
    786786    ///Before the use of these functions,
    787787    ///either run() or start() must be called.
    788    
     788
    789789    ///@{
    790790
    791791    ///Gives back the shortest path.
    792    
     792
    793793    ///Gives back the shortest path.
    794794    ///\pre The \c t should be reachable from the source.
    795     Path path(Node t) 
     795    Path path(Node t)
    796796    {
    797797      return Path(*G, *_pred, t);
     
    833833    ///using this function.
    834834    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    835                                   G->source((*_pred)[v]); }
    836    
     835                                  G->source((*_pred)[v]); }
     836
    837837    ///Returns a reference to the NodeMap of distances.
    838838
     
    840840    ///be called before using this function.
    841841    const DistMap &distMap() const { return *_dist;}
    842  
     842
    843843    ///Returns a reference to the shortest path tree map.
    844844
     
    847847    ///\pre \ref run() must be called before using this function.
    848848    const PredMap &predMap() const { return *_pred;}
    849  
     849
    850850    ///Checks if a node is reachable from the root.
    851851
     
    863863    ///
    864864    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
    865    
     865
    866866    ///@}
    867867  };
     
    870870
    871871
    872  
     872
    873873  ///Default traits class of Dijkstra function.
    874874
     
    879879  struct DijkstraWizardDefaultTraits
    880880  {
    881     ///The digraph type the algorithm runs on. 
     881    ///The digraph type the algorithm runs on.
    882882    typedef GR Digraph;
    883883    ///The type of the map that stores the arc lengths.
     
    902902    ///Instantiates a HeapCrossRef.
    903903
    904     ///This function instantiates a \ref HeapCrossRef. 
    905     /// \param G is the digraph, to which we would like to define the 
     904    ///This function instantiates a \ref HeapCrossRef.
     905    /// \param G is the digraph, to which we would like to define the
    906906    /// HeapCrossRef.
    907907    /// \todo The digraph alone may be insufficient for the initialization
    908     static HeapCrossRef *createHeapCrossRef(const GR &G) 
     908    static HeapCrossRef *createHeapCrossRef(const GR &G)
    909909    {
    910910      return new HeapCrossRef(G);
    911911    }
    912    
     912
    913913    ///The heap type used by Dijkstra algorithm.
    914914
     
    918918    ///\sa Dijkstra
    919919    typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
    920                     std::less<Value> > Heap;
    921 
    922     static Heap *createHeap(HeapCrossRef& R) 
     920                    std::less<Value> > Heap;
     921
     922    static Heap *createHeap(HeapCrossRef& R)
    923923    {
    924924      return new Heap(R);
     
    927927    ///\brief The type of the map that stores the last
    928928    ///arcs of the shortest paths.
    929     /// 
     929    ///
    930930    ///The type of the map that stores the last
    931931    ///arcs of the shortest paths.
     
    934934    typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
    935935    ///Instantiates a PredMap.
    936  
    937     ///This function instantiates a \ref PredMap. 
     936
     937    ///This function instantiates a \ref PredMap.
    938938    ///\param g is the digraph, to which we would like to define the PredMap.
    939939    ///\todo The digraph alone may be insufficient for the initialization
    940940#ifdef DOXYGEN
    941     static PredMap *createPredMap(const GR &g) 
     941    static PredMap *createPredMap(const GR &g)
    942942#else
    943     static PredMap *createPredMap(const GR &) 
     943    static PredMap *createPredMap(const GR &)
    944944#endif
    945945    {
     
    947947    }
    948948    ///The type of the map that stores whether a nodes is processed.
    949  
     949
    950950    ///The type of the map that stores whether a nodes is processed.
    951951    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    956956    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    957957    ///Instantiates a ProcessedMap.
    958  
    959     ///This function instantiates a \ref ProcessedMap. 
     958
     959    ///This function instantiates a \ref ProcessedMap.
    960960    ///\param g is the digraph, to which
    961961    ///we would like to define the \ref ProcessedMap
     
    969969    }
    970970    ///The type of the map that stores the dists of the nodes.
    971  
     971
    972972    ///The type of the map that stores the dists of the nodes.
    973973    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    975975    typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
    976976    ///Instantiates a DistMap.
    977  
    978     ///This function instantiates a \ref DistMap. 
     977
     978    ///This function instantiates a \ref DistMap.
    979979    ///\param g is the digraph, to which we would like to define the \ref DistMap
    980980#ifdef DOXYGEN
     
    987987    }
    988988  };
    989  
     989
    990990  /// Default traits used by \ref DijkstraWizard
    991991
     
    10191019    public:
    10201020    /// Constructor.
    1021    
     1021
    10221022    /// This constructor does not require parameters, therefore it initiates
    10231023    /// all of the attributes to default values (0, INVALID).
    10241024    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
    1025                            _dist(0), _source(INVALID) {}
     1025                           _dist(0), _source(INVALID) {}
    10261026
    10271027    /// Constructor.
    1028    
     1028
    10291029    /// This constructor requires some parameters,
    10301030    /// listed in the parameters list.
     
    10341034    /// \param s is the initial value of  \ref _source
    10351035    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    1036       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 
    1037       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 
     1036      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
     1037      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
    10381038      _pred(0), _dist(0), _source(s) {}
    10391039
    10401040  };
    1041  
     1041
    10421042  /// A class to make the usage of Dijkstra algorithm easier
    10431043
     
    10571057  ///
    10581058  /// It does not have own \ref run method. When its \ref run method is called
    1059   /// it initiates a plain \ref Dijkstra class, and calls the \ref 
     1059  /// it initiates a plain \ref Dijkstra class, and calls the \ref
    10601060  /// Dijkstra::run method of it.
    10611061  template<class TR>
     
    10741074    //\e
    10751075    typedef typename Digraph::OutArcIt OutArcIt;
    1076    
     1076
    10771077    ///The type of the map that stores the arc lengths.
    10781078    typedef typename TR::LengthMap LengthMap;
     
    11031103
    11041104    ///Runs Dijkstra algorithm from a given node.
    1105    
     1105
    11061106    ///Runs Dijkstra algorithm from a given node.
    11071107    ///The node can be given by the \ref source function.
     
    11091109    {
    11101110      if(Base::_source==INVALID) throw UninitializedParameter();
    1111       Dijkstra<Digraph,LengthMap,TR> 
    1112         dij(*reinterpret_cast<const Digraph*>(Base::_g),
     1111      Dijkstra<Digraph,LengthMap,TR>
     1112        dij(*reinterpret_cast<const Digraph*>(Base::_g),
    11131113            *reinterpret_cast<const LengthMap*>(Base::_length));
    11141114      if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     
    11331133      DefPredMapBase(const TR &b) : TR(b) {}
    11341134    };
    1135    
     1135
    11361136    ///\brief \ref named-templ-param "Named parameter"
    11371137    ///function for setting PredMap type
     
    11411141    ///
    11421142    template<class T>
    1143     DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 
     1143    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
    11441144    {
    11451145      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    11461146      return DijkstraWizard<DefPredMapBase<T> >(*this);
    11471147    }
    1148    
     1148
    11491149    template<class T>
    11501150    struct DefDistMapBase : public Base {
     
    11531153      DefDistMapBase(const TR &b) : TR(b) {}
    11541154    };
    1155    
     1155
    11561156    ///\brief \ref named-templ-param "Named parameter"
    11571157    ///function for setting DistMap type
     
    11611161    ///
    11621162    template<class T>
    1163     DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 
     1163    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
    11641164    {
    11651165      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    11661166      return DijkstraWizard<DefDistMapBase<T> >(*this);
    11671167    }
    1168    
     1168
    11691169    /// Sets the source node, from which the Dijkstra algorithm runs.
    11701170
    11711171    /// Sets the source node, from which the Dijkstra algorithm runs.
    11721172    /// \param s is the source node.
    1173     DijkstraWizard<TR> &source(Node s) 
     1173    DijkstraWizard<TR> &source(Node s)
    11741174    {
    11751175      Base::_source=s;
    11761176      return *this;
    11771177    }
    1178    
     1178
    11791179  };
    1180  
     1180
    11811181  ///Function type interface for Dijkstra algorithm.
    11821182
Note: See TracChangeset for help on using the changeset viewer.