// -*- c++ -*-

 #ifndef HUGO_BIPARTITE_GRAPHS_H

 #define HUGO_BIPARTITE_GRAPHS_H

 #include <bfs_iterator.h>

 #include <for_each_macros.h>

 namespace hugo {

   /// This function eat a read-write \c BoolMap& bool_map, 

   /// which have to work well up 

   /// to its \c set and \c operator[]() method. Thus we have to deal 

   /// very carefully with an uninitialized \c IterableBoolMap.

   template<typename Graph, typename BoolMap> 

   bool isBipartite(const Graph& g, BoolMap& bool_map) {

     typedef typename Graph::template NodeMap<bool> ReachedMap;

     ReachedMap reached(g/*, false*/);

     BfsIterator<Graph, ReachedMap> bfs(g, reached);

     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {

       if (!reached[n]) {

 	bfs.pushAndSetReached(n);

 	bool_map.set(n, false) {

 	  while (!bfs.finished()) {

 	    if (bfs.isBNodeNewlyReached()) {

 	      bool_map.set(bfs.bNode())=!bfs.aNode();

 	    } else {

 	      if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {

 		return false;

 	      }

 	    }

 	    ++bfs;

 	  }

 	}

       }

     }

     return true;

   }

 }

 #endif //HUGO_BIPARTITE_GRAPHS_H