1.1 --- a/src/work/marci/bfs_dfs_misc.h	Sun Apr 17 18:57:22 2005 +0000
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,97 +0,0 @@
     1.4 -// -*- c++ -*-
     1.5 -#ifndef LEMON_BFS_DFS_MISC_H
     1.6 -#define LEMON_BFS_DFS_MISC_H
     1.7 -
     1.8 -/// \ingroup galgs
     1.9 -/// \file
    1.10 -/// \brief Miscellaneous algorithms using bfs and dfs.
    1.11 -///
    1.12 -/// This file contains several algorithms using bfs and dfs.
    1.13 -///
    1.14 -// ///\author Marton Makai
    1.15 -
    1.16 -#include <bfs_dfs.h>
    1.17 -#include <for_each_macros.h>
    1.18 -
    1.19 -namespace lemon {
    1.20 -
    1.21 -  /// This function eats a read-write \c BoolMap& bool_map, 
    1.22 -  /// which have to work well up 
    1.23 -  /// to its \c set and \c operator[]() method. Thus we have to deal 
    1.24 -  /// very carefully with an uninitialized \c IterableBoolMap.
    1.25 -  /// \ingroup galgs
    1.26 -  template<typename Graph, typename BoolMap> 
    1.27 -  bool isBipartite(const Graph& g, BoolMap& bool_map) {
    1.28 -    typedef typename Graph::template NodeMap<bool> ReachedMap;
    1.29 -    ReachedMap reached(g/*, false*/);
    1.30 -    BfsIterator<Graph, ReachedMap> bfs(g, reached);
    1.31 -    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    1.32 -      if (!reached[n]) {
    1.33 -	bfs.pushAndSetReached(n);
    1.34 -	bool_map.set(n, false);
    1.35 -	while (!bfs.finished()) {
    1.36 -	  if (bfs.isBNodeNewlyReached()) {
    1.37 -	    bool_map.set(bfs.bNode())=!bfs.aNode();
    1.38 -	  } else {
    1.39 -	    if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
    1.40 -	      return false;
    1.41 -	    }
    1.42 -	  }
    1.43 -	  ++bfs;
    1.44 -	}
    1.45 -      }
    1.46 -    }
    1.47 -    
    1.48 -    return true;
    1.49 -  }
    1.50 -
    1.51 -  /// experimental topsort, 
    1.52 -  /// I think the final version will work as an iterator
    1.53 -  /// if the graph is not a acyclic, the na pre-topological order is obtained 
    1.54 -  /// (see Schrijver's book).
    1.55 -  /// PredMap have to be a writtable node-map.
    1.56 -  /// If the graph is directed and not acyclic, 
    1.57 -  /// then going back from the returned node via the pred information, a 
    1.58 -  /// cycle is obtained.
    1.59 -  /// \ingroup galgs
    1.60 -  template<typename Graph, typename PredMap> 
    1.61 -  typename Graph::Node 
    1.62 -  topSort(const Graph& g, std::list<typename Graph::Node>& l, 
    1.63 -	       PredMap& pred) {
    1.64 -    l.clear();
    1.65 -    typedef typename Graph::template NodeMap<bool> ReachedMap;
    1.66 -    typedef typename Graph::template NodeMap<bool> ExaminedMap;    
    1.67 -    ReachedMap reached(g/*, false*/);
    1.68 -    ExaminedMap examined(g/*, false*/);
    1.69 -    DfsIterator<Graph, ReachedMap> dfs(g, reached);
    1.70 -    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    1.71 -      if (!reached[n]) {
    1.72 -	dfs.pushAndSetReached(n);
    1.73 -	pred.set(n, INVALID);
    1.74 -	while (!dfs.finished()) {
    1.75 -	  ++dfs;
    1.76 -	  if (dfs.isBNodeNewlyReached()) {
    1.77 -	    ///\bug lemon 0.2-ben Edge kell
    1.78 -	    pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
    1.79 -	  } else {
    1.80 -	    ///\bug ugyanaz
    1.81 -	    if (g.valid(typename Graph::OutEdgeIt(dfs)) && 
    1.82 -		!examined[dfs.bNode()]) {
    1.83 -	      ///\bug lemon 0.2-ben Edge kell
    1.84 -	      pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
    1.85 -	      return dfs.aNode();
    1.86 -	    }
    1.87 -	  }
    1.88 -	  if (dfs.isANodeExamined()) {
    1.89 -	    l.push_back(dfs.aNode());
    1.90 -	    examined.set(dfs.aNode(), true);
    1.91 -	  }
    1.92 -	}
    1.93 -      }
    1.94 -    }
    1.95 -    return INVALID;
    1.96 -  }
    1.97 -
    1.98 -} //namespace lemon
    1.99 -
   1.100 -#endif //LEMON_BFS_DFS_MISC_H