lemon-0.x: src/work/marci/bipartite

     1 // -*- c++ -*-

     2 #ifndef HUGO_BIPARTITE_GRAPHS_H

     3 #define HUGO_BIPARTITE_GRAPHS_H

     5 #include <bfs_iterator.h>

     6 #include <for_each_macros.h>

     8 namespace hugo {

    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

author	athos
	Tue, 04 May 2004 16:52:15 +0000
changeset 530	d9c06ac0b3a3
child 540	405ccc3105e1
permissions	-rw-r--r--