source: lemon-0.x/src/work/marci/bfs_dfs_misc.h @ 541:5c5d970ef2f0

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