# HG changeset patch
# User marci
# Date 1083146363 0
# Node ID 14a1d11ddf211541ba02baa782937edbd2014720
# Parent  0cd33e3e60cbf9a005b86da10bc58104d450ebfa
for checking bipartiteness

diff -r 0cd33e3e60cb -r 14a1d11ddf21 src/work/marci/bipartite_graphs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/bipartite_graphs.h	Wed Apr 28 09:59:23 2004 +0000
@@ -0,0 +1,39 @@
+// -*- 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