src/lemon/bfs.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 986 e997802b855c
child 1218 5331168bbb18
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
     1 /* -*- C++ -*-
     2  * src/lemon/bfs.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_BFS_H
    18 #define LEMON_BFS_H
    19 
    20 ///\ingroup flowalgs
    21 ///\file
    22 ///\brief Bfs algorithm.
    23 ///
    24 ///\todo Revise Manual.
    25 
    26 #include <lemon/bin_heap.h>
    27 #include <lemon/invalid.h>
    28 #include <lemon/graph_utils.h>
    29 
    30 namespace lemon {
    31 
    32 /// \addtogroup flowalgs
    33 /// @{
    34 
    35   ///%BFS algorithm class.
    36 
    37   ///This class provides an efficient implementation of %BFS algorithm.
    38   ///\param GR The graph type the algorithm runs on.
    39   ///This class does the same as Dijkstra does with constant 1 edge length,
    40   ///but it is faster.
    41   ///
    42   ///\author Alpar Juttner
    43 
    44 #ifdef DOXYGEN
    45   template <typename GR>
    46 #else
    47   template <typename GR>
    48 #endif
    49   class Bfs{
    50   public:
    51     ///The type of the underlying graph.
    52     typedef GR Graph;
    53     ///\e
    54     typedef typename Graph::Node Node;
    55     ///\e
    56     typedef typename Graph::NodeIt NodeIt;
    57     ///\e
    58     typedef typename Graph::Edge Edge;
    59     ///\e
    60     typedef typename Graph::OutEdgeIt OutEdgeIt;
    61     
    62     ///\brief The type of the map that stores the last
    63     ///edges of the shortest paths.
    64     typedef typename Graph::template NodeMap<Edge> PredMap;
    65     ///\brief The type of the map that stores the last but one
    66     ///nodes of the shortest paths.
    67     typedef typename Graph::template NodeMap<Node> PredNodeMap;
    68     ///The type of the map that stores the dists of the nodes.
    69     typedef typename Graph::template NodeMap<int> DistMap;
    70 
    71   private:
    72     /// Pointer to the underlying graph.
    73     const Graph *G;
    74     ///Pointer to the map of predecessors edges.
    75     PredMap *predecessor;
    76     ///Indicates if \ref predecessor is locally allocated (\c true) or not.
    77     bool local_predecessor;
    78     ///Pointer to the map of predecessors nodes.
    79     PredNodeMap *pred_node;
    80     ///Indicates if \ref pred_node is locally allocated (\c true) or not.
    81     bool local_pred_node;
    82     ///Pointer to the map of distances.
    83     DistMap *distance;
    84     ///Indicates if \ref distance is locally allocated (\c true) or not.
    85     bool local_distance;
    86 
    87     ///The source node of the last execution.
    88     Node source;
    89 
    90 
    91     ///Initializes the maps.
    92     void init_maps() 
    93     {
    94       if(!predecessor) {
    95 	local_predecessor = true;
    96 	predecessor = new PredMap(*G);
    97       }
    98       if(!pred_node) {
    99 	local_pred_node = true;
   100 	pred_node = new PredNodeMap(*G);
   101       }
   102       if(!distance) {
   103 	local_distance = true;
   104 	distance = new DistMap(*G);
   105       }
   106     }
   107     
   108   public :    
   109     ///Constructor.
   110     
   111     ///\param _G the graph the algorithm will run on.
   112     ///
   113     Bfs(const Graph& _G) :
   114       G(&_G),
   115       predecessor(NULL), local_predecessor(false),
   116       pred_node(NULL), local_pred_node(false),
   117       distance(NULL), local_distance(false)
   118     { }
   119     
   120     ///Destructor.
   121     ~Bfs() 
   122     {
   123       if(local_predecessor) delete predecessor;
   124       if(local_pred_node) delete pred_node;
   125       if(local_distance) delete distance;
   126     }
   127 
   128     ///Sets the map storing the predecessor edges.
   129 
   130     ///Sets the map storing the predecessor edges.
   131     ///If you don't use this function before calling \ref run(),
   132     ///it will allocate one. The destuctor deallocates this
   133     ///automatically allocated map, of course.
   134     ///\return <tt> (*this) </tt>
   135     Bfs &setPredMap(PredMap &m) 
   136     {
   137       if(local_predecessor) {
   138 	delete predecessor;
   139 	local_predecessor=false;
   140       }
   141       predecessor = &m;
   142       return *this;
   143     }
   144 
   145     ///Sets the map storing the predecessor nodes.
   146 
   147     ///Sets the map storing the predecessor nodes.
   148     ///If you don't use this function before calling \ref run(),
   149     ///it will allocate one. The destuctor deallocates this
   150     ///automatically allocated map, of course.
   151     ///\return <tt> (*this) </tt>
   152     Bfs &setPredNodeMap(PredNodeMap &m) 
   153     {
   154       if(local_pred_node) {
   155 	delete pred_node;
   156 	local_pred_node=false;
   157       }
   158       pred_node = &m;
   159       return *this;
   160     }
   161 
   162     ///Sets the map storing the distances calculated by the algorithm.
   163 
   164     ///Sets the map storing the distances calculated by the algorithm.
   165     ///If you don't use this function before calling \ref run(),
   166     ///it will allocate one. The destuctor deallocates this
   167     ///automatically allocated map, of course.
   168     ///\return <tt> (*this) </tt>
   169     Bfs &setDistMap(DistMap &m) 
   170     {
   171       if(local_distance) {
   172 	delete distance;
   173 	local_distance=false;
   174       }
   175       distance = &m;
   176       return *this;
   177     }
   178     
   179   ///Runs %BFS algorithm from node \c s.
   180 
   181   ///This method runs the %BFS algorithm from a root node \c s
   182   ///in order to
   183   ///compute a
   184   ///shortest path to each node. The algorithm computes
   185   ///- The %BFS tree.
   186   ///- The distance of each node from the root.
   187  
   188     void run(Node s) {
   189       
   190       init_maps();
   191       
   192       source = s;
   193       
   194       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   195 	predecessor->set(u,INVALID);
   196 	pred_node->set(u,INVALID);
   197       }
   198       
   199       int N = countNodes(*G);
   200       std::vector<typename Graph::Node> Q(N);
   201       int Qh=0;
   202       int Qt=0;
   203       
   204       Q[Qh++]=source;
   205       distance->set(s, 0);
   206       do {
   207 	Node m;
   208 	Node n=Q[Qt++];
   209 	int d= (*distance)[n]+1;
   210 	
   211 	for(OutEdgeIt e(*G,n);e!=INVALID;++e)
   212 	  if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
   213 	    Q[Qh++]=m;
   214 	    predecessor->set(m,e);
   215 	    pred_node->set(m,n);
   216 	    distance->set(m,d);
   217 	  }
   218       } while(Qt!=Qh);
   219     }
   220     
   221     ///The distance of a node from the root.
   222 
   223     ///Returns the distance of a node from the root.
   224     ///\pre \ref run() must be called before using this function.
   225     ///\warning If node \c v in unreachable from the root the return value
   226     ///of this funcion is undefined.
   227     int dist(Node v) const { return (*distance)[v]; }
   228 
   229     ///Returns the 'previous edge' of the %BFS path tree.
   230 
   231     ///For a node \c v it returns the 'previous edge' of the %BFS tree,
   232     ///i.e. it returns the last edge of a shortest path from the root to \c
   233     ///v. It is \ref INVALID
   234     ///if \c v is unreachable from the root or if \c v=s. The
   235     ///%BFS tree used here is equal to the %BFS tree used in
   236     ///\ref predNode(Node v).  \pre \ref run() must be called before using
   237     ///this function.
   238     Edge pred(Node v) const { return (*predecessor)[v]; }
   239 
   240     ///Returns the 'previous node' of the %BFS tree.
   241 
   242     ///For a node \c v it returns the 'previous node' on the %BFS tree,
   243     ///i.e. it returns the last but one node from a shortest path from the
   244     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
   245     ///\c v=s. The shortest path tree used here is equal to the %BFS
   246     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
   247     ///using this function.
   248     Node predNode(Node v) const { return (*pred_node)[v]; }
   249     
   250     ///Returns a reference to the NodeMap of distances.
   251     
   252     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
   253     ///be called before using this function.
   254     const DistMap &distMap() const { return *distance;}
   255  
   256     ///Returns a reference to the %BFS tree map.
   257 
   258     ///Returns a reference to the NodeMap of the edges of the
   259     ///%BFS tree.
   260     ///\pre \ref run() must be called before using this function.
   261     const PredMap &predMap() const { return *predecessor;}
   262  
   263     ///Returns a reference to the map of last but one nodes of shortest paths.
   264 
   265     ///Returns a reference to the NodeMap of the last but one nodes on the
   266     ///%BFS tree.
   267     ///\pre \ref run() must be called before using this function.
   268     const PredNodeMap &predNodeMap() const { return *pred_node;}
   269 
   270     ///Checks if a node is reachable from the root.
   271 
   272     ///Returns \c true if \c v is reachable from the root.
   273     ///\note The root node is reported to be reached!
   274     ///
   275     ///\pre \ref run() must be called before using this function.
   276     ///
   277     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
   278     
   279   };
   280   
   281 /// @}
   282   
   283 } //END OF NAMESPACE LEMON
   284 
   285 #endif
   286 
   287