lemon-0.x: src/work/marci/bfs_iterator.h@76c005b15354

     1 // -*- c++ -*-

     2 #ifndef HUGO_BFS_ITERATOR_H

     3 #define HUGO_BFS_ITERATOR_H

     5 #include <queue>

     6 #include <stack>

     7 #include <utility>

     9 namespace hugo {

    11 //   template <typename Graph>

    12 //   struct bfs {

    13 //     typedef typename Graph::Node Node;

    14 //     typedef typename Graph::Edge Edge;

    15 //     typedef typename Graph::NodeIt NodeIt;

    16 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

    17 //     Graph& G;

    18 //     Node s;

    19 //     typename Graph::NodeMap<bool> reached;

    20 //     typename Graph::NodeMap<Edge> pred;

    21 //     typename Graph::NodeMap<int> dist;

    22 //     std::queue<Node> bfs_queue;

    23 //     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {

    24 //       bfs_queue.push(s);

    25 //       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)

    26 // 	reached.set(i, false);

    27 //       reached.set(s, true);

    28 //       dist.set(s, 0);

    29 //     }

    31 //     void run() {

    32 //       while (!bfs_queue.empty()) {

    33 // 	Node v=bfs_queue.front();

    34 // 	OutEdgeIt e=G.template first<OutEdgeIt>(v);

    35 // 	bfs_queue.pop();

    36 // 	for( ; e.valid(); ++e) {

    37 // 	  Node w=G.bNode(e);

    38 // 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;

    39 // 	  if (!reached.get(w)) {

    40 // 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    41 // 	    bfs_queue.push(w);

    42 // 	    dist.set(w, dist.get(v)+1);

    43 // 	    pred.set(w, e);

    44 // 	    reached.set(w, true);

    45 // 	  } else {

    46 // 	    std::cout << G.id(w) << " is already reached" << std::endl;

    47 // 	  }

    48 // 	}

    49 //       }

    50 //     }

    51 //   };

    53 //   template <typename Graph>

    54 //   struct bfs_visitor {

    55 //     typedef typename Graph::Node Node;

    56 //     typedef typename Graph::Edge Edge;

    57 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

    58 //     Graph& G;

    59 //     bfs_visitor(Graph& _G) : G(_G) { }

    60 //     void at_previously_reached(OutEdgeIt& e) {

    61 //       //Node v=G.aNode(e);

    62 //       Node w=G.bNode(e);

    63 //       std::cout << G.id(w) << " is already reached" << std::endl;

    64 //    }

    65 //     void at_newly_reached(OutEdgeIt& e) {

    66 //       //Node v=G.aNode(e);

    67 //       Node w=G.bNode(e);

    68 //       std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    69 //     }

    70 //   };

    72 //   template <typename Graph, typename ReachedMap, typename visitor_type>

    73 //   struct bfs_iterator {

    74 //     typedef typename Graph::Node Node;

    75 //     typedef typename Graph::Edge Edge;

    76 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

    77 //     Graph& G;

    78 //     std::queue<OutEdgeIt>& bfs_queue;

    79 //     ReachedMap& reached;

    80 //     visitor_type& visitor;

    81 //     void process() {

    82 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

    83 //       if (bfs_queue.empty()) return;

    84 //       OutEdgeIt e=bfs_queue.front();

    85 //       //Node v=G.aNode(e);

    86 //       Node w=G.bNode(e);

    87 //       if (!reached.get(w)) {

    88 // 	visitor.at_newly_reached(e);

    89 // 	bfs_queue.push(G.template first<OutEdgeIt>(w));

    90 // 	reached.set(w, true);

    91 //       } else {

    92 // 	visitor.at_previously_reached(e);

    93 //       }

    94 //     }

    95 //     bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {

    96 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

    97 //       valid();

    98 //     }

    99 //     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {

   100 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   101 //       //if (bfs_queue.empty()) return *this;

   102 //       if (!valid()) return *this;

   103 //       ++(bfs_queue.front());

   104 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   105 //       valid();

   106 //       return *this;

   107 //     }

   108 //     //void next() {

   109 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   110 //     //  if (bfs_queue.empty()) return;

   111 //     //  ++(bfs_queue.front());

   112 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   113 //     //}

   114 //     bool valid() {

   115 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   116 //       if (bfs_queue.empty()) return false; else return true;

   117 //     }

   118 //     //bool finished() {

   119 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   120 //     //  if (bfs_queue.empty()) return true; else return false;

   121 //     //}

   122 //     operator Edge () { return bfs_queue.front(); }

   124 //   };

   126 //   template <typename Graph, typename ReachedMap>

   127 //   struct bfs_iterator1 {

   128 //     typedef typename Graph::Node Node;

   129 //     typedef typename Graph::Edge Edge;

   130 //     typedef typename Graph::OutEdgeIt OutEdgeIt;

   131 //     Graph& G;

   132 //     std::queue<OutEdgeIt>& bfs_queue;

   133 //     ReachedMap& reached;

   134 //     bool _newly_reached;

   135 //     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   136 //       valid();

   137 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   138 // 	OutEdgeIt e=bfs_queue.front();

   139 // 	Node w=G.bNode(e);

   140 // 	if (!reached.get(w)) {

   141 // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));

   142 // 	  reached.set(w, true);

   143 // 	  _newly_reached=true;

   144 // 	} else {

   145 // 	  _newly_reached=false;

   146 // 	}

   147 //       }

   148 //     }

   149 //     bfs_iterator1<Graph, ReachedMap>& operator++() {

   150 //       if (!valid()) return *this;

   151 //       ++(bfs_queue.front());

   152 //       valid();

   153 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   154 // 	OutEdgeIt e=bfs_queue.front();

   155 // 	Node w=G.bNode(e);

   156 // 	if (!reached.get(w)) {

   157 // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));

   158 // 	  reached.set(w, true);

   159 // 	  _newly_reached=true;

   160 // 	} else {

   161 // 	  _newly_reached=false;

   162 // 	}

   163 //       }

   164 //       return *this;

   165 //     }

   166 //     bool valid() {

   167 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }

   168 //       if (bfs_queue.empty()) return false; else return true;

   169 //     }

   170 //     operator OutEdgeIt() { return bfs_queue.front(); }

   171 //     //ize

   172 //     bool newly_reached() { return _newly_reached; }

   174 //   };

   176 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   177 //   struct BfsIterator {

   178 //     typedef typename Graph::Node Node;

   179 //     Graph& G;

   180 //     std::queue<OutEdgeIt>& bfs_queue;

   181 //     ReachedMap& reached;

   182 //     bool b_node_newly_reached;

   183 //     OutEdgeIt actual_edge;

   184 //     BfsIterator(Graph& _G,

   185 // 		std::queue<OutEdgeIt>& _bfs_queue,

   186 // 		ReachedMap& _reached) :

   187 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   188 //       actual_edge=bfs_queue.front();

   189 //       if (actual_edge.valid()) {

   190 // 	Node w=G.bNode(actual_edge);

   191 // 	if (!reached.get(w)) {

   192 // 	  bfs_queue.push(G.firstOutEdge(w));

   193 // 	  reached.set(w, true);

   194 // 	  b_node_newly_reached=true;

   195 // 	} else {

   196 // 	  b_node_newly_reached=false;

   197 // 	}

   198 //       }

   199 //     }

   200 //     BfsIterator<Graph, OutEdgeIt, ReachedMap>&

   201 //     operator++() {

   202 //       if (bfs_queue.front().valid()) {

   203 // 	++(bfs_queue.front());

   204 // 	actual_edge=bfs_queue.front();

   205 // 	if (actual_edge.valid()) {

   206 // 	  Node w=G.bNode(actual_edge);

   207 // 	  if (!reached.get(w)) {

   208 // 	    bfs_queue.push(G.firstOutEdge(w));

   209 // 	    reached.set(w, true);

   210 // 	    b_node_newly_reached=true;

   211 // 	  } else {

   212 // 	    b_node_newly_reached=false;

   213 // 	  }

   214 // 	}

   215 //       } else {

   216 // 	bfs_queue.pop();

   217 // 	actual_edge=bfs_queue.front();

   218 // 	if (actual_edge.valid()) {

   219 // 	  Node w=G.bNode(actual_edge);

   220 // 	  if (!reached.get(w)) {

   221 // 	    bfs_queue.push(G.firstOutEdge(w));

   222 // 	    reached.set(w, true);

   223 // 	    b_node_newly_reached=true;

   224 // 	  } else {

   225 // 	    b_node_newly_reached=false;

   226 // 	  }

   227 // 	}

   228 //       }

   229 //       return *this;

   230 //     }

   231 //     bool finished() { return bfs_queue.empty(); }

   232 //     operator OutEdgeIt () { return actual_edge; }

   233 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   234 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   235 //   };

   238 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   239 //   struct DfsIterator {

   240 //     typedef typename Graph::Node Node;

   241 //     Graph& G;

   242 //     std::stack<OutEdgeIt>& bfs_queue;

   243 //     ReachedMap& reached;

   244 //     bool b_node_newly_reached;

   245 //     OutEdgeIt actual_edge;

   246 //     DfsIterator(Graph& _G,

   247 // 		std::stack<OutEdgeIt>& _bfs_queue,

   248 // 		ReachedMap& _reached) :

   249 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   250 //       actual_edge=bfs_queue.top();

   251 //       if (actual_edge.valid()) {

   252 // 	Node w=G.bNode(actual_edge);

   253 // 	if (!reached.get(w)) {

   254 // 	  bfs_queue.push(G.firstOutEdge(w));

   255 // 	  reached.set(w, true);

   256 // 	  b_node_newly_reached=true;

   257 // 	} else {

   258 // 	  ++(bfs_queue.top());

   259 // 	  b_node_newly_reached=false;

   260 // 	}

   261 //       } else {

   262 // 	bfs_queue.pop();

   263 //       }

   264 //     }

   265 //     DfsIterator<Graph, OutEdgeIt, ReachedMap>&

   266 //     operator++() {

   267 //       actual_edge=bfs_queue.top();

   268 //       if (actual_edge.valid()) {

   269 // 	Node w=G.bNode(actual_edge);

   270 // 	if (!reached.get(w)) {

   271 // 	  bfs_queue.push(G.firstOutEdge(w));

   272 // 	  reached.set(w, true);

   273 // 	  b_node_newly_reached=true;

   274 // 	} else {

   275 // 	  ++(bfs_queue.top());

   276 // 	  b_node_newly_reached=false;

   277 // 	}

   278 //       } else {

   279 // 	bfs_queue.pop();

   280 //       }

   281 //       return *this;

   282 //     }

   283 //     bool finished() { return bfs_queue.empty(); }

   284 //     operator OutEdgeIt () { return actual_edge; }

   285 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   286 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   287 //   };

   289 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   290 //   struct BfsIterator1 {

   291 //     typedef typename Graph::Node Node;

   292 //     Graph& G;

   293 //     std::queue<OutEdgeIt>& bfs_queue;

   294 //     ReachedMap& reached;

   295 //     bool b_node_newly_reached;

   296 //     OutEdgeIt actual_edge;

   297 //     BfsIterator1(Graph& _G,

   298 // 		std::queue<OutEdgeIt>& _bfs_queue,

   299 // 		ReachedMap& _reached) :

   300 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   301 //       actual_edge=bfs_queue.front();

   302 //       if (actual_edge.valid()) {

   303 //       	Node w=G.bNode(actual_edge);

   304 // 	if (!reached.get(w)) {

   305 // 	  bfs_queue.push(OutEdgeIt(G, w));

   306 // 	  reached.set(w, true);

   307 // 	  b_node_newly_reached=true;

   308 // 	} else {

   309 // 	  b_node_newly_reached=false;

   310 // 	}

   311 //       }

   312 //     }

   313 //     void next() {

   314 //       if (bfs_queue.front().valid()) {

   315 // 	++(bfs_queue.front());

   316 // 	actual_edge=bfs_queue.front();

   317 // 	if (actual_edge.valid()) {

   318 // 	  Node w=G.bNode(actual_edge);

   319 // 	  if (!reached.get(w)) {

   320 // 	    bfs_queue.push(OutEdgeIt(G, w));

   321 // 	    reached.set(w, true);

   322 // 	    b_node_newly_reached=true;

   323 // 	  } else {

   324 // 	    b_node_newly_reached=false;

   325 // 	  }

   326 // 	}

   327 //       } else {

   328 // 	bfs_queue.pop();

   329 // 	actual_edge=bfs_queue.front();

   330 // 	if (actual_edge.valid()) {

   331 // 	  Node w=G.bNode(actual_edge);

   332 // 	  if (!reached.get(w)) {

   333 // 	    bfs_queue.push(OutEdgeIt(G, w));

   334 // 	    reached.set(w, true);

   335 // 	    b_node_newly_reached=true;

   336 // 	  } else {

   337 // 	    b_node_newly_reached=false;

   338 // 	  }

   339 // 	}

   340 //       }

   341 //       //return *this;

   342 //     }

   343 //     bool finished() { return bfs_queue.empty(); }

   344 //     operator OutEdgeIt () { return actual_edge; }

   345 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   346 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }

   347 //   };

   350 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   351 //   struct DfsIterator1 {

   352 //     typedef typename Graph::Node Node;

   353 //     Graph& G;

   354 //     std::stack<OutEdgeIt>& bfs_queue;

   355 //     ReachedMap& reached;

   356 //     bool b_node_newly_reached;

   357 //     OutEdgeIt actual_edge;

   358 //     DfsIterator1(Graph& _G,

   359 // 		std::stack<OutEdgeIt>& _bfs_queue,

   360 // 		ReachedMap& _reached) :

   361 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   362 //       //actual_edge=bfs_queue.top();

   363 //       //if (actual_edge.valid()) {

   364 //       //	Node w=G.bNode(actual_edge);

   365 //       //if (!reached.get(w)) {

   366 //       //  bfs_queue.push(OutEdgeIt(G, w));

   367 //       //  reached.set(w, true);

   368 //       //  b_node_newly_reached=true;

   369 //       //} else {

   370 //       //  ++(bfs_queue.top());

   371 //       //  b_node_newly_reached=false;

   372 //       //}

   373 //       //} else {

   374 //       //	bfs_queue.pop();

   375 //       //}

   376 //     }

   377 //     void next() {

   378 //       actual_edge=bfs_queue.top();

   379 //       if (actual_edge.valid()) {

   380 // 	Node w=G.bNode(actual_edge);

   381 // 	if (!reached.get(w)) {

   382 // 	  bfs_queue.push(OutEdgeIt(G, w));

   383 // 	  reached.set(w, true);

   384 // 	  b_node_newly_reached=true;

   385 // 	} else {

   386 // 	  ++(bfs_queue.top());

   387 // 	  b_node_newly_reached=false;

   388 // 	}

   389 //       } else {

   390 // 	bfs_queue.pop();

   391 //       }

   392 //       //return *this;

   393 //     }

   394 //     bool finished() { return bfs_queue.empty(); }

   395 //     operator OutEdgeIt () { return actual_edge; }

   396 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

   397 //     bool aNodeIsLeaved() { return !(actual_edge.valid()); }

   398 //   };

   400 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   401 //   class BfsIterator2 {

   402 //     typedef typename Graph::Node Node;

   403 //     const Graph& G;

   404 //     std::queue<OutEdgeIt> bfs_queue;

   405 //     ReachedMap reached;

   406 //     bool b_node_newly_reached;

   407 //     OutEdgeIt actual_edge;

   408 //   public:

   409 //     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }

   410 //     void pushAndSetReached(Node s) {

   411 //       reached.set(s, true);

   412 //       if (bfs_queue.empty()) {

   413 // 	bfs_queue.push(G.template first<OutEdgeIt>(s));

   414 // 	actual_edge=bfs_queue.front();

   415 // 	if (actual_edge.valid()) {

   416 // 	  Node w=G.bNode(actual_edge);

   417 // 	  if (!reached.get(w)) {

   418 // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));

   419 // 	    reached.set(w, true);

   420 // 	    b_node_newly_reached=true;

   421 // 	  } else {

   422 // 	    b_node_newly_reached=false;

   423 // 	  }

   424 // 	} //else {

   425 // 	//}

   426 //       } else {

   427 // 	bfs_queue.push(G.template first<OutEdgeIt>(s));

   428 //       }

   429 //     }

   430 //     BfsIterator2<Graph, OutEdgeIt, ReachedMap>&

   431 //     operator++() {

   432 //       if (bfs_queue.front().valid()) {

   433 // 	++(bfs_queue.front());

   434 // 	actual_edge=bfs_queue.front();

   435 // 	if (actual_edge.valid()) {

   436 // 	  Node w=G.bNode(actual_edge);

   437 // 	  if (!reached.get(w)) {

   438 // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));

   439 // 	    reached.set(w, true);

   440 // 	    b_node_newly_reached=true;

   441 // 	  } else {

   442 // 	    b_node_newly_reached=false;

   443 // 	  }

   444 // 	}

   445 //       } else {

   446 // 	bfs_queue.pop();

   447 // 	if (!bfs_queue.empty()) {

   448 // 	  actual_edge=bfs_queue.front();

   449 // 	  if (actual_edge.valid()) {

   450 // 	    Node w=G.bNode(actual_edge);

   451 // 	    if (!reached.get(w)) {

   452 // 	      bfs_queue.push(G.template first<OutEdgeIt>(w));

   453 // 	      reached.set(w, true);

   454 // 	      b_node_newly_reached=true;

   455 // 	    } else {

   456 // 	      b_node_newly_reached=false;

   457 // 	    }

   458 // 	  }

   459 // 	}

   460 //       }

   461 //       return *this;

   462 //     }

   463 //     bool finished() const { return bfs_queue.empty(); }

   464 //     operator OutEdgeIt () const { return actual_edge; }

   465 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   466 //     bool isANodeExamined() const { return !(actual_edge.valid()); }

   467 //     const ReachedMap& getReachedMap() const { return reached; }

   468 //     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }

   469 //  };

   472 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   473 //   class BfsIterator3 {

   474 //     typedef typename Graph::Node Node;

   475 //     const Graph& G;

   476 //     std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;

   477 //     ReachedMap reached;

   478 //     bool b_node_newly_reached;

   479 //     OutEdgeIt actual_edge;

   480 //   public:

   481 //     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }

   482 //     void pushAndSetReached(Node s) {

   483 //       reached.set(s, true);

   484 //       if (bfs_queue.empty()) {

   485 // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));

   486 // 	actual_edge=bfs_queue.front().second;

   487 // 	if (actual_edge.valid()) {

   488 // 	  Node w=G.bNode(actual_edge);

   489 // 	  if (!reached.get(w)) {

   490 // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   491 // 	    reached.set(w, true);

   492 // 	    b_node_newly_reached=true;

   493 // 	  } else {

   494 // 	    b_node_newly_reached=false;

   495 // 	  }

   496 // 	} //else {

   497 // 	//}

   498 //       } else {

   499 // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));

   500 //       }

   501 //     }

   502 //     BfsIterator3<Graph, OutEdgeIt, ReachedMap>&

   503 //     operator++() {

   504 //       if (bfs_queue.front().second.valid()) {

   505 // 	++(bfs_queue.front().second);

   506 // 	actual_edge=bfs_queue.front().second;

   507 // 	if (actual_edge.valid()) {

   508 // 	  Node w=G.bNode(actual_edge);

   509 // 	  if (!reached.get(w)) {

   510 // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   511 // 	    reached.set(w, true);

   512 // 	    b_node_newly_reached=true;

   513 // 	  } else {

   514 // 	    b_node_newly_reached=false;

   515 // 	  }

   516 // 	}

   517 //       } else {

   518 // 	bfs_queue.pop();

   519 // 	if (!bfs_queue.empty()) {

   520 // 	  actual_edge=bfs_queue.front().second;

   521 // 	  if (actual_edge.valid()) {

   522 // 	    Node w=G.bNode(actual_edge);

   523 // 	    if (!reached.get(w)) {

   524 // 	      bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));

   525 // 	      reached.set(w, true);

   526 // 	      b_node_newly_reached=true;

   527 // 	    } else {

   528 // 	      b_node_newly_reached=false;

   529 // 	    }

   530 // 	  }

   531 // 	}

   532 //       }

   533 //       return *this;

   534 //     }

   535 //     bool finished() const { return bfs_queue.empty(); }

   536 //     operator OutEdgeIt () const { return actual_edge; }

   537 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   538 //     bool isANodeExamined() const { return !(actual_edge.valid()); }

   539 //     Node aNode() const { return bfs_queue.front().first; }

   540 //     Node bNode() const { return G.bNode(actual_edge); }

   541 //     const ReachedMap& getReachedMap() const { return reached; }

   542 //     //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }

   543 //  };

   546 //   template <typename Graph, typename OutEdgeIt,

   547 // 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   548 //   class BfsIterator4 {

   549 //     typedef typename Graph::Node Node;

   550 //     const Graph& G;

   551 //     std::queue<Node> bfs_queue;

   552 //     ReachedMap& reached;

   553 //     bool b_node_newly_reached;

   554 //     OutEdgeIt actual_edge;

   555 //     bool own_reached_map;

   556 //   public:

   557 //     BfsIterator4(const Graph& _G, ReachedMap& _reached) :

   558 //       G(_G), reached(_reached),

   559 //       own_reached_map(false) { }

   560 //     BfsIterator4(const Graph& _G) :

   561 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   562 //       own_reached_map(true) { }

   563 //     ~BfsIterator4() { if (own_reached_map) delete &reached; }

   564 //     void pushAndSetReached(Node s) {

   565 //       //std::cout << "mimi" << &reached << std::endl;

   566 //       reached.set(s, true);

   567 //       //std::cout << "mumus" << std::endl;

   568 //       if (bfs_queue.empty()) {

   569 // 	//std::cout << "bibi1" << std::endl;

   570 // 	bfs_queue.push(s);

   571 // 	//std::cout << "zizi" << std::endl;

   572 // 	G./*getF*/first(actual_edge, s);

   573 // 	//std::cout << "kiki" << std::endl;

   574 // 	if (G.valid(actual_edge)/*.valid()*/) {

   575 // 	  Node w=G.bNode(actual_edge);

   576 // 	  if (!reached.get(w)) {

   577 // 	    bfs_queue.push(w);

   578 // 	    reached.set(w, true);

   579 // 	    b_node_newly_reached=true;

   580 // 	  } else {

   581 // 	    b_node_newly_reached=false;

   582 // 	  }

   583 // 	}

   584 //       } else {

   585 // 	//std::cout << "bibi2" << std::endl;

   586 // 	bfs_queue.push(s);

   587 //       }

   588 //     }

   589 //     BfsIterator4<Graph, OutEdgeIt, ReachedMap>&

   590 //     operator++() {

   591 //       if (G.valid(actual_edge)/*.valid()*/) {

   592 // 	/*++*/G.next(actual_edge);

   593 // 	if (G.valid(actual_edge)/*.valid()*/) {

   594 // 	  Node w=G.bNode(actual_edge);

   595 // 	  if (!reached.get(w)) {

   596 // 	    bfs_queue.push(w);

   597 // 	    reached.set(w, true);

   598 // 	    b_node_newly_reached=true;

   599 // 	  } else {

   600 // 	    b_node_newly_reached=false;

   601 // 	  }

   602 // 	}

   603 //       } else {

   604 // 	bfs_queue.pop();

   605 // 	if (!bfs_queue.empty()) {

   606 // 	  G./*getF*/first(actual_edge, bfs_queue.front());

   607 // 	  if (G.valid(actual_edge)/*.valid()*/) {

   608 // 	    Node w=G.bNode(actual_edge);

   609 // 	    if (!reached.get(w)) {

   610 // 	      bfs_queue.push(w);

   611 // 	      reached.set(w, true);

   612 // 	      b_node_newly_reached=true;

   613 // 	    } else {

   614 // 	      b_node_newly_reached=false;

   615 // 	    }

   616 // 	  }

   617 // 	}

   618 //       }

   619 //       return *this;

   620 //     }

   621 //     bool finished() const { return bfs_queue.empty(); }

   622 //     operator OutEdgeIt () const { return actual_edge; }

   623 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   624 //     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   625 //     Node aNode() const { return bfs_queue.front(); }

   626 //     Node bNode() const { return G.bNode(actual_edge); }

   627 //     const ReachedMap& getReachedMap() const { return reached; }

   628 //     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   629 //  };

   632   template <typename Graph, /*typename OutEdgeIt,*/

   633 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   634   class BfsIterator5 {

   635   protected:

   636     typedef typename Graph::Node Node;

   637     typedef typename Graph::OutEdgeIt OutEdgeIt;

   638     const Graph* graph;

   639     std::queue<Node> bfs_queue;

   640     ReachedMap& reached;

   641     bool b_node_newly_reached;

   642     OutEdgeIt actual_edge;

   643     bool own_reached_map;

   644   public:

   645     BfsIterator5(const Graph& _graph, ReachedMap& _reached) :

   646       graph(&_graph), reached(_reached),

   647       own_reached_map(false) { }

   648     BfsIterator5(const Graph& _graph) :

   649       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),

   650       own_reached_map(true) { }

   651     ~BfsIterator5() { if (own_reached_map) delete &reached; }

   652     void pushAndSetReached(Node s) {

   653       reached.set(s, true);

   654       if (bfs_queue.empty()) {

   655 	bfs_queue.push(s);

   656 	graph->first(actual_edge, s);

   657 	if (graph->valid(actual_edge)) {

   658 	  Node w=graph->bNode(actual_edge);

   659 	  if (!reached[w]) {

   660 	    bfs_queue.push(w);

   661 	    reached.set(w, true);

   662 	    b_node_newly_reached=true;

   663 	  } else {

   664 	    b_node_newly_reached=false;

   665 	  }

   666 	}

   667       } else {

   668 	bfs_queue.push(s);

   669       }

   670     }

   671     BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&

   672     operator++() {

   673       if (graph->valid(actual_edge)) {

   674 	graph->next(actual_edge);

   675 	if (graph->valid(actual_edge)) {

   676 	  Node w=graph->bNode(actual_edge);

   677 	  if (!reached[w]) {

   678 	    bfs_queue.push(w);

   679 	    reached.set(w, true);

   680 	    b_node_newly_reached=true;

   681 	  } else {

   682 	    b_node_newly_reached=false;

   683 	  }

   684 	}

   685       } else {

   686 	bfs_queue.pop();

   687 	if (!bfs_queue.empty()) {

   688 	  graph->first(actual_edge, bfs_queue.front());

   689 	  if (graph->valid(actual_edge)) {

   690 	    Node w=graph->bNode(actual_edge);

   691 	    if (!reached[w]) {

   692 	      bfs_queue.push(w);

   693 	      reached.set(w, true);

   694 	      b_node_newly_reached=true;

   695 	    } else {

   696 	      b_node_newly_reached=false;

   697 	    }

   698 	  }

   699 	}

   700       }

   701       return *this;

   702     }

   703     bool finished() const { return bfs_queue.empty(); }

   704     operator OutEdgeIt () const { return actual_edge; }

   705     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   706     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

   707     Node aNode() const { return bfs_queue.front(); }

   708     Node bNode() const { return graph->bNode(actual_edge); }

   709     const ReachedMap& getReachedMap() const { return reached; }

   710     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   711   };

   713 //   template <typename Graph, typename OutEdgeIt,

   714 // 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   715 //   class DfsIterator4 {

   716 //     typedef typename Graph::Node Node;

   717 //     const Graph& G;

   718 //     std::stack<OutEdgeIt> dfs_stack;

   719 //     bool b_node_newly_reached;

   720 //     OutEdgeIt actual_edge;

   721 //     Node actual_node;

   722 //     ReachedMap& reached;

   723 //     bool own_reached_map;

   724 //   public:

   725 //     DfsIterator4(const Graph& _G, ReachedMap& _reached) :

   726 //       G(_G), reached(_reached),

   727 //       own_reached_map(false) { }

   728 //     DfsIterator4(const Graph& _G) :

   729 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),

   730 //       own_reached_map(true) { }

   731 //     ~DfsIterator4() { if (own_reached_map) delete &reached; }

   732 //     void pushAndSetReached(Node s) {

   733 //       actual_node=s;

   734 //       reached.set(s, true);

   735 //       dfs_stack.push(G.template first<OutEdgeIt>(s));

   736 //     }

   737 //     DfsIterator4<Graph, OutEdgeIt, ReachedMap>&

   738 //     operator++() {

   739 //       actual_edge=dfs_stack.top();

   740 //       //actual_node=G.aNode(actual_edge);

   741 //       if (G.valid(actual_edge)/*.valid()*/) {

   742 // 	Node w=G.bNode(actual_edge);

   743 // 	actual_node=w;

   744 // 	if (!reached.get(w)) {

   745 // 	  dfs_stack.push(G.template first<OutEdgeIt>(w));

   746 // 	  reached.set(w, true);

   747 // 	  b_node_newly_reached=true;

   748 // 	} else {

   749 // 	  actual_node=G.aNode(actual_edge);

   750 // 	  /*++*/G.next(dfs_stack.top());

   751 // 	  b_node_newly_reached=false;

   752 // 	}

   753 //       } else {

   754 // 	//actual_node=G.aNode(dfs_stack.top());

   755 // 	dfs_stack.pop();

   756 //       }

   757 //       return *this;

   758 //     }

   759 //     bool finished() const { return dfs_stack.empty(); }

   760 //     operator OutEdgeIt () const { return actual_edge; }

   761 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   762 //     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }

   763 //     Node aNode() const { return actual_node; /*FIXME*/}

   764 //     Node bNode() const { return G.bNode(actual_edge); }

   765 //     const ReachedMap& getReachedMap() const { return reached; }

   766 //     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   767 //   };

   769   template <typename Graph, /*typename OutEdgeIt,*/

   770 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   771   class DfsIterator5 {

   772   protected:

   773     typedef typename Graph::Node Node;

   774     typedef typename Graph::OutEdgeIt OutEdgeIt;

   775     const Graph* graph;

   776     std::stack<OutEdgeIt> dfs_stack;

   777     bool b_node_newly_reached;

   778     OutEdgeIt actual_edge;

   779     Node actual_node;

   780     ReachedMap& reached;

   781     bool own_reached_map;

   782   public:

   783     DfsIterator5(const Graph& _graph, ReachedMap& _reached) :

   784       graph(&_graph), reached(_reached),

   785       own_reached_map(false) { }

   786     DfsIterator5(const Graph& _graph) :

   787       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),

   788       own_reached_map(true) { }

   789     ~DfsIterator5() { if (own_reached_map) delete &reached; }

   790     void pushAndSetReached(Node s) {

   791       actual_node=s;

   792       reached.set(s, true);

   793       OutEdgeIt e;

   794       graph->first(e, s);

   795       dfs_stack.push(e);

   796     }

   797     DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&

   798     operator++() {

   799       actual_edge=dfs_stack.top();

   800       //actual_node=G.aNode(actual_edge);

   801       if (graph->valid(actual_edge)/*.valid()*/) {

   802 	Node w=graph->bNode(actual_edge);

   803 	actual_node=w;

   804 	if (!reached[w]) {

   805 	  OutEdgeIt e;

   806 	  graph->first(e, w);

   807 	  dfs_stack.push(e);

   808 	  reached.set(w, true);

   809 	  b_node_newly_reached=true;

   810 	} else {

   811 	  actual_node=graph->aNode(actual_edge);

   812 	  graph->next(dfs_stack.top());

   813 	  b_node_newly_reached=false;

   814 	}

   815       } else {

   816 	//actual_node=G.aNode(dfs_stack.top());

   817 	dfs_stack.pop();

   818       }

   819       return *this;

   820     }

   821     bool finished() const { return dfs_stack.empty(); }

   822     operator OutEdgeIt () const { return actual_edge; }

   823     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   824     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

   825     Node aNode() const { return actual_node; /*FIXME*/}

   826     Node bNode() const { return G.bNode(actual_edge); }

   827     const ReachedMap& getReachedMap() const { return reached; }

   828     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   829   };

   833 } // namespace hugo

   835 #endif //HUGO_BFS_ITERATOR_H

author	klao
	Mon, 05 Apr 2004 18:24:37 +0000
changeset 310	76c005b15354
parent 301	7eb324ed5da3
child 360	91fba31268d6
permissions	-rw-r--r--