is_bipartite

Tests whether an undirected graph is bipartite using a DFS-based coloring approach.

Complexity: O(V + E)
Defined in: <boost/graph/bipartite.hpp>

Example

// Bipartite Check example
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;

int main() {
    // Bipartite graph: {0,2} and {1,3} with edges only between sets
    Graph bipartite_g{4};
    boost::add_edge(0, 1, bipartite_g); boost::add_edge(0, 3, bipartite_g);
    boost::add_edge(2, 1, bipartite_g); boost::add_edge(2, 3, bipartite_g);

    // Non-bipartite graph: triangle
    Graph triangle{3};
    boost::add_edge(0, 1, triangle); boost::add_edge(1, 2, triangle);
    boost::add_edge(0, 2, triangle);

    std::cout << "4-cycle is bipartite: "
              << (boost::is_bipartite(bipartite_g) ? "yes" : "no") << "\n";
    std::cout << "Triangle is bipartite: "
              << (boost::is_bipartite(triangle) ? "yes" : "no") << "\n";
}
4-cycle is bipartite: yes
Triangle is bipartite: no

(1) With partition map and index map

template <typename Graph, typename IndexMap,
          typename PartitionMap>
bool is_bipartite(
    const Graph& graph,
    const IndexMap index_map,
    PartitionMap partition_map);
Direction Parameter Description

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 type VertexIndexMap must 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 PartitionMap type must be a model of Readable Property Map and Writable Property Map. The value type must model ColorValue.

(2) With index map only

template <typename Graph, typename IndexMap>
bool is_bipartite(
    const Graph& graph,
    const IndexMap index_map);
Direction Parameter Description

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 type VertexIndexMap must 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.

(3) Using internal index map

template <typename Graph>
bool is_bipartite(
    const Graph& graph);
Direction Parameter Description

IN

const Graph& graph

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

Description

The is_bipartite() function 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.

Returns

true if the graph is bipartite, false otherwise. When a partition_map is provided (overload (1)), it will additionally contain the two-coloring of the vertices.

Example

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

Edit this Page