1.1 --- a/lemon/bfs.h Tue Sep 23 18:42:49 2008 +0200
1.2 +++ b/lemon/bfs.h Fri Sep 26 12:40:11 2008 +0200
1.3 @@ -607,11 +607,11 @@
1.4 ///Executes the algorithm until the given target node is reached.
1.5 ///
1.6 ///This method runs the %BFS algorithm from the root node(s)
1.7 - ///in order to compute the shortest path to \c dest.
1.8 + ///in order to compute the shortest path to \c t.
1.9 ///
1.10 ///The algorithm computes
1.11 - ///- the shortest path to \c dest,
1.12 - ///- the distance of \c dest from the root(s).
1.13 + ///- the shortest path to \c t,
1.14 + ///- the distance of \c t from the root(s).
1.15 ///
1.16 ///\pre init() must be called and at least one root node should be
1.17 ///added with addSource() before using this function.
1.18 @@ -623,10 +623,10 @@
1.19 /// b.processNextNode(t, reach);
1.20 /// }
1.21 ///\endcode
1.22 - void start(Node dest)
1.23 + void start(Node t)
1.24 {
1.25 bool reach = false;
1.26 - while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1.27 + while ( !emptyQueue() && !reach ) processNextNode(t, reach);
1.28 }
1.29
1.30 ///Executes the algorithm until a condition is met.
1.31 @@ -664,7 +664,7 @@
1.32 return rnode;
1.33 }
1.34
1.35 - ///Runs the algorithm from the given node.
1.36 + ///Runs the algorithm from the given source node.
1.37
1.38 ///This method runs the %BFS algorithm from node \c s
1.39 ///in order to compute the shortest path to each node.
1.40 @@ -688,10 +688,10 @@
1.41 ///Finds the shortest path between \c s and \c t.
1.42
1.43 ///This method runs the %BFS algorithm from node \c s
1.44 - ///in order to compute the shortest path to \c t.
1.45 + ///in order to compute the shortest path to node \c t
1.46 + ///(it stops searching when \c t is processed).
1.47 ///
1.48 - ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
1.49 - ///if \c t is reachable form \c s, \c 0 otherwise.
1.50 + ///\return \c true if \c t is reachable form \c s.
1.51 ///
1.52 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
1.53 ///shortcut of the following code.
1.54 @@ -700,11 +700,11 @@
1.55 /// b.addSource(s);
1.56 /// b.start(t);
1.57 ///\endcode
1.58 - int run(Node s,Node t) {
1.59 + bool run(Node s,Node t) {
1.60 init();
1.61 addSource(s);
1.62 start(t);
1.63 - return reached(t) ? _curr_dist : 0;
1.64 + return reached(t);
1.65 }
1.66
1.67 ///Runs the algorithm to visit all nodes in the digraph.
1.68 @@ -1621,11 +1621,11 @@
1.69 /// Executes the algorithm until the given target node is reached.
1.70 ///
1.71 /// This method runs the %BFS algorithm from the root node(s)
1.72 - /// in order to compute the shortest path to \c dest.
1.73 + /// in order to compute the shortest path to \c t.
1.74 ///
1.75 /// The algorithm computes
1.76 - /// - the shortest path to \c dest,
1.77 - /// - the distance of \c dest from the root(s).
1.78 + /// - the shortest path to \c t,
1.79 + /// - the distance of \c t from the root(s).
1.80 ///
1.81 /// \pre init() must be called and at least one root node should be
1.82 /// added with addSource() before using this function.
1.83 @@ -1637,9 +1637,9 @@
1.84 /// b.processNextNode(t, reach);
1.85 /// }
1.86 /// \endcode
1.87 - void start(Node dest) {
1.88 + void start(Node t) {
1.89 bool reach = false;
1.90 - while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1.91 + while ( !emptyQueue() && !reach ) processNextNode(t, reach);
1.92 }
1.93
1.94 /// \brief Executes the algorithm until a condition is met.
1.95 @@ -1677,7 +1677,7 @@
1.96 return rnode;
1.97 }
1.98
1.99 - /// \brief Runs the algorithm from the given node.
1.100 + /// \brief Runs the algorithm from the given source node.
1.101 ///
1.102 /// This method runs the %BFS algorithm from node \c s
1.103 /// in order to compute the shortest path to each node.
1.104 @@ -1698,6 +1698,28 @@
1.105 start();
1.106 }
1.107
1.108 + /// \brief Finds the shortest path between \c s and \c t.
1.109 + ///
1.110 + /// This method runs the %BFS algorithm from node \c s
1.111 + /// in order to compute the shortest path to node \c t
1.112 + /// (it stops searching when \c t is processed).
1.113 + ///
1.114 + /// \return \c true if \c t is reachable form \c s.
1.115 + ///
1.116 + /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
1.117 + /// shortcut of the following code.
1.118 + ///\code
1.119 + /// b.init();
1.120 + /// b.addSource(s);
1.121 + /// b.start(t);
1.122 + ///\endcode
1.123 + bool run(Node s,Node t) {
1.124 + init();
1.125 + addSource(s);
1.126 + start(t);
1.127 + return reached(t);
1.128 + }
1.129 +
1.130 /// \brief Runs the algorithm to visit all nodes in the digraph.
1.131 ///
1.132 /// This method runs the %BFS algorithm in order to
2.1 --- a/lemon/dfs.h Tue Sep 23 18:42:49 2008 +0200
2.2 +++ b/lemon/dfs.h Fri Sep 26 12:40:11 2008 +0200
2.3 @@ -558,17 +558,17 @@
2.4 ///Executes the algorithm until the given target node is reached.
2.5 ///
2.6 ///This method runs the %DFS algorithm from the root node
2.7 - ///in order to compute the DFS path to \c dest.
2.8 + ///in order to compute the DFS path to \c t.
2.9 ///
2.10 ///The algorithm computes
2.11 - ///- the %DFS path to \c dest,
2.12 - ///- the distance of \c dest from the root in the %DFS tree.
2.13 + ///- the %DFS path to \c t,
2.14 + ///- the distance of \c t from the root in the %DFS tree.
2.15 ///
2.16 ///\pre init() must be called and a root node should be
2.17 ///added with addSource() before using this function.
2.18 - void start(Node dest)
2.19 + void start(Node t)
2.20 {
2.21 - while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
2.22 + while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
2.23 processNextArc();
2.24 }
2.25
2.26 @@ -598,7 +598,7 @@
2.27 return emptyQueue() ? INVALID : _stack[_stack_head];
2.28 }
2.29
2.30 - ///Runs the algorithm from the given node.
2.31 + ///Runs the algorithm from the given source node.
2.32
2.33 ///This method runs the %DFS algorithm from node \c s
2.34 ///in order to compute the DFS path to each node.
2.35 @@ -622,10 +622,10 @@
2.36 ///Finds the %DFS path between \c s and \c t.
2.37
2.38 ///This method runs the %DFS algorithm from node \c s
2.39 - ///in order to compute the DFS path to \c t.
2.40 + ///in order to compute the DFS path to node \c t
2.41 + ///(it stops searching when \c t is processed)
2.42 ///
2.43 - ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
2.44 - ///if \c t is reachable form \c s, \c 0 otherwise.
2.45 + ///\return \c true if \c t is reachable form \c s.
2.46 ///
2.47 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
2.48 ///just a shortcut of the following code.
2.49 @@ -634,11 +634,11 @@
2.50 /// d.addSource(s);
2.51 /// d.start(t);
2.52 ///\endcode
2.53 - int run(Node s,Node t) {
2.54 + bool run(Node s,Node t) {
2.55 init();
2.56 addSource(s);
2.57 start(t);
2.58 - return reached(t)?_stack_head+1:0;
2.59 + return reached(t);
2.60 }
2.61
2.62 ///Runs the algorithm to visit all nodes in the digraph.
2.63 @@ -1526,16 +1526,16 @@
2.64 /// Executes the algorithm until the given target node is reached.
2.65 ///
2.66 /// This method runs the %DFS algorithm from the root node
2.67 - /// in order to compute the DFS path to \c dest.
2.68 + /// in order to compute the DFS path to \c t.
2.69 ///
2.70 /// The algorithm computes
2.71 - /// - the %DFS path to \c dest,
2.72 - /// - the distance of \c dest from the root in the %DFS tree.
2.73 + /// - the %DFS path to \c t,
2.74 + /// - the distance of \c t from the root in the %DFS tree.
2.75 ///
2.76 /// \pre init() must be called and a root node should be added
2.77 /// with addSource() before using this function.
2.78 - void start(Node dest) {
2.79 - while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
2.80 + void start(Node t) {
2.81 + while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
2.82 processNextArc();
2.83 }
2.84
2.85 @@ -1564,7 +1564,7 @@
2.86 return emptyQueue() ? INVALID : _stack[_stack_head];
2.87 }
2.88
2.89 - /// \brief Runs the algorithm from the given node.
2.90 + /// \brief Runs the algorithm from the given source node.
2.91 ///
2.92 /// This method runs the %DFS algorithm from node \c s.
2.93 /// in order to compute the DFS path to each node.
2.94 @@ -1588,10 +1588,10 @@
2.95 /// \brief Finds the %DFS path between \c s and \c t.
2.96
2.97 /// This method runs the %DFS algorithm from node \c s
2.98 - /// in order to compute the DFS path to \c t.
2.99 + /// in order to compute the DFS path to node \c t
2.100 + /// (it stops searching when \c t is processed).
2.101 ///
2.102 - /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
2.103 - /// if \c t is reachable form \c s, \c 0 otherwise.
2.104 + /// \return \c true if \c t is reachable form \c s.
2.105 ///
2.106 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
2.107 /// just a shortcut of the following code.
2.108 @@ -1600,11 +1600,11 @@
2.109 /// d.addSource(s);
2.110 /// d.start(t);
2.111 ///\endcode
2.112 - int run(Node s,Node t) {
2.113 + bool run(Node s,Node t) {
2.114 init();
2.115 addSource(s);
2.116 start(t);
2.117 - return reached(t)?_stack_head+1:0;
2.118 + return reached(t);
2.119 }
2.120
2.121 /// \brief Runs the algorithm to visit all nodes in the digraph.
3.1 --- a/lemon/dijkstra.h Tue Sep 23 18:42:49 2008 +0200
3.2 +++ b/lemon/dijkstra.h Fri Sep 26 12:40:11 2008 +0200
3.3 @@ -728,23 +728,26 @@
3.4 while ( !emptyQueue() ) processNextNode();
3.5 }
3.6
3.7 - ///Executes the algorithm until the given target node is reached.
3.8 + ///Executes the algorithm until the given target node is processed.
3.9
3.10 - ///Executes the algorithm until the given target node is reached.
3.11 + ///Executes the algorithm until the given target node is processed.
3.12 ///
3.13 ///This method runs the %Dijkstra algorithm from the root node(s)
3.14 - ///in order to compute the shortest path to \c dest.
3.15 + ///in order to compute the shortest path to \c t.
3.16 ///
3.17 ///The algorithm computes
3.18 - ///- the shortest path to \c dest,
3.19 - ///- the distance of \c dest from the root(s).
3.20 + ///- the shortest path to \c t,
3.21 + ///- the distance of \c t from the root(s).
3.22 ///
3.23 ///\pre init() must be called and at least one root node should be
3.24 ///added with addSource() before using this function.
3.25 - void start(Node dest)
3.26 + void start(Node t)
3.27 {
3.28 - while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
3.29 - if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
3.30 + while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
3.31 + if ( !_heap->empty() ) {
3.32 + finalizeNodeData(_heap->top(),_heap->prio());
3.33 + _heap->pop();
3.34 + }
3.35 }
3.36
3.37 ///Executes the algorithm until a condition is met.
3.38 @@ -772,7 +775,7 @@
3.39 return _heap->top();
3.40 }
3.41
3.42 - ///Runs the algorithm from the given node.
3.43 + ///Runs the algorithm from the given source node.
3.44
3.45 ///This method runs the %Dijkstra algorithm from node \c s
3.46 ///in order to compute the shortest path to each node.
3.47 @@ -796,10 +799,10 @@
3.48 ///Finds the shortest path between \c s and \c t.
3.49
3.50 ///This method runs the %Dijkstra algorithm from node \c s
3.51 - ///in order to compute the shortest path to \c t.
3.52 + ///in order to compute the shortest path to node \c t
3.53 + ///(it stops searching when \c t is processed).
3.54 ///
3.55 - ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
3.56 - ///if \c t is reachable form \c s, \c 0 otherwise.
3.57 + ///\return \c true if \c t is reachable form \c s.
3.58 ///
3.59 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
3.60 ///shortcut of the following code.
3.61 @@ -808,11 +811,11 @@
3.62 /// d.addSource(s);
3.63 /// d.start(t);
3.64 ///\endcode
3.65 - Value run(Node s,Node t) {
3.66 + bool run(Node s,Node t) {
3.67 init();
3.68 addSource(s);
3.69 start(t);
3.70 - return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
3.71 + return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
3.72 }
3.73
3.74 ///@}
3.75 @@ -908,7 +911,7 @@
3.76
3.77 ///Returns \c true if \c v is processed, i.e. the shortest
3.78 ///path to \c v has already found.
3.79 - ///\pre Either \ref run() or \ref start()
3.80 + ///\pre Either \ref run() or \ref init()
3.81 ///must be called before using this function.
3.82 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
3.83 Heap::POST_HEAP; }
3.84 @@ -917,8 +920,12 @@
3.85
3.86 ///Returns the current distance of a node from the root(s).
3.87 ///It may be decreased in the following processes.
3.88 - ///\pre \c v should be reached but not processed.
3.89 - Value currentDist(Node v) const { return (*_heap)[v]; }
3.90 + ///\pre Either \ref run() or \ref init()
3.91 + ///must be called before using this function and
3.92 + ///node \c v must be reached but not necessarily processed.
3.93 + Value currentDist(Node v) const {
3.94 + return processed(v) ? (*_dist)[v] : (*_heap)[v];
3.95 + }
3.96
3.97 ///@}
3.98 };
4.1 --- a/test/bfs_test.cc Tue Sep 23 18:42:49 2008 +0200
4.2 +++ b/test/bfs_test.cc Fri Sep 26 12:40:11 2008 +0200
4.3 @@ -54,27 +54,52 @@
4.4 {
4.5 typedef concepts::Digraph Digraph;
4.6 typedef Bfs<Digraph> BType;
4.7 + typedef Digraph::Node Node;
4.8 + typedef Digraph::Arc Arc;
4.9
4.10 Digraph G;
4.11 - Digraph::Node n;
4.12 - Digraph::Arc e;
4.13 + Node s, t;
4.14 + Arc e;
4.15 int l;
4.16 bool b;
4.17 BType::DistMap d(G);
4.18 BType::PredMap p(G);
4.19 + Path<Digraph> pp;
4.20
4.21 - BType bfs_test(G);
4.22 + {
4.23 + BType bfs_test(G);
4.24
4.25 - bfs_test.run(n);
4.26 + bfs_test.run(s);
4.27 + bfs_test.run(s,t);
4.28 + bfs_test.run();
4.29
4.30 - l = bfs_test.dist(n);
4.31 - e = bfs_test.predArc(n);
4.32 - n = bfs_test.predNode(n);
4.33 - d = bfs_test.distMap();
4.34 - p = bfs_test.predMap();
4.35 - b = bfs_test.reached(n);
4.36 + l = bfs_test.dist(t);
4.37 + e = bfs_test.predArc(t);
4.38 + s = bfs_test.predNode(t);
4.39 + b = bfs_test.reached(t);
4.40 + d = bfs_test.distMap();
4.41 + p = bfs_test.predMap();
4.42 + pp = bfs_test.path(t);
4.43 + }
4.44 + {
4.45 + BType
4.46 + ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
4.47 + ::SetDistMap<concepts::ReadWriteMap<Node,int> >
4.48 + ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
4.49 + ::SetProcessedMap<concepts::WriteMap<Node,bool> >
4.50 + ::SetStandardProcessedMap
4.51 + ::Create bfs_test(G);
4.52
4.53 - Path<Digraph> pp = bfs_test.path(n);
4.54 + bfs_test.run(s);
4.55 + bfs_test.run(s,t);
4.56 + bfs_test.run();
4.57 +
4.58 + l = bfs_test.dist(t);
4.59 + e = bfs_test.predArc(t);
4.60 + s = bfs_test.predNode(t);
4.61 + b = bfs_test.reached(t);
4.62 + pp = bfs_test.path(t);
4.63 + }
4.64 }
4.65
4.66 void checkBfsFunctionCompile()
5.1 --- a/test/dfs_test.cc Tue Sep 23 18:42:49 2008 +0200
5.2 +++ b/test/dfs_test.cc Fri Sep 26 12:40:11 2008 +0200
5.3 @@ -56,27 +56,52 @@
5.4 {
5.5 typedef concepts::Digraph Digraph;
5.6 typedef Dfs<Digraph> DType;
5.7 + typedef Digraph::Node Node;
5.8 + typedef Digraph::Arc Arc;
5.9
5.10 Digraph G;
5.11 - Digraph::Node n;
5.12 - Digraph::Arc e;
5.13 + Node s, t;
5.14 + Arc e;
5.15 int l;
5.16 bool b;
5.17 DType::DistMap d(G);
5.18 DType::PredMap p(G);
5.19 + Path<Digraph> pp;
5.20
5.21 - DType dfs_test(G);
5.22 + {
5.23 + DType dfs_test(G);
5.24
5.25 - dfs_test.run(n);
5.26 + dfs_test.run(s);
5.27 + dfs_test.run(s,t);
5.28 + dfs_test.run();
5.29
5.30 - l = dfs_test.dist(n);
5.31 - e = dfs_test.predArc(n);
5.32 - n = dfs_test.predNode(n);
5.33 - d = dfs_test.distMap();
5.34 - p = dfs_test.predMap();
5.35 - b = dfs_test.reached(n);
5.36 + l = dfs_test.dist(t);
5.37 + e = dfs_test.predArc(t);
5.38 + s = dfs_test.predNode(t);
5.39 + b = dfs_test.reached(t);
5.40 + d = dfs_test.distMap();
5.41 + p = dfs_test.predMap();
5.42 + pp = dfs_test.path(t);
5.43 + }
5.44 + {
5.45 + DType
5.46 + ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
5.47 + ::SetDistMap<concepts::ReadWriteMap<Node,int> >
5.48 + ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
5.49 + ::SetProcessedMap<concepts::WriteMap<Node,bool> >
5.50 + ::SetStandardProcessedMap
5.51 + ::Create dfs_test(G);
5.52
5.53 - Path<Digraph> pp = dfs_test.path(n);
5.54 + dfs_test.run(s);
5.55 + dfs_test.run(s,t);
5.56 + dfs_test.run();
5.57 +
5.58 + l = dfs_test.dist(t);
5.59 + e = dfs_test.predArc(t);
5.60 + s = dfs_test.predNode(t);
5.61 + b = dfs_test.reached(t);
5.62 + pp = dfs_test.path(t);
5.63 + }
5.64 }
5.65
5.66 void checkDfsFunctionCompile()
6.1 --- a/test/dijkstra_test.cc Tue Sep 23 18:42:49 2008 +0200
6.2 +++ b/test/dijkstra_test.cc Fri Sep 26 12:40:11 2008 +0200
6.3 @@ -22,6 +22,7 @@
6.4 #include <lemon/lgf_reader.h>
6.5 #include <lemon/dijkstra.h>
6.6 #include <lemon/path.h>
6.7 +#include <lemon/bin_heap.h>
6.8
6.9 #include "graph_test.h"
6.10 #include "test_tools.h"
6.11 @@ -55,28 +56,54 @@
6.12 typedef concepts::Digraph Digraph;
6.13 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
6.14 typedef Dijkstra<Digraph, LengthMap> DType;
6.15 + typedef Digraph::Node Node;
6.16 + typedef Digraph::Arc Arc;
6.17
6.18 Digraph G;
6.19 - Digraph::Node n;
6.20 - Digraph::Arc e;
6.21 + Node s, t;
6.22 + Arc e;
6.23 VType l;
6.24 bool b;
6.25 DType::DistMap d(G);
6.26 DType::PredMap p(G);
6.27 LengthMap length;
6.28 + Path<Digraph> pp;
6.29
6.30 - DType dijkstra_test(G,length);
6.31 + {
6.32 + DType dijkstra_test(G,length);
6.33
6.34 - dijkstra_test.run(n);
6.35 + dijkstra_test.run(s);
6.36 + dijkstra_test.run(s,t);
6.37
6.38 - l = dijkstra_test.dist(n);
6.39 - e = dijkstra_test.predArc(n);
6.40 - n = dijkstra_test.predNode(n);
6.41 - d = dijkstra_test.distMap();
6.42 - p = dijkstra_test.predMap();
6.43 - b = dijkstra_test.reached(n);
6.44 + l = dijkstra_test.dist(t);
6.45 + e = dijkstra_test.predArc(t);
6.46 + s = dijkstra_test.predNode(t);
6.47 + b = dijkstra_test.reached(t);
6.48 + d = dijkstra_test.distMap();
6.49 + p = dijkstra_test.predMap();
6.50 + pp = dijkstra_test.path(t);
6.51 + }
6.52 + {
6.53 + DType
6.54 + ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
6.55 + ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
6.56 + ::SetProcessedMap<concepts::WriteMap<Node,bool> >
6.57 + ::SetStandardProcessedMap
6.58 + ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
6.59 + ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
6.60 + ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
6.61 + ::Create dijkstra_test(G,length);
6.62
6.63 - Path<Digraph> pp = dijkstra_test.path(n);
6.64 + dijkstra_test.run(s);
6.65 + dijkstra_test.run(s,t);
6.66 +
6.67 + l = dijkstra_test.dist(t);
6.68 + e = dijkstra_test.predArc(t);
6.69 + s = dijkstra_test.predNode(t);
6.70 + b = dijkstra_test.reached(t);
6.71 + pp = dijkstra_test.path(t);
6.72 + }
6.73 +
6.74 }
6.75
6.76 void checkDijkstraFunctionCompile()