COIN-OR::LEMON - Graph Library

Changeset 286:da414906fe21 in lemon-1.2 for lemon/bfs.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/bfs.h

    r278 r286  
    608608    ///
    609609    ///This method runs the %BFS algorithm from the root node(s)
    610     ///in order to compute the shortest path to \c dest.
     610    ///in order to compute the shortest path to \c t.
    611611    ///
    612612    ///The algorithm computes
    613     ///- the shortest path to \c dest,
    614     ///- the distance of \c dest from the root(s).
     613    ///- the shortest path to \c t,
     614    ///- the distance of \c t from the root(s).
    615615    ///
    616616    ///\pre init() must be called and at least one root node should be
     
    624624    ///  }
    625625    ///\endcode
    626     void start(Node dest)
     626    void start(Node t)
    627627    {
    628628      bool reach = false;
    629       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     629      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    630630    }
    631631
     
    665665    }
    666666
    667     ///Runs the algorithm from the given node.
     667    ///Runs the algorithm from the given source node.
    668668
    669669    ///This method runs the %BFS algorithm from node \c s
     
    689689
    690690    ///This method runs the %BFS algorithm from node \c s
    691     ///in order to compute the shortest path to \c t.
    692     ///
    693     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    694     ///if \c t is reachable form \c s, \c 0 otherwise.
     691    ///in order to compute the shortest path to node \c t
     692    ///(it stops searching when \c t is processed).
     693    ///
     694    ///\return \c true if \c t is reachable form \c s.
    695695    ///
    696696    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     
    701701    ///  b.start(t);
    702702    ///\endcode
    703     int run(Node s,Node t) {
     703    bool run(Node s,Node t) {
    704704      init();
    705705      addSource(s);
    706706      start(t);
    707       return reached(t) ? _curr_dist : 0;
     707      return reached(t);
    708708    }
    709709
     
    16221622    ///
    16231623    /// This method runs the %BFS algorithm from the root node(s)
    1624     /// in order to compute the shortest path to \c dest.
     1624    /// in order to compute the shortest path to \c t.
    16251625    ///
    16261626    /// The algorithm computes
    1627     /// - the shortest path to \c dest,
    1628     /// - the distance of \c dest from the root(s).
     1627    /// - the shortest path to \c t,
     1628    /// - the distance of \c t from the root(s).
    16291629    ///
    16301630    /// \pre init() must be called and at least one root node should be
     
    16381638    ///   }
    16391639    /// \endcode
    1640     void start(Node dest) {
     1640    void start(Node t) {
    16411641      bool reach = false;
    1642       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     1642      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    16431643    }
    16441644
     
    16781678    }
    16791679
    1680     /// \brief Runs the algorithm from the given node.
     1680    /// \brief Runs the algorithm from the given source node.
    16811681    ///
    16821682    /// This method runs the %BFS algorithm from node \c s
     
    16971697      addSource(s);
    16981698      start();
     1699    }
     1700
     1701    /// \brief Finds the shortest path between \c s and \c t.
     1702    ///
     1703    /// This method runs the %BFS algorithm from node \c s
     1704    /// in order to compute the shortest path to node \c t
     1705    /// (it stops searching when \c t is processed).
     1706    ///
     1707    /// \return \c true if \c t is reachable form \c s.
     1708    ///
     1709    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     1710    /// shortcut of the following code.
     1711    ///\code
     1712    ///   b.init();
     1713    ///   b.addSource(s);
     1714    ///   b.start(t);
     1715    ///\endcode
     1716    bool run(Node s,Node t) {
     1717      init();
     1718      addSource(s);
     1719      start(t);
     1720      return reached(t);
    16991721    }
    17001722
Note: See TracChangeset for help on using the changeset viewer.