COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 408:69f33ef03334 in lemon-main


Ignore:
Timestamp:
12/02/08 11:31:20 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
407:e22fc10ab6f1 (diff), 405:6b9057cdcd8b (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

    r405 r408  
    4848    static Value plus(const Value& left, const Value& right) {
    4949      return left + right;
    50     }
    51     /// \brief Gives back true only if the first value is less than the second.
    52     static bool less(const Value& left, const Value& right) {
    53       return left < right;
    54     }
    55   };
    56 
    57   /// \brief Widest path operation traits for the Dijkstra algorithm class.
    58   ///
    59   /// This operation traits class defines all computational operations and
    60   /// constants which are used in the Dijkstra algorithm for widest path
    61   /// computation.
    62   ///
    63   /// \see DijkstraDefaultOperationTraits
    64   template <typename Value>
    65   struct DijkstraWidestPathOperationTraits {
    66     /// \brief Gives back the maximum value of the type.
    67     static Value zero() {
    68       return std::numeric_limits<Value>::max();
    69     }
    70     /// \brief Gives back the minimum of the given two elements.
    71     static Value plus(const Value& left, const Value& right) {
    72       return std::min(left, right);
    7350    }
    7451    /// \brief Gives back true only if the first value is less than the second.

  • lemon/dijkstra.h

    r397 r408  
    180180  ///
    181181  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default value is \ref ListDigraph.
    183   ///The value of GR is not used directly by \ref Dijkstra, it is only
    184   ///passed to \ref DijkstraDefaultTraits.
    185   ///\tparam LM A readable arc map that determines the lengths of the
    186   ///arcs. It is read once for each arc, so the map may involve in
     182  ///The default type is \ref ListDigraph.
     183  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
     184  ///the lengths of the arcs.
     185  ///It is read once for each arc, so the map may involve in
    187186  ///relatively time consuming process to compute the arc lengths if
    188187  ///it is necessary. The default map type is \ref
    189   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    190   ///The value of LM is not used directly by \ref Dijkstra, it is only
    191   ///passed to \ref DijkstraDefaultTraits.
    192   ///\tparam TR Traits class to set various data types used by the algorithm.
    193   ///The default traits class is \ref DijkstraDefaultTraits
    194   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    195   ///for the documentation of a Dijkstra traits class.
     188  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    196189#ifdef DOXYGEN
    197190  template <typename GR, typename LM, typename TR>
    … …  
    227220    typedef typename TR::OperationTraits OperationTraits;
    228221
    229     ///The traits class.
     222    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    230223    typedef TR Traits;
    231224
    … …  
    309302    ///\ref named-templ-param "Named parameter" for setting
    310303    ///PredMap type.
     304    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    311305    template <class T>
    312306    struct SetPredMap
    … …  
    329323    ///\ref named-templ-param "Named parameter" for setting
    330324    ///DistMap type.
     325    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    331326    template <class T>
    332327    struct SetDistMap
    … …  
    349344    ///\ref named-templ-param "Named parameter" for setting
    350345    ///ProcessedMap type.
     346    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    351347    template <class T>
    352348    struct SetProcessedMap
    … …  
    389385    };
    390386    ///\brief \ref named-templ-param "Named parameter" for setting
    391     ///heap and cross reference type
     387    ///heap and cross reference types
    392388    ///
    393389    ///\ref named-templ-param "Named parameter" for setting heap and cross
    394     ///reference type.
     390    ///reference types. If this named parameter is used, then external
     391    ///heap and cross reference objects must be passed to the algorithm
     392    ///using the \ref heap() function before calling \ref run(Node) "run()"
     393    ///or \ref init().
     394    ///\sa SetStandardHeap
    395395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396396    struct SetHeap
    … …  
    412412    };
    413413    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference type with automatic allocation
     414    ///heap and cross reference types with automatic allocation
    415415    ///
    416416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference type. It can allocate the heap and the cross reference
    418     ///object if the cross reference's constructor waits for the digraph as
    419     ///parameter and the heap's constructor waits for the cross reference.
     417    ///reference types with automatic allocation.
     418    ///They should have standard constructor interfaces to be able to
     419    ///automatically created by the algorithm (i.e. the digraph should be
     420    ///passed to the constructor of the cross reference and the cross
     421    ///reference should be passed to the constructor of the heap).
     422    ///However external heap and cross reference objects could also be
     423    ///passed to the algorithm using the \ref heap() function before
     424    ///calling \ref run(Node) "run()" or \ref init().
     425    ///\sa SetHeap
    420426    template <class H, class CR = typename Digraph::template NodeMap<int> >
    421427    struct SetStandardHeap
    … …  
    487493
    488494    ///Sets the map that stores the predecessor arcs.
    489     ///If you don't use this function before calling \ref run(),
    490     ///it will allocate one. The destructor deallocates this
    491     ///automatically allocated map, of course.
     495    ///If you don't use this function before calling \ref run(Node) "run()"
     496    ///or \ref init(), an instance will be allocated automatically.
     497    ///The destructor deallocates this automatically allocated map,
     498    ///of course.
    492499    ///\return <tt> (*this) </tt>
    493500    Dijkstra &predMap(PredMap &m)
    … …  
    504511
    505512    ///Sets the map that indicates which nodes are processed.
    506     ///If you don't use this function before calling \ref run(),
    507     ///it will allocate one. The destructor deallocates this
    508     ///automatically allocated map, of course.
     513    ///If you don't use this function before calling \ref run(Node) "run()"
     514    ///or \ref init(), an instance will be allocated automatically.
     515    ///The destructor deallocates this automatically allocated map,
     516    ///of course.
    509517    ///\return <tt> (*this) </tt>
    510518    Dijkstra &processedMap(ProcessedMap &m)
    … …  
    522530    ///Sets the map that stores the distances of the nodes calculated by the
    523531    ///algorithm.
    524     ///If you don't use this function before calling \ref run(),
    525     ///it will allocate one. The destructor deallocates this
    526     ///automatically allocated map, of course.
     532    ///If you don't use this function before calling \ref run(Node) "run()"
     533    ///or \ref init(), an instance will be allocated automatically.
     534    ///The destructor deallocates this automatically allocated map,
     535    ///of course.
    527536    ///\return <tt> (*this) </tt>
    528537    Dijkstra &distMap(DistMap &m)
    … …  
    539548
    540549    ///Sets the heap and the cross reference used by algorithm.
    541     ///If you don't use this function before calling \ref run(),
    542     ///it will allocate one. The destructor deallocates this
    543     ///automatically allocated heap and cross reference, of course.
     550    ///If you don't use this function before calling \ref run(Node) "run()"
     551    ///or \ref init(), heap and cross reference instances will be
     552    ///allocated automatically.
     553    ///The destructor deallocates these automatically allocated objects,
     554    ///of course.
    544555    ///\return <tt> (*this) </tt>
    545556    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
    … …  
    568579  public:
    569580
    570     ///\name Execution control
    571     ///The simplest way to execute the algorithm is to use one of the
    572     ///member functions called \ref lemon::Dijkstra::run() "run()".
    573     ///\n
    574     ///If you need more control on the execution, first you must call
    575     ///\ref lemon::Dijkstra::init() "init()", then you can add several
    576     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
    577     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
    578     ///actual path computation.
     581    ///\name Execution Control
     582    ///The simplest way to execute the %Dijkstra algorithm is to use
     583    ///one of the member functions called \ref run(Node) "run()".\n
     584    ///If you need more control on the execution, first you have to call
     585    ///\ref init(), then you can add several source nodes with
     586    ///\ref addSource(). Finally the actual path computation can be
     587    ///performed with one of the \ref start() functions.
    579588
    580589    ///@{
    581590
     591    ///\brief Initializes the internal data structures.
     592    ///
    582593    ///Initializes the internal data structures.
    583 
    584     ///Initializes the internal data structures.
    585     ///
    586594    void init()
    587595    {
    … …  
    659667    }
    660668
    661     ///\brief Returns \c false if there are nodes
    662     ///to be processed.
    663     ///
    664     ///Returns \c false if there are nodes
    665     ///to be processed in the priority heap.
     669    ///Returns \c false if there are nodes to be processed.
     670
     671    ///Returns \c false if there are nodes to be processed
     672    ///in the priority heap.
    666673    bool emptyQueue() const { return _heap->empty(); }
    667674
    668     ///Returns the number of the nodes to be processed in the priority heap
    669 
    670     ///Returns the number of the nodes to be processed in the priority heap.
    671     ///
     675    ///Returns the number of the nodes to be processed.
     676
     677    ///Returns the number of the nodes to be processed
     678    ///in the priority heap.
    672679    int queueSize() const { return _heap->size(); }
    673680
    … …  
    790797
    791798    ///\name Query Functions
    792     ///The result of the %Dijkstra algorithm can be obtained using these
     799    ///The results of the %Dijkstra algorithm can be obtained using these
    793800    ///functions.\n
    794     ///Either \ref lemon::Dijkstra::run() "run()" or
    795     ///\ref lemon::Dijkstra::start() "start()" must be called before
    796     ///using them.
     801    ///Either \ref run(Node) "run()" or \ref start() should be called
     802    ///before using them.
    797803
    798804    ///@{
    … …  
    802808    ///Returns the shortest path to a node.
    803809    ///
    804     ///\warning \c t should be reachable from the root(s).
    805     ///
    806     ///\pre Either \ref run() or \ref start() must be called before
    807     ///using this function.
     810    ///\warning \c t should be reached from the root(s).
     811    ///
     812    ///\pre Either \ref run(Node) "run()" or \ref init()
     813    ///must be called before using this function.
    808814    Path path(Node t) const { return Path(*G, *_pred, t); }
    809815
    … …  
    812818    ///Returns the distance of a node from the root(s).
    813819    ///
    814     ///\warning If node \c v is not reachable from the root(s), then
     820    ///\warning If node \c v is not reached from the root(s), then
    815821    ///the return value of this function is undefined.
    816822    ///
    817     ///\pre Either \ref run() or \ref start() must be called before
    818     ///using this function.
     823    ///\pre Either \ref run(Node) "run()" or \ref init()
     824    ///must be called before using this function.
    819825    Value dist(Node v) const { return (*_dist)[v]; }
    820826
    … …  
    823829    ///This function returns the 'previous arc' of the shortest path
    824830    ///tree for the node \c v, i.e. it returns the last arc of a
    825     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    826     ///is not reachable from the root(s) or if \c v is a root.
     831    ///shortest path from a root to \c v. It is \c INVALID if \c v
     832    ///is not reached from the root(s) or if \c v is a root.
    827833    ///
    828834    ///The shortest path tree used here is equal to the shortest path
    829835    ///tree used in \ref predNode().
    830836    ///
    831     ///\pre Either \ref run() or \ref start() must be called before
    832     ///using this function.
     837    ///\pre Either \ref run(Node) "run()" or \ref init()
     838    ///must be called before using this function.
    833839    Arc predArc(Node v) const { return (*_pred)[v]; }
    834840
    … …  
    837843    ///This function returns the 'previous node' of the shortest path
    838844    ///tree for the node \c v, i.e. it returns the last but one node
    839     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    840     ///if \c v is not reachable from the root(s) or if \c v is a root.
     845    ///from a shortest path from a root to \c v. It is \c INVALID
     846    ///if \c v is not reached from the root(s) or if \c v is a root.
    841847    ///
    842848    ///The shortest path tree used here is equal to the shortest path
    843849    ///tree used in \ref predArc().
    844850    ///
    845     ///\pre Either \ref run() or \ref start() must be called before
    846     ///using this function.
     851    ///\pre Either \ref run(Node) "run()" or \ref init()
     852    ///must be called before using this function.
    847853    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    848854                                  G->source((*_pred)[v]); }
    … …  
    854860    ///of the nodes calculated by the algorithm.
    855861    ///
    856     ///\pre Either \ref run() or \ref init()
     862    ///\pre Either \ref run(Node) "run()" or \ref init()
    857863    ///must be called before using this function.
    858864    const DistMap &distMap() const { return *_dist;}
    … …  
    864870    ///arcs, which form the shortest path tree.
    865871    ///
    866     ///\pre Either \ref run() or \ref init()
     872    ///\pre Either \ref run(Node) "run()" or \ref init()
    867873    ///must be called before using this function.
    868874    const PredMap &predMap() const { return *_pred;}
    869875
    870     ///Checks if a node is reachable from the root(s).
    871 
    872     ///Returns \c true if \c v is reachable from the root(s).
    873     ///\pre Either \ref run() or \ref start()
     876    ///Checks if a node is reached from the root(s).
     877
     878    ///Returns \c true if \c v is reached from the root(s).
     879    ///
     880    ///\pre Either \ref run(Node) "run()" or \ref init()
    874881    ///must be called before using this function.
    875882    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
    … …  
    880887    ///Returns \c true if \c v is processed, i.e. the shortest
    881888    ///path to \c v has already found.
    882     ///\pre Either \ref run() or \ref init()
     889    ///
     890    ///\pre Either \ref run(Node) "run()" or \ref init()
    883891    ///must be called before using this function.
    884892    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
    … …  
    889897    ///Returns the current distance of a node from the root(s).
    890898    ///It may be decreased in the following processes.
    891     ///\pre Either \ref run() or \ref init()
     899    ///
     900    ///\pre Either \ref run(Node) "run()" or \ref init()
    892901    ///must be called before using this function and
    893902    ///node \c v must be reached but not necessarily processed.
    … …  
    10721081  /// This auxiliary class is created to implement the
    10731082  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1074   /// It does not have own \ref run() method, it uses the functions
    1075   /// and features of the plain \ref Dijkstra.
     1083  /// It does not have own \ref run(Node) "run()" method, it uses the
     1084  /// functions and features of the plain \ref Dijkstra.
    10761085  ///
    10771086  /// This class should only be used through the \ref dijkstra() function,
    … …  
    12681277  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12691278  ///\endcode
    1270   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1279  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12711280  ///to the end of the parameter list.
    12721281  ///\sa DijkstraWizard
Note: See TracChangeset for help on using the changeset viewer.