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