marci@455: // -*- c++ -*-
marci@455: #ifndef HUGO_BIPARTITE_GRAPHS_H
marci@455: #define HUGO_BIPARTITE_GRAPHS_H
marci@455: 
marci@455: #include <bfs_iterator.h>
marci@455: #include <for_each_macros.h>
marci@455: 
marci@455: namespace hugo {
marci@455: 
marci@455:   /// This function eat a read-write \c BoolMap& bool_map, 
marci@455:   /// which have to work well up 
marci@455:   /// to its \c set and \c operator[]() method. Thus we have to deal 
marci@455:   /// very carefully with an uninitialized \c IterableBoolMap.
marci@455:   template<typename Graph, typename BoolMap> 
marci@455:   bool isBipartite(const Graph& g, BoolMap& bool_map) {
marci@455:     typedef typename Graph::template NodeMap<bool> ReachedMap;
marci@455:     ReachedMap reached(g/*, false*/);
marci@455:     BfsIterator<Graph, ReachedMap> bfs(g, reached);
marci@455:     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
marci@455:       if (!reached[n]) {
marci@455: 	bfs.pushAndSetReached(n);
marci@455: 	bool_map.set(n, false) {
marci@455: 	  while (!bfs.finished()) {
marci@455: 	    if (bfs.isBNodeNewlyReached()) {
marci@455: 	      bool_map.set(bfs.bNode())=!bfs.aNode();
marci@455: 	    } else {
marci@455: 	      if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
marci@455: 		return false;
marci@455: 	      }
marci@455: 	    }
marci@455: 	    ++bfs;
marci@455: 	  }
marci@455: 	}
marci@455:       }
marci@455:     }
marci@455:     return true;
marci@455:   }
marci@455: }
marci@455: #endif //HUGO_BIPARTITE_GRAPHS_H