COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graphs.h @ 503:769f31e9f7b0

Last change on this file since 503:769f31e9f7b0 was 455:14a1d11ddf21, checked in by marci, 17 years ago

for checking bipartiteness

File size: 1.0 KB
Line 
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
8namespace 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
Note: See TracBrowser for help on using the repository browser.