COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 244:c30731a37f91 in lemon-1.0 for lemon/dijkstra.h


Ignore:
Timestamp:
08/03/08 13:34:57 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Many improvements in bfs.h, dfs.h and dijkstra.h

  • Add run() function to Bfs and run(s,t) function to DfsVisit?.
  • Add debug checking to addSource() function of Dfs and DfsVisit?.
  • Add a few missing named parameters (according to \todo notes).
  • Small fixes in the code (e.g. missing derivations).
  • Many doc improvements.
  • Remove \todo and \warning comments which are no longer valid.
  • Remove \author commands (see ticket #39).
  • Fixes in the the doc (e.g. wrong references).
  • Hide the doc of most of the private and protected members.
  • Use public typedefs instead of template parameters in public functions.
  • Use better parameter names for some functions.
  • Other small changes to make the doc more uniform.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/dijkstra.h

    r210 r244  
    3434namespace lemon {
    3535
    36   /// \brief Default OperationTraits for the Dijkstra algorithm class.
     36  /// \brief Default operation traits for the Dijkstra algorithm class.
    3737  ///
    38   /// It defines all computational operations and constants which are
    39   /// used in the Dijkstra algorithm.
     38  /// This operation traits class defines all computational operations and
     39  /// constants which are used in the Dijkstra algorithm.
    4040  template <typename Value>
    4141  struct DijkstraDefaultOperationTraits {
    … …  
    4848      return left + right;
    4949    }
    50     /// \brief Gives back true only if the first value less than the second.
     50    /// \brief Gives back true only if the first value is less than the second.
    5151    static bool less(const Value& left, const Value& right) {
    5252      return left < right;
    … …  
    5454  };
    5555
    56   /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
     56  /// \brief Widest path operation traits for the Dijkstra algorithm class.
    5757  ///
    58   /// It defines all computational operations and constants which are
    59   /// used in the Dijkstra algorithm for widest path computation.
     58  /// This operation traits class defines all computational operations and
     59  /// constants which are used in the Dijkstra algorithm for widest path
     60  /// computation.
     61  ///
     62  /// \see DijkstraDefaultOperationTraits
    6063  template <typename Value>
    6164  struct DijkstraWidestPathOperationTraits {
    … …  
    6871      return std::min(left, right);
    6972    }
    70     /// \brief Gives back true only if the first value less than the second.
     73    /// \brief Gives back true only if the first value is less than the second.
    7174    static bool less(const Value& left, const Value& right) {
    7275      return left < right;
    … …  
    7780
    7881  ///Default traits class of Dijkstra class.
    79   ///\tparam GR Digraph type.
    80   ///\tparam LM Type of length map.
     82  ///\tparam GR The type of the digraph.
     83  ///\tparam LM The type of the length map.
    8184  template<class GR, class LM>
    8285  struct DijkstraDefaultTraits
    8386  {
    84     ///The digraph type the algorithm runs on.
     87    ///The type of the digraph the algorithm runs on.
    8588    typedef GR Digraph;
     89
    8690    ///The type of the map that stores the arc lengths.
    8791
    … …  
    8993    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    9094    typedef LM LengthMap;
    91     //The type of the length of the arcs.
     95    ///The type of the length of the arcs.
    9296    typedef typename LM::Value Value;
     97
    9398    /// Operation traits for Dijkstra algorithm.
    9499
    95     /// It defines the used operation by the algorithm.
     100    /// This class defines the operations that are used in the algorithm.
    96101    /// \see DijkstraDefaultOperationTraits
    97102    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    98     /// The cross reference type used by heap.
    99 
    100 
    101     /// The cross reference type used by heap.
     103
     104    /// The cross reference type used by the heap.
     105
     106    /// The cross reference type used by the heap.
    102107    /// Usually it is \c Digraph::NodeMap<int>.
    103108    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    104     ///Instantiates a HeapCrossRef.
    105 
    106     ///This function instantiates a \c HeapCrossRef.
    107     /// \param G is the digraph, to which we would like to define the
    108     /// HeapCrossRef.
    109     static HeapCrossRef *createHeapCrossRef(const GR &G)
    110     {
    111       return new HeapCrossRef(G);
    112     }
    113 
    114     ///The heap type used by Dijkstra algorithm.
    115 
    116     ///The heap type used by Dijkstra algorithm.
     109    ///Instantiates a \ref HeapCrossRef.
     110
     111    ///This function instantiates a \ref HeapCrossRef.
     112    /// \param g is the digraph, to which we would like to define the
     113    /// \ref HeapCrossRef.
     114    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
     115    {
     116      return new HeapCrossRef(g);
     117    }
     118
     119    ///The heap type used by the Dijkstra algorithm.
     120
     121    ///The heap type used by the Dijkstra algorithm.
    117122    ///
    118123    ///\sa BinHeap
    119124    ///\sa Dijkstra
    120125    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    121 
    122     static Heap *createHeap(HeapCrossRef& R)
    123     {
    124       return new Heap(R);
    125     }
    126 
    127     ///\brief The type of the map that stores the last
     126    ///Instantiates a \ref Heap.
     127
     128    ///This function instantiates a \ref Heap.
     129    static Heap *createHeap(HeapCrossRef& r)
     130    {
     131      return new Heap(r);
     132    }
     133
     134    ///\brief The type of the map that stores the predecessor
    128135    ///arcs of the shortest paths.
    129136    ///
    130     ///The type of the map that stores the last
     137    ///The type of the map that stores the predecessor
    131138    ///arcs of the shortest paths.
    132139    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    133     ///
    134     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    135     ///Instantiates a PredMap.
    136 
    137     ///This function instantiates a \c PredMap.
    138     ///\param G is the digraph, to which we would like to define the PredMap.
     140    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     141    ///Instantiates a \ref PredMap.
     142
     143    ///This function instantiates a \ref PredMap.
     144    ///\param g is the digraph, to which we would like to define the
     145    ///\ref PredMap.
    139146    ///\todo The digraph alone may be insufficient for the initialization
    140     static PredMap *createPredMap(const GR &G)
    141     {
    142       return new PredMap(G);
    143     }
    144 
    145     ///The type of the map that stores whether a nodes is processed.
    146 
    147     ///The type of the map that stores whether a nodes is processed.
     147    static PredMap *createPredMap(const Digraph &g)
     148    {
     149      return new PredMap(g);
     150    }
     151
     152    ///The type of the map that indicates which nodes are processed.
     153
     154    ///The type of the map that indicates which nodes are processed.
    148155    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    149156    ///By default it is a NullMap.
    150157    ///\todo If it is set to a real map,
    151158    ///Dijkstra::processed() should read this.
    152     ///\todo named parameter to set this type, function to read and write.
    153159    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    154     ///Instantiates a ProcessedMap.
    155 
    156     ///This function instantiates a \c ProcessedMap.
     160    ///Instantiates a \ref ProcessedMap.
     161
     162    ///This function instantiates a \ref ProcessedMap.
    157163    ///\param g is the digraph, to which
    158     ///we would like to define the \c ProcessedMap
     164    ///we would like to define the \ref ProcessedMap
    159165#ifdef DOXYGEN
    160     static ProcessedMap *createProcessedMap(const GR &g)
     166    static ProcessedMap *createProcessedMap(const Digraph &g)
    161167#else
    162     static ProcessedMap *createProcessedMap(const GR &)
     168    static ProcessedMap *createProcessedMap(const Digraph &)
    163169#endif
    164170    {
    165171      return new ProcessedMap();
    166172    }
    167     ///The type of the map that stores the dists of the nodes.
    168 
    169     ///The type of the map that stores the dists of the nodes.
     173
     174    ///The type of the map that stores the distances of the nodes.
     175
     176    ///The type of the map that stores the distances of the nodes.
    170177    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    171     ///
    172178    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    173     ///Instantiates a DistMap.
     179    ///Instantiates a \ref DistMap.
    174180
    175181    ///This function instantiates a \ref DistMap.
    176     ///\param G is the digraph, to which we would like to define
     182    ///\param g is the digraph, to which we would like to define
    177183    ///the \ref DistMap
    178     static DistMap *createDistMap(const GR &G)
    179     {
    180       return new DistMap(G);
     184    static DistMap *createDistMap(const Digraph &g)
     185    {
     186      return new DistMap(g);
    181187    }
    182188  };
    … …  
    185191
    186192  /// \ingroup shortest_path
    187   ///This class provides an efficient implementation of %Dijkstra algorithm.
     193  ///This class provides an efficient implementation of the %Dijkstra algorithm.
     194  ///
    188195  ///The arc lengths are passed to the algorithm using a
    189196  ///\ref concepts::ReadMap "ReadMap",
    190197  ///so it is easy to change it to any kind of length.
    191   ///
    192198  ///The type of the length is determined by the
    193199  ///\ref concepts::ReadMap::Value "Value" of the length map.
    194   ///
    195200  ///It is also possible to change the underlying priority heap.
    196201  ///
    197   ///\tparam GR The digraph type the algorithm runs on. The default value
    198   ///is \ref ListDigraph. The value of GR is not used directly by
    199   ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
    200   ///\tparam LM This read-only ArcMap determines the lengths of the
     202  ///There is also a \ref dijkstra() "function type interface" for the
     203  ///%Dijkstra algorithm, which is convenient in the simplier cases and
     204  ///it can be used easier.
     205  ///
     206  ///\tparam GR The type of the digraph the algorithm runs on.
     207  ///The default value is \ref ListDigraph.
     208  ///The value of GR is not used directly by \ref Dijkstra, it is only
     209  ///passed to \ref DijkstraDefaultTraits.
     210  ///\tparam LM A readable arc map that determines the lengths of the
    201211  ///arcs. It is read once for each arc, so the map may involve in
    202   ///relatively time consuming process to compute the arc length if
     212  ///relatively time consuming process to compute the arc lengths if
    203213  ///it is necessary. The default map type is \ref
    204   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
    205   ///of LM is not used directly by Dijkstra, it is only passed to \ref
    206   ///DijkstraDefaultTraits.
    207   ///\tparam TR Traits class to set
    208   ///various data types used by the algorithm.  The default traits
    209   ///class is \ref DijkstraDefaultTraits
    210   ///"DijkstraDefaultTraits<GR,LM>".  See \ref
    211   ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
    212   ///class.
    213 
     214  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     215  ///The value of LM is not used directly by \ref Dijkstra, it is only
     216  ///passed to \ref DijkstraDefaultTraits.
     217  ///\tparam TR Traits class to set various data types used by the algorithm.
     218  ///The default traits class is \ref DijkstraDefaultTraits
     219  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
     220  ///for the documentation of a Dijkstra traits class.
    214221#ifdef DOXYGEN
    215222  template <typename GR, typename LM, typename TR>
    … …  
    221228  class Dijkstra {
    222229  public:
    223     /**
    224      * \brief \ref Exception for uninitialized parameters.
    225      *
    226      * This error represents problems in the initialization
    227      * of the parameters of the algorithms.
    228      */
     230    ///\ref Exception for uninitialized parameters.
     231
     232    ///This error represents problems in the initialization of the
     233    ///parameters of the algorithm.
    229234    class UninitializedParameter : public lemon::UninitializedParameter {
    230235    public:
    … …  
    234239    };
    235240
    236     typedef TR Traits;
    237     ///The type of the underlying digraph.
     241    ///The type of the digraph the algorithm runs on.
    238242    typedef typename TR::Digraph Digraph;
    239     ///\e
    240     typedef typename Digraph::Node Node;
    241     ///\e
    242     typedef typename Digraph::NodeIt NodeIt;
    243     ///\e
    244     typedef typename Digraph::Arc Arc;
    245     ///\e
    246     typedef typename Digraph::OutArcIt OutArcIt;
    247243
    248244    ///The type of the length of the arcs.
    … …  
    250246    ///The type of the map that stores the arc lengths.
    251247    typedef typename TR::LengthMap LengthMap;
    252     ///\brief The type of the map that stores the last
    253     ///arcs of the shortest paths.
     248    ///\brief The type of the map that stores the predecessor arcs of the
     249    ///shortest paths.
    254250    typedef typename TR::PredMap PredMap;
    255     ///The type of the map indicating if a node is processed.
     251    ///The type of the map that stores the distances of the nodes.
     252    typedef typename TR::DistMap DistMap;
     253    ///The type of the map that indicates which nodes are processed.
    256254    typedef typename TR::ProcessedMap ProcessedMap;
    257     ///The type of the map that stores the dists of the nodes.
    258     typedef typename TR::DistMap DistMap;
     255    ///The type of the paths.
     256    typedef PredMapPath<Digraph, PredMap> Path;
    259257    ///The cross reference type used for the current heap.
    260258    typedef typename TR::HeapCrossRef HeapCrossRef;
    261     ///The heap type used by the dijkstra algorithm.
     259    ///The heap type used by the algorithm.
    262260    typedef typename TR::Heap Heap;
    263     ///The operation traits.
     261    ///The operation traits class.
    264262    typedef typename TR::OperationTraits OperationTraits;
     263
     264    ///The traits class.
     265    typedef TR Traits;
     266
    265267  private:
    266     /// Pointer to the underlying digraph.
     268
     269    typedef typename Digraph::Node Node;
     270    typedef typename Digraph::NodeIt NodeIt;
     271    typedef typename Digraph::Arc Arc;
     272    typedef typename Digraph::OutArcIt OutArcIt;
     273
     274    //Pointer to the underlying digraph.
    267275    const Digraph *G;
    268     /// Pointer to the length map
     276    //Pointer to the length map.
    269277    const LengthMap *length;
    270     ///Pointer to the map of predecessors arcs.
     278    //Pointer to the map of predecessors arcs.
    271279    PredMap *_pred;
    272     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     280    //Indicates if _pred is locally allocated (true) or not.
    273281    bool local_pred;
    274     ///Pointer to the map of distances.
     282    //Pointer to the map of distances.
    275283    DistMap *_dist;
    276     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     284    //Indicates if _dist is locally allocated (true) or not.
    277285    bool local_dist;
    278     ///Pointer to the map of processed status of the nodes.
     286    //Pointer to the map of processed status of the nodes.
    279287    ProcessedMap *_processed;
    280     ///Indicates if \ref _processed is locally allocated (\c true) or not.
     288    //Indicates if _processed is locally allocated (true) or not.
    281289    bool local_processed;
    282     ///Pointer to the heap cross references.
     290    //Pointer to the heap cross references.
    283291    HeapCrossRef *_heap_cross_ref;
    284     ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
     292    //Indicates if _heap_cross_ref is locally allocated (true) or not.
    285293    bool local_heap_cross_ref;
    286     ///Pointer to the heap.
     294    //Pointer to the heap.
    287295    Heap *_heap;
    288     ///Indicates if \ref _heap is locally allocated (\c true) or not.
     296    //Indicates if _heap is locally allocated (true) or not.
    289297    bool local_heap;
    290298
    291299    ///Creates the maps if necessary.
    292 
    293300    ///\todo Better memory allocation (instead of new).
    294301    void create_maps()
    … …  
    316323    }
    317324
    318   public :
     325  public:
    319326
    320327    typedef Dijkstra Create;
    … …  
    332339      }
    333340    };
    334     ///\ref named-templ-param "Named parameter" for setting PredMap type
    335 
    336     ///\ref named-templ-param "Named parameter" for setting PredMap type
    337     ///
     341    ///\brief \ref named-templ-param "Named parameter" for setting
     342    ///\ref PredMap type.
     343    ///
     344    ///\ref named-templ-param "Named parameter" for setting
     345    ///\ref PredMap type.
    338346    template <class T>
    339347    struct DefPredMap
    … …  
    350358      }
    351359    };
    352     ///\ref named-templ-param "Named parameter" for setting DistMap type
    353 
    354     ///\ref named-templ-param "Named parameter" for setting DistMap type
    355     ///
     360    ///\brief \ref named-templ-param "Named parameter" for setting
     361    ///\ref DistMap type.
     362    ///
     363    ///\ref named-templ-param "Named parameter" for setting
     364    ///\ref DistMap type.
    356365    template <class T>
    357366    struct DefDistMap
    … …  
    363372    struct DefProcessedMapTraits : public Traits {
    364373      typedef T ProcessedMap;
    365       static ProcessedMap *createProcessedMap(const Digraph &G)
     374      static ProcessedMap *createProcessedMap(const Digraph &)
    366375      {
    367376        throw UninitializedParameter();
    368377      }
    369378    };
    370     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    371 
    372     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    373     ///
     379    ///\brief \ref named-templ-param "Named parameter" for setting
     380    ///\ref ProcessedMap type.
     381    ///
     382    ///\ref named-templ-param "Named parameter" for setting
     383    ///\ref ProcessedMap type.
    374384    template <class T>
    375385    struct DefProcessedMap
    … …  
    380390    struct DefDigraphProcessedMapTraits : public Traits {
    381391      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    382       static ProcessedMap *createProcessedMap(const Digraph &G)
     392      static ProcessedMap *createProcessedMap(const Digraph &g)
    383393      {
    384         return new ProcessedMap(G);
    385       }
    386     };
    387     ///\brief \ref named-templ-param "Named parameter"
    388     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    389     ///
    390     ///\ref named-templ-param "Named parameter"
    391     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
    392     ///If you don't set it explicitely, it will be automatically allocated.
     394        return new ProcessedMap(g);
     395      }
     396    };
     397    ///\brief \ref named-templ-param "Named parameter" for setting
     398    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     399    ///
     400    ///\ref named-templ-param "Named parameter" for setting
     401    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     402    ///If you don't set it explicitly, it will be automatically allocated.
    393403    template <class T>
    394404    struct DefProcessedMapToBeDefaultMap
    … …  
    414424    ///
    415425    ///\ref named-templ-param "Named parameter" for setting heap and cross
    416     ///reference type
    417     ///
     426    ///reference type.
    418427    template <class H, class CR = typename Digraph::template NodeMap<int> >
    419428    struct DefHeap
    … …  
    454463
    455464    /// \brief \ref named-templ-param "Named parameter" for setting
    456     /// OperationTraits type
    457     ///
    458     /// \ref named-templ-param "Named parameter" for setting OperationTraits
    459     /// type
     465    ///\ref OperationTraits type
     466    ///
     467    ///\ref named-templ-param "Named parameter" for setting
     468    ///\ref OperationTraits type.
    460469    template <class T>
    461470    struct DefOperationTraits
    … …  
    467476    ///@}
    468477
    469 
    470478  protected:
    471479
    … …  
    476484    ///Constructor.
    477485
    478     ///\param _G the digraph the algorithm will run on.
    479     ///\param _length the length map used by the algorithm.
    480     Dijkstra(const Digraph& _G, const LengthMap& _length) :
    481       G(&_G), length(&_length),
     486    ///Constructor.
     487    ///\param _g The digraph the algorithm runs on.
     488    ///\param _length The length map used by the algorithm.
     489    Dijkstra(const Digraph& _g, const LengthMap& _length) :
     490      G(&_g), length(&_length),
    482491      _pred(NULL), local_pred(false),
    483492      _dist(NULL), local_dist(false),
    … …  
    507516    }
    508517
    509     ///Sets the map storing the predecessor arcs.
    510 
    511     ///Sets the map storing the predecessor arcs.
     518    ///Sets the map that stores the predecessor arcs.
     519
     520    ///Sets the map that stores the predecessor arcs.
    512521    ///If you don't use this function before calling \ref run(),
    513     ///it will allocate one. The destuctor deallocates this
     522    ///it will allocate one. The destructor deallocates this
    514523    ///automatically allocated map, of course.
    515524    ///\return <tt> (*this) </tt>
    … …  
    524533    }
    525534
    526     ///Sets the map storing the distances calculated by the algorithm.
    527 
    528     ///Sets the map storing the distances calculated by the algorithm.
     535    ///Sets the map that indicates which nodes are processed.
     536
     537    ///Sets the map that indicates which nodes are processed.
    529538    ///If you don't use this function before calling \ref run(),
    530     ///it will allocate one. The destuctor deallocates this
     539    ///it will allocate one. The destructor deallocates this
     540    ///automatically allocated map, of course.
     541    ///\return <tt> (*this) </tt>
     542    Dijkstra &processedMap(ProcessedMap &m)
     543    {
     544      if(local_processed) {
     545        delete _processed;
     546        local_processed=false;
     547      }
     548      _processed = &m;
     549      return *this;
     550    }
     551
     552    ///Sets the map that stores the distances of the nodes.
     553
     554    ///Sets the map that stores the distances of the nodes calculated by the
     555    ///algorithm.
     556    ///If you don't use this function before calling \ref run(),
     557    ///it will allocate one. The destructor deallocates this
    531558    ///automatically allocated map, of course.
    532559    ///\return <tt> (*this) </tt>
    … …  
    545572    ///Sets the heap and the cross reference used by algorithm.
    546573    ///If you don't use this function before calling \ref run(),
    547     ///it will allocate one. The destuctor deallocates this
     574    ///it will allocate one. The destructor deallocates this
    548575    ///automatically allocated heap and cross reference, of course.
    549576    ///\return <tt> (*this) </tt>
    … …  
    564591
    565592  private:
     593
    566594    void finalizeNodeData(Node v,Value dst)
    567595    {
    … …  
    572600  public:
    573601
    574     typedef PredMapPath<Digraph, PredMap> Path;
    575 
    576602    ///\name Execution control
    577     ///The simplest way to execute the algorithm is to use
    578     ///one of the member functions called \c run(...).
     603    ///The simplest way to execute the algorithm is to use one of the
     604    ///member functions called \ref lemon::Dijkstra::run() "run()".
    579605    ///\n
    580     ///If you need more control on the execution,
    581     ///first you must call \ref init(), then you can add several source nodes
    582     ///with \ref addSource().
    583     ///Finally \ref start() will perform the actual path
    584     ///computation.
     606    ///If you need more control on the execution, first you must call
     607    ///\ref lemon::Dijkstra::init() "init()", then you can add several
     608    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
     609    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
     610    ///actual path computation.
    585611
    586612    ///@{
    … …  
    604630
    605631    ///Adds a new source node to the priority heap.
    606     ///
    607632    ///The optional second parameter is the initial distance of the node.
    608633    ///
    609     ///It checks if the node has already been added to the heap and
     634    ///The function checks if the node has already been added to the heap and
    610635    ///it is pushed to the heap only if either it was not in the heap
    611636    ///or the shortest path found till then is shorter than \c dst.
    … …  
    626651    ///\return The processed node.
    627652    ///
    628     ///\warning The priority heap must not be empty!
     653    ///\warning The priority heap must not be empty.
    629654    Node processNextNode()
    630655    {
    … …  
    657682    }
    658683
    659     ///Next node to be processed.
    660 
    661     ///Next node to be processed.
    662     ///
    663     ///\return The next node to be processed or INVALID if the priority heap
    664     /// is empty.
    665     Node nextNode()
     684    ///The next node to be processed.
     685
     686    ///Returns the next node to be processed or \c INVALID if the
     687    ///priority heap is empty.
     688    Node nextNode() const
    666689    {
    667690      return !_heap->empty()?_heap->top():INVALID;
    … …  
    669692
    670693    ///\brief Returns \c false if there are nodes
    671     ///to be processed in the priority heap
     694    ///to be processed.
    672695    ///
    673696    ///Returns \c false if there are nodes
    674     ///to be processed in the priority heap
    675     bool emptyQueue() { return _heap->empty(); }
     697    ///to be processed in the priority heap.
     698    bool emptyQueue() const { return _heap->empty(); }
     699
    676700    ///Returns the number of the nodes to be processed in the priority heap
    677701
    678     ///Returns the number of the nodes to be processed in the priority heap
    679     ///
    680     int queueSize() { return _heap->size(); }
     702    ///Returns the number of the nodes to be processed in the priority heap.
     703    ///
     704    int queueSize() const { return _heap->size(); }
    681705
    682706    ///Executes the algorithm.
    … …  
    684708    ///Executes the algorithm.
    685709    ///
    686     ///\pre init() must be called and at least one node should be added
    687     ///with addSource() before using this function.
    688     ///
    689710    ///This method runs the %Dijkstra algorithm from the root node(s)
    690     ///in order to
    691     ///compute the
    692     ///shortest path to each node. The algorithm computes
    693     ///- The shortest path tree.
    694     ///- The distance of each node from the root(s).
    695     ///
     711    ///in order to compute the shortest path to each node.
     712    ///
     713    ///The algorithm computes
     714    ///- the shortest path tree (forest),
     715    ///- the distance of each node from the root(s).
     716    ///
     717    ///\pre init() must be called and at least one root node should be
     718    ///added with addSource() before using this function.
     719    ///
     720    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
     721    ///\code
     722    ///  while ( !d.emptyQueue() ) {
     723    ///    d.processNextNode();
     724    ///  }
     725    ///\endcode
    696726    void start()
    697727    {
    698       while ( !_heap->empty() ) processNextNode();
    699     }
    700 
    701     ///Executes the algorithm until \c dest is reached.
    702 
    703     ///Executes the algorithm until \c dest is reached.
    704     ///
    705     ///\pre init() must be called and at least one node should be added
    706     ///with addSource() before using this function.
     728      while ( !emptyQueue() ) processNextNode();
     729    }
     730
     731    ///Executes the algorithm until the given target node is reached.
     732
     733    ///Executes the algorithm until the given target node is reached.
    707734    ///
    708735    ///This method runs the %Dijkstra algorithm from the root node(s)
    709     ///in order to
    710     ///compute the
    711     ///shortest path to \c dest. The algorithm computes
    712     ///- The shortest path to \c  dest.
    713     ///- The distance of \c dest from the root(s).
    714     ///
     736    ///in order to compute the shortest path to \c dest.
     737    ///
     738    ///The algorithm computes
     739    ///- the shortest path to \c dest,
     740    ///- the distance of \c dest from the root(s).
     741    ///
     742    ///\pre init() must be called and at least one root node should be
     743    ///added with addSource() before using this function.
    715744    void start(Node dest)
    716745    {
    … …  
    723752    ///Executes the algorithm until a condition is met.
    724753    ///
    725     ///\pre init() must be called and at least one node should be added
    726     ///with addSource() before using this function.
    727     ///
    728     ///\param nm must be a bool (or convertible) node map. The algorithm
     754    ///This method runs the %Dijkstra algorithm from the root node(s) in
     755    ///order to compute the shortest path to a node \c v with
     756    /// <tt>nm[v]</tt> true, if such a node can be found.
     757    ///
     758    ///\param nm A \c bool (or convertible) node map. The algorithm
    729759    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
    730760    ///
    731761    ///\return The reached node \c v with <tt>nm[v]</tt> true or
    732762    ///\c INVALID if no such node was found.
     763    ///
     764    ///\pre init() must be called and at least one root node should be
     765    ///added with addSource() before using this function.
    733766    template<class NodeBoolMap>
    734767    Node start(const NodeBoolMap &nm)
    … …  
    740773    }
    741774
    742     ///Runs %Dijkstra algorithm from node \c s.
    743 
    744     ///This method runs the %Dijkstra algorithm from a root node \c s
    745     ///in order to
    746     ///compute the
    747     ///shortest path to each node. The algorithm computes
    748     ///- The shortest path tree.
    749     ///- The distance of each node from the root.
    750     ///
    751     ///\note d.run(s) is just a shortcut of the following code.
     775    ///Runs the algorithm from the given node.
     776
     777    ///This method runs the %Dijkstra algorithm from node \c s
     778    ///in order to compute the shortest path to each node.
     779    ///
     780    ///The algorithm computes
     781    ///- the shortest path tree,
     782    ///- the distance of each node from the root.
     783    ///
     784    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
    752785    ///\code
    753786    ///  d.init();
    … …  
    763796    ///Finds the shortest path between \c s and \c t.
    764797
    765     ///Finds the shortest path between \c s and \c t.
    766     ///
    767     ///\return The length of the shortest s---t path if there exists one,
    768     ///0 otherwise.
    769     ///\note Apart from the return value, d.run(s) is
    770     ///just a shortcut of the following code.
     798    ///This method runs the %Dijkstra algorithm from node \c s
     799    ///in order to compute the shortest path to \c t.
     800    ///
     801    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
     802    ///if \c t is reachable form \c s, \c 0 otherwise.
     803    ///
     804    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
     805    ///shortcut of the following code.
    771806    ///\code
    772807    ///  d.init();
    … …  
    786821    ///The result of the %Dijkstra algorithm can be obtained using these
    787822    ///functions.\n
    788     ///Before the use of these functions,
    789     ///either run() or start() must be called.
     823    ///Either \ref lemon::Dijkstra::run() "run()" or
     824    ///\ref lemon::Dijkstra::start() "start()" must be called before
     825    ///using them.
    790826
    791827    ///@{
    792828
    793     ///Gives back the shortest path.
    794 
    795     ///Gives back the shortest path.
    796     ///\pre The \c t should be reachable from the source.
    797     Path path(Node t)
    798     {
    799       return Path(*G, *_pred, t);
    800     }
    801 
    802     ///The distance of a node from the root.
    803 
    804     ///Returns the distance of a node from the root.
    805     ///\pre \ref run() must be called before using this function.
    806     ///\warning If node \c v in unreachable from the root the return value
    807     ///of this funcion is undefined.
     829    ///The shortest path to a node.
     830
     831    ///Returns the shortest path to a node.
     832    ///
     833    ///\warning \c t should be reachable from the root(s).
     834    ///
     835    ///\pre Either \ref run() or \ref start() must be called before
     836    ///using this function.
     837    Path path(Node t) const { return Path(*G, *_pred, t); }
     838
     839    ///The distance of a node from the root(s).
     840
     841    ///Returns the distance of a node from the root(s).
     842    ///
     843    ///\warning If node \c v is not reachable from the root(s), then
     844    ///the return value of this function is undefined.
     845    ///
     846    ///\pre Either \ref run() or \ref start() must be called before
     847    ///using this function.
    808848    Value dist(Node v) const { return (*_dist)[v]; }
    809849
    810     ///The current distance of a node from the root.
    811 
    812     ///Returns the current distance of a node from the root.
    813     ///It may be decreased in the following processes.
    814     ///\pre \c node should be reached but not processed
    815     Value currentDist(Node v) const { return (*_heap)[v]; }
    816 
    817     ///Returns the 'previous arc' of the shortest path tree.
    818 
    819     ///For a node \c v it returns the 'previous arc' of the shortest path tree,
    820     ///i.e. it returns the last arc of a shortest path from the root to \c
    821     ///v. It is \ref INVALID
    822     ///if \c v is unreachable from the root or if \c v=s. The
    823     ///shortest path tree used here is equal to the shortest path tree used in
    824     ///\ref predNode().  \pre \ref run() must be called before using
    825     ///this function.
     850    ///Returns the 'previous arc' of the shortest path tree for a node.
     851
     852    ///This function returns the 'previous arc' of the shortest path
     853    ///tree for the node \c v, i.e. it returns the last arc of a
     854    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     855    ///is not reachable from the root(s) or if \c v is a root.
     856    ///
     857    ///The shortest path tree used here is equal to the shortest path
     858    ///tree used in \ref predNode().
     859    ///
     860    ///\pre Either \ref run() or \ref start() must be called before
     861    ///using this function.
    826862    Arc predArc(Node v) const { return (*_pred)[v]; }
    827863
    828     ///Returns the 'previous node' of the shortest path tree.
    829 
    830     ///For a node \c v it returns the 'previous node' of the shortest path tree,
    831     ///i.e. it returns the last but one node from a shortest path from the
    832     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    833     ///\c v=s. The shortest path tree used here is equal to the shortest path
    834     ///tree used in \ref predArc().  \pre \ref run() must be called before
     864    ///Returns the 'previous node' of the shortest path tree for a node.
     865
     866    ///This function returns the 'previous node' of the shortest path
     867    ///tree for the node \c v, i.e. it returns the last but one node
     868    ///from a shortest path from the root(s) to \c v. It is \c INVALID
     869    ///if \c v is not reachable from the root(s) or if \c v is a root.
     870    ///
     871    ///The shortest path tree used here is equal to the shortest path
     872    ///tree used in \ref predArc().
     873    ///
     874    ///\pre Either \ref run() or \ref start() must be called before
    835875    ///using this function.
    836876    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    837877                                  G->source((*_pred)[v]); }
    838878
    839     ///Returns a reference to the NodeMap of distances.
    840 
    841     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    842     ///be called before using this function.
     879    ///\brief Returns a const reference to the node map that stores the
     880    ///distances of the nodes.
     881    ///
     882    ///Returns a const reference to the node map that stores the distances
     883    ///of the nodes calculated by the algorithm.
     884    ///
     885    ///\pre Either \ref run() or \ref init()
     886    ///must be called before using this function.
    843887    const DistMap &distMap() const { return *_dist;}
    844888
    845     ///Returns a reference to the shortest path tree map.
    846 
    847     ///Returns a reference to the NodeMap of the arcs of the
    848     ///shortest path tree.
    849     ///\pre \ref run() must be called before using this function.
     889    ///\brief Returns a const reference to the node map that stores the
     890    ///predecessor arcs.
     891    ///
     892    ///Returns a const reference to the node map that stores the predecessor
     893    ///arcs, which form the shortest path tree.
     894    ///
     895    ///\pre Either \ref run() or \ref init()
     896    ///must be called before using this function.
    850897    const PredMap &predMap() const { return *_pred;}
    851898
    852     ///Checks if a node is reachable from the root.
    853 
    854     ///Returns \c true if \c v is reachable from the root.
    855     ///\warning The source nodes are inditated as unreached.
    856     ///\pre \ref run() must be called before using this function.
    857     ///
    858     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
     899    ///Checks if a node is reachable from the root(s).
     900
     901    ///Returns \c true if \c v is reachable from the root(s).
     902    ///\pre Either \ref run() or \ref start()
     903    ///must be called before using this function.
     904    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     905                                        Heap::PRE_HEAP; }
    859906
    860907    ///Checks if a node is processed.
    … …  
    862909    ///Returns \c true if \c v is processed, i.e. the shortest
    863910    ///path to \c v has already found.
    864     ///\pre \ref run() must be called before using this function.
    865     ///
    866     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
     911    ///\pre Either \ref run() or \ref start()
     912    ///must be called before using this function.
     913    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     914                                          Heap::POST_HEAP; }
     915
     916    ///The current distance of a node from the root(s).
     917
     918    ///Returns the current distance of a node from the root(s).
     919    ///It may be decreased in the following processes.
     920    ///\pre \c v should be reached but not processed.
     921    Value currentDist(Node v) const { return (*_heap)[v]; }
    867922
    868923    ///@}
    … …  
    870925
    871926
    872 
    873 
    874 
    875   ///Default traits class of Dijkstra function.
    876 
    877   ///Default traits class of Dijkstra function.
    878   ///\tparam GR Digraph type.
    879   ///\tparam LM Type of length map.
     927  ///Default traits class of dijkstra() function.
     928
     929  ///Default traits class of dijkstra() function.
     930  ///\tparam GR The type of the digraph.
     931  ///\tparam LM The type of the length map.
    880932  template<class GR, class LM>
    881933  struct DijkstraWizardDefaultTraits
    882934  {
    883     ///The digraph type the algorithm runs on.
     935    ///The type of the digraph the algorithm runs on.
    884936    typedef GR Digraph;
    885937    ///The type of the map that stores the arc lengths.
    … …  
    888940    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    889941    typedef LM LengthMap;
    890     //The type of the length of the arcs.
     942    ///The type of the length of the arcs.
    891943    typedef typename LM::Value Value;
     944
    892945    /// Operation traits for Dijkstra algorithm.
    893946
    894     /// It defines the used operation by the algorithm.
     947    /// This class defines the operations that are used in the algorithm.
    895948    /// \see DijkstraDefaultOperationTraits
    896949    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    897     ///The heap type used by Dijkstra algorithm.
    898 
    899     /// The cross reference type used by heap.
    900 
    901     /// The cross reference type used by heap.
     950
     951    /// The cross reference type used by the heap.
     952
     953    /// The cross reference type used by the heap.
    902954    /// Usually it is \c Digraph::NodeMap<int>.
    903955    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    904     ///Instantiates a HeapCrossRef.
     956    ///Instantiates a \ref HeapCrossRef.
    905957
    906958    ///This function instantiates a \ref HeapCrossRef.
    907     /// \param G is the digraph, to which we would like to define the
     959    /// \param g is the digraph, to which we would like to define the
    908960    /// HeapCrossRef.
    909961    /// \todo The digraph alone may be insufficient for the initialization
    910     static HeapCrossRef *createHeapCrossRef(const GR &G)
    911     {
    912       return new HeapCrossRef(G);
    913     }
    914 
    915     ///The heap type used by Dijkstra algorithm.
    916 
    917     ///The heap type used by Dijkstra algorithm.
     962    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
     963    {
     964      return new HeapCrossRef(g);
     965    }
     966
     967    ///The heap type used by the Dijkstra algorithm.
     968
     969    ///The heap type used by the Dijkstra algorithm.
    918970    ///
    919971    ///\sa BinHeap
    920972    ///\sa Dijkstra
    921     typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
     973    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
    922974                    std::less<Value> > Heap;
    923975
    924     static Heap *createHeap(HeapCrossRef& R)
    925     {
    926       return new Heap(R);
    927     }
    928 
    929     ///\brief The type of the map that stores the last
     976    ///Instantiates a \ref Heap.
     977
     978    ///This function instantiates a \ref Heap.
     979    /// \param r is the HeapCrossRef which is used.
     980    static Heap *createHeap(HeapCrossRef& r)
     981    {
     982      return new Heap(r);
     983    }
     984
     985    ///\brief The type of the map that stores the predecessor
    930986    ///arcs of the shortest paths.
    931987    ///
    932     ///The type of the map that stores the last
     988    ///The type of the map that stores the predecessor
    933989    ///arcs of the shortest paths.
    934990    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    935     ///
    936     typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
    937     ///Instantiates a PredMap.
     991    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
     992    ///Instantiates a \ref PredMap.
    938993
    939994    ///This function instantiates a \ref PredMap.
    940     ///\param g is the digraph, to which we would like to define the PredMap.
    941     ///\todo The digraph alone may be insufficient for the initialization
     995    ///\param g is the digraph, to which we would like to define the
     996    ///\ref PredMap.
     997    ///\todo The digraph alone may be insufficient to initialize
    942998#ifdef DOXYGEN
    943     static PredMap *createPredMap(const GR &g)
     999    static PredMap *createPredMap(const Digraph &g)
    9441000#else
    945     static PredMap *createPredMap(const GR &)
     1001    static PredMap *createPredMap(const Digraph &)
    9461002#endif
    9471003    {
    9481004      return new PredMap();
    9491005    }
    950     ///The type of the map that stores whether a nodes is processed.
    951 
    952     ///The type of the map that stores whether a nodes is processed.
     1006
     1007    ///The type of the map that indicates which nodes are processed.
     1008
     1009    ///The type of the map that indicates which nodes are processed.
    9531010    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    9541011    ///By default it is a NullMap.
    … …  
    9571014    ///\todo named parameter to set this type, function to read and write.
    9581015    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    959     ///Instantiates a ProcessedMap.
     1016    ///Instantiates a \ref ProcessedMap.
    9601017
    9611018    ///This function instantiates a \ref ProcessedMap.
    9621019    ///\param g is the digraph, to which
    963     ///we would like to define the \ref ProcessedMap
     1020    ///we would like to define the \ref ProcessedMap.
    9641021#ifdef DOXYGEN
    965     static ProcessedMap *createProcessedMap(const GR &g)
     1022    static ProcessedMap *createProcessedMap(const Digraph &g)
    9661023#else
    967     static ProcessedMap *createProcessedMap(const GR &)
     1024    static ProcessedMap *createProcessedMap(const Digraph &)
    9681025#endif
    9691026    {
    9701027      return new ProcessedMap();
    9711028    }
    972     ///The type of the map that stores the dists of the nodes.
    973 
    974     ///The type of the map that stores the dists of the nodes.
     1029
     1030    ///The type of the map that stores the distances of the nodes.
     1031
     1032    ///The type of the map that stores the distances of the nodes.
    9751033    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    976     ///
    977     typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
    978     ///Instantiates a DistMap.
     1034    typedef NullMap<typename Digraph::Node,Value> DistMap;
     1035    ///Instantiates a \ref DistMap.
    9791036
    9801037    ///This function instantiates a \ref DistMap.
    … …  
    9821039    ///the \ref DistMap
    9831040#ifdef DOXYGEN
    984     static DistMap *createDistMap(const GR &g)
     1041    static DistMap *createDistMap(const Digraph &g)
    9851042#else
    986     static DistMap *createDistMap(const GR &)
     1043    static DistMap *createDistMap(const Digraph &)
    9871044#endif
    9881045    {
    … …  
    9911048  };
    9921049
    993   /// Default traits used by \ref DijkstraWizard
     1050  /// Default traits class used by \ref DijkstraWizard
    9941051
    9951052  /// To make it easier to use Dijkstra algorithm
    996   ///we have created a wizard class.
     1053  /// we have created a wizard class.
    9971054  /// This \ref DijkstraWizard class needs default traits,
    998   ///as well as the \ref Dijkstra class.
     1055  /// as well as the \ref Dijkstra class.
    9991056  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10001057  /// \ref DijkstraWizard class.
    … …  
    10031060  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
    10041061  {
    1005 
    10061062    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
    10071063  protected:
    1008     /// Type of the nodes in the digraph.
     1064    //The type of the nodes in the digraph.
    10091065    typedef typename Base::Digraph::Node Node;
    10101066
    1011     /// Pointer to the underlying digraph.
     1067    //Pointer to the digraph the algorithm runs on.
    10121068    void *_g;
    1013     /// Pointer to the length map
     1069    //Pointer to the length map
    10141070    void *_length;
    1015     ///Pointer to the map of predecessors arcs.
     1071    //Pointer to the map of predecessors arcs.
    10161072    void *_pred;
    1017     ///Pointer to the map of distances.
     1073    //Pointer to the map of distances.
    10181074    void *_dist;
    1019     ///Pointer to the source node.
     1075    //Pointer to the source node.
    10201076    Node _source;
    10211077
    1022     public:
     1078  public:
    10231079    /// Constructor.
    10241080
    … …  
    10331089    /// listed in the parameters list.
    10341090    /// Others are initiated to 0.
    1035     /// \param g is the initial value of  \ref _g
    1036     /// \param l is the initial value of  \ref _length
    1037     /// \param s is the initial value of  \ref _source
     1091    /// \param g The digraph the algorithm runs on.
     1092    /// \param l The length map.
     1093    /// \param s The source node.
    10381094    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    10391095      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    … …  
    10431099  };
    10441100
    1045   /// A class to make the usage of Dijkstra algorithm easier
    1046 
    1047   /// This class is created to make it easier to use Dijkstra algorithm.
    1048   /// It uses the functions and features of the plain \ref Dijkstra,
    1049   /// but it is much simpler to use it.
     1101  /// Auxiliary class for the function type interface of Dijkstra algorithm.
     1102
     1103  /// This auxiliary class is created to implement the function type
     1104  /// interface of \ref Dijkstra algorithm. It uses the functions and features
     1105  /// of the plain \ref Dijkstra, but it is much simpler to use it.
     1106  /// It should only be used through the \ref dijkstra() function, which makes
     1107  /// it easier to use the algorithm.
    10501108  ///
    10511109  /// Simplicity means that the way to change the types defined
    … …  
    10561114  /// the original class by using the ::
    10571115  /// operator. In the case of \ref DijkstraWizard only
    1058   /// a function have to be called and it will
     1116  /// a function have to be called, and it will
    10591117  /// return the needed class.
    10601118  ///
    1061   /// It does not have own \ref run method. When its \ref run method is called
    1062   /// it initiates a plain \ref Dijkstra class, and calls the \ref
    1063   /// Dijkstra::run method of it.
     1119  /// It does not have own \ref run() method. When its \ref run() method
     1120  /// is called, it initiates a plain \ref Dijkstra object, and calls the
     1121  /// \ref Dijkstra::run() method of it.
    10641122  template<class TR>
    10651123  class DijkstraWizard : public TR
    … …  
    10671125    typedef TR Base;
    10681126
    1069     ///The type of the underlying digraph.
     1127    ///The type of the digraph the algorithm runs on.
    10701128    typedef typename TR::Digraph Digraph;
    1071     //\e
     1129
    10721130    typedef typename Digraph::Node Node;
    1073     //\e
    10741131    typedef typename Digraph::NodeIt NodeIt;
    1075     //\e
    10761132    typedef typename Digraph::Arc Arc;
    1077     //\e
    10781133    typedef typename Digraph::OutArcIt OutArcIt;
    10791134
    … …  
    10821137    ///The type of the length of the arcs.
    10831138    typedef typename LengthMap::Value Value;
    1084     ///\brief The type of the map that stores the last
     1139    ///\brief The type of the map that stores the predecessor
    10851140    ///arcs of the shortest paths.
    10861141    typedef typename TR::PredMap PredMap;
    1087     ///The type of the map that stores the dists of the nodes.
     1142    ///The type of the map that stores the distances of the nodes.
    10881143    typedef typename TR::DistMap DistMap;
     1144    ///The type of the map that indicates which nodes are processed.
     1145    typedef typename TR::ProcessedMap ProcessedMap;
    10891146    ///The heap type used by the dijkstra algorithm.
    10901147    typedef typename TR::Heap Heap;
     1148
    10911149  public:
     1150
    10921151    /// Constructor.
    10931152    DijkstraWizard() : TR() {}
    … …  
    11051164    ~DijkstraWizard() {}
    11061165
    1107     ///Runs Dijkstra algorithm from a given node.
    1108 
    1109     ///Runs Dijkstra algorithm from a given node.
    1110     ///The node can be given by the \ref source function.
     1166    ///Runs Dijkstra algorithm from a source node.
     1167
     1168    ///Runs Dijkstra algorithm from a source node.
     1169    ///The node can be given with the \ref source() function.
    11111170    void run()
    11121171    {
    … …  
    11301189    }
    11311190
     1191    /// Sets the source node, from which the Dijkstra algorithm runs.
     1192
     1193    /// Sets the source node, from which the Dijkstra algorithm runs.
     1194    /// \param s is the source node.
     1195    DijkstraWizard<TR> &source(Node s)
     1196    {
     1197      Base::_source=s;
     1198      return *this;
     1199    }
     1200
    11321201    template<class T>
    11331202    struct DefPredMapBase : public Base {
    … …  
    11361205      DefPredMapBase(const TR &b) : TR(b) {}
    11371206    };
    1138 
    11391207    ///\brief \ref named-templ-param "Named parameter"
    1140     ///function for setting PredMap type
    1141     ///
    1142     /// \ref named-templ-param "Named parameter"
    1143     ///function for setting PredMap type
    1144     ///
     1208    ///for setting \ref PredMap object.
     1209    ///
     1210    ///\ref named-templ-param "Named parameter"
     1211    ///for setting \ref PredMap object.
    11451212    template<class T>
    11461213    DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
    … …  
    11481215      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    11491216      return DijkstraWizard<DefPredMapBase<T> >(*this);
     1217    }
     1218
     1219    template<class T>
     1220    struct DefProcessedMapBase : public Base {
     1221      typedef T ProcessedMap;
     1222      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
     1223      DefProcessedMapBase(const TR &b) : TR(b) {}
     1224    };
     1225    ///\brief \ref named-templ-param "Named parameter"
     1226    ///for setting \ref ProcessedMap object.
     1227    ///
     1228    /// \ref named-templ-param "Named parameter"
     1229    ///for setting \ref ProcessedMap object.
     1230    template<class T>
     1231    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1232    {
     1233      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
     1234      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
    11501235    }
    11511236
    … …  
    11561241      DefDistMapBase(const TR &b) : TR(b) {}
    11571242    };
    1158 
    11591243    ///\brief \ref named-templ-param "Named parameter"
    1160     ///function for setting DistMap type
    1161     ///
    1162     /// \ref named-templ-param "Named parameter"
    1163     ///function for setting DistMap type
    1164     ///
     1244    ///for setting \ref DistMap object.
     1245    ///
     1246    ///\ref named-templ-param "Named parameter"
     1247    ///for setting \ref DistMap object.
    11651248    template<class T>
    11661249    DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
    … …  
    11681251      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    11691252      return DijkstraWizard<DefDistMapBase<T> >(*this);
    1170     }
    1171 
    1172     /// Sets the source node, from which the Dijkstra algorithm runs.
    1173 
    1174     /// Sets the source node, from which the Dijkstra algorithm runs.
    1175     /// \param s is the source node.
    1176     DijkstraWizard<TR> &source(Node s)
    1177     {
    1178       Base::_source=s;
    1179       return *this;
    11801253    }
    11811254
Note: See TracChangeset for help on using the changeset viewer.