// -*- c++ -*-

#ifndef LEMON_BFS_DFS_MISC_H

#define LEMON_BFS_DFS_MISC_H

/// \ingroup galgs

/// \file

/// \brief Miscellaneous algorithms using bfs and dfs.

///

/// This file contains several algorithms using bfs and dfs.

///

// ///\author Marton Makai

#include <bfs_dfs.h>

#include <for_each_macros.h>

namespace lemon {

  /// This function eats 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.

  /// \ingroup galgs

  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

  /// if the graph is not a acyclic, the na pre-topological order is obtained 

  /// (see Schrijver's book).

  /// PredMap have to be a writtable node-map.

  /// If the graph is directed and not acyclic, 

  /// then going back from the returned node via the pred information, a 

  /// cycle is obtained.

  /// \ingroup galgs

  template<typename Graph, typename PredMap> 

  typename Graph::Node 

  topSort(const Graph& g, std::list<typename Graph::Node>& l, 

	       PredMap& pred) {

    l.clear();

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

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

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

    ExaminedMap examined(g/*, false*/);

    DfsIterator<Graph, ReachedMap> dfs(g, reached);

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

      if (!reached[n]) {

	dfs.pushAndSetReached(n);

	pred.set(n, INVALID);

	while (!dfs.finished()) {

	  ++dfs;

	  if (dfs.isBNodeNewlyReached()) {

	    ///\bug lemon 0.2-ben Edge kell

	    pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));

	  } else {

	    ///\bug ugyanaz

	    if (g.valid(typename Graph::OutEdgeIt(dfs)) && 

		!examined[dfs.bNode()]) {

	      ///\bug lemon 0.2-ben Edge kell

	      pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));

	      return dfs.aNode();

	    }

	  }

	  if (dfs.isANodeExamined()) {

	    l.push_back(dfs.aNode());

	    examined.set(dfs.aNode(), true);

	  }

	}

      }

    }

    return INVALID;

  }

} //namespace lemon

#endif //LEMON_BFS_DFS_MISC_H