COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r764 r631  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the arc lengths.
     75    ///The type of the length of the arcs.
    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 conform to the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must meet 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 conform to the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must meet 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 conform to the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must meet 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.
    175171  ///
    176172  ///The arc lengths are passed to the algorithm using a
     
    206202    typedef typename TR::Digraph Digraph;
    207203
    208     ///The type of the arc lengths.
     204    ///The type of the length of the arcs.
    209205    typedef typename TR::LengthMap::Value Value;
    210206    ///The type of the map that stores the arc lengths.
     
    309305    ///\ref named-templ-param "Named parameter" for setting
    310306    ///\c PredMap type.
    311     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     307    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    312308    template <class T>
    313309    struct SetPredMap
     
    330326    ///\ref named-templ-param "Named parameter" for setting
    331327    ///\c DistMap type.
    332     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     328    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    333329    template <class T>
    334330    struct SetDistMap
     
    351347    ///\ref named-templ-param "Named parameter" for setting
    352348    ///\c ProcessedMap type.
    353     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     349    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    354350    template <class T>
    355351    struct SetProcessedMap
     
    448444    ///\ref named-templ-param "Named parameter" for setting
    449445    ///\c OperationTraits type.
    450     /// For more information see \ref DijkstraDefaultOperationTraits.
    451446    template <class T>
    452447    struct SetOperationTraits
     
    590585    ///The simplest way to execute the %Dijkstra algorithm is to use
    591586    ///one of the member functions called \ref run(Node) "run()".\n
    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
     587    ///If you need more control on the execution, first you have to call
     588    ///\ref init(), then you can add several source nodes with
    594589    ///\ref addSource(). Finally the actual path computation can be
    595590    ///performed with one of the \ref start() functions.
     
    807802    ///The results of the %Dijkstra algorithm can be obtained using these
    808803    ///functions.\n
    809     ///Either \ref run(Node) "run()" or \ref init() should be called
     804    ///Either \ref run(Node) "run()" or \ref start() should be called
    810805    ///before using them.
    811806
    812807    ///@{
    813808
    814     ///The shortest path to the given node.
    815 
    816     ///Returns the shortest path to the given node from the root(s).
     809    ///The shortest path to a node.
     810
     811    ///Returns the shortest path to a node.
    817812    ///
    818813    ///\warning \c t should be reached from the root(s).
     
    822817    Path path(Node t) const { return Path(*G, *_pred, t); }
    823818
    824     ///The distance of the given node from the root(s).
    825 
    826     ///Returns the distance of the given node from the root(s).
     819    ///The distance of a node from the root(s).
     820
     821    ///Returns the distance of a node from the root(s).
    827822    ///
    828823    ///\warning If node \c v is not reached from the root(s), then
     
    833828    Value dist(Node v) const { return (*_dist)[v]; }
    834829
    835     ///\brief Returns the 'previous arc' of the shortest path tree for
    836     ///the given node.
    837     ///
     830    ///Returns the 'previous arc' of the shortest path tree for a node.
     831
    838832    ///This function returns the 'previous arc' of the shortest path
    839833    ///tree for the node \c v, i.e. it returns the last arc of a
     
    842836    ///
    843837    ///The shortest path tree used here is equal to the shortest path
    844     ///tree used in \ref predNode() and \ref predMap().
     838    ///tree used in \ref predNode().
    845839    ///
    846840    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    848842    Arc predArc(Node v) const { return (*_pred)[v]; }
    849843
    850     ///\brief Returns the 'previous node' of the shortest path tree for
    851     ///the given node.
    852     ///
     844    ///Returns the 'previous node' of the shortest path tree for a node.
     845
    853846    ///This function returns the 'previous node' of the shortest path
    854847    ///tree for the node \c v, i.e. it returns the last but one node
    855     ///of a shortest path from a root to \c v. It is \c INVALID
     848    ///from a shortest path from a root to \c v. It is \c INVALID
    856849    ///if \c v is not reached from the root(s) or if \c v is a root.
    857850    ///
    858851    ///The shortest path tree used here is equal to the shortest path
    859     ///tree used in \ref predArc() and \ref predMap().
     852    ///tree used in \ref predArc().
    860853    ///
    861854    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    878871    ///
    879872    ///Returns a const reference to the node map that stores the predecessor
    880     ///arcs, which form the shortest path tree (forest).
     873    ///arcs, which form the shortest path tree.
    881874    ///
    882875    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    884877    const PredMap &predMap() const { return *_pred;}
    885878
    886     ///Checks if the given node is reached from the root(s).
     879    ///Checks if a node is reached from the root(s).
    887880
    888881    ///Returns \c true if \c v is reached from the root(s).
     
    903896                                          Heap::POST_HEAP; }
    904897
    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).
     898    ///The current distance of a node from the root(s).
     899
     900    ///Returns the current distance of a node from the root(s).
    908901    ///It may be decreased in the following processes.
    909902    ///
     
    932925
    933926    ///The type of the map that stores the arc lengths.
    934     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    935928    typedef LEN LengthMap;
    936     ///The type of the arc lengths.
     929    ///The type of the length of the arcs.
    937930    typedef typename LEN::Value Value;
    938931
     
    981974    ///The type of the map that stores the predecessor
    982975    ///arcs of the shortest paths.
    983     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     976    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    984977    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    985978    ///Instantiates a PredMap.
     
    996989
    997990    ///The type of the map that indicates which nodes are processed.
    998     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     991    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    999992    ///By default it is a NullMap.
    1000993    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    10161009
    10171010    ///The type of the map that stores the distances of the nodes.
    1018     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     1011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10191012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10201013    ///Instantiates a DistMap.
     
    10311024
    10321025    ///The type of the shortest paths.
    1033     ///It must conform to the \ref concepts::Path "Path" concept.
     1026    ///It must meet the \ref concepts::Path "Path" concept.
    10341027    typedef lemon::Path<Digraph> Path;
    10351028  };
     
    10371030  /// Default traits class used by DijkstraWizard
    10381031
    1039   /// Default traits class used by DijkstraWizard.
    1040   /// \tparam GR The type of the digraph.
    1041   /// \tparam LEN The type of the length map.
     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.
    10421038  template<typename GR, typename LEN>
    10431039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
     
    10981094    typedef TR Base;
    10991095
     1096    ///The type of the digraph the algorithm runs on.
    11001097    typedef typename TR::Digraph Digraph;
    11011098
     
    11051102    typedef typename Digraph::OutArcIt OutArcIt;
    11061103
     1104    ///The type of the map that stores the arc lengths.
    11071105    typedef typename TR::LengthMap LengthMap;
     1106    ///The type of the length of the arcs.
    11081107    typedef typename LengthMap::Value Value;
     1108    ///\brief The type of the map that stores the predecessor
     1109    ///arcs of the shortest paths.
    11091110    typedef typename TR::PredMap PredMap;
     1111    ///The type of the map that stores the distances of the nodes.
    11101112    typedef typename TR::DistMap DistMap;
     1113    ///The type of the map that indicates which nodes are processed.
    11111114    typedef typename TR::ProcessedMap ProcessedMap;
     1115    ///The type of the shortest paths
    11121116    typedef typename TR::Path Path;
     1117    ///The heap type used by the dijkstra algorithm.
    11131118    typedef typename TR::Heap Heap;
    11141119
     
    11821187      SetPredMapBase(const TR &b) : TR(b) {}
    11831188    };
    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.
     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.
    11901194    template<class T>
    11911195    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
     
    12011205      SetDistMapBase(const TR &b) : TR(b) {}
    12021206    };
    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.
     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.
    12101212    template<class T>
    12111213    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     
    12211223      SetProcessedMapBase(const TR &b) : TR(b) {}
    12221224    };
    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.
     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.
    12291230    template<class T>
    12301231    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12391240      SetPathBase(const TR &b) : TR(b) {}
    12401241    };
    1241 
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.
Note: See TracChangeset for help on using the changeset viewer.