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 186 insertions and 80 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

@@ -609,7 +609,7 @@
 		    ///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).
 		    ///
@@ -625,6 +625,6 @@
 		    ///\endcode
-		    void start(Node dest)
+		    void start(Node t)
+		    {
 		      bool reach = false;
-		      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
@@ -666,3 +666,3 @@
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
@@ -690,6 +690,6 @@
 		    ///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.
 		    ///
@@ -702,3 +702,3 @@
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
@@ -706,3 +706,3 @@
 		      start(t);
-		      return reached(t) ? _curr_dist : 0;
 		      return reached(t);
+		    }
@@ -1623,7 +1623,7 @@
 		    /// 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).
 		    ///
@@ -1639,5 +1639,5 @@
 		    /// \endcode
-		    void start(Node dest) {
+		    void start(Node t) {
 		      bool reach = false;
-		      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
@@ -1679,3 +1679,3 @@
 		    /// \brief Runs the algorithm from the given node.
+		    /// \brief Runs the algorithm from the given source node.
 		    ///
@@ -1700,2 +1700,24 @@
 		    /// \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.

lemon/dfs.h

Show inline comments

@@ -560,7 +560,7 @@
 		    ///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.
 		    ///
@@ -568,5 +568,5 @@
 		    ///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();
@@ -600,3 +600,3 @@
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
@@ -624,6 +624,6 @@
 		    ///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.
 		    ///
@@ -636,3 +636,3 @@
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
@@ -640,3 +640,3 @@
 		      start(t);
-		      return reached(t)?_stack_head+1:0;
 		      return reached(t);
+		    }
@@ -1528,7 +1528,7 @@
 		    /// 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.
 		    ///
@@ -1536,4 +1536,4 @@
 		    /// 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();
@@ -1566,3 +1566,3 @@
 		    /// \brief Runs the algorithm from the given node.
+		    /// \brief Runs the algorithm from the given source node.
 		    ///
@@ -1590,6 +1590,6 @@
 		    /// 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.
 		    ///
@@ -1602,3 +1602,3 @@
 		    ///\endcode
-		    int run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
@@ -1606,3 +1606,3 @@
 		      start(t);
-		      return reached(t)?_stack_head+1:0;
 		      return reached(t);
+		    }

lemon/dijkstra.h

Show inline comments

@@ -730,12 +730,12 @@
-		    ///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).
 		    ///
@@ -743,6 +743,9 @@
 		    ///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();
+		      }
+		    }
@@ -774,3 +777,3 @@
 		    ///Runs the algorithm from the given node.
+		    ///Runs the algorithm from the given source node.
@@ -798,6 +801,6 @@
 		    ///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.
 		    ///
@@ -810,3 +813,3 @@
 		    ///\endcode
-		    Value run(Node s,Node t) {
+		    bool run(Node s,Node t) {
 		      init();
@@ -814,3 +817,3 @@
 		      start(t);
-		      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
+		      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
+		    }
@@ -910,3 +913,3 @@
 		    ///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.
@@ -919,4 +922,8 @@
 		    ///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

@@ -56,6 +56,8 @@
 		  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;
@@ -64,15 +66,38 @@
 		  BType::PredMap p(G);
 		  Path<Digraph> pp;
+		  {
 		  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);
+		    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();
-		  b  = bfs_test.reached(n);
+		    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);
+		  }
+		}

test/dfs_test.cc

Show inline comments

@@ -58,6 +58,8 @@
 		  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;
@@ -66,15 +68,38 @@
 		  DType::PredMap p(G);
 		  Path<Digraph> pp;
+		  {
 		  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);
+		    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();
-		  b  = dfs_test.reached(n);
+		    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);
+		  }
+		}

test/dijkstra_test.cc

Show inline comments

@@ -24,2 +24,3 @@
 		#include <lemon/path.h>
 		#include <lemon/bin_heap.h>
@@ -57,6 +58,8 @@
 		  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;
@@ -66,15 +69,39 @@
 		  LengthMap length;
 		  Path<Digraph> pp;
+		  {
 		  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);
+		    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();
-		  b  = dijkstra_test.reached(n);
+		    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);
+		  }
+		}

0 comments (0 inline)

RhodeCode

Login to your account