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