LEMON/LEMON-official Changeset - r286:da414906fe21

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r286:da414906fe21

« 279:6307bb

287:bb40b6 »

r286:da414906fe21

Fri, 26 Sep 2008 12:40:11

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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.

0 6 0

default

6 files changed with 195 insertions and 89 deletions:

lemon/bfs.h

lemon/dfs.h

lemon/dijkstra.h

test/bfs_test.cc

test/dfs_test.cc

test/dijkstra_test.cc

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

@@ -607,11 +607,11 @@
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
-		    ///in order to compute the shortest path to \c dest.
+		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path to \c dest,
 		    ///- the distance of \c dest from the root(s).
 		    ///- the shortest path to \c t,
 		    ///- the distance of \c t from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
@@ -623,10 +623,10 @@
 		    ///    b.processNextNode(t, reach);
 		    ///  }
 		    ///\endcode
-		    void start(Node dest)
+		    void start(Node t)
+		    {
 		      bool reach = false;
-		      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
@@ -664,7 +664,7 @@
 		      return rnode;
+		    }
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
@@ -688,10 +688,10 @@
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %BFS algorithm from node \c s
-		    ///in order to compute the shortest path to \c t.
+		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
@@ -700,11 +700,11 @@
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
-		      return reached(t) ? _curr_dist : 0;
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
@@ -1621,11 +1621,11 @@
 		    /// Executes the algorithm until the given target node is reached.
 		    ///
 		    /// This method runs the %BFS algorithm from the root node(s)
-		    /// in order to compute the shortest path to \c dest.
+		    /// in order to compute the shortest path to \c t.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path to \c dest,
 		    /// - the distance of \c dest from the root(s).
 		    /// - the shortest path to \c t,
 		    /// - the distance of \c t from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
@@ -1637,9 +1637,9 @@
 		    ///     b.processNextNode(t, reach);
 		    ///   }
 		    /// \endcode
-		    void start(Node dest) {
+		    void start(Node t) {
 		      bool reach = false;
-		      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    /// \brief Executes the algorithm until a condition is met.
@@ -1677,7 +1677,7 @@
 		      return rnode;
+		    }
 		    /// \brief Runs the algorithm from the given node.
+		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to each node.
@@ -1698,6 +1698,28 @@
 		      start();
+		    }
 		    /// \brief Finds the shortest path between \c s and \c t.
 		    ///
 		    /// This method runs the %BFS algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    /// shortcut of the following code.
 		    ///\code
 		    ///   b.init();
 		    ///   b.addSource(s);
 		    ///   b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    ///
 		    /// This method runs the %BFS algorithm in order to

lemon/dfs.h

Show inline comments

@@ -558,17 +558,17 @@
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
-		    ///in order to compute the DFS path to \c dest.
+		    ///in order to compute the DFS path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS path to \c dest,
 		    ///- the distance of \c dest from the root in the %DFS tree.
 		    ///- the %DFS path to \c t,
 		    ///- the distance of \c t from the root in the %DFS tree.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
-		    void start(Node dest)
+		    void start(Node t)
+		    {
-		      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
+		      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
 		        processNextArc();
+		    }
@@ -598,7 +598,7 @@
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
@@ -622,10 +622,10 @@
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///This method runs the %DFS algorithm from node \c s
-		    ///in order to compute the DFS path to \c t.
+		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed)
 		    ///
 		    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    ///just a shortcut of the following code.
@@ -634,11 +634,11 @@
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
-		      return reached(t)?_stack_head+1:0;
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
@@ -1526,16 +1526,16 @@
 		    /// Executes the algorithm until the given target node is reached.
 		    ///
 		    /// This method runs the %DFS algorithm from the root node
