marci@174: // -*- c++ -*-
marci@174: #ifndef BFS_ITERATOR_H
marci@174: #define BFS_ITERATOR_H
marci@174: 
marci@174: #include <queue>
marci@174: #include <stack>
marci@174: #include <utility>
marci@174: #include <graph_wrapper.h>
marci@174: 
marci@174: namespace hugo {
marci@174: 
marci@174:   template <typename Graph>
marci@174:   struct bfs {
marci@174:     typedef typename Graph::Node Node;
marci@174:     typedef typename Graph::Edge Edge;
marci@174:     typedef typename Graph::NodeIt NodeIt;
marci@174:     typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@174:     Graph& G;
marci@174:     Node s;
marci@174:     typename Graph::NodeMap<bool> reached;
marci@174:     typename Graph::NodeMap<Edge> pred;
marci@174:     typename Graph::NodeMap<int> dist;
marci@174:     std::queue<Node> bfs_queue;
marci@174:     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
marci@174:       bfs_queue.push(s); 
marci@174:       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) 
marci@174: 	reached.set(i, false);
marci@174:       reached.set(s, true);
marci@174:       dist.set(s, 0); 
marci@174:     }
marci@174:     
marci@174:     void run() {
marci@174:       while (!bfs_queue.empty()) {
marci@174: 	Node v=bfs_queue.front();
marci@174: 	OutEdgeIt e=G.template first<OutEdgeIt>(v);
marci@174: 	bfs_queue.pop();
marci@174: 	for( ; e.valid(); ++e) {
marci@174: 	  Node w=G.bNode(e);
marci@174: 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
marci@174: 	  if (!reached.get(w)) {
marci@174: 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@174: 	    bfs_queue.push(w);
marci@174: 	    dist.set(w, dist.get(v)+1);
marci@174: 	    pred.set(w, e);
marci@174: 	    reached.set(w, true);
marci@174: 	  } else {
marci@174: 	    std::cout << G.id(w) << " is already reached" << std::endl;
marci@174: 	  }
marci@174: 	}
marci@174:       }
marci@174:     }
marci@174:   };
marci@174: 
marci@174: //   template <typename Graph> 
marci@174: //   struct bfs_visitor {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     typedef typename Graph::Edge Edge;
marci@174: //     typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@174: //     Graph& G;
marci@174: //     bfs_visitor(Graph& _G) : G(_G) { }
marci@174: //     void at_previously_reached(OutEdgeIt& e) { 
marci@174: //       //Node v=G.aNode(e);
marci@174: //       Node w=G.bNode(e);
marci@174: //       std::cout << G.id(w) << " is already reached" << std::endl;
marci@174: //    }
marci@174: //     void at_newly_reached(OutEdgeIt& e) { 
marci@174: //       //Node v=G.aNode(e);
marci@174: //       Node w=G.bNode(e);
marci@174: //       std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@174: //     }
marci@174: //   };
marci@174: 
marci@174: //   template <typename Graph, typename ReachedMap, typename visitor_type>
marci@174: //   struct bfs_iterator {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     typedef typename Graph::Edge Edge;
marci@174: //     typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@174: //     Graph& G;
marci@174: //     std::queue<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     visitor_type& visitor;
marci@174: //     void process() {
marci@174: //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       if (bfs_queue.empty()) return;
marci@174: //       OutEdgeIt e=bfs_queue.front();
marci@174: //       //Node v=G.aNode(e);
marci@174: //       Node w=G.bNode(e);
marci@174: //       if (!reached.get(w)) {
marci@174: // 	visitor.at_newly_reached(e);
marci@174: // 	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	reached.set(w, true);
marci@174: //       } else {
marci@174: // 	visitor.at_previously_reached(e);
marci@174: //       }
marci@174: //     }
marci@174: //     bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
marci@174: //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       valid();
marci@174: //     }
marci@174: //     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { 
marci@174: //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       //if (bfs_queue.empty()) return *this;
marci@174: //       if (!valid()) return *this;
marci@174: //       ++(bfs_queue.front());
marci@174: //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       valid();
marci@174: //       return *this;
marci@174: //     }
marci@174: //     //void next() { 
marci@174: //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //     //  if (bfs_queue.empty()) return;
marci@174: //     //  ++(bfs_queue.front());
marci@174: //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //     //}
marci@174: //     bool valid() { 
marci@174: //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       if (bfs_queue.empty()) return false; else return true;
marci@174: //     }
marci@174: //     //bool finished() { 
marci@174: //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //     //  if (bfs_queue.empty()) return true; else return false;
marci@174: //     //}
marci@174: //     operator Edge () { return bfs_queue.front(); }
marci@174: 
marci@174: //   };
marci@174: 
marci@174: //   template <typename Graph, typename ReachedMap>
marci@174: //   struct bfs_iterator1 {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     typedef typename Graph::Edge Edge;
marci@174: //     typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@174: //     Graph& G;
marci@174: //     std::queue<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     bool _newly_reached;
marci@174: //     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@174: //       valid();
marci@174: //       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@174: // 	OutEdgeIt e=bfs_queue.front();
marci@174: // 	Node w=G.bNode(e);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  _newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  _newly_reached=false;
marci@174: // 	}
marci@174: //       }
marci@174: //     }
marci@174: //     bfs_iterator1<Graph, ReachedMap>& operator++() { 
marci@174: //       if (!valid()) return *this;
marci@174: //       ++(bfs_queue.front());
marci@174: //       valid();
marci@174: //       if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@174: // 	OutEdgeIt e=bfs_queue.front();
marci@174: // 	Node w=G.bNode(e);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  _newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  _newly_reached=false;
marci@174: // 	}
marci@174: //       }
marci@174: //       return *this;
marci@174: //     }
marci@174: //     bool valid() { 
marci@174: //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@174: //       if (bfs_queue.empty()) return false; else return true;
marci@174: //     }
marci@174: //     operator OutEdgeIt() { return bfs_queue.front(); }
marci@174: //     //ize
marci@174: //     bool newly_reached() { return _newly_reached; }
marci@174: 
marci@174: //   };
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   struct BfsIterator {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     Graph& G;
marci@174: //     std::queue<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //     BfsIterator(Graph& _G, 
marci@174: // 		std::queue<OutEdgeIt>& _bfs_queue, 
marci@174: // 		ReachedMap& _reached) : 
marci@174: //       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@174: //       actual_edge=bfs_queue.front();
marci@174: //       if (actual_edge.valid()) { 
marci@174: // 	Node w=G.bNode(actual_edge);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(G.firstOutEdge(w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  b_node_newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  b_node_newly_reached=false;
marci@174: // 	}
marci@174: //       }
marci@174: //     }
marci@174: //     BfsIterator<Graph, OutEdgeIt, ReachedMap>& 
marci@174: //     operator++() { 
marci@174: //       if (bfs_queue.front().valid()) { 
marci@174: // 	++(bfs_queue.front());
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(G.firstOutEdge(w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop(); 
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(G.firstOutEdge(w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       }
marci@174: //       return *this;
marci@174: //     }
marci@174: //     bool finished() { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () { return actual_edge; }
marci@174: //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@174: //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@174: //   };
marci@174: 
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   struct DfsIterator {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     Graph& G;
marci@174: //     std::stack<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //     DfsIterator(Graph& _G, 
marci@174: // 		std::stack<OutEdgeIt>& _bfs_queue, 
marci@174: // 		ReachedMap& _reached) : 
marci@174: //       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@174: //       actual_edge=bfs_queue.top();
marci@174: //       if (actual_edge.valid()) { 
marci@174: // 	Node w=G.bNode(actual_edge);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(G.firstOutEdge(w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  b_node_newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  ++(bfs_queue.top());
marci@174: // 	  b_node_newly_reached=false;
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop();
marci@174: //       }
marci@174: //     }
marci@174: //     DfsIterator<Graph, OutEdgeIt, ReachedMap>& 
marci@174: //     operator++() { 
marci@174: //       actual_edge=bfs_queue.top();
marci@174: //       if (actual_edge.valid()) { 
marci@174: // 	Node w=G.bNode(actual_edge);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(G.firstOutEdge(w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  b_node_newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  ++(bfs_queue.top());
marci@174: // 	  b_node_newly_reached=false;
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop();
marci@174: //       }
marci@174: //       return *this;
marci@174: //     }
marci@174: //     bool finished() { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () { return actual_edge; }
marci@174: //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@174: //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@174: //   };
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   struct BfsIterator1 {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     Graph& G;
marci@174: //     std::queue<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //     BfsIterator1(Graph& _G, 
marci@174: // 		std::queue<OutEdgeIt>& _bfs_queue, 
marci@174: // 		ReachedMap& _reached) : 
marci@174: //       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@174: //       actual_edge=bfs_queue.front();
marci@174: //       if (actual_edge.valid()) { 
marci@174: //       	Node w=G.bNode(actual_edge);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(OutEdgeIt(G, w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  b_node_newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  b_node_newly_reached=false;
marci@174: // 	}
marci@174: //       }
marci@174: //     }
marci@174: //     void next() { 
marci@174: //       if (bfs_queue.front().valid()) { 
marci@174: // 	++(bfs_queue.front());
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(OutEdgeIt(G, w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop(); 
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(OutEdgeIt(G, w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       }
marci@174: //       //return *this;
marci@174: //     }
marci@174: //     bool finished() { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () { return actual_edge; }
marci@174: //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@174: //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@174: //   };
marci@174: 
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   struct DfsIterator1 {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     Graph& G;
marci@174: //     std::stack<OutEdgeIt>& bfs_queue;
marci@174: //     ReachedMap& reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //     DfsIterator1(Graph& _G, 
marci@174: // 		std::stack<OutEdgeIt>& _bfs_queue, 
marci@174: // 		ReachedMap& _reached) : 
marci@174: //       G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@174: //       //actual_edge=bfs_queue.top();
marci@174: //       //if (actual_edge.valid()) { 
marci@174: //       //	Node w=G.bNode(actual_edge);
marci@174: //       //if (!reached.get(w)) {
marci@174: //       //  bfs_queue.push(OutEdgeIt(G, w));
marci@174: //       //  reached.set(w, true);
marci@174: //       //  b_node_newly_reached=true;
marci@174: //       //} else {
marci@174: //       //  ++(bfs_queue.top());
marci@174: //       //  b_node_newly_reached=false;
marci@174: //       //}
marci@174: //       //} else {
marci@174: //       //	bfs_queue.pop();
marci@174: //       //}
marci@174: //     }
marci@174: //     void next() { 
marci@174: //       actual_edge=bfs_queue.top();
marci@174: //       if (actual_edge.valid()) { 
marci@174: // 	Node w=G.bNode(actual_edge);
marci@174: // 	if (!reached.get(w)) {
marci@174: // 	  bfs_queue.push(OutEdgeIt(G, w));
marci@174: // 	  reached.set(w, true);
marci@174: // 	  b_node_newly_reached=true;
marci@174: // 	} else {
marci@174: // 	  ++(bfs_queue.top());
marci@174: // 	  b_node_newly_reached=false;
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop();
marci@174: //       }
marci@174: //       //return *this;
marci@174: //     }
marci@174: //     bool finished() { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () { return actual_edge; }
marci@174: //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@174: //     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
marci@174: //   };
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   class BfsIterator2 {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     const Graph& G;
marci@174: //     std::queue<OutEdgeIt> bfs_queue;
marci@174: //     ReachedMap reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //   public:
marci@174: //     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
marci@174: //     void pushAndSetReached(Node s) { 
marci@174: //       reached.set(s, true);
marci@174: //       if (bfs_queue.empty()) {
marci@174: // 	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) { 
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	} //else {
marci@174: // 	//}
marci@174: //       } else {
marci@174: // 	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@174: //       }
marci@174: //     }
marci@174: //     BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
marci@174: //     operator++() { 
marci@174: //       if (bfs_queue.front().valid()) { 
marci@174: // 	++(bfs_queue.front());
marci@174: // 	actual_edge=bfs_queue.front();
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop(); 
marci@174: // 	if (!bfs_queue.empty()) {
marci@174: // 	  actual_edge=bfs_queue.front();
marci@174: // 	  if (actual_edge.valid()) {
marci@174: // 	    Node w=G.bNode(actual_edge);
marci@174: // 	    if (!reached.get(w)) {
marci@174: // 	      bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@174: // 	      reached.set(w, true);
marci@174: // 	      b_node_newly_reached=true;
marci@174: // 	    } else {
marci@174: // 	      b_node_newly_reached=false;
marci@174: // 	    }
marci@174: // 	  }
marci@174: // 	}
marci@174: //       }
marci@174: //       return *this;
marci@174: //     }
marci@174: //     bool finished() const { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () const { return actual_edge; }
marci@174: //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174: //     bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@174: //     const ReachedMap& getReachedMap() const { return reached; }
marci@174: //     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
marci@174: //  };
marci@174: 
marci@174: 
marci@174: //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@174: //   class BfsIterator3 {
marci@174: //     typedef typename Graph::Node Node;
marci@174: //     const Graph& G;
marci@174: //     std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
marci@174: //     ReachedMap reached;
marci@174: //     bool b_node_newly_reached;
marci@174: //     OutEdgeIt actual_edge;
marci@174: //   public:
marci@174: //     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
marci@174: //     void pushAndSetReached(Node s) { 
marci@174: //       reached.set(s, true);
marci@174: //       if (bfs_queue.empty()) {
marci@174: // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@174: // 	actual_edge=bfs_queue.front().second;
marci@174: // 	if (actual_edge.valid()) { 
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	} //else {
marci@174: // 	//}
marci@174: //       } else {
marci@174: // 	bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@174: //       }
marci@174: //     }
marci@174: //     BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
marci@174: //     operator++() { 
marci@174: //       if (bfs_queue.front().second.valid()) { 
marci@174: // 	++(bfs_queue.front().second);
marci@174: // 	actual_edge=bfs_queue.front().second;
marci@174: // 	if (actual_edge.valid()) {
marci@174: // 	  Node w=G.bNode(actual_edge);
marci@174: // 	  if (!reached.get(w)) {
marci@174: // 	    bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@174: // 	    reached.set(w, true);
marci@174: // 	    b_node_newly_reached=true;
marci@174: // 	  } else {
marci@174: // 	    b_node_newly_reached=false;
marci@174: // 	  }
marci@174: // 	}
marci@174: //       } else {
marci@174: // 	bfs_queue.pop(); 
marci@174: // 	if (!bfs_queue.empty()) {
marci@174: // 	  actual_edge=bfs_queue.front().second;
marci@174: // 	  if (actual_edge.valid()) {
marci@174: // 	    Node w=G.bNode(actual_edge);
marci@174: // 	    if (!reached.get(w)) {
marci@174: // 	      bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@174: // 	      reached.set(w, true);
marci@174: // 	      b_node_newly_reached=true;
marci@174: // 	    } else {
marci@174: // 	      b_node_newly_reached=false;
marci@174: // 	    }
marci@174: // 	  }
marci@174: // 	}
marci@174: //       }
marci@174: //       return *this;
marci@174: //     }
marci@174: //     bool finished() const { return bfs_queue.empty(); }
marci@174: //     operator OutEdgeIt () const { return actual_edge; }
marci@174: //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174: //     bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@174: //     Node aNode() const { return bfs_queue.front().first; }
marci@174: //     Node bNode() const { return G.bNode(actual_edge); }
marci@174: //     const ReachedMap& getReachedMap() const { return reached; }
marci@174: //     //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
marci@174: //  };
marci@174: 
marci@174: 
marci@174:   template <typename Graph, typename OutEdgeIt, 
marci@174: 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
marci@174:   class BfsIterator4 {
marci@174:     typedef typename Graph::Node Node;
marci@174:     const Graph& G;
marci@174:     std::queue<Node> bfs_queue;
marci@174:     ReachedMap& reached;
marci@174:     bool b_node_newly_reached;
marci@174:     OutEdgeIt actual_edge;
marci@174:     bool own_reached_map;
marci@174:   public:
marci@174:     BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
marci@174:       G(_G), reached(_reached), 
marci@174:       own_reached_map(false) { }
marci@174:     BfsIterator4(const Graph& _G) : 
marci@174:       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
marci@174:       own_reached_map(true) { }
marci@174:     ~BfsIterator4() { if (own_reached_map) delete &reached; }
marci@174:     void pushAndSetReached(Node s) { 
marci@174:       //std::cout << "mimi" << &reached << std::endl;
marci@174:       reached.set(s, true);
marci@174:       //std::cout << "mumus" << std::endl;
marci@174:       if (bfs_queue.empty()) {
marci@174: 	//std::cout << "bibi1" << std::endl;
marci@174: 	bfs_queue.push(s);
marci@174: 	//std::cout << "zizi" << std::endl;
marci@174: 	G./*getF*/first(actual_edge, s);
marci@174: 	//std::cout << "kiki" << std::endl;
marci@174: 	if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	  Node w=G.bNode(actual_edge);
marci@174: 	  if (!reached.get(w)) {
marci@174: 	    bfs_queue.push(w);
marci@174: 	    reached.set(w, true);
marci@174: 	    b_node_newly_reached=true;
marci@174: 	  } else {
marci@174: 	    b_node_newly_reached=false;
marci@174: 	  }
marci@174: 	} 
marci@174:       } else {
marci@174: 	//std::cout << "bibi2" << std::endl;
marci@174: 	bfs_queue.push(s);
marci@174:       }
marci@174:     }
marci@174:     BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
marci@174:     operator++() { 
marci@174:       if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	/*++*/G.next(actual_edge);
marci@174: 	if (G.valid(actual_edge)/*.valid()*/) {
marci@174: 	  Node w=G.bNode(actual_edge);
marci@174: 	  if (!reached.get(w)) {
marci@174: 	    bfs_queue.push(w);
marci@174: 	    reached.set(w, true);
marci@174: 	    b_node_newly_reached=true;
marci@174: 	  } else {
marci@174: 	    b_node_newly_reached=false;
marci@174: 	  }
marci@174: 	}
marci@174:       } else {
marci@174: 	bfs_queue.pop(); 
marci@174: 	if (!bfs_queue.empty()) {
marci@174: 	  G./*getF*/first(actual_edge, bfs_queue.front());
marci@174: 	  if (G.valid(actual_edge)/*.valid()*/) {
marci@174: 	    Node w=G.bNode(actual_edge);
marci@174: 	    if (!reached.get(w)) {
marci@174: 	      bfs_queue.push(w);
marci@174: 	      reached.set(w, true);
marci@174: 	      b_node_newly_reached=true;
marci@174: 	    } else {
marci@174: 	      b_node_newly_reached=false;
marci@174: 	    }
marci@174: 	  }
marci@174: 	}
marci@174:       }
marci@174:       return *this;
marci@174:     }
marci@174:     bool finished() const { return bfs_queue.empty(); }
marci@174:     operator OutEdgeIt () const { return actual_edge; }
marci@174:     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174:     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
marci@174:     Node aNode() const { return bfs_queue.front(); }
marci@174:     Node bNode() const { return G.bNode(actual_edge); }
marci@174:     const ReachedMap& getReachedMap() const { return reached; }
marci@174:     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
marci@174:  };  
marci@174: 
marci@174: 
marci@174:   template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
marci@174: 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
marci@174:   class BfsIterator5 {
marci@174:     typedef typename GraphWrapper::Node Node;
marci@174:     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@174:     GraphWrapper G;
marci@174:     std::queue<Node> bfs_queue;
marci@174:     ReachedMap& reached;
marci@174:     bool b_node_newly_reached;
marci@174:     OutEdgeIt actual_edge;
marci@174:     bool own_reached_map;
marci@174:   public:
marci@174:     BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
marci@174:       G(_G), reached(_reached), 
marci@174:       own_reached_map(false) { }
marci@174:     BfsIterator5(const GraphWrapper& _G) : 
marci@174:       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
marci@174:       own_reached_map(true) { }
marci@174: //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G, 
marci@174: // 		 ReachedMap& _reached) : 
marci@174: //       G(_G), reached(_reached), 
marci@174: //       own_reached_map(false) { }
marci@174: //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : 
marci@174: //       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
marci@174: //       own_reached_map(true) { }
marci@174:     ~BfsIterator5() { if (own_reached_map) delete &reached; }
marci@174:     void pushAndSetReached(Node s) { 
marci@174:       reached.set(s, true);
marci@174:       if (bfs_queue.empty()) {
marci@174: 	bfs_queue.push(s);
marci@174: 	G./*getF*/first(actual_edge, s);
marci@174: 	if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	  Node w=G.bNode(actual_edge);
marci@174: 	  if (!reached.get(w)) {
marci@174: 	    bfs_queue.push(w);
marci@174: 	    reached.set(w, true);
marci@174: 	    b_node_newly_reached=true;
marci@174: 	  } else {
marci@174: 	    b_node_newly_reached=false;
marci@174: 	  }
marci@174: 	} 
marci@174:       } else {
marci@174: 	bfs_queue.push(s);
marci@174:       }
marci@174:     }
marci@174:     BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
marci@174:     operator++() { 
marci@174:       if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	/*++*/G.next(actual_edge);
marci@174: 	if (G.valid(actual_edge)/*.valid()*/) {
marci@174: 	  Node w=G.bNode(actual_edge);
marci@174: 	  if (!reached.get(w)) {
marci@174: 	    bfs_queue.push(w);
marci@174: 	    reached.set(w, true);
marci@174: 	    b_node_newly_reached=true;
marci@174: 	  } else {
marci@174: 	    b_node_newly_reached=false;
marci@174: 	  }
marci@174: 	}
marci@174:       } else {
marci@174: 	bfs_queue.pop(); 
marci@174: 	if (!bfs_queue.empty()) {
marci@174: 	  G./*getF*/first(actual_edge, bfs_queue.front());
marci@174: 	  if (G.valid(actual_edge)/*.valid()*/) {
marci@174: 	    Node w=G.bNode(actual_edge);
marci@174: 	    if (!reached.get(w)) {
marci@174: 	      bfs_queue.push(w);
marci@174: 	      reached.set(w, true);
marci@174: 	      b_node_newly_reached=true;
marci@174: 	    } else {
marci@174: 	      b_node_newly_reached=false;
marci@174: 	    }
marci@174: 	  }
marci@174: 	}
marci@174:       }
marci@174:       return *this;
marci@174:     }
marci@174:     bool finished() const { return bfs_queue.empty(); }
marci@174:     operator OutEdgeIt () const { return actual_edge; }
marci@174:     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174:     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
marci@174:     Node aNode() const { return bfs_queue.front(); }
marci@174:     Node bNode() const { return G.bNode(actual_edge); }
marci@174:     const ReachedMap& getReachedMap() const { return reached; }
marci@174:     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
marci@174:   };  
marci@174: 
marci@174:   template <typename Graph, typename OutEdgeIt, 
marci@174: 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
marci@174:   class DfsIterator4 {
marci@174:     typedef typename Graph::Node Node;
marci@174:     const Graph& G;
marci@174:     std::stack<OutEdgeIt> dfs_stack;
marci@174:     bool b_node_newly_reached;
marci@174:     OutEdgeIt actual_edge;
marci@174:     Node actual_node;
marci@174:     ReachedMap& reached;
marci@174:     bool own_reached_map;
marci@174:   public:
marci@174:     DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
marci@174:       G(_G), reached(_reached), 
marci@174:       own_reached_map(false) { }
marci@174:     DfsIterator4(const Graph& _G) : 
marci@174:       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
marci@174:       own_reached_map(true) { }
marci@174:     ~DfsIterator4() { if (own_reached_map) delete &reached; }
marci@174:     void pushAndSetReached(Node s) { 
marci@174:       actual_node=s;
marci@174:       reached.set(s, true);
marci@174:       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
marci@174:     }
marci@174:     DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
marci@174:     operator++() { 
marci@174:       actual_edge=dfs_stack.top();
marci@174:       //actual_node=G.aNode(actual_edge);
marci@174:       if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	Node w=G.bNode(actual_edge);
marci@174: 	actual_node=w;
marci@174: 	if (!reached.get(w)) {
marci@174: 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
marci@174: 	  reached.set(w, true);
marci@174: 	  b_node_newly_reached=true;
marci@174: 	} else {
marci@174: 	  actual_node=G.aNode(actual_edge);
marci@174: 	  /*++*/G.next(dfs_stack.top());
marci@174: 	  b_node_newly_reached=false;
marci@174: 	}
marci@174:       } else {
marci@174: 	//actual_node=G.aNode(dfs_stack.top());
marci@174: 	dfs_stack.pop();
marci@174:       }
marci@174:       return *this;
marci@174:     }
marci@174:     bool finished() const { return dfs_stack.empty(); }
marci@174:     operator OutEdgeIt () const { return actual_edge; }
marci@174:     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174:     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
marci@174:     Node aNode() const { return actual_node; /*FIXME*/}
marci@174:     Node bNode() const { return G.bNode(actual_edge); }
marci@174:     const ReachedMap& getReachedMap() const { return reached; }
marci@174:     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@174:   };
marci@174: 
marci@174:   template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
marci@174: 	    typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
marci@174:   class DfsIterator5 {
marci@174:     typedef typename GraphWrapper::Node Node;
marci@174:     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@174:     GraphWrapper G;
marci@174:     std::stack<OutEdgeIt> dfs_stack;
marci@174:     bool b_node_newly_reached;
marci@174:     OutEdgeIt actual_edge;
marci@174:     Node actual_node;
marci@174:     ReachedMap& reached;
marci@174:     bool own_reached_map;
marci@174:   public:
marci@174:     DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
marci@174:       G(_G), reached(_reached), 
marci@174:       own_reached_map(false) { }
marci@174:     DfsIterator5(const GraphWrapper& _G) : 
marci@174:       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
marci@174:       own_reached_map(true) { }
marci@174:     ~DfsIterator5() { if (own_reached_map) delete &reached; }
marci@174:     void pushAndSetReached(Node s) { 
marci@174:       actual_node=s;
marci@174:       reached.set(s, true);
marci@174:       dfs_stack.push(G.template first<OutEdgeIt>(s)); 
marci@174:     }
marci@174:     DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
marci@174:     operator++() { 
marci@174:       actual_edge=dfs_stack.top();
marci@174:       //actual_node=G.aNode(actual_edge);
marci@174:       if (G.valid(actual_edge)/*.valid()*/) { 
marci@174: 	Node w=G.bNode(actual_edge);
marci@174: 	actual_node=w;
marci@174: 	if (!reached.get(w)) {
marci@174: 	  dfs_stack.push(G.template first<OutEdgeIt>(w));
marci@174: 	  reached.set(w, true);
marci@174: 	  b_node_newly_reached=true;
marci@174: 	} else {
marci@174: 	  actual_node=G.aNode(actual_edge);
marci@174: 	  /*++*/G.next(dfs_stack.top());
marci@174: 	  b_node_newly_reached=false;
marci@174: 	}
marci@174:       } else {
marci@174: 	//actual_node=G.aNode(dfs_stack.top());
marci@174: 	dfs_stack.pop();
marci@174:       }
marci@174:       return *this;
marci@174:     }
marci@174:     bool finished() const { return dfs_stack.empty(); }
marci@174:     operator OutEdgeIt () const { return actual_edge; }
marci@174:     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@174:     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
marci@174:     Node aNode() const { return actual_node; /*FIXME*/}
marci@174:     Node bNode() const { return G.bNode(actual_edge); }
marci@174:     const ReachedMap& getReachedMap() const { return reached; }
marci@174:     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@174:   };
marci@174: 
marci@174: 
marci@174: 
marci@174: } // namespace hugo
marci@174: 
marci@174: #endif //BFS_ITERATOR_H