COIN-OR::LEMON - Graph Library

Changeset 286:da414906fe21 in lemon


Ignore:
Timestamp:
09/26/08 12:40:11 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
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.
Files:
6 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 
  • lemon/dfs.h

    r278 r286  
    559559    /// 
    560560    ///This method runs the %DFS algorithm from the root node 
    561     ///in order to compute the DFS path to \c dest. 
     561    ///in order to compute the DFS path to \c t. 
    562562    /// 
    563563    ///The algorithm computes 
    564     ///- the %DFS path to \c dest, 
    565     ///- the distance of \c dest from the root in the %DFS tree. 
     564    ///- the %DFS path to \c t, 
     565    ///- the distance of \c t from the root in the %DFS tree. 
    566566    /// 
    567567    ///\pre init() must be called and a root node should be 
    568568    ///added with addSource() before using this function. 
    569     void start(Node dest) 
    570     { 
    571       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
     569    void start(Node t) 
     570    { 
     571      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) 
    572572        processNextArc(); 
    573573    } 
     
    599599    } 
    600600 
    601     ///Runs the algorithm from the given node. 
     601    ///Runs the algorithm from the given source node. 
    602602 
    603603    ///This method runs the %DFS algorithm from node \c s 
     
    623623 
    624624    ///This method runs the %DFS algorithm from node \c s 
    625     ///in order to compute the DFS path to \c t. 
    626     /// 
    627     ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path, 
    628     ///if \c t is reachable form \c s, \c 0 otherwise. 
     625    ///in order to compute the DFS path to node \c t 
     626    ///(it stops searching when \c t is processed) 
     627    /// 
     628    ///\return \c true if \c t is reachable form \c s. 
    629629    /// 
    630630    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is 
     
    635635    ///  d.start(t); 
    636636    ///\endcode 
    637     int run(Node s,Node t) { 
     637    bool run(Node s,Node t) { 
    638638      init(); 
    639639      addSource(s); 
    640640      start(t); 
    641       return reached(t)?_stack_head+1:0; 
     641      return reached(t); 
    642642    } 
    643643 
     
    15271527    /// 
    15281528    /// This method runs the %DFS algorithm from the root node 
    1529     /// in order to compute the DFS path to \c dest. 
     1529    /// in order to compute the DFS path to \c t. 
    15301530    /// 
    15311531    /// The algorithm computes 
    1532     /// - the %DFS path to \c dest, 
    1533     /// - the distance of \c dest from the root in the %DFS tree. 
     1532    /// - the %DFS path to \c t, 
     1533    /// - the distance of \c t from the root in the %DFS tree. 
    15341534    /// 
    15351535    /// \pre init() must be called and a root node should be added 
    15361536    /// with addSource() before using this function. 
    1537     void start(Node dest) { 
    1538       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) 
     1537    void start(Node t) { 
     1538      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) 
    15391539        processNextArc(); 
    15401540    } 
     
    15651565    } 
    15661566 
    1567     /// \brief Runs the algorithm from the given node. 
     1567    /// \brief Runs the algorithm from the given source node. 
    15681568    /// 
    15691569    /// This method runs the %DFS algorithm from node \c s. 
     
    15891589 
    15901590    /// This method runs the %DFS algorithm from node \c s 
    1591     /// in order to compute the DFS path to \c t. 
    1592     /// 
    1593     /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path, 
    1594     /// if \c t is reachable form \c s, \c 0 otherwise. 
     1591    /// in order to compute the DFS path to node \c t 
     1592    /// (it stops searching when \c t is processed). 
     1593    /// 
     1594    /// \return \c true if \c t is reachable form \c s. 
    15951595    /// 
    15961596    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is 
     
    16011601    ///   d.start(t); 
    16021602    ///\endcode 
    1603     int run(Node s,Node t) { 
     1603    bool run(Node s,Node t) { 
    16041604      init(); 
    16051605      addSource(s); 
    16061606      start(t); 
    1607       return reached(t)?_stack_head+1:0; 
     1607      return reached(t); 
    16081608    } 
    16091609 
  • 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    ///@} 
  • test/bfs_test.cc

    r278 r286  
    5555  typedef concepts::Digraph Digraph; 
    5656  typedef Bfs<Digraph> BType; 
     57  typedef Digraph::Node Node; 
     58  typedef Digraph::Arc Arc; 
    5759 
    5860  Digraph G; 
    59   Digraph::Node n; 
    60   Digraph::Arc e; 
     61  Node s, t; 
     62  Arc e; 
    6163  int l; 
    6264  bool b; 
    6365  BType::DistMap d(G); 
    6466  BType::PredMap p(G); 
     67  Path<Digraph> pp; 
    6568 
    66   BType bfs_test(G); 
     69  { 
     70    BType bfs_test(G); 
    6771 
    68   bfs_test.run(n); 
     72    bfs_test.run(s); 
     73    bfs_test.run(s,t); 
     74    bfs_test.run(); 
    6975 
    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); 
     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); 
    7692 
    77   Path<Digraph> pp = bfs_test.path(n); 
     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  } 
    78103} 
    79104 
  • test/dfs_test.cc

    r278 r286  
    5757  typedef concepts::Digraph Digraph; 
    5858  typedef Dfs<Digraph> DType; 
     59  typedef Digraph::Node Node; 
     60  typedef Digraph::Arc Arc; 
    5961 
    6062  Digraph G; 
    61   Digraph::Node n; 
    62   Digraph::Arc e; 
     63  Node s, t; 
     64  Arc e; 
    6365  int l; 
    6466  bool b; 
    6567  DType::DistMap d(G); 
    6668  DType::PredMap p(G); 
     69  Path<Digraph> pp; 
    6770 
    68   DType dfs_test(G); 
     71  { 
     72    DType dfs_test(G); 
    6973 
    70   dfs_test.run(n); 
     74    dfs_test.run(s); 
     75    dfs_test.run(s,t); 
     76    dfs_test.run(); 
    7177 
    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); 
     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); 
    7894 
    79   Path<Digraph> pp = dfs_test.path(n); 
     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  } 
    80105} 
    81106 
  • test/dijkstra_test.cc

    r278 r286  
    2323#include <lemon/dijkstra.h> 
    2424#include <lemon/path.h> 
     25#include <lemon/bin_heap.h> 
    2526 
    2627#include "graph_test.h" 
     
    5657  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; 
    5758  typedef Dijkstra<Digraph, LengthMap> DType; 
     59  typedef Digraph::Node Node; 
     60  typedef Digraph::Arc Arc; 
    5861 
    5962  Digraph G; 
    60   Digraph::Node n; 
    61   Digraph::Arc e; 
     63  Node s, t; 
     64  Arc e; 
    6265  VType l; 
    6366  bool b; 
     
    6568  DType::PredMap p(G); 
    6669  LengthMap length; 
     70  Path<Digraph> pp; 
    6771 
    68   DType dijkstra_test(G,length); 
     72  { 
     73    DType dijkstra_test(G,length); 
    6974 
    70   dijkstra_test.run(n); 
     75    dijkstra_test.run(s); 
     76    dijkstra_test.run(s,t); 
    7177 
    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); 
     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); 
    7896 
    79   Path<Digraph> pp = dijkstra_test.path(n); 
     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 
    80107} 
    81108 
Note: See TracChangeset for help on using the changeset viewer.