COIN-OR::LEMON - Graph Library

Changeset 287:bb40b6db0a58 in lemon-1.0 for lemon/dijkstra.h


Ignore:
Timestamp:
09/27/08 14:33:28 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
288:47b3a3b67837, 290:f6899946c1ac
Parents:
286:da414906fe21 (diff), 285:d8dc5acf739b (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

    r281 r287  
    725725    }
    726726
    727     ///Executes the algorithm until the given target node is reached.
    728 
    729     ///Executes the algorithm until the given target node is reached.
     727    ///Executes the algorithm until the given target node is processed.
     728
     729    ///Executes the algorithm until the given target node is processed.
    730730    ///
    731731    ///This method runs the %Dijkstra algorithm from the root node(s)
    732     ///in order to compute the shortest path to \c dest.
     732    ///in order to compute the shortest path to \c t.
    733733    ///
    734734    ///The algorithm computes
    735     ///- the shortest path to \c dest,
    736     ///- the distance of \c dest from the root(s).
     735    ///- the shortest path to \c t,
     736    ///- the distance of \c t from the root(s).
    737737    ///
    738738    ///\pre init() must be called and at least one root node should be
    739739    ///added with addSource() before using this function.
    740     void start(Node dest)
    741     {
    742       while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
    743       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     740    void start(Node t)
     741    {
     742      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
     743      if ( !_heap->empty() ) {
     744        finalizeNodeData(_heap->top(),_heap->prio());
     745        _heap->pop();
     746      }
    744747    }
    745748
     
    769772    }
    770773
    771     ///Runs the algorithm from the given node.
     774    ///Runs the algorithm from the given source node.
    772775
    773776    ///This method runs the %Dijkstra algorithm from node \c s
     
    793796
    794797    ///This method runs the %Dijkstra algorithm from node \c s
    795     ///in order to compute the shortest path to \c t.
    796     ///
    797     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    798     ///if \c t is reachable form \c s, \c 0 otherwise.
     798    ///in order to compute the shortest path to node \c t
     799    ///(it stops searching when \c t is processed).
     800    ///
     801    ///\return \c true if \c t is reachable form \c s.
    799802    ///
    800803    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
     
    805808    ///  d.start(t);
    806809    ///\endcode
    807     Value run(Node s,Node t) {
     810    bool run(Node s,Node t) {
    808811      init();
    809812      addSource(s);
    810813      start(t);
    811       return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
     814      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
    812815    }
    813816
     
    905908    ///Returns \c true if \c v is processed, i.e. the shortest
    906909    ///path to \c v has already found.
    907     ///\pre Either \ref run() or \ref start()
     910    ///\pre Either \ref run() or \ref init()
    908911    ///must be called before using this function.
    909912    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    914917    ///Returns the current distance of a node from the root(s).
    915918    ///It may be decreased in the following processes.
    916     ///\pre \c v should be reached but not processed.
    917     Value currentDist(Node v) const { return (*_heap)[v]; }
     919    ///\pre Either \ref run() or \ref init()
     920    ///must be called before using this function and
     921    ///node \c v must be reached but not necessarily processed.
     922    Value currentDist(Node v) const {
     923      return processed(v) ? (*_dist)[v] : (*_heap)[v];
     924    }
    918925
    919926    ///@}
  • lemon/dijkstra.h

    r286 r287  
    145145    ///\param g is the digraph, to which we would like to define the
    146146    ///\ref PredMap.
    147     ///\todo The digraph alone may be insufficient for the initialization
    148147    static PredMap *createPredMap(const Digraph &g)
    149148    {
     
    156155    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    157156    ///By default it is a NullMap.
    158     ///\todo If it is set to a real map,
    159     ///Dijkstra::processed() should read this.
    160157    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    161158    ///Instantiates a \ref ProcessedMap.
     
    298295    bool local_heap;
    299296
    300     ///Creates the maps if necessary.
    301     ///\todo Better memory allocation (instead of new).
     297    //Creates the maps if necessary.
    302298    void create_maps()
    303299    {
     
    966962    /// \param g is the digraph, to which we would like to define the
    967963    /// HeapCrossRef.
    968     /// \todo The digraph alone may be insufficient for the initialization
    969964    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    970965    {
     
    1002997    ///\param g is the digraph, to which we would like to define the
    1003998    ///\ref PredMap.
    1004     ///\todo The digraph alone may be insufficient to initialize
    1005999    static PredMap *createPredMap(const Digraph &g)
    10061000    {
     
    10131007    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10141008    ///By default it is a NullMap.
    1015     ///\todo If it is set to a real map,
    1016     ///Dijkstra::processed() should read this.
    1017     ///\todo named parameter to set this type, function to read and write.
    10181009    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    10191010    ///Instantiates a \ref ProcessedMap.
     
    10611052  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10621053  /// \ref DijkstraWizard class.
    1063   /// \todo More named parameters are required...
    10641054  template<class GR,class LM>
    10651055  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
Note: See TracChangeset for help on using the changeset viewer.