source: lemon-0.x/src/work/marci/bfs_dfs_misc.h @ 615:b6b31b75b522

// -*- c++ -*-
#ifndef HUGO_BFS_DFS_MISC_H
#define HUGO_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 hugo {

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

#endif //HUGO_BFS_DFS_MISC_H