COIN-OR::LEMON - Graph Library

Changeset 286:da414906fe21 in lemon for lemon/dijkstra.h


Ignore:
Timestamp:
09/26/08 12:40:11 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements related to BFS/DFS/Dijkstra (ticket #96)

  • Add run(s,t) function to BfsVisit?.
  • Modify run(s,t) functions in the class interfaces to return bool value.
  • Bug fix in Dijkstra::start(t) function.
  • Improve Dijkstra::currentDist().
  • Extend test files to check named class template parameters.
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r278 r286  
    729729    }
    730730
    731     ///Executes the algorithm until the given target node is reached.
    732 
    733     ///Executes the algorithm until the given target node is reached.
     731    ///Executes the algorithm until the given target node is processed.
     732
     733    ///Executes the algorithm until the given target node is processed.
    734734    ///
    735735    ///This method runs the %Dijkstra algorithm from the root node(s)
    736     ///in order to compute the shortest path to \c dest.
     736    ///in order to compute the shortest path to \c t.
    737737    ///
    738738    ///The algorithm computes
    739     ///- the shortest path to \c dest,
    740     ///- the distance of \c dest from the root(s).
     739    ///- the shortest path to \c t,
     740    ///- the distance of \c t from the root(s).
    741741    ///
    742742    ///\pre init() must be called and at least one root node should be
    743743    ///added with addSource() before using this function.
    744     void start(Node dest)
    745     {
    746       while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
    747       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
     744    void start(Node t)
     745    {
     746      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
     747      if ( !_heap->empty() ) {
     748        finalizeNodeData(_heap->top(),_heap->prio());
     749        _heap->pop();
     750      }
    748751    }
    749752
     
    773776    }
    774777
    775     ///Runs the algorithm from the given node.
     778    ///Runs the algorithm from the given source node.
    776779
    777780    ///This method runs the %Dijkstra algorithm from node \c s
     
    797800
    798801    ///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.
     802    ///in order to compute the shortest path to node \c t
     803    ///(it stops searching when \c t is processed).
     804    ///
     805    ///\return \c true if \c t is reachable form \c s.
    803806    ///
    804807    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
     
    809812    ///  d.start(t);
    810813    ///\endcode
    811     Value run(Node s,Node t) {
     814    bool run(Node s,Node t) {
    812815      init();
    813816      addSource(s);
    814817      start(t);
    815       return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
     818      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
    816819    }
    817820
     
    909912    ///Returns \c true if \c v is processed, i.e. the shortest
    910913    ///path to \c v has already found.
    911     ///\pre Either \ref run() or \ref start()
     914    ///\pre Either \ref run() or \ref init()
    912915    ///must be called before using this function.
    913916    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    918921    ///Returns the current distance of a node from the root(s).
    919922    ///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]; }
     923    ///\pre Either \ref run() or \ref init()
     924    ///must be called before using this function and
     925    ///node \c v must be reached but not necessarily processed.
     926    Value currentDist(Node v) const {
     927      return processed(v) ? (*_dist)[v] : (*_heap)[v];
     928    }
    922929
    923930    ///@}
Note: See TracChangeset for help on using the changeset viewer.