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