lemon-0.x: src/work/bfs_iterator.hh@82d3dbe912d9

     1 #ifndef BFS_ITERATOR_HH

     2 #define BFS_ITERATOR_HH

     4 #include <queue>

     5 #include <stack>

     7 namespace marci {

     9   template <typename Graph>

    10   struct bfs {

    11     typedef typename Graph::NodeIt NodeIt;

    12     typedef typename Graph::EdgeIt EdgeIt;

    13     typedef typename Graph::EachNodeIt EachNodeIt;

    14     typedef typename Graph::OutEdgeIt OutEdgeIt;

    15     Graph& G;

    16     NodeIt s;

    17     typename Graph::NodeMap<bool> reached;

    18     typename Graph::NodeMap<EdgeIt> pred;

    19     typename Graph::NodeMap<int> dist;

    20     std::queue<NodeIt> bfs_queue;

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

    22       bfs_queue.push(s);

    23       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)

    24 	reached.set(i, false);

    25       reached.set(s, true);

    26       dist.set(s, 0);

    27     }

    29     void run() {

    30       while (!bfs_queue.empty()) {

    31 	NodeIt v=bfs_queue.front();

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

    33 	bfs_queue.pop();

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

    35 	  NodeIt w=G.bNode(e);

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

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

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

    39 	    bfs_queue.push(w);

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

    41 	    pred.set(w, e);

    42 	    reached.set(w, true);

    43 	  } else {

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

    45 	  }

    46 	}

    47       }

    48     }

    49   };

    51   template <typename Graph>

    52   struct bfs_visitor {

    53     typedef typename Graph::NodeIt NodeIt;

    54     typedef typename Graph::EdgeIt EdgeIt;

    55     typedef typename Graph::OutEdgeIt OutEdgeIt;

    56     Graph& G;

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

    58     void at_previously_reached(OutEdgeIt& e) {

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

    60       NodeIt w=G.bNode(e);

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

    62    }

    63     void at_newly_reached(OutEdgeIt& e) {

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

    65       NodeIt w=G.bNode(e);

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

    67     }

    68   };

    70   template <typename Graph, typename ReachedMap, typename visitor_type>

    71   struct bfs_iterator {

    72     typedef typename Graph::NodeIt NodeIt;

    73     typedef typename Graph::EdgeIt EdgeIt;

    74     typedef typename Graph::OutEdgeIt OutEdgeIt;

    75     Graph& G;

    76     std::queue<OutEdgeIt>& bfs_queue;

    77     ReachedMap& reached;

    78     visitor_type& visitor;

    79     void process() {

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

    81       if (bfs_queue.empty()) return;

    82       OutEdgeIt e=bfs_queue.front();

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

    84       NodeIt w=G.bNode(e);

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

    86 	visitor.at_newly_reached(e);

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

    88 	reached.set(w, true);

    89       } else {

    90 	visitor.at_previously_reached(e);

    91       }

    92     }

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

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

    95       valid();

    96     }

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

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

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

   100       if (!valid()) return *this;

   101       ++(bfs_queue.front());

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

   103       valid();

   104       return *this;

   105     }

   106     //void next() {

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

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

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

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

   111     //}

   112     bool valid() {

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

   114       if (bfs_queue.empty()) return false; else return true;

   115     }

   116     //bool finished() {

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

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

   119     //}

   120     operator EdgeIt () { return bfs_queue.front(); }

   122   };

   124   template <typename Graph, typename ReachedMap>

   125   struct bfs_iterator1 {

   126     typedef typename Graph::NodeIt NodeIt;

   127     typedef typename Graph::EdgeIt EdgeIt;

   128     typedef typename Graph::OutEdgeIt OutEdgeIt;

   129     Graph& G;

   130     std::queue<OutEdgeIt>& bfs_queue;

   131     ReachedMap& reached;

   132     bool _newly_reached;

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

   134       valid();

   135       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   136 	OutEdgeIt e=bfs_queue.front();

   137 	NodeIt w=G.bNode(e);

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

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

   140 	  reached.set(w, true);

   141 	  _newly_reached=true;

   142 	} else {

   143 	  _newly_reached=false;

   144 	}

   145       }

   146     }

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

   148       if (!valid()) return *this;

   149       ++(bfs_queue.front());

   150       valid();

   151       if (!bfs_queue.empty() && bfs_queue.front().valid()) {

   152 	OutEdgeIt e=bfs_queue.front();

   153 	NodeIt w=G.bNode(e);

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

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

   156 	  reached.set(w, true);

   157 	  _newly_reached=true;

   158 	} else {

   159 	  _newly_reached=false;

   160 	}

   161       }

   162       return *this;

   163     }

   164     bool valid() {

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

   166       if (bfs_queue.empty()) return false; else return true;

   167     }

   168     operator OutEdgeIt() { return bfs_queue.front(); }

   169     //ize

   170     bool newly_reached() { return _newly_reached; }

   172   };

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

   175   struct BfsIterator {

   176     typedef typename Graph::NodeIt NodeIt;

   177     Graph& G;

   178     std::queue<OutEdgeIt>& bfs_queue;

   179     ReachedMap& reached;

   180     bool b_node_newly_reached;

   181     OutEdgeIt actual_edge;

   182     BfsIterator(Graph& _G,

   183 		std::queue<OutEdgeIt>& _bfs_queue,

   184 		ReachedMap& _reached) :

   185       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   186       actual_edge=bfs_queue.front();

   187       if (actual_edge.valid()) {

   188 	NodeIt w=G.bNode(actual_edge);

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

   190 	  bfs_queue.push(G.firstOutEdge(w));

   191 	  reached.set(w, true);

   192 	  b_node_newly_reached=true;

   193 	} else {

   194 	  b_node_newly_reached=false;

   195 	}

   196       }

   197     }

   198     BfsIterator<Graph, OutEdgeIt, ReachedMap>&

   199     operator++() {

   200       if (bfs_queue.front().valid()) {

   201 	++(bfs_queue.front());

   202 	actual_edge=bfs_queue.front();

   203 	if (actual_edge.valid()) {

   204 	  NodeIt w=G.bNode(actual_edge);

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

   206 	    bfs_queue.push(G.firstOutEdge(w));

   207 	    reached.set(w, true);

   208 	    b_node_newly_reached=true;

   209 	  } else {

   210 	    b_node_newly_reached=false;

   211 	  }

   212 	}

   213       } else {

   214 	bfs_queue.pop();

   215 	actual_edge=bfs_queue.front();

   216 	if (actual_edge.valid()) {

   217 	  NodeIt w=G.bNode(actual_edge);

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

   219 	    bfs_queue.push(G.firstOutEdge(w));

   220 	    reached.set(w, true);

   221 	    b_node_newly_reached=true;

   222 	  } else {

   223 	    b_node_newly_reached=false;

   224 	  }

   225 	}

   226       }

   227       return *this;

   228     }

   229     bool finished() { return bfs_queue.empty(); }

   230     operator OutEdgeIt () { return actual_edge; }

   231     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

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

   233   };

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

   237   struct DfsIterator {

   238     typedef typename Graph::NodeIt NodeIt;

   239     Graph& G;

   240     std::stack<OutEdgeIt>& bfs_queue;

   241     ReachedMap& reached;

   242     bool b_node_newly_reached;

   243     OutEdgeIt actual_edge;

   244     DfsIterator(Graph& _G,

   245 		std::stack<OutEdgeIt>& _bfs_queue,

   246 		ReachedMap& _reached) :

   247       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   248       actual_edge=bfs_queue.top();

   249       if (actual_edge.valid()) {

   250 	NodeIt w=G.bNode(actual_edge);

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

   252 	  bfs_queue.push(G.firstOutEdge(w));

   253 	  reached.set(w, true);

   254 	  b_node_newly_reached=true;

   255 	} else {

   256 	  ++(bfs_queue.top());

   257 	  b_node_newly_reached=false;

   258 	}

   259       } else {

   260 	bfs_queue.pop();

   261       }

   262     }

   263     DfsIterator<Graph, OutEdgeIt, ReachedMap>&

   264     operator++() {

   265       actual_edge=bfs_queue.top();

   266       if (actual_edge.valid()) {

   267 	NodeIt w=G.bNode(actual_edge);

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

   269 	  bfs_queue.push(G.firstOutEdge(w));

   270 	  reached.set(w, true);

   271 	  b_node_newly_reached=true;

   272 	} else {

   273 	  ++(bfs_queue.top());

   274 	  b_node_newly_reached=false;

   275 	}

   276       } else {

   277 	bfs_queue.pop();

   278       }

   279       return *this;

   280     }

   281     bool finished() { return bfs_queue.empty(); }

   282     operator OutEdgeIt () { return actual_edge; }

   283     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

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

   285   };

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

   288   struct BfsIterator1 {

   289     typedef typename Graph::NodeIt NodeIt;

   290     Graph& G;

   291     std::queue<OutEdgeIt>& bfs_queue;

   292     ReachedMap& reached;

   293     bool b_node_newly_reached;

   294     OutEdgeIt actual_edge;

   295     BfsIterator1(Graph& _G,

   296 		std::queue<OutEdgeIt>& _bfs_queue,

   297 		ReachedMap& _reached) :

   298       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   299       actual_edge=bfs_queue.front();

   300       if (actual_edge.valid()) {

   301       	NodeIt w=G.bNode(actual_edge);

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

   303 	  bfs_queue.push(OutEdgeIt(G, w));

   304 	  reached.set(w, true);

   305 	  b_node_newly_reached=true;

   306 	} else {

   307 	  b_node_newly_reached=false;

   308 	}

   309       }

   310     }

   311     void next() {

   312       if (bfs_queue.front().valid()) {

   313 	++(bfs_queue.front());

   314 	actual_edge=bfs_queue.front();

   315 	if (actual_edge.valid()) {

   316 	  NodeIt w=G.bNode(actual_edge);

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

   318 	    bfs_queue.push(OutEdgeIt(G, w));

   319 	    reached.set(w, true);

   320 	    b_node_newly_reached=true;

   321 	  } else {

   322 	    b_node_newly_reached=false;

   323 	  }

   324 	}

   325       } else {

   326 	bfs_queue.pop();

   327 	actual_edge=bfs_queue.front();

   328 	if (actual_edge.valid()) {

   329 	  NodeIt w=G.bNode(actual_edge);

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

   331 	    bfs_queue.push(OutEdgeIt(G, w));

   332 	    reached.set(w, true);

   333 	    b_node_newly_reached=true;

   334 	  } else {

   335 	    b_node_newly_reached=false;

   336 	  }

   337 	}

   338       }

   339       //return *this;

   340     }

   341     bool finished() { return bfs_queue.empty(); }

   342     operator OutEdgeIt () { return actual_edge; }

   343     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

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

   345   };

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

   349   struct DfsIterator1 {

   350     typedef typename Graph::NodeIt NodeIt;

   351     Graph& G;

   352     std::stack<OutEdgeIt>& bfs_queue;

   353     ReachedMap& reached;

   354     bool b_node_newly_reached;

   355     OutEdgeIt actual_edge;

   356     DfsIterator1(Graph& _G,

   357 		std::stack<OutEdgeIt>& _bfs_queue,

   358 		ReachedMap& _reached) :

   359       G(_G), bfs_queue(_bfs_queue), reached(_reached) {

   360       //actual_edge=bfs_queue.top();

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

   362       //	NodeIt w=G.bNode(actual_edge);

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

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

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

   366       //  b_node_newly_reached=true;

   367       //} else {

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

   369       //  b_node_newly_reached=false;

   370       //}

   371       //} else {

   372       //	bfs_queue.pop();

   373       //}

   374     }

   375     void next() {

   376       actual_edge=bfs_queue.top();

   377       if (actual_edge.valid()) {

   378 	NodeIt w=G.bNode(actual_edge);

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

   380 	  bfs_queue.push(OutEdgeIt(G, w));

   381 	  reached.set(w, true);

   382 	  b_node_newly_reached=true;

   383 	} else {

   384 	  ++(bfs_queue.top());

   385 	  b_node_newly_reached=false;

   386 	}

   387       } else {

   388 	bfs_queue.pop();

   389       }

   390       //return *this;

   391     }

   392     bool finished() { return bfs_queue.empty(); }

   393     operator OutEdgeIt () { return actual_edge; }

   394     bool bNodeIsNewlyReached() { return b_node_newly_reached; }

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

   396   };

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

   399   class BfsIterator2 {

   400     typedef typename Graph::NodeIt NodeIt;

   401     const Graph& G;

   402     std::queue<OutEdgeIt> bfs_queue;

   403     ReachedMap reached;

   404     bool b_node_newly_reached;

   405     OutEdgeIt actual_edge;

   406   public:

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

   408     void pushAndSetReached(NodeIt s) {

   409       reached.set(s, true);

   410       if (bfs_queue.empty()) {

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

   412 	actual_edge=bfs_queue.front();

   413 	if (actual_edge.valid()) {

   414 	  NodeIt w=G.bNode(actual_edge);

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

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

   417 	    reached.set(w, true);

   418 	    b_node_newly_reached=true;

   419 	  } else {

   420 	    b_node_newly_reached=false;

   421 	  }

   422 	} //else {

   423 	//}

   424       } else {

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

   426       }

   427     }

   428     BfsIterator2<Graph, OutEdgeIt, ReachedMap>&

   429     operator++() {

   430       if (bfs_queue.front().valid()) {

   431 	++(bfs_queue.front());

   432 	actual_edge=bfs_queue.front();

   433 	if (actual_edge.valid()) {

   434 	  NodeIt w=G.bNode(actual_edge);

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

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

   437 	    reached.set(w, true);

   438 	    b_node_newly_reached=true;

   439 	  } else {

   440 	    b_node_newly_reached=false;

   441 	  }

   442 	}

   443       } else {

   444 	bfs_queue.pop();

   445 	if (!bfs_queue.empty()) {

   446 	  actual_edge=bfs_queue.front();

   447 	  if (actual_edge.valid()) {

   448 	    NodeIt w=G.bNode(actual_edge);

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

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

   451 	      reached.set(w, true);

   452 	      b_node_newly_reached=true;

   453 	    } else {

   454 	      b_node_newly_reached=false;

   455 	    }

   456 	  }

   457 	}

   458       }

   459       return *this;

   460     }

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

   462     operator OutEdgeIt () const { return actual_edge; }

   463     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

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

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

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

   467  };

   469 } // namespace marci

   471 #endif //BFS_ITERATOR_HH

author	alpar
	Mon, 16 Feb 2004 10:57:01 +0000
changeset 74	82d3dbe912d9
parent 58	f71840c04b2a
child 75	87623302a68f
permissions	-rw-r--r--