# HG changeset patch # User alpar # Date 1094051321 0 # Node ID e06d0d16595fc662fc9af22e95315c709676ecf1 # Parent 83c49c272679da4a9d27716241583a21d308a470 - DFS class (bfs.h and bfs_test.cc) added - Bugfixes in Dijkstra and Bfs diff -r 83c49c272679 -r e06d0d16595f src/hugo/bfs.h --- a/src/hugo/bfs.h Wed Sep 01 09:04:07 2004 +0000 +++ b/src/hugo/bfs.h Wed Sep 01 15:08:41 2004 +0000 @@ -280,7 +280,7 @@ /// ///\pre \ref run() must be called before using this function. /// - bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; } + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } }; diff -r 83c49c272679 -r e06d0d16595f src/hugo/dfs.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/dfs.h Wed Sep 01 15:08:41 2004 +0000 @@ -0,0 +1,301 @@ +// -*- C++ -*- +#ifndef HUGO_DFS_H +#define HUGO_DFS_H + +///\ingroup flowalgs +///\file +///\brief Dfs algorithm. +/// +///\todo Revise Manual. + +#include +#include + +namespace hugo { + +/// \addtogroup flowalgs +/// @{ + + ///%Dfs algorithm class. + + ///This class provides an efficient implementation of %Dfs algorithm. + ///The edge lengths are passed to the algorithm using a + ///\ref ReadMapSkeleton "readable map", + ///so it is easy to change it to any kind of length. + /// + ///The type of the length is determined by the \c ValueType of the length map. + /// + ///It is also possible to change the underlying priority heap. + /// + ///\param GR The graph type the algorithm runs on. + ///\param LM This read-only + ///EdgeMap + ///determines the + ///lengths of the edges. It is read once for each edge, so the map + ///may involve in relatively time consuming process to compute the edge + ///length if it is necessary. The default map type is + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" + ///\param Heap The heap type used by the %Dfs + ///algorithm. The default + ///is using \ref BinHeap "binary heap". + /// + ///\author Jacint Szabo and Alpar Juttner + ///\todo We need a typedef-names should be standardized. (-: + ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap + ///should not be fixed. (Problematic to solve). + +#ifdef DOXYGEN + template +#else + template +#endif + class Dfs{ + public: + ///The type of the underlying graph. + typedef GR Graph; + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename Graph::template NodeMap PredMap; + ///\brief The type of the map that stores the last but one + ///nodes of the shortest paths. + typedef typename Graph::template NodeMap PredNodeMap; + ///The type of the map that stores the dists of the nodes. + typedef typename Graph::template NodeMap DistMap; + + private: + const Graph *G; + PredMap *predecessor; + bool local_predecessor; + PredNodeMap *pred_node; + bool local_pred_node; + DistMap *distance; + bool local_distance; + + //The source node of the last execution. + Node source; + + + ///Initialize maps. + + ///\todo Error if \c G or are \c NULL. + ///\todo Better memory allocation (instead of new). + void init_maps() + { +// if(!length) { +// local_length = true; +// length = new LM(G); +// } + if(!predecessor) { + local_predecessor = true; + predecessor = new PredMap(*G); + } + if(!pred_node) { + local_pred_node = true; + pred_node = new PredNodeMap(*G); + } + if(!distance) { + local_distance = true; + distance = new DistMap(*G); + } + } + + public : + Dfs(const Graph& _G) : + G(&_G), + predecessor(NULL), local_predecessor(false), + pred_node(NULL), local_pred_node(false), + distance(NULL), local_distance(false) + { } + + ~Dfs() + { + // if(local_length) delete length; + if(local_predecessor) delete predecessor; + if(local_pred_node) delete pred_node; + if(local_distance) delete distance; + } + + ///Sets the graph the algorithm will run on. + + ///Sets the graph the algorithm will run on. + ///\return (*this) + Dfs &setGraph(const Graph &_G) + { + G = &_G; + return *this; + } + ///Sets the length map. + + ///Sets the map storing the predecessor edges. + + ///Sets the map storing the predecessor edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dfs &setPredMap(PredMap &m) + { + if(local_predecessor) { + delete predecessor; + local_predecessor=false; + } + predecessor = &m; + return *this; + } + + ///Sets the map storing the predecessor nodes. + + ///Sets the map storing the predecessor nodes. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dfs &setPredNodeMap(PredNodeMap &m) + { + if(local_pred_node) { + delete pred_node; + local_pred_node=false; + } + pred_node = &m; + return *this; + } + + ///Sets the map storing the distances calculated by the algorithm. + + ///Sets the map storing the distances calculated by the algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Dfs &setDistMap(DistMap &m) + { + if(local_distance) { + delete distance; + local_distance=false; + } + distance = &m; + return *this; + } + + ///Runs %DFS algorithm from node \c s. + + ///This method runs the %DFS algorithm from a root node \c s + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root. + + void run(Node s) { + + init_maps(); + + source = s; + + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { + predecessor->set(u,INVALID); + pred_node->set(u,INVALID); + } + + int N=G->nodeNum(); + std::vector Q(N); + + int Qh=0; + + G->first(Q[Qh],s); + distance->set(s, 0); + + Node n=s; + Node m; + OutEdgeIt e; + do { + if((e=Q[Qh])!=INVALID) + if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) { + predecessor->set(m,e); + pred_node->set(m,n); + G->first(Q[++Qh],m); + distance->set(m,Qh); + n=m; + } + else ++Q[Qh]; + else if(--Qh>=0) n=G->tail(Q[Qh]); + } while(Qh>=0); + } + + ///The distance of a node from the root. + + ///Returns the distance of a node from the root. + ///\pre \ref run() must be called before using this function. + ///\warning If node \c v in unreachable from the root the return value + ///of this funcion is undefined. + int dist(Node v) const { return (*distance)[v]; } + + ///Returns the 'previous edge' of the shortest path tree. + + ///For a node \c v it returns the 'previous edge' of the shortest path tree, + ///i.e. it returns the last edge from a shortest path from the root to \c + ///v. It is \ref INVALID + ///if \c v is unreachable from the root or if \c v=s. The + ///shortest path tree used here is equal to the shortest path tree used in + ///\ref predNode(Node v). \pre \ref run() must be called before using + ///this function. + Edge pred(Node v) const { return (*predecessor)[v]; } + + ///Returns the 'previous node' of the shortest path tree. + + ///For a node \c v it returns the 'previous node' of the shortest path tree, + ///i.e. it returns the last but one node from a shortest path from the + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if + ///\c v=s. The shortest path tree used here is equal to the shortest path + ///tree used in \ref pred(Node v). \pre \ref run() must be called before + ///using this function. + Node predNode(Node v) const { return (*pred_node)[v]; } + + ///Returns a reference to the NodeMap of distances. + + ///Returns a reference to the NodeMap of distances. \pre \ref run() must + ///be called before using this function. + const DistMap &distMap() const { return *distance;} + + ///Returns a reference to the shortest path tree map. + + ///Returns a reference to the NodeMap of the edges of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *predecessor;} + + ///Returns a reference to the map of nodes of shortest paths. + + ///Returns a reference to the NodeMap of the last but one nodes of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. + const PredNodeMap &predNodeMap() const { return *pred_node;} + + ///Checks if a node is reachable from the root. + + ///Returns \c true if \c v is reachable from the root. + ///\warning The root node is reported to be reached! + /// + ///\pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } + + }; + + + // ********************************************************************** + // IMPLEMENTATIONS + // ********************************************************************** + +/// @} + +} //END OF NAMESPACE HUGO + +#endif + + diff -r 83c49c272679 -r e06d0d16595f src/hugo/dijkstra.h --- a/src/hugo/dijkstra.h Wed Sep 01 09:04:07 2004 +0000 +++ b/src/hugo/dijkstra.h Wed Sep 01 15:08:41 2004 +0000 @@ -279,6 +279,7 @@ ///shortest path tree used here is equal to the shortest path tree used in ///\ref predNode(Node v). \pre \ref run() must be called before using ///this function. + ///\todo predEdge could be a better name. Edge pred(Node v) const { return (*predecessor)[v]; } ///Returns the 'previous node' of the shortest path tree. @@ -317,7 +318,7 @@ ///\warning the root node is reported to be reached! ///\pre \ref run() must be called before using this function. /// - bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; } + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } }; diff -r 83c49c272679 -r e06d0d16595f src/test/Makefile.am --- a/src/test/Makefile.am Wed Sep 01 09:04:07 2004 +0000 +++ b/src/test/Makefile.am Wed Sep 01 15:08:41 2004 +0000 @@ -2,7 +2,7 @@ noinst_HEADERS = test_tools.h -check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \ +check_PROGRAMS = graph_test dijkstra_test bfs_test dfs_test time_measure_test \ error_test xy_test \ unionfind_test test_tools_pass test_tools_fail @@ -12,6 +12,7 @@ graph_test_SOURCES = graph_test.cc dijkstra_test_SOURCES = dijkstra_test.cc bfs_test_SOURCES = bfs_test.cc +dfs_test_SOURCES = dfs_test.cc unionfind_test_SOURCES = unionfind_test.cc time_measure_test_SOURCES = time_measure_test.cc error_test_SOURCES = error_test.cc diff -r 83c49c272679 -r e06d0d16595f src/test/bfs_test.cc --- a/src/test/bfs_test.cc Wed Sep 01 09:04:07 2004 +0000 +++ b/src/test/bfs_test.cc Wed Sep 01 15:08:41 2004 +0000 @@ -76,14 +76,17 @@ "Wrong output."); } - ///\bug This works only for integer lengths - for(NodeIt v(G); v==INVALID; ++v) - if ( bfs_test.reached(v) ) { + for(NodeIt v(G); v==INVALID; ++v) { + check(bfs_test.reached(v),"Each node should be reached."); + if ( bfs_test.pred(v)!=INVALID ) { Edge e=bfs_test.pred(v); Node u=G.tail(e); + check(u==bfs_test.predNode(v),"Wrong tree."); check(bfs_test.dist(v) - bfs_test.dist(u) == 1, - "Bad shortest path tree edge! Difference: " + "Wrong distance. Difference: " << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1)); } + } } + diff -r 83c49c272679 -r e06d0d16595f src/test/dfs_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/dfs_test.cc Wed Sep 01 15:08:41 2004 +0000 @@ -0,0 +1,79 @@ +#include "test_tools.h" +#include +#include + +using namespace hugo; + +const int PET_SIZE =5; + + +void check_Dfs_SmartGraph_Compile() +{ + typedef int VType; + typedef SmartGraph Graph; + + typedef Graph::Edge Edge; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + typedef Graph::NodeIt NodeIt; + typedef Graph::EdgeMap LengthMap; + + typedef Dfs BType; + + Graph G; + Node n; + Edge e; + VType l; + bool b; + BType::DistMap d(G); + BType::PredMap p(G); + BType::PredNodeMap pn(G); + LengthMap cap(G); + + BType dfs_test(G); + + dfs_test.run(n); + + l = dfs_test.dist(n); + e = dfs_test.pred(n); + n = dfs_test.predNode(n); + d = dfs_test.distMap(); + p = dfs_test.predMap(); + pn = dfs_test.predNodeMap(); + b = dfs_test.reached(n); + +} + +int main() +{ + + typedef SmartGraph Graph; + + typedef Graph::Edge Edge; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + typedef Graph::NodeIt NodeIt; + typedef Graph::EdgeMap LengthMap; + + Graph G; + Node s, t; + PetStruct ps = addPetersen(G,PET_SIZE); + + s=ps.outer[2]; + t=ps.inner[0]; + + Dfs dfs_test(G); + dfs_test.run(s); + + for(NodeIt v(G); v!=INVALID; ++v) { + check(dfs_test.reached(v),"Each node should be reached."); + if ( dfs_test.pred(v)!=INVALID ) { + Edge e=dfs_test.pred(v); + Node u=G.tail(e); + check(u==dfs_test.predNode(v),"Wrong tree."); + check(dfs_test.dist(v) - dfs_test.dist(u) == 1, + "Wrong distance." << dfs_test.dist(v) << " " <