lemon-0.x: src/work/bfs_iterator.hh@15362fafaf1a

     1 #ifndef BFS_ITERATOR_HH

     2 #define BFS_ITERATOR_HH

     4 #include <queue>

     5 #include <stack>

     6 #include <utility>

     7 #include <graph_wrapper.h>

     9 namespace marci {

    11   template <typename Graph>

    12   struct bfs {

    13     typedef typename Graph::NodeIt NodeIt;

    14     typedef typename Graph::EdgeIt EdgeIt;

    15     typedef typename Graph::EachNodeIt EachNodeIt;

    16     typedef typename Graph::OutEdgeIt OutEdgeIt;

    17     Graph& G;

    18     NodeIt s;

    19     typename Graph::NodeMap<bool> reached;

    20     typename Graph::NodeMap<EdgeIt> pred;

    21     typename Graph::NodeMap<int> dist;

    22     std::queue<NodeIt> bfs_queue;

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

    24       bfs_queue.push(s);

    25       for(EachNodeIt i=G.template first<EachNodeIt>(); 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 	NodeIt v=bfs_queue.front();

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

    35 	bfs_queue.pop();

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

    37 	  NodeIt 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::NodeIt NodeIt;

    56     typedef typename Graph::EdgeIt EdgeIt;

    57     typedef typename Graph::OutEdgeIt OutEdgeIt;

    58     Graph& G;

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

    60     void at_previously_reached(OutEdgeIt& e) {

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

    62       NodeIt w=G.bNode(e);

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

    64    }

    65     void at_newly_reached(OutEdgeIt& e) {

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

    67       NodeIt 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::NodeIt NodeIt;

    75     typedef typename Graph::EdgeIt EdgeIt;

    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       //NodeIt v=G.aNode(e);

    86       NodeIt 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 EdgeIt () { return bfs_queue.front(); }

   124   };

   126   template <typename Graph, typename ReachedMap>

   127   struct bfs_iterator1 {

   128     typedef typename Graph::NodeIt NodeIt;

   129     typedef typename Graph::EdgeIt EdgeIt;

   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 	NodeIt 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 	NodeIt 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::NodeIt NodeIt;

   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 	NodeIt 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 	  NodeIt 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 	  NodeIt 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::NodeIt NodeIt;

   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 	NodeIt 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 	NodeIt 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 aNodeIsLeaved() { return !(actual_edge.valid()); }

   287   };

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

   290   struct BfsIterator1 {

   291     typedef typename Graph::NodeIt NodeIt;

   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       	NodeIt 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 	  NodeIt 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 	  NodeIt 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::NodeIt NodeIt;

   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       //	NodeIt 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 	NodeIt 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::NodeIt NodeIt;

   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(NodeIt 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 	  NodeIt 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 	  NodeIt 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 	    NodeIt 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::NodeIt NodeIt;

   475     const Graph& G;

   476     std::queue< std::pair<NodeIt, 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(NodeIt s) {

   483       reached.set(s, true);

   484       if (bfs_queue.empty()) {

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

   486 	actual_edge=bfs_queue.front().second;

   487 	if (actual_edge.valid()) {

   488 	  NodeIt w=G.bNode(actual_edge);

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

   490 	    bfs_queue.push(std::pair<NodeIt, 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<NodeIt, 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 	  NodeIt w=G.bNode(actual_edge);

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

   510 	    bfs_queue.push(std::pair<NodeIt, 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 	    NodeIt w=G.bNode(actual_edge);

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

   524 	      bfs_queue.push(std::pair<NodeIt, 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     NodeIt aNode() const { return bfs_queue.front().first; }

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

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

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

   543  };

   545   template <typename Graph, typename OutEdgeIt, typename ReachedMap>

   546   class BfsIterator4 {

   547     typedef typename Graph::NodeIt NodeIt;

   548     const Graph& G;

   549     std::queue<NodeIt> bfs_queue;

   550     ReachedMap reached;

   551     bool b_node_newly_reached;

   552     OutEdgeIt actual_edge;

   553   public:

   554     BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }

   555     void pushAndSetReached(NodeIt s) {

   556       reached.set(s, true);

   557       if (bfs_queue.empty()) {

   558 	bfs_queue.push(s);

   559 	G.getFirst(actual_edge, s);

   560 	if (actual_edge.valid()) {

   561 	  NodeIt w=G.bNode(actual_edge);

   562 	  if (!reached.get(w)) {

   563 	    bfs_queue.push(w);

   564 	    reached.set(w, true);

   565 	    b_node_newly_reached=true;

   566 	  } else {

   567 	    b_node_newly_reached=false;

   568 	  }

   569 	}

   570       } else {

   571 	bfs_queue.push(s);

   572       }

   573     }

   574     BfsIterator4<Graph, OutEdgeIt, ReachedMap>&

   575     operator++() {

   576       if (actual_edge.valid()) {

   577 	++actual_edge;

   578 	if (actual_edge.valid()) {

   579 	  NodeIt w=G.bNode(actual_edge);

   580 	  if (!reached.get(w)) {

   581 	    bfs_queue.push(w);

   582 	    reached.set(w, true);

   583 	    b_node_newly_reached=true;

   584 	  } else {

   585 	    b_node_newly_reached=false;

   586 	  }

   587 	}

   588       } else {

   589 	bfs_queue.pop();

   590 	if (!bfs_queue.empty()) {

   591 	  G.getFirst(actual_edge, bfs_queue.front());

   592 	  if (actual_edge.valid()) {

   593 	    NodeIt w=G.bNode(actual_edge);

   594 	    if (!reached.get(w)) {

   595 	      bfs_queue.push(w);

   596 	      reached.set(w, true);

   597 	      b_node_newly_reached=true;

   598 	    } else {

   599 	      b_node_newly_reached=false;

   600 	    }

   601 	  }

   602 	}

   603       }

   604       return *this;

   605     }

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

   607     operator OutEdgeIt () const { return actual_edge; }

   608     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

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

   610     NodeIt aNode() const { return bfs_queue.front(); }

   611     NodeIt bNode() const { return G.bNode(actual_edge); }

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

   613     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }

   614  };

   617   template <typename GraphWrapper, typename ReachedMap>

   618   class BfsIterator5 {

   619     typedef typename GraphWrapper::NodeIt NodeIt;

   620     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   621     GraphWrapper gw;

   622     std::queue<NodeIt> bfs_queue;

   623     ReachedMap reached;

   624     bool b_node_newly_reached;

   625     OutEdgeIt actual_edge;

   626   public:

   627     BfsIterator5(GraphWrapper _gw) :

   628       gw(_gw), reached(_gw.getGraph()) { }

   629     void pushAndSetReached(NodeIt s) {

   630       reached.set(s, true);

   631       if (bfs_queue.empty()) {

   632 	bfs_queue.push(s);

   633 	gw.getFirst(actual_edge, s);

   634 	if (actual_edge.valid()) {

   635 	  NodeIt w=gw.bNode(actual_edge);

   636 	  if (!reached.get(w)) {

   637 	    bfs_queue.push(w);

   638 	    reached.set(w, true);

   639 	    b_node_newly_reached=true;

   640 	  } else {

   641 	    b_node_newly_reached=false;

   642 	  }

   643 	}

   644       } else {

   645 	bfs_queue.push(s);

   646       }

   647     }

   648     BfsIterator5<GraphWrapper, ReachedMap>&

   649     operator++() {

   650       if (actual_edge.valid()) {

   651 	++actual_edge;

   652 	if (actual_edge.valid()) {

   653 	  NodeIt w=gw.bNode(actual_edge);

   654 	  if (!reached.get(w)) {

   655 	    bfs_queue.push(w);

   656 	    reached.set(w, true);

   657 	    b_node_newly_reached=true;

   658 	  } else {

   659 	    b_node_newly_reached=false;

   660 	  }

   661 	}

   662       } else {

   663 	bfs_queue.pop();

   664 	if (!bfs_queue.empty()) {

   665 	  gw.getFirst(actual_edge, bfs_queue.front());

   666 	  if (actual_edge.valid()) {

   667 	    NodeIt w=gw.bNode(actual_edge);

   668 	    if (!reached.get(w)) {

   669 	      bfs_queue.push(w);

   670 	      reached.set(w, true);

   671 	      b_node_newly_reached=true;

   672 	    } else {

   673 	      b_node_newly_reached=false;

   674 	    }

   675 	  }

   676 	}

   677       }

   678       return *this;

   679     }

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

   681     operator OutEdgeIt () const { return actual_edge; }

   682     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

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

   684     NodeIt aNode() const { return bfs_queue.front(); }

   685     NodeIt bNode() const { return gw.bNode(actual_edge); }

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

   687     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }

   688  };

   692 } // namespace marci

   694 #endif //BFS_ITERATOR_HH

author	jacint
	Tue, 17 Feb 2004 11:16:39 +0000
changeset 85	15362fafaf1a
parent 64	72bd463289a9
child 99	f26897fb91fd
permissions	-rw-r--r--