marci@455: // -*- c++ -*-
marci@543: #ifndef HUGO_BFS_DFS_MISC_H
marci@543: #define HUGO_BFS_DFS_MISC_H
marci@455: 
marci@615: /// \ingroup galgs
marci@615: /// \file
marci@615: /// \brief Miscellaneous algorithms using bfs and dfs.
marci@604: ///
marci@615: /// This file contains several algorithms using bfs and dfs.
marci@604: ///
marci@604: // ///\author Marton Makai
marci@604: 
marci@602: #include <bfs_dfs.h>
marci@455: #include <for_each_macros.h>
marci@455: 
marci@455: namespace hugo {
marci@455: 
marci@615:   /// This function eats a read-write \c BoolMap& bool_map, 
marci@455:   /// which have to work well up 
marci@455:   /// to its \c set and \c operator[]() method. Thus we have to deal 
marci@455:   /// very carefully with an uninitialized \c IterableBoolMap.
marci@615:   /// \ingroup galgs
marci@455:   template<typename Graph, typename BoolMap> 
marci@455:   bool isBipartite(const Graph& g, BoolMap& bool_map) {
marci@455:     typedef typename Graph::template NodeMap<bool> ReachedMap;
marci@455:     ReachedMap reached(g/*, false*/);
marci@455:     BfsIterator<Graph, ReachedMap> bfs(g, reached);
marci@455:     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
marci@455:       if (!reached[n]) {
marci@455: 	bfs.pushAndSetReached(n);
marci@549: 	bool_map.set(n, false);
marci@549: 	while (!bfs.finished()) {
marci@549: 	  if (bfs.isBNodeNewlyReached()) {
marci@549: 	    bool_map.set(bfs.bNode())=!bfs.aNode();
marci@549: 	  } else {
marci@549: 	    if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
marci@549: 	      return false;
marci@455: 	    }
marci@455: 	  }
marci@549: 	  ++bfs;
marci@455: 	}
marci@455:       }
marci@455:     }
marci@549:     
marci@455:     return true;
marci@455:   }
marci@540: 
marci@540:   /// experimental topsort, 
marci@540:   /// I think the final version will work as an iterator
marci@549:   /// if the graph is not a acyclic, the na pre-topological order is obtained 
marci@577:   /// (see Schrijver's book).
marci@577:   /// PredMap have to be a writtable node-map.
marci@577:   /// If the graph is directed and not acyclic, 
marci@577:   /// then going back from the returned node via the pred information, a 
marci@577:   /// cycle is obtained.
marci@615:   /// \ingroup galgs
marci@577:   template<typename Graph, typename PredMap> 
marci@577:   typename Graph::Node 
marci@577:   topSort(const Graph& g, std::list<typename Graph::Node>& l, 
marci@577: 	       PredMap& pred) {
marci@540:     l.clear();
marci@540:     typedef typename Graph::template NodeMap<bool> ReachedMap;
marci@577:     typedef typename Graph::template NodeMap<bool> ExaminedMap;    
marci@540:     ReachedMap reached(g/*, false*/);
marci@577:     ExaminedMap examined(g/*, false*/);
marci@540:     DfsIterator<Graph, ReachedMap> dfs(g, reached);
marci@540:     FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
marci@540:       if (!reached[n]) {
marci@540: 	dfs.pushAndSetReached(n);
marci@577: 	pred.set(n, INVALID);
marci@543: 	while (!dfs.finished()) {
marci@552: 	  ++dfs;
marci@577: 	  if (dfs.isBNodeNewlyReached()) {
marci@577: 	    ///\bug hugo 0.2-ben Edge kell
marci@577: 	    pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
marci@577: 	  } else {
marci@577: 	    ///\bug ugyanaz
marci@577: 	    if (g.valid(typename Graph::OutEdgeIt(dfs)) && 
marci@577: 		!examined[dfs.bNode()]) {
marci@577: 	      ///\bug hugo 0.2-ben Edge kell
marci@577: 	      pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
marci@577: 	      return dfs.aNode();
marci@577: 	    }
marci@577: 	  }
marci@543: 	  if (dfs.isANodeExamined()) {
marci@543: 	    l.push_back(dfs.aNode());
marci@577: 	    examined.set(dfs.aNode(), true);
marci@540: 	  }
marci@540: 	}
marci@540:       }
marci@540:     }
marci@577:     return INVALID;
marci@540:   }
marci@615: 
marci@548: } //namespace hugo
marci@548: 
marci@543: #endif //HUGO_BFS_DFS_MISC_H