// -*- 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