diff -r 2d6c8075d9d0 -r 818510fa3d99 src/hugo/bfs.h --- a/src/hugo/bfs.h Wed Sep 29 14:12:26 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,286 +0,0 @@ -/* -*- C++ -*- - * src/hugo/bfs.h - Part of HUGOlib, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef HUGO_BFS_H -#define HUGO_BFS_H - -///\ingroup flowalgs -///\file -///\brief Bfs algorithm. -/// -///\todo Revise Manual. - -#include -#include - -namespace hugo { - -/// \addtogroup flowalgs -/// @{ - - ///%BFS algorithm class. - - ///This class provides an efficient implementation of %BFS algorithm. - ///\param GR The graph type the algorithm runs on. - ///This class does the same as Dijkstra does with constant 1 edge length, - ///but it is faster. - /// - ///\author Alpar Juttner - -#ifdef DOXYGEN - template -#else - template -#endif - class Bfs{ - public: - ///The type of the underlying graph. - typedef GR Graph; - ///\e - typedef typename Graph::Node Node; - ///\e - typedef typename Graph::NodeIt NodeIt; - ///\e - typedef typename Graph::Edge Edge; - ///\e - 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: - /// Pointer to the underlying graph. - const Graph *G; - ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///Pointer to the map of predecessors nodes. - PredNodeMap *pred_node; - ///Indicates if \ref pred_node is locally allocated (\c true) or not. - bool local_pred_node; - ///Pointer to the map of distances. - DistMap *distance; - ///Indicates if \ref distance is locally allocated (\c true) or not. - bool local_distance; - - ///The source node of the last execution. - Node source; - - - ///Initializes the maps. - void init_maps() - { - 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 : - ///Constructor. - - ///\param _G the graph the algorithm will run on. - /// - Bfs(const Graph& _G) : - G(&_G), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) - { } - - ///Destructor. - ~Bfs() - { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///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) - Bfs &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) - Bfs &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) - Bfs &setDistMap(DistMap &m) - { - if(local_distance) { - delete distance; - local_distance=false; - } - distance = &m; - return *this; - } - - ///Runs %BFS algorithm from node \c s. - - ///This method runs the %BFS algorithm from a root node \c s - ///in order to - ///compute a - ///shortest path to each node. The algorithm computes - ///- The %BFS 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; - int Qt=0; - - Q[Qh++]=source; - distance->set(s, 0); - do { - Node m; - Node n=Q[Qt++]; - int d= (*distance)[n]+1; - - for(OutEdgeIt e(*G,n);e!=INVALID;++e) - if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) { - Q[Qh++]=m; - predecessor->set(m,e); - pred_node->set(m,n); - distance->set(m,d); - } - } while(Qt!=Qh); - } - - ///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 %BFS path tree. - - ///For a node \c v it returns the 'previous edge' of the %BFS tree, - ///i.e. it returns the last edge of 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 - ///%BFS tree used here is equal to the %BFS 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 %BFS tree. - - ///For a node \c v it returns the 'previous node' on the %BFS 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 %BFS - ///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 %BFS tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///%BFS tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return *predecessor;} - - ///Returns a reference to the map of last but one nodes of shortest paths. - - ///Returns a reference to the NodeMap of the last but one nodes on the - ///%BFS 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. - ///\note 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; } - - }; - -/// @} - -} //END OF NAMESPACE HUGO - -#endif - -