equal
deleted
inserted
replaced
|
1 // -*- c++ -*- |
|
2 #ifndef HUGO_BIPARTITE_GRAPHS_H |
|
3 #define HUGO_BIPARTITE_GRAPHS_H |
|
4 |
|
5 #include <bfs_iterator.h> |
|
6 #include <for_each_macros.h> |
|
7 |
|
8 namespace hugo { |
|
9 |
|
10 /// This function eat a read-write \c BoolMap& bool_map, |
|
11 /// which have to work well up |
|
12 /// to its \c set and \c operator[]() method. Thus we have to deal |
|
13 /// very carefully with an uninitialized \c IterableBoolMap. |
|
14 template<typename Graph, typename BoolMap> |
|
15 bool isBipartite(const Graph& g, BoolMap& bool_map) { |
|
16 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
17 ReachedMap reached(g/*, false*/); |
|
18 BfsIterator<Graph, ReachedMap> bfs(g, reached); |
|
19 FOR_EACH_LOC(typename Graph::NodeIt, n, g) { |
|
20 if (!reached[n]) { |
|
21 bfs.pushAndSetReached(n); |
|
22 bool_map.set(n, false) { |
|
23 while (!bfs.finished()) { |
|
24 if (bfs.isBNodeNewlyReached()) { |
|
25 bool_map.set(bfs.bNode())=!bfs.aNode(); |
|
26 } else { |
|
27 if (bool_map[bfs.bNode()]==bool_map[bfs.aNode()]) { |
|
28 return false; |
|
29 } |
|
30 } |
|
31 ++bfs; |
|
32 } |
|
33 } |
|
34 } |
|
35 } |
|
36 return true; |
|
37 } |
|
38 } |
|
39 #endif //HUGO_BIPARTITE_GRAPHS_H |