COIN-OR::LEMON - Graph Library

Changeset 717:684964884a2e in lemon-1.2 for lemon/dijkstra.h


Ignore:
Timestamp:
09/25/09 09:13:03 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
716:f47b6c94577e (diff), 715:ece80147fb08 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r713 r717  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the length of the arcs.
     75    ///The type of the arc lengths.
    7676    typedef typename LEN::Value Value;
    7777
     
    117117    ///The type of the map that stores the predecessor
    118118    ///arcs of the shortest paths.
    119     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    120120    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    121121    ///Instantiates a \c PredMap.
     
    132132
    133133    ///The type of the map that indicates which nodes are processed.
    134     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    135135    ///By default it is a NullMap.
    136136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    152152
    153153    ///The type of the map that stores the distances of the nodes.
    154     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    155155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    156156    ///Instantiates a \c DistMap.
     
    169169  /// \ingroup shortest_path
    170170  ///This class provides an efficient implementation of the %Dijkstra algorithm.
     171  ///
     172  ///The %Dijkstra algorithm solves the single-source shortest path problem
     173  ///when all arc lengths are non-negative. If there are negative lengths,
     174  ///the BellmanFord algorithm should be used instead.
    171175  ///
    172176  ///The arc lengths are passed to the algorithm using a
     
    202206    typedef typename TR::Digraph Digraph;
    203207
    204     ///The type of the length of the arcs.
     208    ///The type of the arc lengths.
    205209    typedef typename TR::LengthMap::Value Value;
    206210    ///The type of the map that stores the arc lengths.
     
    305309    ///\ref named-templ-param "Named parameter" for setting
    306310    ///\c PredMap type.
    307     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     311    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    308312    template <class T>
    309313    struct SetPredMap
     
    326330    ///\ref named-templ-param "Named parameter" for setting
    327331    ///\c DistMap type.
    328     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     332    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    329333    template <class T>
    330334    struct SetDistMap
     
    347351    ///\ref named-templ-param "Named parameter" for setting
    348352    ///\c ProcessedMap type.
    349     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     353    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    350354    template <class T>
    351355    struct SetProcessedMap
     
    444448    ///\ref named-templ-param "Named parameter" for setting
    445449    ///\c OperationTraits type.
     450    /// For more information see \ref DijkstraDefaultOperationTraits.
    446451    template <class T>
    447452    struct SetOperationTraits
     
    802807    ///The results of the %Dijkstra algorithm can be obtained using these
    803808    ///functions.\n
    804     ///Either \ref run(Node) "run()" or \ref start() should be called
     809    ///Either \ref run(Node) "run()" or \ref init() should be called
    805810    ///before using them.
    806811
    807812    ///@{
    808813
    809     ///The shortest path to a node.
    810 
    811     ///Returns the shortest path to a node.
     814    ///The shortest path to the given node.
     815
     816    ///Returns the shortest path to the given node from the root(s).
    812817    ///
    813818    ///\warning \c t should be reached from the root(s).
     
    817822    Path path(Node t) const { return Path(*G, *_pred, t); }
    818823
    819     ///The distance of a node from the root(s).
    820 
    821     ///Returns the distance of a node from the root(s).
     824    ///The distance of the given node from the root(s).
     825
     826    ///Returns the distance of the given node from the root(s).
    822827    ///
    823828    ///\warning If node \c v is not reached from the root(s), then
     
    828833    Value dist(Node v) const { return (*_dist)[v]; }
    829834
    830     ///Returns the 'previous arc' of the shortest path tree for a node.
    831 
     835    ///\brief Returns the 'previous arc' of the shortest path tree for
     836    ///the given node.
     837    ///
    832838    ///This function returns the 'previous arc' of the shortest path
    833839    ///tree for the node \c v, i.e. it returns the last arc of a
     
    836842    ///
    837843    ///The shortest path tree used here is equal to the shortest path
    838     ///tree used in \ref predNode().
     844    ///tree used in \ref predNode() and \ref predMap().
    839845    ///
    840846    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    842848    Arc predArc(Node v) const { return (*_pred)[v]; }
    843849
    844     ///Returns the 'previous node' of the shortest path tree for a node.
    845 
     850    ///\brief Returns the 'previous node' of the shortest path tree for
     851    ///the given node.
     852    ///
    846853    ///This function returns the 'previous node' of the shortest path
    847854    ///tree for the node \c v, i.e. it returns the last but one node
    848     ///from a shortest path from a root to \c v. It is \c INVALID
     855    ///of a shortest path from a root to \c v. It is \c INVALID
    849856    ///if \c v is not reached from the root(s) or if \c v is a root.
    850857    ///
    851858    ///The shortest path tree used here is equal to the shortest path
    852     ///tree used in \ref predArc().
     859    ///tree used in \ref predArc() and \ref predMap().
    853860    ///
    854861    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    871878    ///
    872879    ///Returns a const reference to the node map that stores the predecessor
    873     ///arcs, which form the shortest path tree.
     880    ///arcs, which form the shortest path tree (forest).
    874881    ///
    875882    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    877884    const PredMap &predMap() const { return *_pred;}
    878885
    879     ///Checks if a node is reached from the root(s).
     886    ///Checks if the given node is reached from the root(s).
    880887
    881888    ///Returns \c true if \c v is reached from the root(s).
     
    896903                                          Heap::POST_HEAP; }
    897904
    898     ///The current distance of a node from the root(s).
    899 
    900     ///Returns the current distance of a node from the root(s).
     905    ///The current distance of the given node from the root(s).
     906
     907    ///Returns the current distance of the given node from the root(s).
    901908    ///It may be decreased in the following processes.
    902909    ///
     
    925932
    926933    ///The type of the map that stores the arc lengths.
    927     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     934    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    928935    typedef LEN LengthMap;
    929     ///The type of the length of the arcs.
     936    ///The type of the arc lengths.
    930937    typedef typename LEN::Value Value;
    931938
     
    974981    ///The type of the map that stores the predecessor
    975982    ///arcs of the shortest paths.
    976     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     983    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    977984    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    978985    ///Instantiates a PredMap.
     
    989996
    990997    ///The type of the map that indicates which nodes are processed.
    991     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     998    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    992999    ///By default it is a NullMap.
    9931000    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    10091016
    10101017    ///The type of the map that stores the distances of the nodes.
    1011     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1018    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    10121019    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10131020    ///Instantiates a DistMap.
     
    10241031
    10251032    ///The type of the shortest paths.
    1026     ///It must meet the \ref concepts::Path "Path" concept.
     1033    ///It must conform to the \ref concepts::Path "Path" concept.
    10271034    typedef lemon::Path<Digraph> Path;
    10281035  };
     
    10301037  /// Default traits class used by DijkstraWizard
    10311038
    1032   /// To make it easier to use Dijkstra algorithm
    1033   /// we have created a wizard class.
    1034   /// This \ref DijkstraWizard class needs default traits,
    1035   /// as well as the \ref Dijkstra class.
    1036   /// The \ref DijkstraWizardBase is a class to be the default traits of the
    1037   /// \ref DijkstraWizard class.
     1039  /// Default traits class used by DijkstraWizard.
     1040  /// \tparam GR The type of the digraph.
     1041  /// \tparam LEN The type of the length map.
    10381042  template<typename GR, typename LEN>
    10391043  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
     
    10941098    typedef TR Base;
    10951099
    1096     ///The type of the digraph the algorithm runs on.
    10971100    typedef typename TR::Digraph Digraph;
    10981101
     
    11021105    typedef typename Digraph::OutArcIt OutArcIt;
    11031106
    1104     ///The type of the map that stores the arc lengths.
    11051107    typedef typename TR::LengthMap LengthMap;
    1106     ///The type of the length of the arcs.
    11071108    typedef typename LengthMap::Value Value;
    1108     ///\brief The type of the map that stores the predecessor
    1109     ///arcs of the shortest paths.
    11101109    typedef typename TR::PredMap PredMap;
    1111     ///The type of the map that stores the distances of the nodes.
    11121110    typedef typename TR::DistMap DistMap;
    1113     ///The type of the map that indicates which nodes are processed.
    11141111    typedef typename TR::ProcessedMap ProcessedMap;
    1115     ///The type of the shortest paths
    11161112    typedef typename TR::Path Path;
    1117     ///The heap type used by the dijkstra algorithm.
    11181113    typedef typename TR::Heap Heap;
    11191114
     
    11871182      SetPredMapBase(const TR &b) : TR(b) {}
    11881183    };
    1189     ///\brief \ref named-func-param "Named parameter"
    1190     ///for setting PredMap object.
    1191     ///
    1192     ///\ref named-func-param "Named parameter"
    1193     ///for setting PredMap object.
     1184
     1185    ///\brief \ref named-templ-param "Named parameter" for setting
     1186    ///the predecessor map.
     1187    ///
     1188    ///\ref named-templ-param "Named parameter" function for setting
     1189    ///the map that stores the predecessor arcs of the nodes.
    11941190    template<class T>
    11951191    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
     
    12051201      SetDistMapBase(const TR &b) : TR(b) {}
    12061202    };
    1207     ///\brief \ref named-func-param "Named parameter"
    1208     ///for setting DistMap object.
    1209     ///
    1210     ///\ref named-func-param "Named parameter"
    1211     ///for setting DistMap object.
     1203
     1204    ///\brief \ref named-templ-param "Named parameter" for setting
     1205    ///the distance map.
     1206    ///
     1207    ///\ref named-templ-param "Named parameter" function for setting
     1208    ///the map that stores the distances of the nodes calculated
     1209    ///by the algorithm.
    12121210    template<class T>
    12131211    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     
    12231221      SetProcessedMapBase(const TR &b) : TR(b) {}
    12241222    };
    1225     ///\brief \ref named-func-param "Named parameter"
    1226     ///for setting ProcessedMap object.
    1227     ///
    1228     /// \ref named-func-param "Named parameter"
    1229     ///for setting ProcessedMap object.
     1223
     1224    ///\brief \ref named-func-param "Named parameter" for setting
     1225    ///the processed map.
     1226    ///
     1227    ///\ref named-templ-param "Named parameter" function for setting
     1228    ///the map that indicates which nodes are processed.
    12301229    template<class T>
    12311230    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12401239      SetPathBase(const TR &b) : TR(b) {}
    12411240    };
     1241
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.
  • lemon/dijkstra.h

    r716 r717  
    590590    ///The simplest way to execute the %Dijkstra algorithm is to use
    591591    ///one of the member functions called \ref run(Node) "run()".\n
    592     ///If you need more control on the execution, first you have to call
    593     ///\ref init(), then you can add several source nodes with
     592    ///If you need better control on the execution, you have to call
     593    ///\ref init() first, then you can add several source nodes with
    594594    ///\ref addSource(). Finally the actual path computation can be
    595595    ///performed with one of the \ref start() functions.
Note: See TracChangeset for help on using the changeset viewer.