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

dfs.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/dfs.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_DFS_H
00018 #define LEMON_DFS_H
00019 
00025 
00026 #include <lemon/graph_utils.h>
00027 #include <lemon/invalid.h>
00028 
00029 namespace lemon {
00030 
00033 
00035 
00041 
00042 #ifdef DOXYGEN
00043   template <typename GR>
00044 #else
00045   template <typename GR>
00046 #endif
00047   class Dfs{
00048   public:
00050     typedef GR Graph;
00052     typedef typename Graph::Node Node;
00054     typedef typename Graph::NodeIt NodeIt;
00056     typedef typename Graph::Edge Edge;
00058     typedef typename Graph::OutEdgeIt OutEdgeIt;
00059     
00062     typedef typename Graph::template NodeMap<Edge> PredMap;
00065     typedef typename Graph::template NodeMap<Node> PredNodeMap;
00067     typedef typename Graph::template NodeMap<int> DistMap;
00068 
00069   private:
00071     const Graph *G;
00073     PredMap *predecessor;
00075     bool local_predecessor;
00077     PredNodeMap *pred_node;
00079     bool local_pred_node;
00081     DistMap *distance;
00083     bool local_distance;
00084 
00086     Node source;
00087 
00088 
00090     void init_maps() 
00091     {
00092       if(!predecessor) {
00093         local_predecessor = true;
00094         predecessor = new PredMap(*G);
00095       }
00096       if(!pred_node) {
00097         local_pred_node = true;
00098         pred_node = new PredNodeMap(*G);
00099       }
00100       if(!distance) {
00101         local_distance = true;
00102         distance = new DistMap(*G);
00103       }
00104     }
00105     
00106   public :    
00108     
00111     Dfs(const Graph& _G) :
00112       G(&_G),
00113       predecessor(NULL), local_predecessor(false),
00114       pred_node(NULL), local_pred_node(false),
00115       distance(NULL), local_distance(false)
00116     { }
00117     
00119     ~Dfs() 
00120     {
00121       if(local_predecessor) delete predecessor;
00122       if(local_pred_node) delete pred_node;
00123       if(local_distance) delete distance;
00124     }
00125 
00127 
00133     Dfs &setPredMap(PredMap &m) 
00134     {
00135       if(local_predecessor) {
00136         delete predecessor;
00137         local_predecessor=false;
00138       }
00139       predecessor = &m;
00140       return *this;
00141     }
00142 
00144 
00150     Dfs &setPredNodeMap(PredNodeMap &m) 
00151     {
00152       if(local_pred_node) {
00153         delete pred_node;
00154         local_pred_node=false;
00155       }
00156       pred_node = &m;
00157       return *this;
00158     }
00159 
00161 
00167     Dfs &setDistMap(DistMap &m) 
00168     {
00169       if(local_distance) {
00170         delete distance;
00171         local_distance=false;
00172       }
00173       distance = &m;
00174       return *this;
00175     }
00176     
00178 
00184  
00185     void run(Node s) {
00186       
00187       init_maps();
00188       
00189       source = s;
00190       
00191       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00192         predecessor->set(u,INVALID);
00193         pred_node->set(u,INVALID);
00194       }
00195       
00196       int N = countNodes(*G);
00197       std::vector<typename Graph::OutEdgeIt> Q(N);
00198 
00199       int Qh=0;
00200       
00201       Q[Qh] = OutEdgeIt(*G, s);
00202       distance->set(s, 0);
00203 
00204       Node n=s;
00205       Node m;
00206       OutEdgeIt e;
00207       do {
00208         if((e=Q[Qh])!=INVALID)
00209           if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
00210             predecessor->set(m,e);
00211             pred_node->set(m,n);
00212             Q[++Qh] = OutEdgeIt(*G, m);
00213             distance->set(m,Qh);
00214             n=m;
00215           }
00216           else ++Q[Qh];
00217         else if(--Qh>=0) n=G->source(Q[Qh]);
00218       } while(Qh>=0);
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 
00249     Node predNode(Node v) const { return (*pred_node)[v]; }
00250     
00252     
00256     const DistMap &distMap() const { return *distance;}
00257  
00259 
00263     const PredMap &predMap() const { return *predecessor;}
00264  
00266 
00271     const PredNodeMap &predNodeMap() const { return *pred_node;}
00272 
00274 
00280     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
00281     
00282   };
00283   
00285   
00286 } //END OF NAMESPACE LEMON
00287 
00288 #endif
00289 
00290 

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