find_odd_cycle

Tests a graph for bipartiteness and, if not bipartite, finds an odd-length cycle.

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

Example

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    Graph g(5);
    // Triangle 0-1-2 makes this non-bipartite
    boost::add_edge(0, 1, g); boost::add_edge(1, 2, g);
    boost::add_edge(2, 0, g); boost::add_edge(2, 3, g);
    boost::add_edge(3, 4, g);

    using Partition = boost::one_bit_color_map<
        boost::property_map<Graph, boost::vertex_index_t>::type>;
    Partition partition(num_vertices(g), get(boost::vertex_index, g));

    std::vector<int> cycle;
    boost::find_odd_cycle(g, get(boost::vertex_index, g), partition,
        std::back_inserter(cycle));

    if (cycle.empty()) {
        std::cout << "Graph is bipartite\n";
    } else {
        std::cout << "Odd cycle found:";
        for (auto v : cycle) std::cout << " " << v;
        std::cout << "\n";
    }
}
Odd cycle found: 2 1 0

(1) With partition map and index map

template <typename Graph, typename IndexMap,
          typename PartitionMap, typename OutputIterator>
OutputIterator find_odd_cycle(
    const Graph& graph,
    const IndexMap index_map,
    PartitionMap partition_map,
    OutputIterator result);
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.

OUT

OutputIterator result

The find_odd_cycle function finds an odd-length cycle if the graph is not bipartite. The sequence of vertices producing such a cycle is written into this iterator. The OutputIterator type must be a model of OutputIterator. The graph’s vertex descriptor type must be in the set of value types of the iterator. The final value is returned by the function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing is written, thus the given iterator matches the return value.

(2) With index map (no partition map)

template <typename Graph, typename IndexMap,
          typename OutputIterator>
OutputIterator find_odd_cycle(
    const Graph& graph,
    const IndexMap index_map,
    OutputIterator result);
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

OutputIterator result

The find_odd_cycle function finds an odd-length cycle if the graph is not bipartite. The sequence of vertices producing such a cycle is written into this iterator. The OutputIterator type must be a model of OutputIterator. The graph’s vertex descriptor type must be in the set of value types of the iterator. The final value is returned by the function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing is written, thus the given iterator matches the return value.

(3) Using the internal index map

template <typename Graph, typename OutputIterator>
OutputIterator find_odd_cycle(
    const Graph& graph,
    OutputIterator result);
Direction Parameter Description

IN

const Graph& graph

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

OUT

OutputIterator result

The find_odd_cycle function finds an odd-length cycle if the graph is not bipartite. The sequence of vertices producing such a cycle is written into this iterator. The OutputIterator type must be a model of OutputIterator. The graph’s vertex descriptor type must be in the set of value types of the iterator. The final value is returned by the function. If the graph is bipartite (i.e. no odd-length cycle exists), nothing is written, thus the given iterator matches the return value.

Description

The find_odd_cycle 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.

Another equivalent characterization is the non-existance of odd-length cycles, meaning that a graph is bipartite if and only if it does not contain a cycle with an odd number of vertices as a subgraph. find_odd_cycle() does nearly the same as is_bipartite(), but additionally constructs an odd-length cycle if the graph is found to be not bipartite.

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 odd-length cycle is written into the Output Iterator result if one exists. The final final iterator is returned by the function.

Returns

The function returns an OutputIterator pointing past the last vertex written. If the graph is bipartite (i.e. no odd-length cycle exists), nothing is written, and the returned iterator equals the input result.

Edit this Page