-		    /// in order to compute the DFS path to \c dest.
+		    /// in order to compute the DFS path to \c t.
 		    ///
 		    /// The algorithm computes
 		    /// - the %DFS path to \c dest,
 		    /// - the distance of \c dest from the root in the %DFS tree.
 		    /// - the %DFS path to \c t,
 		    /// - the distance of \c t from the root in the %DFS tree.
 		    ///
 		    /// \pre init() must be called and a root node should be added
 		    /// with addSource() before using this function.
 		    void start(Node dest) {
 		      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
 		    void start(Node t) {
 		      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
 		        processNextArc();
+		    }
@@ -1564,7 +1564,7 @@
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    /// \brief Runs the algorithm from the given node.
+		    /// \brief Runs the algorithm from the given source node.
 		    ///
 		    /// This method runs the %DFS algorithm from node \c s.
 		    /// in order to compute the DFS path to each node.
@@ -1588,10 +1588,10 @@
 		    /// \brief Finds the %DFS path between \c s and \c t.
 		    /// This method runs the %DFS algorithm from node \c s
-		    /// in order to compute the DFS path to \c t.
+		    /// in order to compute the DFS path to node \c t
 		    /// (it stops searching when \c t is processed).
 		    ///
 		    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
 		    /// if \c t is reachable form \c s, \c 0 otherwise.
 		    /// \return \c true if \c t is reachable form \c s.
 		    ///
 		    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    /// just a shortcut of the following code.
@@ -1600,11 +1600,11 @@
 		    ///   d.addSource(s);
 		    ///   d.start(t);
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
-		      return reached(t)?_stack_head+1:0;
 		      return reached(t);
+		    }
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.

lemon/dijkstra.h

Show inline comments

@@ -728,23 +728,26 @@
 		      while ( !emptyQueue() ) processNextNode();
+		    }
-		    ///Executes the algorithm until the given target node is reached.
+		    ///Executes the algorithm until the given target node is processed.
-		    ///Executes the algorithm until the given target node is reached.
+		    ///Executes the algorithm until the given target node is processed.
 		    ///
 		    ///This method runs the %Dijkstra algorithm from the root node(s)
-		    ///in order to compute the shortest path to \c dest.
+		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path to \c dest,
 		    ///- the distance of \c dest from the root(s).
 		    ///- the shortest path to \c t,
 		    ///- the distance of \c t from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
-		    void start(Node dest)
+		    void start(Node t)
+		    {
 		      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
 		      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
 		      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
 		      if ( !_heap->empty() ) {
 		        finalizeNodeData(_heap->top(),_heap->prio());
 		        _heap->pop();
+		      }
+		    }
 		    ///Executes the algorithm until a condition is met.
@@ -772,7 +775,7 @@
 		      return _heap->top();
+		    }
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
@@ -796,10 +799,10 @@
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %Dijkstra algorithm from node \c s
-		    ///in order to compute the shortest path to \c t.
+		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
 		    ///if \c t is reachable form \c s, \c 0 otherwise.
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
@@ -808,11 +811,11 @@
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
-		    Value run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
-		      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
+		      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
+		    }
 		    ///@}
@@ -908,7 +911,7 @@
 		    ///Returns \c true if \c v is processed, i.e. the shortest
 		    ///path to \c v has already found.
-		    ///\pre Either \ref run() or \ref start()
+		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function.
 		    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
 		                                          Heap::POST_HEAP; }
@@ -917,8 +920,12 @@
 		    ///Returns the current distance of a node from the root(s).
 		    ///It may be decreased in the following processes.
 		    ///\pre \c v should be reached but not processed.
 		    Value currentDist(Node v) const { return (*_heap)[v]; }
 		    ///\pre Either \ref run() or \ref init()
 		    ///must be called before using this function and
 		    ///node \c v must be reached but not necessarily processed.
 		    Value currentDist(Node v) const {
 		      return processed(v) ? (*_dist)[v] : (*_heap)[v];
+		    }
 		    ///@}
 		  };

test/bfs_test.cc

Show inline comments

@@ -54,27 +54,52 @@
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Bfs<Digraph> BType;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  Node s, t;
 		  Arc e;
 		  int l;
 		  bool b;
 		  BType::DistMap d(G);
 		  BType::PredMap p(G);
 		  Path<Digraph> pp;
-		  BType bfs_test(G);
+		  {
 		    BType bfs_test(G);
-		  bfs_test.run(n);
+		    bfs_test.run(s);
 		    bfs_test.run(s,t);
 		    bfs_test.run();
 		  l  = bfs_test.dist(n);
 		  e  = bfs_test.predArc(n);
 		  n  = bfs_test.predNode(n);
 		  d  = bfs_test.distMap();
 		  p  = bfs_test.predMap();
 		  b  = bfs_test.reached(n);
 		    l  = bfs_test.dist(t);
 		    e  = bfs_test.predArc(t);
 		    s  = bfs_test.predNode(t);
 		    b  = bfs_test.reached(t);
 		    d  = bfs_test.distMap();
 		    p  = bfs_test.predMap();
 		    pp = bfs_test.path(t);
+		  }
+		  {
 		    BType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
 		      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::SetStandardProcessedMap
 		      ::Create bfs_test(G);
-		  Path<Digraph> pp = bfs_test.path(n);
+		    bfs_test.run(s);
 		    bfs_test.run(s,t);
 		    bfs_test.run();
 		    l  = bfs_test.dist(t);
 		    e  = bfs_test.predArc(t);
 		    s  = bfs_test.predNode(t);
 		    b  = bfs_test.reached(t);
 		    pp = bfs_test.path(t);
+		  }
+		}
 		void checkBfsFunctionCompile()

