1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/bfs.h Mon Aug 30 12:01:47 2004 +0000
1.3 @@ -0,0 +1,298 @@
1.4 +// -*- C++ -*-
1.5 +#ifndef HUGO_BFS_H
1.6 +#define HUGO_BFS_H
1.7 +
1.8 +///\ingroup flowalgs
1.9 +///\file
1.10 +///\brief Bfs 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 + ///%Bfs algorithm class.
1.23 +
1.24 + ///This class provides an efficient implementation of %Bfs 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 %Bfs
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 Bfs{
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 + Bfs(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 + ~Bfs()
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 + Bfs &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 + Bfs &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 + Bfs &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 + Bfs &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 %BFS algorithm from node \c s.
1.189 +
1.190 + ///This method runs the %BFS 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::Node> Q(N);
1.210 + int Qh=0;
1.211 + int Qt=0;
1.212 +
1.213 + Q[Qh++]=source;
1.214 + distance->set(s, 0);
1.215 + do {
1.216 + Node m;
1.217 + Node n=Q[Qt++];
1.218 + int d= (*distance)[n]+1;
1.219 +
1.220 + for(OutEdgeIt e(*G,n);e!=INVALID;++e)
1.221 + if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
1.222 + Q[Qh++]=m;
1.223 + predecessor->set(m,e);
1.224 + pred_node->set(m,n);
1.225 + distance->set(m,d);
1.226 + }
1.227 + } while(Qt!=Qh);
1.228 + }
1.229 +
1.230 + ///The distance of a node from the root.
1.231 +
1.232 + ///Returns the distance of a node from the root.
1.233 + ///\pre \ref run() must be called before using this function.
1.234 + ///\warning If node \c v in unreachable from the root the return value
1.235 + ///of this funcion is undefined.
1.236 + int dist(Node v) const { return (*distance)[v]; }
1.237 +
1.238 + ///Returns the 'previous edge' of the shortest path tree.
1.239 +
1.240 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
1.241 + ///i.e. it returns the last edge from a shortest path from the root to \c
1.242 + ///v. It is \ref INVALID
1.243 + ///if \c v is unreachable from the root or if \c v=s. The
1.244 + ///shortest path tree used here is equal to the shortest path tree used in
1.245 + ///\ref predNode(Node v). \pre \ref run() must be called before using
1.246 + ///this function.
1.247 + Edge pred(Node v) const { return (*predecessor)[v]; }
1.248 +
1.249 + ///Returns the 'previous node' of the shortest path tree.
1.250 +
1.251 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.252 + ///i.e. it returns the last but one node from a shortest path from the
1.253 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.254 + ///\c v=s. The shortest path tree used here is equal to the shortest path
1.255 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.256 + ///using this function.
1.257 + Node predNode(Node v) const { return (*pred_node)[v]; }
1.258 +
1.259 + ///Returns a reference to the NodeMap of distances.
1.260 +
1.261 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.262 + ///be called before using this function.
1.263 + const DistMap &distMap() const { return *distance;}
1.264 +
1.265 + ///Returns a reference to the shortest path tree map.
1.266 +
1.267 + ///Returns a reference to the NodeMap of the edges of the
1.268 + ///shortest path tree.
1.269 + ///\pre \ref run() must be called before using this function.
1.270 + const PredMap &predMap() const { return *predecessor;}
1.271 +
1.272 + ///Returns a reference to the map of nodes of shortest paths.
1.273 +
1.274 + ///Returns a reference to the NodeMap of the last but one nodes of the
1.275 + ///shortest path tree.
1.276 + ///\pre \ref run() must be called before using this function.
1.277 + const PredNodeMap &predNodeMap() const { return *pred_node;}
1.278 +
1.279 + ///Checks if a node is reachable from the root.
1.280 +
1.281 + ///Returns \c true if \c v is reachable from the root.
1.282 + ///\warning The root node is reported to be reached!
1.283 + ///
1.284 + ///\pre \ref run() must be called before using this function.
1.285 + ///
1.286 + bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
1.287 +
1.288 + };
1.289 +
1.290 +
1.291 + // **********************************************************************
1.292 + // IMPLEMENTATIONS
1.293 + // **********************************************************************
1.294 +
1.295 +/// @}
1.296 +
1.297 +} //END OF NAMESPACE HUGO
1.298 +
1.299 +#endif
1.300 +
1.301 +