00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
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 }
00287
00288 #endif
00289
00290