1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/marci/bfs_dfs_misc.h	Thu May 06 13:46:07 2004 +0000
     1.3 @@ -0,0 +1,60 @@
     1.4 +// -*- c++ -*-
     1.5 +#ifndef HUGO_BIPARTITE_GRAPHS_H
     1.6 +#define HUGO_BIPARTITE_GRAPHS_H
     1.7 +
     1.8 +#include <bfs_iterator.h>
     1.9 +#include <for_each_macros.h>
    1.10 +
    1.11 +namespace hugo {
    1.12 +
    1.13 +  /// This function eat a read-write \c BoolMap& bool_map, 
    1.14 +  /// which have to work well up 
    1.15 +  /// to its \c set and \c operator[]() method. Thus we have to deal 
    1.16 +  /// very carefully with an uninitialized \c IterableBoolMap.
    1.17 +  template<typename Graph, typename BoolMap> 
    1.18 +  bool isBipartite(const Graph& g, BoolMap& bool_map) {
    1.19 +    typedef typename Graph::template NodeMap<bool> ReachedMap;
    1.20 +    ReachedMap reached(g/*, false*/);
    1.21 +    BfsIterator<Graph, ReachedMap> bfs(g, reached);
    1.22 +    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    1.23 +      if (!reached[n]) {
    1.24 +	bfs.pushAndSetReached(n);
    1.25 +	bool_map.set(n, false) {
    1.26 +	  while (!bfs.finished()) {
    1.27 +	    if (bfs.isBNodeNewlyReached()) {
    1.28 +	      bool_map.set(bfs.bNode())=!bfs.aNode();
    1.29 +	    } else {
    1.30 +	      if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
    1.31 +		return false;
    1.32 +	      }
    1.33 +	    }
    1.34 +	    ++bfs;
    1.35 +	  }
    1.36 +	}
    1.37 +      }
    1.38 +    }
    1.39 +    return true;
    1.40 +  }
    1.41 +
    1.42 +  /// experimental topsort, 
    1.43 +  /// I think the final version will work as an iterator
    1.44 +  template<typename Graph> 
    1.45 +  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
    1.46 +    l.clear();
    1.47 +    typedef typename Graph::template NodeMap<bool> ReachedMap;
    1.48 +    ReachedMap reached(g/*, false*/);
    1.49 +    DfsIterator<Graph, ReachedMap> dfs(g, reached);
    1.50 +    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    1.51 +      if (!reached[n]) {
    1.52 +	dfs.pushAndSetReached(n);
    1.53 +	while (!bfs.finished()) {
    1.54 +	  if (bfs.isANodeExamined()) {
    1.55 +	    l.push_back(bfs.aNode());
    1.56 +	  }
    1.57 +	  ++bfs;
    1.58 +	}
    1.59 +      }
    1.60 +    }
    1.61 +  }
    1.62 +}
    1.63 +#endif //HUGO_BIPARTITE_GRAPHS_H

     2.1 --- a/src/work/marci/bipartite_graphs.h	Thu May 06 13:44:48 2004 +0000
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,60 +0,0 @@
     2.4 -// -*- c++ -*-
     2.5 -#ifndef HUGO_BIPARTITE_GRAPHS_H
     2.6 -#define HUGO_BIPARTITE_GRAPHS_H
     2.7 -
     2.8 -#include <bfs_iterator.h>
     2.9 -#include <for_each_macros.h>
    2.10 -
    2.11 -namespace hugo {
    2.12 -
    2.13 -  /// This function eat a read-write \c BoolMap& bool_map, 
    2.14 -  /// which have to work well up 
    2.15 -  /// to its \c set and \c operator[]() method. Thus we have to deal 
    2.16 -  /// very carefully with an uninitialized \c IterableBoolMap.
    2.17 -  template<typename Graph, typename BoolMap> 
    2.18 -  bool isBipartite(const Graph& g, BoolMap& bool_map) {
    2.19 -    typedef typename Graph::template NodeMap<bool> ReachedMap;
    2.20 -    ReachedMap reached(g/*, false*/);
    2.21 -    BfsIterator<Graph, ReachedMap> bfs(g, reached);
    2.22 -    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    2.23 -      if (!reached[n]) {
    2.24 -	bfs.pushAndSetReached(n);
    2.25 -	bool_map.set(n, false) {
    2.26 -	  while (!bfs.finished()) {
    2.27 -	    if (bfs.isBNodeNewlyReached()) {
    2.28 -	      bool_map.set(bfs.bNode())=!bfs.aNode();
    2.29 -	    } else {
    2.30 -	      if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) {
    2.31 -		return false;
    2.32 -	      }
    2.33 -	    }
    2.34 -	    ++bfs;
    2.35 -	  }
    2.36 -	}
    2.37 -      }
    2.38 -    }
    2.39 -    return true;
    2.40 -  }
    2.41 -
    2.42 -  /// experimental topsort, 
    2.43 -  /// I think the final version will work as an iterator
    2.44 -  template<typename Graph> 
    2.45 -  void topSort(Graph& g, std::list<typename Graph::Node>& l) {
    2.46 -    l.clear();
    2.47 -    typedef typename Graph::template NodeMap<bool> ReachedMap;
    2.48 -    ReachedMap reached(g/*, false*/);
    2.49 -    DfsIterator<Graph, ReachedMap> dfs(g, reached);
    2.50 -    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    2.51 -      if (!reached[n]) {
    2.52 -	dfs.pushAndSetReached(n);
    2.53 -	while (!bfs.finished()) {
    2.54 -	  if (bfs.isANodeExamined()) {
    2.55 -	    l.push_back(bfs.aNode());
    2.56 -	  }
    2.57 -	  ++bfs;
    2.58 -	}
    2.59 -      }
    2.60 -    }
    2.61 -  }
    2.62 -}
    2.63 -#endif //HUGO_BIPARTITE_GRAPHS_H