...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// Version with a colormap to retrieve the bipartitiontemplate <typename Graph, typename IndexMap, typename PartitionMap> bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map) template <typename Graph, typename IndexMap> bool is_bipartite (const Graph& graph, const IndexMap index_map)// Version which uses the internal index maptemplate <typename Graph> bool is_bipartite (const Graph& graph);

The `is_bipartite()` functions tests a given graph for
bipartiteness using a DFS-based coloring approach.

An undirected graph is bipartite if one can partition its set of vertices
into two sets "left" and "right", such that each edge goes from either side
to the other. Obviously, a two-coloring of the graph is exactly the same as
a two-partition. `is_bipartite()` tests whether such a two-coloring
is possible and can return it in a given property map.

The bipartition is recorded in the color map `partition_map`,
which will contain a two-coloring of the graph, i.e. an assignment of
*black* and *white* to the vertices such that no edge is monochromatic.
The predicate whether the graph is bipartite is the return value of the function.

IN: `const Graph& graph`

An undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

IN: `const IndexMap index_map`

This maps each vertex to an integer in the range

[0, num_vertices(graph)). The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

OUT: `PartitionMap partition_map`

The algorithm tests whether the graph is bipartite and assigns each vertex either a white or a black color, according to the partition. The

PartitionMaptype must be a model of Readable Property Map and Writable Property Map The value type must model ColorValue.

The time complexity for the algorithm is *O(V + E)*.

The file `examples/bipartite.cpp`
contains an example of testing an undirected graph for bipartiteness.

Copyright © 2010 Matthias Walter (xammy@xammy.homelinux.net)