work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator, DfsIterator5 -> DfsIterator
authormarci
Wed, 21 Apr 2004 15:14:45 +0000
changeset 36091fba31268d6
parent 359 8cc53a6b1e61
child 361 ab0899df30d2
work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator, DfsIterator5 -> DfsIterator
src/work/marci/bfs_iterator.h
src/work/marci/bfsit_vs_byhand.cc
src/work/marci/edmonds_karp.h
src/work/marci/iterator_bfs_demo.cc
     1.1 --- a/src/work/marci/bfs_iterator.h	Wed Apr 21 14:59:43 2004 +0000
     1.2 +++ b/src/work/marci/bfs_iterator.h	Wed Apr 21 15:14:45 2004 +0000
     1.3 @@ -8,630 +8,9 @@
     1.4  
     1.5  namespace hugo {
     1.6  
     1.7 -//   template <typename Graph>
     1.8 -//   struct bfs {
     1.9 -//     typedef typename Graph::Node Node;
    1.10 -//     typedef typename Graph::Edge Edge;
    1.11 -//     typedef typename Graph::NodeIt NodeIt;
    1.12 -//     typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.13 -//     Graph& G;
    1.14 -//     Node s;
    1.15 -//     typename Graph::NodeMap<bool> reached;
    1.16 -//     typename Graph::NodeMap<Edge> pred;
    1.17 -//     typename Graph::NodeMap<int> dist;
    1.18 -//     std::queue<Node> bfs_queue;
    1.19 -//     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
    1.20 -//       bfs_queue.push(s); 
    1.21 -//       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) 
    1.22 -// 	reached.set(i, false);
    1.23 -//       reached.set(s, true);
    1.24 -//       dist.set(s, 0); 
    1.25 -//     }
    1.26 -    
    1.27 -//     void run() {
    1.28 -//       while (!bfs_queue.empty()) {
    1.29 -// 	Node v=bfs_queue.front();
    1.30 -// 	OutEdgeIt e=G.template first<OutEdgeIt>(v);
    1.31 -// 	bfs_queue.pop();
    1.32 -// 	for( ; e.valid(); ++e) {
    1.33 -// 	  Node w=G.bNode(e);
    1.34 -// 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
    1.35 -// 	  if (!reached.get(w)) {
    1.36 -// 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    1.37 -// 	    bfs_queue.push(w);
    1.38 -// 	    dist.set(w, dist.get(v)+1);
    1.39 -// 	    pred.set(w, e);
    1.40 -// 	    reached.set(w, true);
    1.41 -// 	  } else {
    1.42 -// 	    std::cout << G.id(w) << " is already reached" << std::endl;
    1.43 -// 	  }
    1.44 -// 	}
    1.45 -//       }
    1.46 -//     }
    1.47 -//   };
    1.48 -
    1.49 -//   template <typename Graph> 
    1.50 -//   struct bfs_visitor {
    1.51 -//     typedef typename Graph::Node Node;
    1.52 -//     typedef typename Graph::Edge Edge;
    1.53 -//     typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.54 -//     Graph& G;
    1.55 -//     bfs_visitor(Graph& _G) : G(_G) { }
    1.56 -//     void at_previously_reached(OutEdgeIt& e) { 
    1.57 -//       //Node v=G.aNode(e);
    1.58 -//       Node w=G.bNode(e);
    1.59 -//       std::cout << G.id(w) << " is already reached" << std::endl;
    1.60 -//    }
    1.61 -//     void at_newly_reached(OutEdgeIt& e) { 
    1.62 -//       //Node v=G.aNode(e);
    1.63 -//       Node w=G.bNode(e);
    1.64 -//       std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    1.65 -//     }
    1.66 -//   };
    1.67 -
    1.68 -//   template <typename Graph, typename ReachedMap, typename visitor_type>
    1.69 -//   struct bfs_iterator {
    1.70 -//     typedef typename Graph::Node Node;
    1.71 -//     typedef typename Graph::Edge Edge;
    1.72 -//     typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.73 -//     Graph& G;
    1.74 -//     std::queue<OutEdgeIt>& bfs_queue;
    1.75 -//     ReachedMap& reached;
    1.76 -//     visitor_type& visitor;
    1.77 -//     void process() {
    1.78 -//       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
    1.79 -//       if (bfs_queue.empty()) return;
    1.80 -//       OutEdgeIt e=bfs_queue.front();
    1.81 -//       //Node v=G.aNode(e);
    1.82 -//       Node w=G.bNode(e);
    1.83 -//       if (!reached.get(w)) {
    1.84 -// 	visitor.at_newly_reached(e);
    1.85 -// 	bfs_queue.push(G.template first<OutEdgeIt>(w));
    1.86 -// 	reached.set(w, true);
    1.87 -//       } else {
    1.88 -// 	visitor.at_previously_reached(e);
    1.89 -//       }
    1.90 -//     }
    1.91 -//     bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
    1.92 -//       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
    1.93 -//       valid();
    1.94 -//     }
    1.95 -//     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { 
    1.96 -//       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
    1.97 -//       //if (bfs_queue.empty()) return *this;
    1.98 -//       if (!valid()) return *this;
    1.99 -//       ++(bfs_queue.front());
   1.100 -//       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.101 -//       valid();
   1.102 -//       return *this;
   1.103 -//     }
   1.104 -//     //void next() { 
   1.105 -//     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.106 -//     //  if (bfs_queue.empty()) return;
   1.107 -//     //  ++(bfs_queue.front());
   1.108 -//     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.109 -//     //}
   1.110 -//     bool valid() { 
   1.111 -//       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.112 -//       if (bfs_queue.empty()) return false; else return true;
   1.113 -//     }
   1.114 -//     //bool finished() { 
   1.115 -//     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.116 -//     //  if (bfs_queue.empty()) return true; else return false;
   1.117 -//     //}
   1.118 -//     operator Edge () { return bfs_queue.front(); }
   1.119 -
   1.120 -//   };
   1.121 -
   1.122 -//   template <typename Graph, typename ReachedMap>
   1.123 -//   struct bfs_iterator1 {
   1.124 -//     typedef typename Graph::Node Node;
   1.125 -//     typedef typename Graph::Edge Edge;
   1.126 -//     typedef typename Graph::OutEdgeIt OutEdgeIt;
   1.127 -//     Graph& G;
   1.128 -//     std::queue<OutEdgeIt>& bfs_queue;
   1.129 -//     ReachedMap& reached;
   1.130 -//     bool _newly_reached;
   1.131 -//     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   1.132 -//       valid();
   1.133 -//       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
   1.134 -// 	OutEdgeIt e=bfs_queue.front();
   1.135 -// 	Node w=G.bNode(e);
   1.136 -// 	if (!reached.get(w)) {
   1.137 -// 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
   1.138 -// 	  reached.set(w, true);
   1.139 -// 	  _newly_reached=true;
   1.140 -// 	} else {
   1.141 -// 	  _newly_reached=false;
   1.142 -// 	}
   1.143 -//       }
   1.144 -//     }
   1.145 -//     bfs_iterator1<Graph, ReachedMap>& operator++() { 
   1.146 -//       if (!valid()) return *this;
   1.147 -//       ++(bfs_queue.front());
   1.148 -//       valid();
   1.149 -//       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
   1.150 -// 	OutEdgeIt e=bfs_queue.front();
   1.151 -// 	Node w=G.bNode(e);
   1.152 -// 	if (!reached.get(w)) {
   1.153 -// 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
   1.154 -// 	  reached.set(w, true);
   1.155 -// 	  _newly_reached=true;
   1.156 -// 	} else {
   1.157 -// 	  _newly_reached=false;
   1.158 -// 	}
   1.159 -//       }
   1.160 -//       return *this;
   1.161 -//     }
   1.162 -//     bool valid() { 
   1.163 -//       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
   1.164 -//       if (bfs_queue.empty()) return false; else return true;
   1.165 -//     }
   1.166 -//     operator OutEdgeIt() { return bfs_queue.front(); }
   1.167 -//     //ize
   1.168 -//     bool newly_reached() { return _newly_reached; }
   1.169 -
   1.170 -//   };
   1.171 -
   1.172 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.173 -//   struct BfsIterator {
   1.174 -//     typedef typename Graph::Node Node;
   1.175 -//     Graph& G;
   1.176 -//     std::queue<OutEdgeIt>& bfs_queue;
   1.177 -//     ReachedMap& reached;
   1.178 -//     bool b_node_newly_reached;
   1.179 -//     OutEdgeIt actual_edge;
   1.180 -//     BfsIterator(Graph& _G, 
   1.181 -// 		std::queue<OutEdgeIt>& _bfs_queue, 
   1.182 -// 		ReachedMap& _reached) : 
   1.183 -//       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   1.184 -//       actual_edge=bfs_queue.front();
   1.185 -//       if (actual_edge.valid()) { 
   1.186 -// 	Node w=G.bNode(actual_edge);
   1.187 -// 	if (!reached.get(w)) {
   1.188 -// 	  bfs_queue.push(G.firstOutEdge(w));
   1.189 -// 	  reached.set(w, true);
   1.190 -// 	  b_node_newly_reached=true;
   1.191 -// 	} else {
   1.192 -// 	  b_node_newly_reached=false;
   1.193 -// 	}
   1.194 -//       }
   1.195 -//     }
   1.196 -//     BfsIterator<Graph, OutEdgeIt, ReachedMap>& 
   1.197 -//     operator++() { 
   1.198 -//       if (bfs_queue.front().valid()) { 
   1.199 -// 	++(bfs_queue.front());
   1.200 -// 	actual_edge=bfs_queue.front();
   1.201 -// 	if (actual_edge.valid()) {
   1.202 -// 	  Node w=G.bNode(actual_edge);
   1.203 -// 	  if (!reached.get(w)) {
   1.204 -// 	    bfs_queue.push(G.firstOutEdge(w));
   1.205 -// 	    reached.set(w, true);
   1.206 -// 	    b_node_newly_reached=true;
   1.207 -// 	  } else {
   1.208 -// 	    b_node_newly_reached=false;
   1.209 -// 	  }
   1.210 -// 	}
   1.211 -//       } else {
   1.212 -// 	bfs_queue.pop(); 
   1.213 -// 	actual_edge=bfs_queue.front();
   1.214 -// 	if (actual_edge.valid()) {
   1.215 -// 	  Node w=G.bNode(actual_edge);
   1.216 -// 	  if (!reached.get(w)) {
   1.217 -// 	    bfs_queue.push(G.firstOutEdge(w));
   1.218 -// 	    reached.set(w, true);
   1.219 -// 	    b_node_newly_reached=true;
   1.220 -// 	  } else {
   1.221 -// 	    b_node_newly_reached=false;
   1.222 -// 	  }
   1.223 -// 	}
   1.224 -//       }
   1.225 -//       return *this;
   1.226 -//     }
   1.227 -//     bool finished() { return bfs_queue.empty(); }
   1.228 -//     operator OutEdgeIt () { return actual_edge; }
   1.229 -//     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   1.230 -//     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   1.231 -//   };
   1.232 -
   1.233 -
   1.234 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.235 -//   struct DfsIterator {
   1.236 -//     typedef typename Graph::Node Node;
   1.237 -//     Graph& G;
   1.238 -//     std::stack<OutEdgeIt>& bfs_queue;
   1.239 -//     ReachedMap& reached;
   1.240 -//     bool b_node_newly_reached;
   1.241 -//     OutEdgeIt actual_edge;
   1.242 -//     DfsIterator(Graph& _G, 
   1.243 -// 		std::stack<OutEdgeIt>& _bfs_queue, 
   1.244 -// 		ReachedMap& _reached) : 
   1.245 -//       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   1.246 -//       actual_edge=bfs_queue.top();
   1.247 -//       if (actual_edge.valid()) { 
   1.248 -// 	Node w=G.bNode(actual_edge);
   1.249 -// 	if (!reached.get(w)) {
   1.250 -// 	  bfs_queue.push(G.firstOutEdge(w));
   1.251 -// 	  reached.set(w, true);
   1.252 -// 	  b_node_newly_reached=true;
   1.253 -// 	} else {
   1.254 -// 	  ++(bfs_queue.top());
   1.255 -// 	  b_node_newly_reached=false;
   1.256 -// 	}
   1.257 -//       } else {
   1.258 -// 	bfs_queue.pop();
   1.259 -//       }
   1.260 -//     }
   1.261 -//     DfsIterator<Graph, OutEdgeIt, ReachedMap>& 
   1.262 -//     operator++() { 
   1.263 -//       actual_edge=bfs_queue.top();
   1.264 -//       if (actual_edge.valid()) { 
   1.265 -// 	Node w=G.bNode(actual_edge);
   1.266 -// 	if (!reached.get(w)) {
   1.267 -// 	  bfs_queue.push(G.firstOutEdge(w));
   1.268 -// 	  reached.set(w, true);
   1.269 -// 	  b_node_newly_reached=true;
   1.270 -// 	} else {
   1.271 -// 	  ++(bfs_queue.top());
   1.272 -// 	  b_node_newly_reached=false;
   1.273 -// 	}
   1.274 -//       } else {
   1.275 -// 	bfs_queue.pop();
   1.276 -//       }
   1.277 -//       return *this;
   1.278 -//     }
   1.279 -//     bool finished() { return bfs_queue.empty(); }
   1.280 -//     operator OutEdgeIt () { return actual_edge; }
   1.281 -//     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   1.282 -//     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   1.283 -//   };
   1.284 -
   1.285 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.286 -//   struct BfsIterator1 {
   1.287 -//     typedef typename Graph::Node Node;
   1.288 -//     Graph& G;
   1.289 -//     std::queue<OutEdgeIt>& bfs_queue;
   1.290 -//     ReachedMap& reached;
   1.291 -//     bool b_node_newly_reached;
   1.292 -//     OutEdgeIt actual_edge;
   1.293 -//     BfsIterator1(Graph& _G, 
   1.294 -// 		std::queue<OutEdgeIt>& _bfs_queue, 
   1.295 -// 		ReachedMap& _reached) : 
   1.296 -//       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   1.297 -//       actual_edge=bfs_queue.front();
   1.298 -//       if (actual_edge.valid()) { 
   1.299 -//       	Node w=G.bNode(actual_edge);
   1.300 -// 	if (!reached.get(w)) {
   1.301 -// 	  bfs_queue.push(OutEdgeIt(G, w));
   1.302 -// 	  reached.set(w, true);
   1.303 -// 	  b_node_newly_reached=true;
   1.304 -// 	} else {
   1.305 -// 	  b_node_newly_reached=false;
   1.306 -// 	}
   1.307 -//       }
   1.308 -//     }
   1.309 -//     void next() { 
   1.310 -//       if (bfs_queue.front().valid()) { 
   1.311 -// 	++(bfs_queue.front());
   1.312 -// 	actual_edge=bfs_queue.front();
   1.313 -// 	if (actual_edge.valid()) {
   1.314 -// 	  Node w=G.bNode(actual_edge);
   1.315 -// 	  if (!reached.get(w)) {
   1.316 -// 	    bfs_queue.push(OutEdgeIt(G, w));
   1.317 -// 	    reached.set(w, true);
   1.318 -// 	    b_node_newly_reached=true;
   1.319 -// 	  } else {
   1.320 -// 	    b_node_newly_reached=false;
   1.321 -// 	  }
   1.322 -// 	}
   1.323 -//       } else {
   1.324 -// 	bfs_queue.pop(); 
   1.325 -// 	actual_edge=bfs_queue.front();
   1.326 -// 	if (actual_edge.valid()) {
   1.327 -// 	  Node w=G.bNode(actual_edge);
   1.328 -// 	  if (!reached.get(w)) {
   1.329 -// 	    bfs_queue.push(OutEdgeIt(G, w));
   1.330 -// 	    reached.set(w, true);
   1.331 -// 	    b_node_newly_reached=true;
   1.332 -// 	  } else {
   1.333 -// 	    b_node_newly_reached=false;
   1.334 -// 	  }
   1.335 -// 	}
   1.336 -//       }
   1.337 -//       //return *this;
   1.338 -//     }
   1.339 -//     bool finished() { return bfs_queue.empty(); }
   1.340 -//     operator OutEdgeIt () { return actual_edge; }
   1.341 -//     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   1.342 -//     bool aNodeIsExamined() { return !(actual_edge.valid()); }
   1.343 -//   };
   1.344 -
   1.345 -
   1.346 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.347 -//   struct DfsIterator1 {
   1.348 -//     typedef typename Graph::Node Node;
   1.349 -//     Graph& G;
   1.350 -//     std::stack<OutEdgeIt>& bfs_queue;
   1.351 -//     ReachedMap& reached;
   1.352 -//     bool b_node_newly_reached;
   1.353 -//     OutEdgeIt actual_edge;
   1.354 -//     DfsIterator1(Graph& _G, 
   1.355 -// 		std::stack<OutEdgeIt>& _bfs_queue, 
   1.356 -// 		ReachedMap& _reached) : 
   1.357 -//       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
   1.358 -//       //actual_edge=bfs_queue.top();
   1.359 -//       //if (actual_edge.valid()) { 
   1.360 -//       //	Node w=G.bNode(actual_edge);
   1.361 -//       //if (!reached.get(w)) {
   1.362 -//       //  bfs_queue.push(OutEdgeIt(G, w));
   1.363 -//       //  reached.set(w, true);
   1.364 -//       //  b_node_newly_reached=true;
   1.365 -//       //} else {
   1.366 -//       //  ++(bfs_queue.top());
   1.367 -//       //  b_node_newly_reached=false;
   1.368 -//       //}
   1.369 -//       //} else {
   1.370 -//       //	bfs_queue.pop();
   1.371 -//       //}
   1.372 -//     }
   1.373 -//     void next() { 
   1.374 -//       actual_edge=bfs_queue.top();
   1.375 -//       if (actual_edge.valid()) { 
   1.376 -// 	Node w=G.bNode(actual_edge);
   1.377 -// 	if (!reached.get(w)) {
   1.378 -// 	  bfs_queue.push(OutEdgeIt(G, w));
   1.379 -// 	  reached.set(w, true);
   1.380 -// 	  b_node_newly_reached=true;
   1.381 -// 	} else {
   1.382 -// 	  ++(bfs_queue.top());
   1.383 -// 	  b_node_newly_reached=false;
   1.384 -// 	}
   1.385 -//       } else {
   1.386 -// 	bfs_queue.pop();
   1.387 -//       }
   1.388 -//       //return *this;
   1.389 -//     }
   1.390 -//     bool finished() { return bfs_queue.empty(); }
   1.391 -//     operator OutEdgeIt () { return actual_edge; }
   1.392 -//     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
   1.393 -//     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
   1.394 -//   };
   1.395 -
   1.396 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.397 -//   class BfsIterator2 {
   1.398 -//     typedef typename Graph::Node Node;
   1.399 -//     const Graph& G;
   1.400 -//     std::queue<OutEdgeIt> bfs_queue;
   1.401 -//     ReachedMap reached;
   1.402 -//     bool b_node_newly_reached;
   1.403 -//     OutEdgeIt actual_edge;
   1.404 -//   public:
   1.405 -//     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
   1.406 -//     void pushAndSetReached(Node s) { 
   1.407 -//       reached.set(s, true);
   1.408 -//       if (bfs_queue.empty()) {
   1.409 -// 	bfs_queue.push(G.template first<OutEdgeIt>(s));
   1.410 -// 	actual_edge=bfs_queue.front();
   1.411 -// 	if (actual_edge.valid()) { 
   1.412 -// 	  Node w=G.bNode(actual_edge);
   1.413 -// 	  if (!reached.get(w)) {
   1.414 -// 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
   1.415 -// 	    reached.set(w, true);
   1.416 -// 	    b_node_newly_reached=true;
   1.417 -// 	  } else {
   1.418 -// 	    b_node_newly_reached=false;
   1.419 -// 	  }
   1.420 -// 	} //else {
   1.421 -// 	//}
   1.422 -//       } else {
   1.423 -// 	bfs_queue.push(G.template first<OutEdgeIt>(s));
   1.424 -//       }
   1.425 -//     }
   1.426 -//     BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
   1.427 -//     operator++() { 
   1.428 -//       if (bfs_queue.front().valid()) { 
   1.429 -// 	++(bfs_queue.front());
   1.430 -// 	actual_edge=bfs_queue.front();
   1.431 -// 	if (actual_edge.valid()) {
   1.432 -// 	  Node w=G.bNode(actual_edge);
   1.433 -// 	  if (!reached.get(w)) {
   1.434 -// 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
   1.435 -// 	    reached.set(w, true);
   1.436 -// 	    b_node_newly_reached=true;
   1.437 -// 	  } else {
   1.438 -// 	    b_node_newly_reached=false;
   1.439 -// 	  }
   1.440 -// 	}
   1.441 -//       } else {
   1.442 -// 	bfs_queue.pop(); 
   1.443 -// 	if (!bfs_queue.empty()) {
   1.444 -// 	  actual_edge=bfs_queue.front();
   1.445 -// 	  if (actual_edge.valid()) {
   1.446 -// 	    Node w=G.bNode(actual_edge);
   1.447 -// 	    if (!reached.get(w)) {
   1.448 -// 	      bfs_queue.push(G.template first<OutEdgeIt>(w));
   1.449 -// 	      reached.set(w, true);
   1.450 -// 	      b_node_newly_reached=true;
   1.451 -// 	    } else {
   1.452 -// 	      b_node_newly_reached=false;
   1.453 -// 	    }
   1.454 -// 	  }
   1.455 -// 	}
   1.456 -//       }
   1.457 -//       return *this;
   1.458 -//     }
   1.459 -//     bool finished() const { return bfs_queue.empty(); }
   1.460 -//     operator OutEdgeIt () const { return actual_edge; }
   1.461 -//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   1.462 -//     bool isANodeExamined() const { return !(actual_edge.valid()); }
   1.463 -//     const ReachedMap& getReachedMap() const { return reached; }
   1.464 -//     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
   1.465 -//  };
   1.466 -
   1.467 -
   1.468 -//   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
   1.469 -//   class BfsIterator3 {
   1.470 -//     typedef typename Graph::Node Node;
   1.471 -//     const Graph& G;
   1.472 -//     std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
   1.473 -//     ReachedMap reached;
   1.474 -//     bool b_node_newly_reached;
   1.475 -//     OutEdgeIt actual_edge;
   1.476 -//   public:
   1.477 -//     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
   1.478 -//     void pushAndSetReached(Node s) { 
   1.479 -//       reached.set(s, true);
   1.480 -//       if (bfs_queue.empty()) {
   1.481 -// 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
   1.482 -// 	actual_edge=bfs_queue.front().second;
   1.483 -// 	if (actual_edge.valid()) { 
   1.484 -// 	  Node w=G.bNode(actual_edge);
   1.485 -// 	  if (!reached.get(w)) {
   1.486 -// 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   1.487 -// 	    reached.set(w, true);
   1.488 -// 	    b_node_newly_reached=true;
   1.489 -// 	  } else {
   1.490 -// 	    b_node_newly_reached=false;
   1.491 -// 	  }
   1.492 -// 	} //else {
   1.493 -// 	//}
   1.494 -//       } else {
   1.495 -// 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
   1.496 -//       }
   1.497 -//     }
   1.498 -//     BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
   1.499 -//     operator++() { 
   1.500 -//       if (bfs_queue.front().second.valid()) { 
   1.501 -// 	++(bfs_queue.front().second);
   1.502 -// 	actual_edge=bfs_queue.front().second;
   1.503 -// 	if (actual_edge.valid()) {
   1.504 -// 	  Node w=G.bNode(actual_edge);
   1.505 -// 	  if (!reached.get(w)) {
   1.506 -// 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   1.507 -// 	    reached.set(w, true);
   1.508 -// 	    b_node_newly_reached=true;
   1.509 -// 	  } else {
   1.510 -// 	    b_node_newly_reached=false;
   1.511 -// 	  }
   1.512 -// 	}
   1.513 -//       } else {
   1.514 -// 	bfs_queue.pop(); 
   1.515 -// 	if (!bfs_queue.empty()) {
   1.516 -// 	  actual_edge=bfs_queue.front().second;
   1.517 -// 	  if (actual_edge.valid()) {
   1.518 -// 	    Node w=G.bNode(actual_edge);
   1.519 -// 	    if (!reached.get(w)) {
   1.520 -// 	      bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
   1.521 -// 	      reached.set(w, true);
   1.522 -// 	      b_node_newly_reached=true;
   1.523 -// 	    } else {
   1.524 -// 	      b_node_newly_reached=false;
   1.525 -// 	    }
   1.526 -// 	  }
   1.527 -// 	}
   1.528 -//       }
   1.529 -//       return *this;
   1.530 -//     }
   1.531 -//     bool finished() const { return bfs_queue.empty(); }
   1.532 -//     operator OutEdgeIt () const { return actual_edge; }
   1.533 -//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   1.534 -//     bool isANodeExamined() const { return !(actual_edge.valid()); }
   1.535 -//     Node aNode() const { return bfs_queue.front().first; }
   1.536 -//     Node bNode() const { return G.bNode(actual_edge); }
   1.537 -//     const ReachedMap& getReachedMap() const { return reached; }
   1.538 -//     //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
   1.539 -//  };
   1.540 -
   1.541 -
   1.542 -//   template <typename Graph, typename OutEdgeIt, 
   1.543 -// 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   1.544 -//   class BfsIterator4 {
   1.545 -//     typedef typename Graph::Node Node;
   1.546 -//     const Graph& G;
   1.547 -//     std::queue<Node> bfs_queue;
   1.548 -//     ReachedMap& reached;
   1.549 -//     bool b_node_newly_reached;
   1.550 -//     OutEdgeIt actual_edge;
   1.551 -//     bool own_reached_map;
   1.552 -//   public:
   1.553 -//     BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
   1.554 -//       G(_G), reached(_reached), 
   1.555 -//       own_reached_map(false) { }
   1.556 -//     BfsIterator4(const Graph& _G) : 
   1.557 -//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   1.558 -//       own_reached_map(true) { }
   1.559 -//     ~BfsIterator4() { if (own_reached_map) delete &reached; }
   1.560 -//     void pushAndSetReached(Node s) { 
   1.561 -//       //std::cout << "mimi" << &reached << std::endl;
   1.562 -//       reached.set(s, true);
   1.563 -//       //std::cout << "mumus" << std::endl;
   1.564 -//       if (bfs_queue.empty()) {
   1.565 -// 	//std::cout << "bibi1" << std::endl;
   1.566 -// 	bfs_queue.push(s);
   1.567 -// 	//std::cout << "zizi" << std::endl;
   1.568 -// 	G./*getF*/first(actual_edge, s);
   1.569 -// 	//std::cout << "kiki" << std::endl;
   1.570 -// 	if (G.valid(actual_edge)/*.valid()*/) { 
   1.571 -// 	  Node w=G.bNode(actual_edge);
   1.572 -// 	  if (!reached.get(w)) {
   1.573 -// 	    bfs_queue.push(w);
   1.574 -// 	    reached.set(w, true);
   1.575 -// 	    b_node_newly_reached=true;
   1.576 -// 	  } else {
   1.577 -// 	    b_node_newly_reached=false;
   1.578 -// 	  }
   1.579 -// 	} 
   1.580 -//       } else {
   1.581 -// 	//std::cout << "bibi2" << std::endl;
   1.582 -// 	bfs_queue.push(s);
   1.583 -//       }
   1.584 -//     }
   1.585 -//     BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   1.586 -//     operator++() { 
   1.587 -//       if (G.valid(actual_edge)/*.valid()*/) { 
   1.588 -// 	/*++*/G.next(actual_edge);
   1.589 -// 	if (G.valid(actual_edge)/*.valid()*/) {
   1.590 -// 	  Node w=G.bNode(actual_edge);
   1.591 -// 	  if (!reached.get(w)) {
   1.592 -// 	    bfs_queue.push(w);
   1.593 -// 	    reached.set(w, true);
   1.594 -// 	    b_node_newly_reached=true;
   1.595 -// 	  } else {
   1.596 -// 	    b_node_newly_reached=false;
   1.597 -// 	  }
   1.598 -// 	}
   1.599 -//       } else {
   1.600 -// 	bfs_queue.pop(); 
   1.601 -// 	if (!bfs_queue.empty()) {
   1.602 -// 	  G./*getF*/first(actual_edge, bfs_queue.front());
   1.603 -// 	  if (G.valid(actual_edge)/*.valid()*/) {
   1.604 -// 	    Node w=G.bNode(actual_edge);
   1.605 -// 	    if (!reached.get(w)) {
   1.606 -// 	      bfs_queue.push(w);
   1.607 -// 	      reached.set(w, true);
   1.608 -// 	      b_node_newly_reached=true;
   1.609 -// 	    } else {
   1.610 -// 	      b_node_newly_reached=false;
   1.611 -// 	    }
   1.612 -// 	  }
   1.613 -// 	}
   1.614 -//       }
   1.615 -//       return *this;
   1.616 -//     }
   1.617 -//     bool finished() const { return bfs_queue.empty(); }
   1.618 -//     operator OutEdgeIt () const { return actual_edge; }
   1.619 -//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   1.620 -//     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   1.621 -//     Node aNode() const { return bfs_queue.front(); }
   1.622 -//     Node bNode() const { return G.bNode(actual_edge); }
   1.623 -//     const ReachedMap& getReachedMap() const { return reached; }
   1.624 -//     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
   1.625 -//  };  
   1.626 -
   1.627 -
   1.628    template <typename Graph, /*typename OutEdgeIt,*/ 
   1.629  	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   1.630 -  class BfsIterator5 {
   1.631 +  class BfsIterator {
   1.632    protected:
   1.633      typedef typename Graph::Node Node;
   1.634      typedef typename Graph::OutEdgeIt OutEdgeIt;
   1.635 @@ -642,13 +21,13 @@
   1.636      OutEdgeIt actual_edge;
   1.637      bool own_reached_map;
   1.638    public:
   1.639 -    BfsIterator5(const Graph& _graph, ReachedMap& _reached) : 
   1.640 +    BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
   1.641        graph(&_graph), reached(_reached), 
   1.642        own_reached_map(false) { }
   1.643 -    BfsIterator5(const Graph& _graph) : 
   1.644 +    BfsIterator(const Graph& _graph) : 
   1.645        graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
   1.646        own_reached_map(true) { }
   1.647 -    ~BfsIterator5() { if (own_reached_map) delete &reached; }
   1.648 +    ~BfsIterator() { if (own_reached_map) delete &reached; }
   1.649      void pushAndSetReached(Node s) { 
   1.650        reached.set(s, true);
   1.651        if (bfs_queue.empty()) {
   1.652 @@ -668,7 +47,7 @@
   1.653  	bfs_queue.push(s);
   1.654        }
   1.655      }
   1.656 -    BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 
   1.657 +    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
   1.658      operator++() { 
   1.659        if (graph->valid(actual_edge)) { 
   1.660  	graph->next(actual_edge);
   1.661 @@ -710,65 +89,9 @@
   1.662      const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
   1.663    };  
   1.664  
   1.665 -//   template <typename Graph, typename OutEdgeIt, 
   1.666 -// 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   1.667 -//   class DfsIterator4 {
   1.668 -//     typedef typename Graph::Node Node;
   1.669 -//     const Graph& G;
   1.670 -//     std::stack<OutEdgeIt> dfs_stack;
   1.671 -//     bool b_node_newly_reached;
   1.672 -//     OutEdgeIt actual_edge;
   1.673 -//     Node actual_node;
   1.674 -//     ReachedMap& reached;
   1.675 -//     bool own_reached_map;
   1.676 -//   public:
   1.677 -//     DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
   1.678 -//       G(_G), reached(_reached), 
   1.679 -//       own_reached_map(false) { }
   1.680 -//     DfsIterator4(const Graph& _G) : 
   1.681 -//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
   1.682 -//       own_reached_map(true) { }
   1.683 -//     ~DfsIterator4() { if (own_reached_map) delete &reached; }
   1.684 -//     void pushAndSetReached(Node s) { 
   1.685 -//       actual_node=s;
   1.686 -//       reached.set(s, true);
   1.687 -//       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
   1.688 -//     }
   1.689 -//     DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
   1.690 -//     operator++() { 
   1.691 -//       actual_edge=dfs_stack.top();
   1.692 -//       //actual_node=G.aNode(actual_edge);
   1.693 -//       if (G.valid(actual_edge)/*.valid()*/) { 
   1.694 -// 	Node w=G.bNode(actual_edge);
   1.695 -// 	actual_node=w;
   1.696 -// 	if (!reached.get(w)) {
   1.697 -// 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
   1.698 -// 	  reached.set(w, true);
   1.699 -// 	  b_node_newly_reached=true;
   1.700 -// 	} else {
   1.701 -// 	  actual_node=G.aNode(actual_edge);
   1.702 -// 	  /*++*/G.next(dfs_stack.top());
   1.703 -// 	  b_node_newly_reached=false;
   1.704 -// 	}
   1.705 -//       } else {
   1.706 -// 	//actual_node=G.aNode(dfs_stack.top());
   1.707 -// 	dfs_stack.pop();
   1.708 -//       }
   1.709 -//       return *this;
   1.710 -//     }
   1.711 -//     bool finished() const { return dfs_stack.empty(); }
   1.712 -//     operator OutEdgeIt () const { return actual_edge; }
   1.713 -//     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   1.714 -//     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
   1.715 -//     Node aNode() const { return actual_node; /*FIXME*/}
   1.716 -//     Node bNode() const { return G.bNode(actual_edge); }
   1.717 -//     const ReachedMap& getReachedMap() const { return reached; }
   1.718 -//     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   1.719 -//   };
   1.720 -
   1.721    template <typename Graph, /*typename OutEdgeIt,*/ 
   1.722  	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   1.723 -  class DfsIterator5 {
   1.724 +  class DfsIterator {
   1.725    protected:
   1.726      typedef typename Graph::Node Node;
   1.727      typedef typename Graph::OutEdgeIt OutEdgeIt;
   1.728 @@ -780,13 +103,13 @@
   1.729      ReachedMap& reached;
   1.730      bool own_reached_map;
   1.731    public:
   1.732 -    DfsIterator5(const Graph& _graph, ReachedMap& _reached) : 
   1.733 +    DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
   1.734        graph(&_graph), reached(_reached), 
   1.735        own_reached_map(false) { }
   1.736 -    DfsIterator5(const Graph& _graph) : 
   1.737 +    DfsIterator(const Graph& _graph) : 
   1.738        graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
   1.739        own_reached_map(true) { }
   1.740 -    ~DfsIterator5() { if (own_reached_map) delete &reached; }
   1.741 +    ~DfsIterator() { if (own_reached_map) delete &reached; }
   1.742      void pushAndSetReached(Node s) { 
   1.743        actual_node=s;
   1.744        reached.set(s, true);
   1.745 @@ -794,7 +117,7 @@
   1.746        graph->first(e, s);
   1.747        dfs_stack.push(e); 
   1.748      }
   1.749 -    DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 
   1.750 +    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
   1.751      operator++() { 
   1.752        actual_edge=dfs_stack.top();
   1.753        //actual_node=G.aNode(actual_edge);
   1.754 @@ -828,8 +151,6 @@
   1.755      const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   1.756    };
   1.757  
   1.758 -
   1.759 -
   1.760  } // namespace hugo
   1.761  
   1.762  #endif //HUGO_BFS_ITERATOR_H
     2.1 --- a/src/work/marci/bfsit_vs_byhand.cc	Wed Apr 21 14:59:43 2004 +0000
     2.2 +++ b/src/work/marci/bfsit_vs_byhand.cc	Wed Apr 21 15:14:45 2004 +0000
     2.3 @@ -51,7 +51,7 @@
     2.4  
     2.5    {
     2.6      ts.reset();      
     2.7 -    BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G);
     2.8 +    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
     2.9      bfs.pushAndSetReached(s);
    2.10      pred.set(s, INVALID);
    2.11      while (!bfs.finished()) { 
     3.1 --- a/src/work/marci/edmonds_karp.h	Wed Apr 21 14:59:43 2004 +0000
     3.2 +++ b/src/work/marci/edmonds_karp.h	Wed Apr 21 15:14:45 2004 +0000
     3.3 @@ -275,7 +275,7 @@
     3.4        ResGW res_graph(*g, *capacity, *flow);
     3.5        bool _augment=false;
     3.6        
     3.7 -      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     3.8 +      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     3.9        bfs.pushAndSetReached(s);
    3.10  	
    3.11        typename ResGW::NodeMap<ResGWEdge> pred(res_graph); 
    3.12 @@ -339,7 +339,7 @@
    3.13  
    3.14        ResGW res_graph(*g, *capacity, *flow);
    3.15  
    3.16 -      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.17 +      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.18  
    3.19        bfs.pushAndSetReached(s);
    3.20        //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
    3.21 @@ -391,7 +391,7 @@
    3.22  	__augment=false;
    3.23  	//computing blocking flow with dfs
    3.24  
    3.25 -	DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
    3.26 +	DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
    3.27  	typename MG::NodeMap<typename MG::Edge> pred(F);
    3.28  	pred.set(sF, INVALID);
    3.29  	//invalid iterators for sources
    3.30 @@ -449,7 +449,7 @@
    3.31        ResGW res_graph(*g, *capacity, *flow);
    3.32  
    3.33        //bfs for distances on the residual graph
    3.34 -      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.35 +      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.36        bfs.pushAndSetReached(s);
    3.37        typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
    3.38  
    3.39 @@ -497,7 +497,7 @@
    3.40        while (__augment) {
    3.41  	__augment=false;
    3.42  	//computing blocking flow with dfs
    3.43 -	DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
    3.44 +	DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
    3.45  	typename MG::NodeMap<typename MG::Edge> pred(F);
    3.46  	pred.set(sF, INVALID);
    3.47  	//invalid iterators for sources
    3.48 @@ -553,7 +553,7 @@
    3.49  
    3.50        ResGW res_graph(*g, *capacity, *flow);
    3.51  
    3.52 -      BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.53 +      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    3.54  
    3.55        bfs.pushAndSetReached(s);
    3.56        DistanceMap<ResGW> dist(res_graph);
    3.57 @@ -593,7 +593,7 @@
    3.58  
    3.59   	__augment=false;
    3.60    	//computing blocking flow with dfs
    3.61 -  	DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> > 
    3.62 +  	DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> > 
    3.63    	  dfs(erasing_res_graph);
    3.64   	typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> 
    3.65   	  pred(erasing_res_graph); 
    3.66 @@ -728,7 +728,7 @@
    3.67  //       bool _augment=false;
    3.68        
    3.69  //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    3.70 -//       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
    3.71 +//       BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
    3.72  //       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
    3.73  //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    3.74  // 	if ((S->get(s)) && (used.get(s)<1) ) {
    3.75 @@ -918,7 +918,7 @@
    3.76  //       EAugGraph res_graph(*G, *flow, *capacity);
    3.77  
    3.78  //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    3.79 -//       BfsIterator5< 
    3.80 +//       BfsIterator< 
    3.81  // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
    3.82  // 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
    3.83  // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    3.84 @@ -958,7 +958,7 @@
    3.85  // 	__augment=false;
    3.86  // 	//computing blocking flow with dfs
    3.87  // 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    3.88 -// 	DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
    3.89 +// 	DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > 
    3.90  // 	  dfs(res_graph);
    3.91  // 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); 
    3.92  // 	//pred.set(s, EAugEdge(INVALID));
     4.1 --- a/src/work/marci/iterator_bfs_demo.cc	Wed Apr 21 14:59:43 2004 +0000
     4.2 +++ b/src/work/marci/iterator_bfs_demo.cc	Wed Apr 21 15:14:45 2004 +0000
     4.3 @@ -103,7 +103,7 @@
     4.4      }
     4.5  
     4.6      cout << "bfs from s ..." << endl;
     4.7 -    BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G);
     4.8 +    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
     4.9      bfs.pushAndSetReached(s);
    4.10      while (!bfs.finished()) {
    4.11        //cout << "edge: ";
    4.12 @@ -136,7 +136,7 @@
    4.13      cout << "    \\-->    ------------->         "<< endl;
    4.14  
    4.15      cout << "dfs from s ..." << endl;
    4.16 -    DfsIterator5< Graph, Graph::NodeMap<bool> > dfs(G);
    4.17 +    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
    4.18      dfs.pushAndSetReached(s);
    4.19      while (!dfs.finished()) {
    4.20        ++dfs;
    4.21 @@ -179,7 +179,7 @@
    4.22      }
    4.23  
    4.24      cout << "bfs from t ..." << endl;
    4.25 -    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
    4.26 +    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    4.27      bfs.pushAndSetReached(t);
    4.28      while (!bfs.finished()) {
    4.29        //cout << "edge: ";
    4.30 @@ -212,7 +212,7 @@
    4.31      cout << "    \\-->    ------------->         "<< endl;
    4.32      
    4.33      cout << "dfs from t ..." << endl;
    4.34 -    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
    4.35 +    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    4.36      dfs.pushAndSetReached(t);
    4.37      while (!dfs.finished()) {
    4.38        ++dfs;
    4.39 @@ -258,7 +258,7 @@
    4.40  //     cout << endl;
    4.41  
    4.42      cout << "bfs from t ..." << endl;
    4.43 -    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
    4.44 +    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    4.45      bfs.pushAndSetReached(t);
    4.46      while (!bfs.finished()) {
    4.47        //cout << "edge: ";
    4.48 @@ -291,7 +291,7 @@
    4.49      cout << "    \\-->    ------------->         "<< endl;
    4.50      
    4.51      cout << "dfs from t ..." << endl;
    4.52 -    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
    4.53 +    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    4.54      dfs.pushAndSetReached(t);
    4.55      while (!dfs.finished()) {
    4.56        ++dfs;