1.1 --- a/src/hugo/bfs.h Wed Sep 01 09:04:07 2004 +0000
1.2 +++ b/src/hugo/bfs.h Wed Sep 01 15:08:41 2004 +0000
1.3 @@ -280,7 +280,7 @@
1.4 ///
1.5 ///\pre \ref run() must be called before using this function.
1.6 ///
1.7 - bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
1.8 + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.9
1.10 };
1.11
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/dfs.h Wed Sep 01 15:08:41 2004 +0000
2.3 @@ -0,0 +1,301 @@
2.4 +// -*- C++ -*-
2.5 +#ifndef HUGO_DFS_H
2.6 +#define HUGO_DFS_H
2.7 +
2.8 +///\ingroup flowalgs
2.9 +///\file
2.10 +///\brief Dfs algorithm.
2.11 +///
2.12 +///\todo Revise Manual.
2.13 +
2.14 +#include <hugo/bin_heap.h>
2.15 +#include <hugo/invalid.h>
2.16 +
2.17 +namespace hugo {
2.18 +
2.19 +/// \addtogroup flowalgs
2.20 +/// @{
2.21 +
2.22 + ///%Dfs algorithm class.
2.23 +
2.24 + ///This class provides an efficient implementation of %Dfs algorithm.
2.25 + ///The edge lengths are passed to the algorithm using a
2.26 + ///\ref ReadMapSkeleton "readable map",
2.27 + ///so it is easy to change it to any kind of length.
2.28 + ///
2.29 + ///The type of the length is determined by the \c ValueType of the length map.
2.30 + ///
2.31 + ///It is also possible to change the underlying priority heap.
2.32 + ///
2.33 + ///\param GR The graph type the algorithm runs on.
2.34 + ///\param LM This read-only
2.35 + ///EdgeMap
2.36 + ///determines the
2.37 + ///lengths of the edges. It is read once for each edge, so the map
2.38 + ///may involve in relatively time consuming process to compute the edge
2.39 + ///length if it is necessary. The default map type is
2.40 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
2.41 + ///\param Heap The heap type used by the %Dfs
2.42 + ///algorithm. The default
2.43 + ///is using \ref BinHeap "binary heap".
2.44 + ///
2.45 + ///\author Jacint Szabo and Alpar Juttner
2.46 + ///\todo We need a typedef-names should be standardized. (-:
2.47 + ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
2.48 + ///should not be fixed. (Problematic to solve).
2.49 +
2.50 +#ifdef DOXYGEN
2.51 + template <typename GR>
2.52 +#else
2.53 + template <typename GR>
2.54 +#endif
2.55 + class Dfs{
2.56 + public:
2.57 + ///The type of the underlying graph.
2.58 + typedef GR Graph;
2.59 + typedef typename Graph::Node Node;
2.60 + typedef typename Graph::NodeIt NodeIt;
2.61 + typedef typename Graph::Edge Edge;
2.62 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.63 +
2.64 + ///\brief The type of the map that stores the last
2.65 + ///edges of the shortest paths.
2.66 + typedef typename Graph::template NodeMap<Edge> PredMap;
2.67 + ///\brief The type of the map that stores the last but one
2.68 + ///nodes of the shortest paths.
2.69 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
2.70 + ///The type of the map that stores the dists of the nodes.
2.71 + typedef typename Graph::template NodeMap<int> DistMap;
2.72 +
2.73 + private:
2.74 + const Graph *G;
2.75 + PredMap *predecessor;
2.76 + bool local_predecessor;
2.77 + PredNodeMap *pred_node;
2.78 + bool local_pred_node;
2.79 + DistMap *distance;
2.80 + bool local_distance;
2.81 +
2.82 + //The source node of the last execution.
2.83 + Node source;
2.84 +
2.85 +
2.86 + ///Initialize maps.
2.87 +
2.88 + ///\todo Error if \c G or are \c NULL.
2.89 + ///\todo Better memory allocation (instead of new).
2.90 + void init_maps()
2.91 + {
2.92 +// if(!length) {
2.93 +// local_length = true;
2.94 +// length = new LM(G);
2.95 +// }
2.96 + if(!predecessor) {
2.97 + local_predecessor = true;
2.98 + predecessor = new PredMap(*G);
2.99 + }
2.100 + if(!pred_node) {
2.101 + local_pred_node = true;
2.102 + pred_node = new PredNodeMap(*G);
2.103 + }
2.104 + if(!distance) {
2.105 + local_distance = true;
2.106 + distance = new DistMap(*G);
2.107 + }
2.108 + }
2.109 +
2.110 + public :
2.111 + Dfs(const Graph& _G) :
2.112 + G(&_G),
2.113 + predecessor(NULL), local_predecessor(false),
2.114 + pred_node(NULL), local_pred_node(false),
2.115 + distance(NULL), local_distance(false)
2.116 + { }
2.117 +
2.118 + ~Dfs()
2.119 + {
2.120 + // if(local_length) delete length;
2.121 + if(local_predecessor) delete predecessor;
2.122 + if(local_pred_node) delete pred_node;
2.123 + if(local_distance) delete distance;
2.124 + }
2.125 +
2.126 + ///Sets the graph the algorithm will run on.
2.127 +
2.128 + ///Sets the graph the algorithm will run on.
2.129 + ///\return <tt> (*this) </tt>
2.130 + Dfs &setGraph(const Graph &_G)
2.131 + {
2.132 + G = &_G;
2.133 + return *this;
2.134 + }
2.135 + ///Sets the length map.
2.136 +
2.137 + ///Sets the map storing the predecessor edges.
2.138 +
2.139 + ///Sets the map storing the predecessor edges.
2.140 + ///If you don't use this function before calling \ref run(),
2.141 + ///it will allocate one. The destuctor deallocates this
2.142 + ///automatically allocated map, of course.
2.143 + ///\return <tt> (*this) </tt>
2.144 + Dfs &setPredMap(PredMap &m)
2.145 + {
2.146 + if(local_predecessor) {
2.147 + delete predecessor;
2.148 + local_predecessor=false;
2.149 + }
2.150 + predecessor = &m;
2.151 + return *this;
2.152 + }
2.153 +
2.154 + ///Sets the map storing the predecessor nodes.
2.155 +
2.156 + ///Sets the map storing the predecessor nodes.
2.157 + ///If you don't use this function before calling \ref run(),
2.158 + ///it will allocate one. The destuctor deallocates this
2.159 + ///automatically allocated map, of course.
2.160 + ///\return <tt> (*this) </tt>
2.161 + Dfs &setPredNodeMap(PredNodeMap &m)
2.162 + {
2.163 + if(local_pred_node) {
2.164 + delete pred_node;
2.165 + local_pred_node=false;
2.166 + }
2.167 + pred_node = &m;
2.168 + return *this;
2.169 + }
2.170 +
2.171 + ///Sets the map storing the distances calculated by the algorithm.
2.172 +
2.173 + ///Sets the map storing the distances calculated by the algorithm.
2.174 + ///If you don't use this function before calling \ref run(),
2.175 + ///it will allocate one. The destuctor deallocates this
2.176 + ///automatically allocated map, of course.
2.177 + ///\return <tt> (*this) </tt>
2.178 + Dfs &setDistMap(DistMap &m)
2.179 + {
2.180 + if(local_distance) {
2.181 + delete distance;
2.182 + local_distance=false;
2.183 + }
2.184 + distance = &m;
2.185 + return *this;
2.186 + }
2.187 +
2.188 + ///Runs %DFS algorithm from node \c s.
2.189 +
2.190 + ///This method runs the %DFS algorithm from a root node \c s
2.191 + ///in order to
2.192 + ///compute the
2.193 + ///shortest path to each node. The algorithm computes
2.194 + ///- The shortest path tree.
2.195 + ///- The distance of each node from the root.
2.196 +
2.197 + void run(Node s) {
2.198 +
2.199 + init_maps();
2.200 +
2.201 + source = s;
2.202 +
2.203 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
2.204 + predecessor->set(u,INVALID);
2.205 + pred_node->set(u,INVALID);
2.206 + }
2.207 +
2.208 + int N=G->nodeNum();
2.209 + std::vector<typename Graph::OutEdgeIt> Q(N);
2.210 +
2.211 + int Qh=0;
2.212 +
2.213 + G->first(Q[Qh],s);
2.214 + distance->set(s, 0);
2.215 +
2.216 + Node n=s;
2.217 + Node m;
2.218 + OutEdgeIt e;
2.219 + do {
2.220 + if((e=Q[Qh])!=INVALID)
2.221 + if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {
2.222 + predecessor->set(m,e);
2.223 + pred_node->set(m,n);
2.224 + G->first(Q[++Qh],m);
2.225 + distance->set(m,Qh);
2.226 + n=m;
2.227 + }
2.228 + else ++Q[Qh];
2.229 + else if(--Qh>=0) n=G->tail(Q[Qh]);
2.230 + } while(Qh>=0);
2.231 + }
2.232 +
2.233 + ///The distance of a node from the root.
2.234 +
2.235 + ///Returns the distance of a node from the root.
2.236 + ///\pre \ref run() must be called before using this function.
2.237 + ///\warning If node \c v in unreachable from the root the return value
2.238 + ///of this funcion is undefined.
2.239 + int dist(Node v) const { return (*distance)[v]; }
2.240 +
2.241 + ///Returns the 'previous edge' of the shortest path tree.
2.242 +
2.243 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
2.244 + ///i.e. it returns the last edge from a shortest path from the root to \c
2.245 + ///v. It is \ref INVALID
2.246 + ///if \c v is unreachable from the root or if \c v=s. The
2.247 + ///shortest path tree used here is equal to the shortest path tree used in
2.248 + ///\ref predNode(Node v). \pre \ref run() must be called before using
2.249 + ///this function.
2.250 + Edge pred(Node v) const { return (*predecessor)[v]; }
2.251 +
2.252 + ///Returns the 'previous node' of the shortest path tree.
2.253 +
2.254 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
2.255 + ///i.e. it returns the last but one node from a shortest path from the
2.256 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
2.257 + ///\c v=s. The shortest path tree used here is equal to the shortest path
2.258 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
2.259 + ///using this function.
2.260 + Node predNode(Node v) const { return (*pred_node)[v]; }
2.261 +
2.262 + ///Returns a reference to the NodeMap of distances.
2.263 +
2.264 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
2.265 + ///be called before using this function.
2.266 + const DistMap &distMap() const { return *distance;}
2.267 +
2.268 + ///Returns a reference to the shortest path tree map.
2.269 +
2.270 + ///Returns a reference to the NodeMap of the edges of the
2.271 + ///shortest path tree.
2.272 + ///\pre \ref run() must be called before using this function.
2.273 + const PredMap &predMap() const { return *predecessor;}
2.274 +
2.275 + ///Returns a reference to the map of nodes of shortest paths.
2.276 +
2.277 + ///Returns a reference to the NodeMap of the last but one nodes of the
2.278 + ///shortest path tree.
2.279 + ///\pre \ref run() must be called before using this function.
2.280 + const PredNodeMap &predNodeMap() const { return *pred_node;}
2.281 +
2.282 + ///Checks if a node is reachable from the root.
2.283 +
2.284 + ///Returns \c true if \c v is reachable from the root.
2.285 + ///\warning The root node is reported to be reached!
2.286 + ///
2.287 + ///\pre \ref run() must be called before using this function.
2.288 + ///
2.289 + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
2.290 +
2.291 + };
2.292 +
2.293 +
2.294 + // **********************************************************************
2.295 + // IMPLEMENTATIONS
2.296 + // **********************************************************************
2.297 +
2.298 +/// @}
2.299 +
2.300 +} //END OF NAMESPACE HUGO
2.301 +
2.302 +#endif
2.303 +
2.304 +
3.1 --- a/src/hugo/dijkstra.h Wed Sep 01 09:04:07 2004 +0000
3.2 +++ b/src/hugo/dijkstra.h Wed Sep 01 15:08:41 2004 +0000
3.3 @@ -279,6 +279,7 @@
3.4 ///shortest path tree used here is equal to the shortest path tree used in
3.5 ///\ref predNode(Node v). \pre \ref run() must be called before using
3.6 ///this function.
3.7 + ///\todo predEdge could be a better name.
3.8 Edge pred(Node v) const { return (*predecessor)[v]; }
3.9
3.10 ///Returns the 'previous node' of the shortest path tree.
3.11 @@ -317,7 +318,7 @@
3.12 ///\warning the root node is reported to be reached!
3.13 ///\pre \ref run() must be called before using this function.
3.14 ///
3.15 - bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
3.16 + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
3.17
3.18 };
3.19
4.1 --- a/src/test/Makefile.am Wed Sep 01 09:04:07 2004 +0000
4.2 +++ b/src/test/Makefile.am Wed Sep 01 15:08:41 2004 +0000
4.3 @@ -2,7 +2,7 @@
4.4
4.5 noinst_HEADERS = test_tools.h
4.6
4.7 -check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
4.8 +check_PROGRAMS = graph_test dijkstra_test bfs_test dfs_test time_measure_test \
4.9 error_test xy_test \
4.10 unionfind_test test_tools_pass test_tools_fail
4.11
4.12 @@ -12,6 +12,7 @@
4.13 graph_test_SOURCES = graph_test.cc
4.14 dijkstra_test_SOURCES = dijkstra_test.cc
4.15 bfs_test_SOURCES = bfs_test.cc
4.16 +dfs_test_SOURCES = dfs_test.cc
4.17 unionfind_test_SOURCES = unionfind_test.cc
4.18 time_measure_test_SOURCES = time_measure_test.cc
4.19 error_test_SOURCES = error_test.cc
5.1 --- a/src/test/bfs_test.cc Wed Sep 01 09:04:07 2004 +0000
5.2 +++ b/src/test/bfs_test.cc Wed Sep 01 15:08:41 2004 +0000
5.3 @@ -76,14 +76,17 @@
5.4 "Wrong output.");
5.5 }
5.6
5.7 - ///\bug This works only for integer lengths
5.8 - for(NodeIt v(G); v==INVALID; ++v)
5.9 - if ( bfs_test.reached(v) ) {
5.10 + for(NodeIt v(G); v==INVALID; ++v) {
5.11 + check(bfs_test.reached(v),"Each node should be reached.");
5.12 + if ( bfs_test.pred(v)!=INVALID ) {
5.13 Edge e=bfs_test.pred(v);
5.14 Node u=G.tail(e);
5.15 + check(u==bfs_test.predNode(v),"Wrong tree.");
5.16 check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
5.17 - "Bad shortest path tree edge! Difference: "
5.18 + "Wrong distance. Difference: "
5.19 << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
5.20 - 1));
5.21 }
5.22 + }
5.23 }
5.24 +
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/test/dfs_test.cc Wed Sep 01 15:08:41 2004 +0000
6.3 @@ -0,0 +1,79 @@
6.4 +#include "test_tools.h"
6.5 +#include <hugo/smart_graph.h>
6.6 +#include <hugo/dfs.h>
6.7 +
6.8 +using namespace hugo;
6.9 +
6.10 +const int PET_SIZE =5;
6.11 +
6.12 +
6.13 +void check_Dfs_SmartGraph_Compile()
6.14 +{
6.15 + typedef int VType;
6.16 + typedef SmartGraph Graph;
6.17 +
6.18 + typedef Graph::Edge Edge;
6.19 + typedef Graph::Node Node;
6.20 + typedef Graph::EdgeIt EdgeIt;
6.21 + typedef Graph::NodeIt NodeIt;
6.22 + typedef Graph::EdgeMap<VType> LengthMap;
6.23 +
6.24 + typedef Dfs<Graph> BType;
6.25 +
6.26 + Graph G;
6.27 + Node n;
6.28 + Edge e;
6.29 + VType l;
6.30 + bool b;
6.31 + BType::DistMap d(G);
6.32 + BType::PredMap p(G);
6.33 + BType::PredNodeMap pn(G);
6.34 + LengthMap cap(G);
6.35 +
6.36 + BType dfs_test(G);
6.37 +
6.38 + dfs_test.run(n);
6.39 +
6.40 + l = dfs_test.dist(n);
6.41 + e = dfs_test.pred(n);
6.42 + n = dfs_test.predNode(n);
6.43 + d = dfs_test.distMap();
6.44 + p = dfs_test.predMap();
6.45 + pn = dfs_test.predNodeMap();
6.46 + b = dfs_test.reached(n);
6.47 +
6.48 +}
6.49 +
6.50 +int main()
6.51 +{
6.52 +
6.53 + typedef SmartGraph Graph;
6.54 +
6.55 + typedef Graph::Edge Edge;
6.56 + typedef Graph::Node Node;
6.57 + typedef Graph::EdgeIt EdgeIt;
6.58 + typedef Graph::NodeIt NodeIt;
6.59 + typedef Graph::EdgeMap<int> LengthMap;
6.60 +
6.61 + Graph G;
6.62 + Node s, t;
6.63 + PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
6.64 +
6.65 + s=ps.outer[2];
6.66 + t=ps.inner[0];
6.67 +
6.68 + Dfs<Graph> dfs_test(G);
6.69 + dfs_test.run(s);
6.70 +
6.71 + for(NodeIt v(G); v!=INVALID; ++v) {
6.72 + check(dfs_test.reached(v),"Each node should be reached.");
6.73 + if ( dfs_test.pred(v)!=INVALID ) {
6.74 + Edge e=dfs_test.pred(v);
6.75 + Node u=G.tail(e);
6.76 + check(u==dfs_test.predNode(v),"Wrong tree.");
6.77 + check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
6.78 + "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
6.79 + }
6.80 + }
6.81 +}
6.82 +
7.1 --- a/src/test/dijkstra_test.cc Wed Sep 01 09:04:07 2004 +0000
7.2 +++ b/src/test/dijkstra_test.cc Wed Sep 01 15:08:41 2004 +0000
7.3 @@ -86,13 +86,17 @@
7.4 }
7.5
7.6 ///\bug This works only for integer lengths
7.7 - for(NodeIt v(G); v!=INVALID; ++v)
7.8 - if ( dijkstra_test.reached(v) ) {
7.9 + for(NodeIt v(G); v!=INVALID; ++v){
7.10 + check(dijkstra_test.reached(v),"Each node should be reached.");
7.11 + if ( dijkstra_test.pred(v)!=INVALID ) {
7.12 Edge e=dijkstra_test.pred(v);
7.13 Node u=G.tail(e);
7.14 + check(u==dijkstra_test.predNode(v),"Wrong tree.");
7.15 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
7.16 - "Bad shortest path tree edge! Difference: "
7.17 + "Wrong distance! Difference: "
7.18 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
7.19 - cap[e]));
7.20 }
7.21 + }
7.22 }
7.23 +