1.1 --- a/src/hugo/bfs.h Wed Sep 29 14:12:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,286 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/hugo/bfs.h - Part of HUGOlib, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef HUGO_BFS_H
1.21 -#define HUGO_BFS_H
1.22 -
1.23 -///\ingroup flowalgs
1.24 -///\file
1.25 -///\brief Bfs algorithm.
1.26 -///
1.27 -///\todo Revise Manual.
1.28 -
1.29 -#include <hugo/bin_heap.h>
1.30 -#include <hugo/invalid.h>
1.31 -
1.32 -namespace hugo {
1.33 -
1.34 -/// \addtogroup flowalgs
1.35 -/// @{
1.36 -
1.37 - ///%BFS algorithm class.
1.38 -
1.39 - ///This class provides an efficient implementation of %BFS algorithm.
1.40 - ///\param GR The graph type the algorithm runs on.
1.41 - ///This class does the same as Dijkstra does with constant 1 edge length,
1.42 - ///but it is faster.
1.43 - ///
1.44 - ///\author Alpar Juttner
1.45 -
1.46 -#ifdef DOXYGEN
1.47 - template <typename GR>
1.48 -#else
1.49 - template <typename GR>
1.50 -#endif
1.51 - class Bfs{
1.52 - public:
1.53 - ///The type of the underlying graph.
1.54 - typedef GR Graph;
1.55 - ///\e
1.56 - typedef typename Graph::Node Node;
1.57 - ///\e
1.58 - typedef typename Graph::NodeIt NodeIt;
1.59 - ///\e
1.60 - typedef typename Graph::Edge Edge;
1.61 - ///\e
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 - /// Pointer to the underlying graph.
1.75 - const Graph *G;
1.76 - ///Pointer to the map of predecessors edges.
1.77 - PredMap *predecessor;
1.78 - ///Indicates if \ref predecessor is locally allocated (\c true) or not.
1.79 - bool local_predecessor;
1.80 - ///Pointer to the map of predecessors nodes.
1.81 - PredNodeMap *pred_node;
1.82 - ///Indicates if \ref pred_node is locally allocated (\c true) or not.
1.83 - bool local_pred_node;
1.84 - ///Pointer to the map of distances.
1.85 - DistMap *distance;
1.86 - ///Indicates if \ref distance is locally allocated (\c true) or not.
1.87 - bool local_distance;
1.88 -
1.89 - ///The source node of the last execution.
1.90 - Node source;
1.91 -
1.92 -
1.93 - ///Initializes the maps.
1.94 - void init_maps()
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 - ///Constructor.
1.112 -
1.113 - ///\param _G the graph the algorithm will run on.
1.114 - ///
1.115 - Bfs(const Graph& _G) :
1.116 - G(&_G),
1.117 - predecessor(NULL), local_predecessor(false),
1.118 - pred_node(NULL), local_pred_node(false),
1.119 - distance(NULL), local_distance(false)
1.120 - { }
1.121 -
1.122 - ///Destructor.
1.123 - ~Bfs()
1.124 - {
1.125 - if(local_predecessor) delete predecessor;
1.126 - if(local_pred_node) delete pred_node;
1.127 - if(local_distance) delete distance;
1.128 - }
1.129 -
1.130 - ///Sets the map storing the predecessor edges.
1.131 -
1.132 - ///Sets the map storing the predecessor edges.
1.133 - ///If you don't use this function before calling \ref run(),
1.134 - ///it will allocate one. The destuctor deallocates this
1.135 - ///automatically allocated map, of course.
1.136 - ///\return <tt> (*this) </tt>
1.137 - Bfs &setPredMap(PredMap &m)
1.138 - {
1.139 - if(local_predecessor) {
1.140 - delete predecessor;
1.141 - local_predecessor=false;
1.142 - }
1.143 - predecessor = &m;
1.144 - return *this;
1.145 - }
1.146 -
1.147 - ///Sets the map storing the predecessor nodes.
1.148 -
1.149 - ///Sets the map storing the predecessor nodes.
1.150 - ///If you don't use this function before calling \ref run(),
1.151 - ///it will allocate one. The destuctor deallocates this
1.152 - ///automatically allocated map, of course.
1.153 - ///\return <tt> (*this) </tt>
1.154 - Bfs &setPredNodeMap(PredNodeMap &m)
1.155 - {
1.156 - if(local_pred_node) {
1.157 - delete pred_node;
1.158 - local_pred_node=false;
1.159 - }
1.160 - pred_node = &m;
1.161 - return *this;
1.162 - }
1.163 -
1.164 - ///Sets the map storing the distances calculated by the algorithm.
1.165 -
1.166 - ///Sets the map storing the distances calculated by the algorithm.
1.167 - ///If you don't use this function before calling \ref run(),
1.168 - ///it will allocate one. The destuctor deallocates this
1.169 - ///automatically allocated map, of course.
1.170 - ///\return <tt> (*this) </tt>
1.171 - Bfs &setDistMap(DistMap &m)
1.172 - {
1.173 - if(local_distance) {
1.174 - delete distance;
1.175 - local_distance=false;
1.176 - }
1.177 - distance = &m;
1.178 - return *this;
1.179 - }
1.180 -
1.181 - ///Runs %BFS algorithm from node \c s.
1.182 -
1.183 - ///This method runs the %BFS algorithm from a root node \c s
1.184 - ///in order to
1.185 - ///compute a
1.186 - ///shortest path to each node. The algorithm computes
1.187 - ///- The %BFS tree.
1.188 - ///- The distance of each node from the root.
1.189 -
1.190 - void run(Node s) {
1.191 -
1.192 - init_maps();
1.193 -
1.194 - source = s;
1.195 -
1.196 - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.197 - predecessor->set(u,INVALID);
1.198 - pred_node->set(u,INVALID);
1.199 - }
1.200 -
1.201 - int N=G->nodeNum();
1.202 - std::vector<typename Graph::Node> Q(N);
1.203 - int Qh=0;
1.204 - int Qt=0;
1.205 -
1.206 - Q[Qh++]=source;
1.207 - distance->set(s, 0);
1.208 - do {
1.209 - Node m;
1.210 - Node n=Q[Qt++];
1.211 - int d= (*distance)[n]+1;
1.212 -
1.213 - for(OutEdgeIt e(*G,n);e!=INVALID;++e)
1.214 - if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
1.215 - Q[Qh++]=m;
1.216 - predecessor->set(m,e);
1.217 - pred_node->set(m,n);
1.218 - distance->set(m,d);
1.219 - }
1.220 - } while(Qt!=Qh);
1.221 - }
1.222 -
1.223 - ///The distance of a node from the root.
1.224 -
1.225 - ///Returns the distance of a node from the root.
1.226 - ///\pre \ref run() must be called before using this function.
1.227 - ///\warning If node \c v in unreachable from the root the return value
1.228 - ///of this funcion is undefined.
1.229 - int dist(Node v) const { return (*distance)[v]; }
1.230 -
1.231 - ///Returns the 'previous edge' of the %BFS path tree.
1.232 -
1.233 - ///For a node \c v it returns the 'previous edge' of the %BFS tree,
1.234 - ///i.e. it returns the last edge of a shortest path from the root to \c
1.235 - ///v. It is \ref INVALID
1.236 - ///if \c v is unreachable from the root or if \c v=s. The
1.237 - ///%BFS tree used here is equal to the %BFS tree used in
1.238 - ///\ref predNode(Node v). \pre \ref run() must be called before using
1.239 - ///this function.
1.240 - Edge pred(Node v) const { return (*predecessor)[v]; }
1.241 -
1.242 - ///Returns the 'previous node' of the %BFS tree.
1.243 -
1.244 - ///For a node \c v it returns the 'previous node' on the %BFS tree,
1.245 - ///i.e. it returns the last but one node from a shortest path from the
1.246 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.247 - ///\c v=s. The shortest path tree used here is equal to the %BFS
1.248 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.249 - ///using this function.
1.250 - Node predNode(Node v) const { return (*pred_node)[v]; }
1.251 -
1.252 - ///Returns a reference to the NodeMap of distances.
1.253 -
1.254 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.255 - ///be called before using this function.
1.256 - const DistMap &distMap() const { return *distance;}
1.257 -
1.258 - ///Returns a reference to the %BFS tree map.
1.259 -
1.260 - ///Returns a reference to the NodeMap of the edges of the
1.261 - ///%BFS tree.
1.262 - ///\pre \ref run() must be called before using this function.
1.263 - const PredMap &predMap() const { return *predecessor;}
1.264 -
1.265 - ///Returns a reference to the map of last but one nodes of shortest paths.
1.266 -
1.267 - ///Returns a reference to the NodeMap of the last but one nodes on the
1.268 - ///%BFS tree.
1.269 - ///\pre \ref run() must be called before using this function.
1.270 - const PredNodeMap &predNodeMap() const { return *pred_node;}
1.271 -
1.272 - ///Checks if a node is reachable from the root.
1.273 -
1.274 - ///Returns \c true if \c v is reachable from the root.
1.275 - ///\note The root node is reported to be reached!
1.276 - ///
1.277 - ///\pre \ref run() must be called before using this function.
1.278 - ///
1.279 - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.280 -
1.281 - };
1.282 -
1.283 -/// @}
1.284 -
1.285 -} //END OF NAMESPACE HUGO
1.286 -
1.287 -#endif
1.288 -
1.289 -