COIN-OR::LEMON - Graph Library

Changeset 287:bb40b6db0a58 in lemon


Ignore:
Timestamp:
09/27/08 14:33:28 (16 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

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r281 r287  
    605605    ///
    606606    ///This method runs the %BFS algorithm from the root node(s)
    607     ///in order to compute the shortest path to \c dest.
     607    ///in order to compute the shortest path to \c t.
    608608    ///
    609609    ///The algorithm computes
    610     ///- the shortest path to \c dest,
    611     ///- the distance of \c dest from the root(s).
     610    ///- the shortest path to \c t,
     611    ///- the distance of \c t from the root(s).
    612612    ///
    613613    ///\pre init() must be called and at least one root node should be
     
    621621    ///  }
    622622    ///\endcode
    623     void start(Node dest)
     623    void start(Node t)
    624624    {
    625625      bool reach = false;
    626       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     626      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    627627    }
    628628
     
    662662    }
    663663
    664     ///Runs the algorithm from the given node.
     664    ///Runs the algorithm from the given source node.
    665665
    666666    ///This method runs the %BFS algorithm from node \c s
     
    686686
    687687    ///This method runs the %BFS algorithm from node \c s
    688     ///in order to compute the shortest path to \c t.
    689     ///
    690     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    691     ///if \c t is reachable form \c s, \c 0 otherwise.
     688    ///in order to compute the shortest path to node \c t
     689    ///(it stops searching when \c t is processed).
     690    ///
     691    ///\return \c true if \c t is reachable form \c s.
    692692    ///
    693693    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     
    698698    ///  b.start(t);
    699699    ///\endcode
    700     int run(Node s,Node t) {
     700    bool run(Node s,Node t) {
    701701      init();
    702702      addSource(s);
    703703      start(t);
    704       return reached(t) ? _curr_dist : 0;
     704      return reached(t);
    705705    }
    706706
     
    16171617    ///
    16181618    /// This method runs the %BFS algorithm from the root node(s)
    1619     /// in order to compute the shortest path to \c dest.
     1619    /// in order to compute the shortest path to \c t.
    16201620    ///
    16211621    /// The algorithm computes
    1622     /// - the shortest path to \c dest,
    1623     /// - the distance of \c dest from the root(s).
     1622    /// - the shortest path to \c t,
     1623    /// - the distance of \c t from the root(s).
    16241624    ///
    16251625    /// \pre init() must be called and at least one root node should be
     
    16331633    ///   }
    16341634    /// \endcode
    1635     void start(Node dest) {
     1635    void start(Node t) {
    16361636      bool reach = false;
    1637       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     1637      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    16381638    }
    16391639
     
    16731673    }
    16741674
    1675     /// \brief Runs the algorithm from the given node.
     1675    /// \brief Runs the algorithm from the given source node.
    16761676    ///
    16771677    /// This method runs the %BFS algorithm from node \c s
     
    16921692      addSource(s);
    16931693      start();
     1694    }
     1695
     1696    /// \brief Finds the shortest path between \c s and \c t.
     1697    ///
     1698    /// This method runs the %BFS algorithm from node \c s
     1699    /// in order to compute the shortest path to node \c t
     1700    /// (it stops searching when \c t is processed).
     1701    ///
     1702    /// \return \c true if \c t is reachable form \c s.
     1703    ///
     1704    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     1705    /// shortcut of the following code.
     1706    ///\code
     1707    ///   b.init();
     1708    ///   b.addSource(s);
     1709    ///   b.start(t);
     1710    ///\endcode
     1711    bool run(Node s,Node t) {
     1712      init();
     1713      addSource(s);
     1714      start(t);
     1715      return reached(t);
    16941716    }
    16951717
  • lemon/bfs.h

    r286 r287  
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///\ref PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
    5857    static PredMap *createPredMap(const Digraph &g)
    5958    {
     
    6564    ///The type of the map that indicates which nodes are processed.
    6665    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     ///By default it is a NullMap.
    6866    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6967    ///Instantiates a \ref ProcessedMap.
     
    197195    int _curr_dist;
    198196
    199     ///Creates the maps if necessary.
    200     ///\todo Better memory allocation (instead of new).
     197    //Creates the maps if necessary.
    201198    void create_maps()
    202199    {
     
    849846    ///\param g is the digraph, to which we would like to define the
    850847    ///\ref PredMap.
    851     ///\todo The digraph alone may be insufficient to initialize
    852848    static PredMap *createPredMap(const Digraph &g)
    853849    {
     
    13711367    int _list_front, _list_back;
    13721368
    1373     ///Creates the maps if necessary.
    1374     ///\todo Better memory allocation (instead of new).
     1369    //Creates the maps if necessary.
    13751370    void create_maps() {
    13761371      if(!_reached) {
  • lemon/dfs.h

    r281 r287  
    556556    ///
    557557    ///This method runs the %DFS algorithm from the root node
    558     ///in order to compute the DFS path to \c dest.
     558    ///in order to compute the DFS path to \c t.
    559559    ///
    560560    ///The algorithm computes
    561     ///- the %DFS path to \c dest,
    562     ///- the distance of \c dest from the root in the %DFS tree.
     561    ///- the %DFS path to \c t,
     562    ///- the distance of \c t from the root in the %DFS tree.
    563563    ///
    564564    ///\pre init() must be called and a root node should be
    565565    ///added with addSource() before using this function.
    566     void start(Node dest)
    567     {
    568       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     566    void start(Node t)
     567    {
     568      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
    569569        processNextArc();
    570570    }
     
    596596    }
    597597
    598     ///Runs the algorithm from the given node.
     598    ///Runs the algorithm from the given source node.
    599599
    600600    ///This method runs the %DFS algorithm from node \c s
     
    620620
    621621    ///This method runs the %DFS algorithm from node \c s
    622     ///in order to compute the DFS path to \c t.
    623     ///
    624     ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    625     ///if \c t is reachable form \c s, \c 0 otherwise.
     622    ///in order to compute the DFS path to node \c t
     623    ///(it stops searching when \c t is processed)
     624    ///
     625    ///\return \c true if \c t is reachable form \c s.
    626626    ///
    627627    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    632632    ///  d.start(t);
    633633    ///\endcode
    634     int run(Node s,Node t) {
     634    bool run(Node s,Node t) {
    635635      init();
    636636      addSource(s);
    637637      start(t);
    638       return reached(t)?_stack_head+1:0;
     638      return reached(t);
    639639    }
    640640
     
    15221522    ///
    15231523    /// This method runs the %DFS algorithm from the root node
    1524     /// in order to compute the DFS path to \c dest.
     1524    /// in order to compute the DFS path to \c t.
    15251525    ///
    15261526    /// The algorithm computes
    1527     /// - the %DFS path to \c dest,
    1528     /// - the distance of \c dest from the root in the %DFS tree.
     1527    /// - the %DFS path to \c t,
     1528    /// - the distance of \c t from the root in the %DFS tree.
    15291529    ///
    15301530    /// \pre init() must be called and a root node should be added
    15311531    /// with addSource() before using this function.
    1532     void start(Node dest) {
    1533       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
     1532    void start(Node t) {
     1533      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
    15341534        processNextArc();
    15351535    }
     
    15601560    }
    15611561
    1562     /// \brief Runs the algorithm from the given node.
     1562    /// \brief Runs the algorithm from the given source node.
    15631563    ///
    15641564    /// This method runs the %DFS algorithm from node \c s.
     
    15841584
    15851585    /// This method runs the %DFS algorithm from node \c s
    1586     /// in order to compute the DFS path to \c t.
    1587     ///
    1588     /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    1589     /// if \c t is reachable form \c s, \c 0 otherwise.
     1586    /// in order to compute the DFS path to node \c t
     1587    /// (it stops searching when \c t is processed).
     1588    ///
     1589    /// \return \c true if \c t is reachable form \c s.
    15901590    ///
    15911591    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    15961596    ///   d.start(t);
    15971597    ///\endcode
    1598     int run(Node s,Node t) {
     1598    bool run(Node s,Node t) {
    15991599      init();
    16001600      addSource(s);
    16011601      start(t);
    1602       return reached(t)?_stack_head+1:0;
     1602      return reached(t);
    16031603    }
    16041604
  • lemon/dfs.h

    r286 r287  
    5656    ///\param g is the digraph, to which we would like to define the
    5757    ///\ref PredMap.
    58     ///\todo The digraph alone may be insufficient to initialize
    5958    static PredMap *createPredMap(const Digraph &g)
    6059    {
     
    6665    ///The type of the map that indicates which nodes are processed.
    6766    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    68     ///By default it is a NullMap.
    6967    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    7068    ///Instantiates a \ref ProcessedMap.
     
    197195    int _stack_head;
    198196
    199     ///Creates the maps if necessary.
    200     ///\todo Better memory allocation (instead of new).
     197    //Creates the maps if necessary.
    201198    void create_maps()
    202199    {
     
    783780    ///\param g is the digraph, to which we would like to define the
    784781    ///\ref PredMap.
    785     ///\todo The digraph alone may be insufficient to initialize
    786782    static PredMap *createPredMap(const Digraph &g)
    787783    {
     
    13181314    int _stack_head;
    13191315
    1320     ///Creates the maps if necessary.
    1321     ///\todo Better memory allocation (instead of new).
     1316    //Creates the maps if necessary.
    13221317    void create_maps() {
    13231318      if(!_reached) {
  • 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.