test/dfs_test.cc

Show inline comments

@@ -56,27 +56,52 @@
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Dfs<Digraph> DType;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  Node s, t;
 		  Arc e;
 		  int l;
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  Path<Digraph> pp;
-		  DType dfs_test(G);
+		  {
 		    DType dfs_test(G);
-		  dfs_test.run(n);
+		    dfs_test.run(s);
 		    dfs_test.run(s,t);
 		    dfs_test.run();
 		  l  = dfs_test.dist(n);
 		  e  = dfs_test.predArc(n);
 		  n  = dfs_test.predNode(n);
 		  d  = dfs_test.distMap();
 		  p  = dfs_test.predMap();
 		  b  = dfs_test.reached(n);
 		    l  = dfs_test.dist(t);
 		    e  = dfs_test.predArc(t);
 		    s  = dfs_test.predNode(t);
 		    b  = dfs_test.reached(t);
 		    d  = dfs_test.distMap();
 		    p  = dfs_test.predMap();
 		    pp = dfs_test.path(t);
+		  }
+		  {
 		    DType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
 		      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::SetStandardProcessedMap
 		      ::Create dfs_test(G);
-		  Path<Digraph> pp = dfs_test.path(n);
+		    dfs_test.run(s);
 		    dfs_test.run(s,t);
 		    dfs_test.run();
 		    l  = dfs_test.dist(t);
 		    e  = dfs_test.predArc(t);
 		    s  = dfs_test.predNode(t);
 		    b  = dfs_test.reached(t);
 		    pp = dfs_test.path(t);
+		  }
+		}
 		void checkDfsFunctionCompile()

test/dijkstra_test.cc

Show inline comments

@@ -22,6 +22,7 @@
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/path.h>
 		#include <lemon/bin_heap.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
@@ -55,28 +56,54 @@
 		  typedef concepts::Digraph Digraph;
 		  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
 		  typedef Dijkstra<Digraph, LengthMap> DType;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  Digraph G;
 		  Digraph::Node n;
 		  Digraph::Arc e;
 		  Node s, t;
 		  Arc e;
 		  VType l;
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  LengthMap length;
 		  Path<Digraph> pp;
-		  DType dijkstra_test(G,length);
+		  {
 		    DType dijkstra_test(G,length);
-		  dijkstra_test.run(n);
+		    dijkstra_test.run(s);
 		    dijkstra_test.run(s,t);
 		  l  = dijkstra_test.dist(n);
 		  e  = dijkstra_test.predArc(n);
 		  n  = dijkstra_test.predNode(n);
 		  d  = dijkstra_test.distMap();
 		  p  = dijkstra_test.predMap();
 		  b  = dijkstra_test.reached(n);
 		    l  = dijkstra_test.dist(t);
 		    e  = dijkstra_test.predArc(t);
 		    s  = dijkstra_test.predNode(t);
 		    b  = dijkstra_test.reached(t);
 		    d  = dijkstra_test.distMap();
 		    p  = dijkstra_test.predMap();
 		    pp = dijkstra_test.path(t);
+		  }
+		  {
 		    DType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::SetStandardProcessedMap
 		      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
 		      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
 		      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
 		      ::Create dijkstra_test(G,length);
-		  Path<Digraph> pp = dijkstra_test.path(n);
+		    dijkstra_test.run(s);
 		    dijkstra_test.run(s,t);
 		    l  = dijkstra_test.dist(t);
 		    e  = dijkstra_test.predArc(t);
 		    s  = dijkstra_test.predNode(t);
 		    b  = dijkstra_test.reached(t);
 		    pp = dijkstra_test.path(t);
+		  }
+		}
 		void checkDijkstraFunctionCompile()

0 comments (0 inline)

RhodeCode

Login to your account