diff -r 405ccc3105e1 -r 5c5d970ef2f0 src/work/marci/bfs_dfs_misc.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/bfs_dfs_misc.h	Thu May 06 13:46:07 2004 +0000
@@ -0,0 +1,60 @@
+// -*- 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;
+  }
+
+  /// experimental topsort, 
+  /// I think the final version will work as an iterator
+  template<typename Graph> 
+  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
+    l.clear();
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+    ReachedMap reached(g/*, false*/);
+    DfsIterator<Graph, ReachedMap> dfs(g, reached);
+    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
+      if (!reached[n]) {
+	dfs.pushAndSetReached(n);
+	while (!bfs.finished()) {
+	  if (bfs.isANodeExamined()) {
+	    l.push_back(bfs.aNode());
+	  }
+	  ++bfs;
+	}
+      }
+    }
+  }
+}
+#endif //HUGO_BIPARTITE_GRAPHS_H