1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/dfs.h Wed Sep 01 15:08:41 2004 +0000
1.3 @@ -0,0 +1,301 @@
1.4 +// -*- C++ -*-
1.5 +#ifndef HUGO_DFS_H
1.6 +#define HUGO_DFS_H
1.7 +
1.8 +///\ingroup flowalgs
1.9 +///\file
1.10 +///\brief Dfs algorithm.
1.11 +///
1.12 +///\todo Revise Manual.
1.13 +
1.14 +#include <hugo/bin_heap.h>
1.15 +#include <hugo/invalid.h>
1.16 +
1.17 +namespace hugo {
1.18 +
1.19 +/// \addtogroup flowalgs
1.20 +/// @{
1.21 +
1.22 + ///%Dfs algorithm class.
1.23 +
1.24 + ///This class provides an efficient implementation of %Dfs algorithm.
1.25 + ///The edge lengths are passed to the algorithm using a
1.26 + ///\ref ReadMapSkeleton "readable map",
1.27 + ///so it is easy to change it to any kind of length.
1.28 + ///
1.29 + ///The type of the length is determined by the \c ValueType of the length map.
1.30 + ///
1.31 + ///It is also possible to change the underlying priority heap.
1.32 + ///
1.33 + ///\param GR The graph type the algorithm runs on.
1.34 + ///\param LM This read-only
1.35 + ///EdgeMap
1.36 + ///determines the
1.37 + ///lengths of the edges. It is read once for each edge, so the map
1.38 + ///may involve in relatively time consuming process to compute the edge
1.39 + ///length if it is necessary. The default map type is
1.40 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.41 + ///\param Heap The heap type used by the %Dfs
1.42 + ///algorithm. The default
1.43 + ///is using \ref BinHeap "binary heap".
1.44 + ///
1.45 + ///\author Jacint Szabo and Alpar Juttner
1.46 + ///\todo We need a typedef-names should be standardized. (-:
1.47 + ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
1.48 + ///should not be fixed. (Problematic to solve).
1.49 +
1.50 +#ifdef DOXYGEN
1.51 + template <typename GR>
1.52 +#else
1.53 + template <typename GR>
1.54 +#endif
1.55 + class Dfs{
1.56 + public:
1.57 + ///The type of the underlying graph.
1.58 + typedef GR Graph;
1.59 + typedef typename Graph::Node Node;
1.60 + typedef typename Graph::NodeIt NodeIt;
1.61 + typedef typename Graph::Edge Edge;
1.62 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.63 +
1.64 + ///\brief The type of the map that stores the last
1.65 + ///edges of the shortest paths.
1.66 + typedef typename Graph::template NodeMap<Edge> PredMap;
1.67 + ///\brief The type of the map that stores the last but one
1.68 + ///nodes of the shortest paths.
1.69 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.70 + ///The type of the map that stores the dists of the nodes.
1.71 + typedef typename Graph::template NodeMap<int> DistMap;
1.72 +
1.73 + private:
1.74 + const Graph *G;
1.75 + PredMap *predecessor;
1.76 + bool local_predecessor;
1.77 + PredNodeMap *pred_node;
1.78 + bool local_pred_node;
1.79 + DistMap *distance;
1.80 + bool local_distance;
1.81 +
1.82 + //The source node of the last execution.
1.83 + Node source;
1.84 +
1.85 +
1.86 + ///Initialize maps.
1.87 +
1.88 + ///\todo Error if \c G or are \c NULL.
1.89 + ///\todo Better memory allocation (instead of new).
1.90 + void init_maps()
1.91 + {
1.92 +// if(!length) {
1.93 +// local_length = true;
1.94 +// length = new LM(G);
1.95 +// }
1.96 + if(!predecessor) {
1.97 + local_predecessor = true;
1.98 + predecessor = new PredMap(*G);
1.99 + }
1.100 + if(!pred_node) {
1.101 + local_pred_node = true;
1.102 + pred_node = new PredNodeMap(*G);
1.103 + }
1.104 + if(!distance) {
1.105 + local_distance = true;
1.106 + distance = new DistMap(*G);
1.107 + }
1.108 + }
1.109 +
1.110 + public :
1.111 + Dfs(const Graph& _G) :
1.112 + G(&_G),
1.113 + predecessor(NULL), local_predecessor(false),
1.114 + pred_node(NULL), local_pred_node(false),
1.115 + distance(NULL), local_distance(false)
1.116 + { }
1.117 +
1.118 + ~Dfs()
1.119 + {
1.120 + // if(local_length) delete length;
1.121 + if(local_predecessor) delete predecessor;
1.122 + if(local_pred_node) delete pred_node;
1.123 + if(local_distance) delete distance;
1.124 + }
1.125 +
1.126 + ///Sets the graph the algorithm will run on.
1.127 +
1.128 + ///Sets the graph the algorithm will run on.
1.129 + ///\return <tt> (*this) </tt>
1.130 + Dfs &setGraph(const Graph &_G)
1.131 + {
1.132 + G = &_G;
1.133 + return *this;
1.134 + }
1.135 + ///Sets the length map.
1.136 +
1.137 + ///Sets the map storing the predecessor edges.
1.138 +
1.139 + ///Sets the map storing the predecessor edges.
1.140 + ///If you don't use this function before calling \ref run(),
1.141 + ///it will allocate one. The destuctor deallocates this
1.142 + ///automatically allocated map, of course.
1.143 + ///\return <tt> (*this) </tt>
1.144 + Dfs &setPredMap(PredMap &m)
1.145 + {
1.146 + if(local_predecessor) {
1.147 + delete predecessor;
1.148 + local_predecessor=false;
1.149 + }
1.150 + predecessor = &m;
1.151 + return *this;
1.152 + }
1.153 +
1.154 + ///Sets the map storing the predecessor nodes.
1.155 +
1.156 + ///Sets the map storing the predecessor nodes.
1.157 + ///If you don't use this function before calling \ref run(),
1.158 + ///it will allocate one. The destuctor deallocates this
1.159 + ///automatically allocated map, of course.
1.160 + ///\return <tt> (*this) </tt>
1.161 + Dfs &setPredNodeMap(PredNodeMap &m)
1.162 + {
1.163 + if(local_pred_node) {
1.164 + delete pred_node;
1.165 + local_pred_node=false;
1.166 + }
1.167 + pred_node = &m;
1.168 + return *this;
1.169 + }
1.170 +
1.171 + ///Sets the map storing the distances calculated by the algorithm.
1.172 +
1.173 + ///Sets the map storing the distances calculated by the algorithm.
1.174 + ///If you don't use this function before calling \ref run(),
1.175 + ///it will allocate one. The destuctor deallocates this
1.176 + ///automatically allocated map, of course.
1.177 + ///\return <tt> (*this) </tt>
1.178 + Dfs &setDistMap(DistMap &m)
1.179 + {
1.180 + if(local_distance) {
1.181 + delete distance;
1.182 + local_distance=false;
1.183 + }
1.184 + distance = &m;
1.185 + return *this;
1.186 + }
1.187 +
1.188 + ///Runs %DFS algorithm from node \c s.
1.189 +
1.190 + ///This method runs the %DFS algorithm from a root node \c s
1.191 + ///in order to
1.192 + ///compute the
1.193 + ///shortest path to each node. The algorithm computes
1.194 + ///- The shortest path tree.
1.195 + ///- The distance of each node from the root.
1.196 +
1.197 + void run(Node s) {
1.198 +
1.199 + init_maps();
1.200 +
1.201 + source = s;
1.202 +
1.203 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.204 + predecessor->set(u,INVALID);
1.205 + pred_node->set(u,INVALID);
1.206 + }
1.207 +
1.208 + int N=G->nodeNum();
1.209 + std::vector<typename Graph::OutEdgeIt> Q(N);
1.210 +
1.211 + int Qh=0;
1.212 +
1.213 + G->first(Q[Qh],s);
1.214 + distance->set(s, 0);
1.215 +
1.216 + Node n=s;
1.217 + Node m;
1.218 + OutEdgeIt e;
1.219 + do {
1.220 + if((e=Q[Qh])!=INVALID)
1.221 + if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {
1.222 + predecessor->set(m,e);
1.223 + pred_node->set(m,n);
1.224 + G->first(Q[++Qh],m);
1.225 + distance->set(m,Qh);
1.226 + n=m;
1.227 + }
1.228 + else ++Q[Qh];
1.229 + else if(--Qh>=0) n=G->tail(Q[Qh]);
1.230 + } while(Qh>=0);
1.231 + }
1.232 +
1.233 + ///The distance of a node from the root.
1.234 +
1.235 + ///Returns the distance of a node from the root.
1.236 + ///\pre \ref run() must be called before using this function.
1.237 + ///\warning If node \c v in unreachable from the root the return value
1.238 + ///of this funcion is undefined.
1.239 + int dist(Node v) const { return (*distance)[v]; }
1.240 +
1.241 + ///Returns the 'previous edge' of the shortest path tree.
1.242 +
1.243 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
1.244 + ///i.e. it returns the last edge from a shortest path from the root to \c
1.245 + ///v. It is \ref INVALID
1.246 + ///if \c v is unreachable from the root or if \c v=s. The
1.247 + ///shortest path tree used here is equal to the shortest path tree used in
1.248 + ///\ref predNode(Node v). \pre \ref run() must be called before using
1.249 + ///this function.
1.250 + Edge pred(Node v) const { return (*predecessor)[v]; }
1.251 +
1.252 + ///Returns the 'previous node' of the shortest path tree.
1.253 +
1.254 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.255 + ///i.e. it returns the last but one node from a shortest path from the
1.256 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.257 + ///\c v=s. The shortest path tree used here is equal to the shortest path
1.258 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.259 + ///using this function.
1.260 + Node predNode(Node v) const { return (*pred_node)[v]; }
1.261 +
1.262 + ///Returns a reference to the NodeMap of distances.
1.263 +
1.264 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.265 + ///be called before using this function.
1.266 + const DistMap &distMap() const { return *distance;}
1.267 +
1.268 + ///Returns a reference to the shortest path tree map.
1.269 +
1.270 + ///Returns a reference to the NodeMap of the edges of the
1.271 + ///shortest path tree.
1.272 + ///\pre \ref run() must be called before using this function.
1.273 + const PredMap &predMap() const { return *predecessor;}
1.274 +
1.275 + ///Returns a reference to the map of nodes of shortest paths.
1.276 +
1.277 + ///Returns a reference to the NodeMap of the last but one nodes of the
1.278 + ///shortest path tree.
1.279 + ///\pre \ref run() must be called before using this function.
1.280 + const PredNodeMap &predNodeMap() const { return *pred_node;}
1.281 +
1.282 + ///Checks if a node is reachable from the root.
1.283 +
1.284 + ///Returns \c true if \c v is reachable from the root.
1.285 + ///\warning The root node is reported to be reached!
1.286 + ///
1.287 + ///\pre \ref run() must be called before using this function.
1.288 + ///
1.289 + bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.290 +
1.291 + };
1.292 +
1.293 +
1.294 + // **********************************************************************
1.295 + // IMPLEMENTATIONS
1.296 + // **********************************************************************
1.297 +
1.298 +/// @}
1.299 +
1.300 +} //END OF NAMESPACE HUGO
1.301 +
1.302 +#endif
1.303 +
1.304 +