COIN-OR::LEMON - Graph Library

Changes in / [287:bb40b6db0a58:285:d8dc5acf739b] in lemon-1.0


Ignore:
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r287 r281  
    605605    ///
    606606    ///This method runs the %BFS algorithm from the root node(s)
    607     ///in order to compute the shortest path to \c t.
     607    ///in order to compute the shortest path to \c dest.
    608608    ///
    609609    ///The algorithm computes
    610     ///- the shortest path to \c t,
    611     ///- the distance of \c t from the root(s).
     610    ///- the shortest path to \c dest,
     611    ///- the distance of \c dest 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 t)
     623    void start(Node dest)
    624624    {
    625625      bool reach = false;
    626       while ( !emptyQueue() && !reach ) processNextNode(t, reach);
     626      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
    627627    }
    628628
     
    662662    }
    663663
    664     ///Runs the algorithm from the given source node.
     664    ///Runs the algorithm from the given 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 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.
     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.
    692692    ///
    693693    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     
    698698    ///  b.start(t);
    699699    ///\endcode
    700     bool run(Node s,Node t) {
     700    int run(Node s,Node t) {
    701701      init();
    702702      addSource(s);
    703703      start(t);
    704       return reached(t);
     704      return reached(t) ? _curr_dist : 0;
    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 t.
     1619    /// in order to compute the shortest path to \c dest.
    16201620    ///
    16211621    /// The algorithm computes
    1622     /// - the shortest path to \c t,
    1623     /// - the distance of \c t from the root(s).
     1622    /// - the shortest path to \c dest,
     1623    /// - the distance of \c dest 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 t) {
     1635    void start(Node dest) {
    16361636      bool reach = false;
    1637       while ( !emptyQueue() && !reach ) processNextNode(t, reach);
     1637      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
    16381638    }
    16391639
     
    16731673    }
    16741674
    1675     /// \brief Runs the algorithm from the given source node.
     1675    /// \brief Runs the algorithm from the given 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);
    17161694    }
    17171695
  • lemon/dfs.h

    r287 r281  
    556556    ///
    557557    ///This method runs the %DFS algorithm from the root node
    558     ///in order to compute the DFS path to \c t.
     558    ///in order to compute the DFS path to \c dest.
    559559    ///
    560560    ///The algorithm computes
    561     ///- the %DFS path to \c t,
    562     ///- the distance of \c t from the root in the %DFS tree.
     561    ///- the %DFS path to \c dest,
     562    ///- the distance of \c dest 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 t)
    567     {
    568       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     566    void start(Node dest)
     567    {
     568      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
    569569        processNextArc();
    570570    }
     
    596596    }
    597597
    598     ///Runs the algorithm from the given source node.
     598    ///Runs the algorithm from the given 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 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.
     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.
    626626    ///
    627627    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    632632    ///  d.start(t);
    633633    ///\endcode
    634     bool run(Node s,Node t) {
     634    int run(Node s,Node t) {
    635635      init();
    636636      addSource(s);
    637637      start(t);
    638       return reached(t);
     638      return reached(t)?_stack_head+1:0;
    639639    }
    640640
     
    15221522    ///
    15231523    /// This method runs the %DFS algorithm from the root node
    1524     /// in order to compute the DFS path to \c t.
     1524    /// in order to compute the DFS path to \c dest.
    15251525    ///
    15261526    /// The algorithm computes
    1527     /// - the %DFS path to \c t,
    1528     /// - the distance of \c t from the root in the %DFS tree.
     1527    /// - the %DFS path to \c dest,
     1528    /// - the distance of \c dest 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 t) {
    1533       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1532    void start(Node dest) {
     1533      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
    15341534        processNextArc();
    15351535    }
     
    15601560    }
    15611561
    1562     /// \brief Runs the algorithm from the given source node.
     1562    /// \brief Runs the algorithm from the given 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 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.
     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.
    15901590    ///
    15911591    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    15961596    ///   d.start(t);
    15971597    ///\endcode
    1598     bool run(Node s,Node t) {
     1598    int run(Node s,Node t) {
    15991599      init();
    16001600      addSource(s);
    16011601      start(t);
    1602       return reached(t);
     1602      return reached(t)?_stack_head+1:0;
    16031603    }
    16041604
  • lemon/dijkstra.h

    r287 r281  
    725725    }
    726726
    727     ///Executes the algorithm until the given target node is processed.
    728 
    729     ///Executes the algorithm until the given target node is processed.
     727    ///Executes the algorithm until the given target node is reached.
     728
     729    ///Executes the algorithm until the given target node is reached.
    730730    ///
    731731    ///This method runs the %Dijkstra algorithm from the root node(s)
    732     ///in order to compute the shortest path to \c t.
     732    ///in order to compute the shortest path to \c dest.
    733733    ///
    734734    ///The algorithm computes
    735     ///- the shortest path to \c t,
    736     ///- the distance of \c t from the root(s).
     735    ///- the shortest path to \c dest,
     736    ///- the distance of \c dest 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 t)
    741     {
    742       while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
    743       if ( !_heap->empty() ) {
    744         finalizeNodeData(_heap->top(),_heap->prio());
    745         _heap->pop();
    746       }
     740    void start(Node dest)
     741    {
     742      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
     743      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    747744    }
    748745
     
    772769    }
    773770
    774     ///Runs the algorithm from the given source node.
     771    ///Runs the algorithm from the given node.
    775772
    776773    ///This method runs the %Dijkstra algorithm from node \c s
     
    796793
    797794    ///This method runs the %Dijkstra algorithm from node \c s
    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.
     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.
    802799    ///
    803800    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
     
    808805    ///  d.start(t);
    809806    ///\endcode
    810     bool run(Node s,Node t) {
     807    Value run(Node s,Node t) {
    811808      init();
    812809      addSource(s);
    813810      start(t);
    814       return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
     811      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
    815812    }
    816813
     
    908905    ///Returns \c true if \c v is processed, i.e. the shortest
    909906    ///path to \c v has already found.
    910     ///\pre Either \ref run() or \ref init()
     907    ///\pre Either \ref run() or \ref start()
    911908    ///must be called before using this function.
    912909    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    917914    ///Returns the current distance of a node from the root(s).
    918915    ///It may be decreased in the following processes.
    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     }
     916    ///\pre \c v should be reached but not processed.
     917    Value currentDist(Node v) const { return (*_heap)[v]; }
    925918
    926919    ///@}
  • test/bfs_test.cc

    r286 r278  
    5555  typedef concepts::Digraph Digraph;
    5656  typedef Bfs<Digraph> BType;
    57   typedef Digraph::Node Node;
    58   typedef Digraph::Arc Arc;
    5957
    6058  Digraph G;
    61   Node s, t;
    62   Arc e;
     59  Digraph::Node n;
     60  Digraph::Arc e;
    6361  int l;
    6462  bool b;
    6563  BType::DistMap d(G);
    6664  BType::PredMap p(G);
    67   Path<Digraph> pp;
    6865
    69   {
    70     BType bfs_test(G);
     66  BType bfs_test(G);
    7167
    72     bfs_test.run(s);
    73     bfs_test.run(s,t);
    74     bfs_test.run();
     68  bfs_test.run(n);
    7569
    76     l  = bfs_test.dist(t);
    77     e  = bfs_test.predArc(t);
    78     s  = bfs_test.predNode(t);
    79     b  = bfs_test.reached(t);
    80     d  = bfs_test.distMap();
    81     p  = bfs_test.predMap();
    82     pp = bfs_test.path(t);
    83   }
    84   {
    85     BType
    86       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    87       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    88       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
    89       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    90       ::SetStandardProcessedMap
    91       ::Create bfs_test(G);
     70  l  = bfs_test.dist(n);
     71  e  = bfs_test.predArc(n);
     72  n  = bfs_test.predNode(n);
     73  d  = bfs_test.distMap();
     74  p  = bfs_test.predMap();
     75  b  = bfs_test.reached(n);
    9276
    93     bfs_test.run(s);
    94     bfs_test.run(s,t);
    95     bfs_test.run();
    96 
    97     l  = bfs_test.dist(t);
    98     e  = bfs_test.predArc(t);
    99     s  = bfs_test.predNode(t);
    100     b  = bfs_test.reached(t);
    101     pp = bfs_test.path(t);
    102   }
     77  Path<Digraph> pp = bfs_test.path(n);
    10378}
    10479
  • test/dfs_test.cc

    r286 r278  
    5757  typedef concepts::Digraph Digraph;
    5858  typedef Dfs<Digraph> DType;
    59   typedef Digraph::Node Node;
    60   typedef Digraph::Arc Arc;
    6159
    6260  Digraph G;
    63   Node s, t;
    64   Arc e;
     61  Digraph::Node n;
     62  Digraph::Arc e;
    6563  int l;
    6664  bool b;
    6765  DType::DistMap d(G);
    6866  DType::PredMap p(G);
    69   Path<Digraph> pp;
    7067
    71   {
    72     DType dfs_test(G);
     68  DType dfs_test(G);
    7369
    74     dfs_test.run(s);
    75     dfs_test.run(s,t);
    76     dfs_test.run();
     70  dfs_test.run(n);
    7771
    78     l  = dfs_test.dist(t);
    79     e  = dfs_test.predArc(t);
    80     s  = dfs_test.predNode(t);
    81     b  = dfs_test.reached(t);
    82     d  = dfs_test.distMap();
    83     p  = dfs_test.predMap();
    84     pp = dfs_test.path(t);
    85   }
    86   {
    87     DType
    88       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    89       ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    90       ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
    91       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    92       ::SetStandardProcessedMap
    93       ::Create dfs_test(G);
     72  l  = dfs_test.dist(n);
     73  e  = dfs_test.predArc(n);
     74  n  = dfs_test.predNode(n);
     75  d  = dfs_test.distMap();
     76  p  = dfs_test.predMap();
     77  b  = dfs_test.reached(n);
    9478
    95     dfs_test.run(s);
    96     dfs_test.run(s,t);
    97     dfs_test.run();
    98 
    99     l  = dfs_test.dist(t);
    100     e  = dfs_test.predArc(t);
    101     s  = dfs_test.predNode(t);
    102     b  = dfs_test.reached(t);
    103     pp = dfs_test.path(t);
    104   }
     79  Path<Digraph> pp = dfs_test.path(n);
    10580}
    10681
  • test/dijkstra_test.cc

    r286 r278  
    2323#include <lemon/dijkstra.h>
    2424#include <lemon/path.h>
    25 #include <lemon/bin_heap.h>
    2625
    2726#include "graph_test.h"
     
    5756  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    5857  typedef Dijkstra<Digraph, LengthMap> DType;
    59   typedef Digraph::Node Node;
    60   typedef Digraph::Arc Arc;
    6158
    6259  Digraph G;
    63   Node s, t;
    64   Arc e;
     60  Digraph::Node n;
     61  Digraph::Arc e;
    6562  VType l;
    6663  bool b;
     
    6865  DType::PredMap p(G);
    6966  LengthMap length;
    70   Path<Digraph> pp;
    7167
    72   {
    73     DType dijkstra_test(G,length);
     68  DType dijkstra_test(G,length);
    7469
    75     dijkstra_test.run(s);
    76     dijkstra_test.run(s,t);
     70  dijkstra_test.run(n);
    7771
    78     l  = dijkstra_test.dist(t);
    79     e  = dijkstra_test.predArc(t);
    80     s  = dijkstra_test.predNode(t);
    81     b  = dijkstra_test.reached(t);
    82     d  = dijkstra_test.distMap();
    83     p  = dijkstra_test.predMap();
    84     pp = dijkstra_test.path(t);
    85   }
    86   {
    87     DType
    88       ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
    89       ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
    90       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    91       ::SetStandardProcessedMap
    92       ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
    93       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    94       ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    95       ::Create dijkstra_test(G,length);
     72  l  = dijkstra_test.dist(n);
     73  e  = dijkstra_test.predArc(n);
     74  n  = dijkstra_test.predNode(n);
     75  d  = dijkstra_test.distMap();
     76  p  = dijkstra_test.predMap();
     77  b  = dijkstra_test.reached(n);
    9678
    97     dijkstra_test.run(s);
    98     dijkstra_test.run(s,t);
    99 
    100     l  = dijkstra_test.dist(t);
    101     e  = dijkstra_test.predArc(t);
    102     s  = dijkstra_test.predNode(t);
    103     b  = dijkstra_test.reached(t);
    104     pp = dijkstra_test.path(t);
    105   }
    106 
     79  Path<Digraph> pp = dijkstra_test.path(n);
    10780}
    10881
Note: See TracChangeset for help on using the changeset viewer.