Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

bfs.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/bfs.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_BFS_H
00018 #define LEMON_BFS_H
00019 
00025 
00026 #include <lemon/bin_heap.h>
00027 #include <lemon/invalid.h>
00028 #include <lemon/graph_utils.h>
00029 
00030 namespace lemon {
00031 
00034 
00036 
00043 
00044 #ifdef DOXYGEN
00045   template <typename GR>
00046 #else
00047   template <typename GR>
00048 #endif
00049   class Bfs{
00050   public:
00052     typedef GR Graph;
00054     typedef typename Graph::Node Node;
00056     typedef typename Graph::NodeIt NodeIt;
00058     typedef typename Graph::Edge Edge;
00060     typedef typename Graph::OutEdgeIt OutEdgeIt;
00061     
00064     typedef typename Graph::template NodeMap<Edge> PredMap;
00067     typedef typename Graph::template NodeMap<Node> PredNodeMap;
00069     typedef typename Graph::template NodeMap<int> DistMap;
00070 
00071   private:
00073     const Graph *G;
00075     PredMap *predecessor;
00077     bool local_predecessor;
00079     PredNodeMap *pred_node;
00081     bool local_pred_node;
00083     DistMap *distance;
00085     bool local_distance;
00086 
00088     Node source;
00089 
00090 
00092     void init_maps() 
00093     {
00094       if(!predecessor) {
00095         local_predecessor = true;
00096         predecessor = new PredMap(*G);
00097       }
00098       if(!pred_node) {
00099         local_pred_node = true;
00100         pred_node = new PredNodeMap(*G);
00101       }
00102       if(!distance) {
00103         local_distance = true;
00104         distance = new DistMap(*G);
00105       }
00106     }
00107     
00108   public :    
00110     
00113     Bfs(const Graph& _G) :
00114       G(&_G),
00115       predecessor(NULL), local_predecessor(false),
00116       pred_node(NULL), local_pred_node(false),
00117       distance(NULL), local_distance(false)
00118     { }
00119     
00121     ~Bfs() 
00122     {
00123       if(local_predecessor) delete predecessor;
00124       if(local_pred_node) delete pred_node;
00125       if(local_distance) delete distance;
00126     }
00127 
00129 
00135     Bfs &setPredMap(PredMap &m) 
00136     {
00137       if(local_predecessor) {
00138         delete predecessor;
00139         local_predecessor=false;
00140       }
00141       predecessor = &m;
00142       return *this;
00143     }
00144 
00146 
00152     Bfs &setPredNodeMap(PredNodeMap &m) 
00153     {
00154       if(local_pred_node) {
00155         delete pred_node;
00156         local_pred_node=false;
00157       }
00158       pred_node = &m;
00159       return *this;
00160     }
00161 
00163 
00169     Bfs &setDistMap(DistMap &m) 
00170     {
00171       if(local_distance) {
00172         delete distance;
00173         local_distance=false;
00174       }
00175       distance = &m;
00176       return *this;
00177     }
00178     
00180 
00187  
00188     void run(Node s) {
00189       
00190       init_maps();
00191       
00192       source = s;
00193       
00194       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00195         predecessor->set(u,INVALID);
00196         pred_node->set(u,INVALID);
00197       }
00198       
00199       int N = countNodes(*G);
00200       std::vector<typename Graph::Node> Q(N);
00201       int Qh=0;
00202       int Qt=0;
00203       
00204       Q[Qh++]=source;
00205       distance->set(s, 0);
00206       do {
00207         Node m;
00208         Node n=Q[Qt++];
00209         int d= (*distance)[n]+1;
00210         
00211         for(OutEdgeIt e(*G,n);e!=INVALID;++e)
00212           if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
00213             Q[Qh++]=m;
00214             predecessor->set(m,e);
00215             pred_node->set(m,n);
00216             distance->set(m,d);
00217           }
00218       } while(Qt!=Qh);
00219     }
00220     
00222 
00227     int dist(Node v) const { return (*distance)[v]; }
00228 
00230 
00238     Edge pred(Node v) const { return (*predecessor)[v]; }
00239 
00241 
00248     Node predNode(Node v) const { return (*pred_node)[v]; }
00249     
00251     
00254     const DistMap &distMap() const { return *distance;}
00255  
00257 
00261     const PredMap &predMap() const { return *predecessor;}
00262  
00264 
00268     const PredNodeMap &predNodeMap() const { return *pred_node;}
00269 
00271 
00277     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
00278     
00279   };
00280   
00282   
00283 } //END OF NAMESPACE LEMON
00284 
00285 #endif
00286 
00287 

Generated on Mon Feb 21 15:02:20 2005 for LEMON by  doxygen 1.4.1