connected_components

Computes the connected components of an undirected graph using a DFS-based approach.

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

Example

// Connected Components example
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

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

int main() {
    Graph g{7};
    // Component 0: {0,1,2}  Component 1: {3,4}  Component 2: {5,6}
    boost::add_edge(0, 1, g); boost::add_edge(1, 2, g);
    boost::add_edge(3, 4, g);
    boost::add_edge(5, 6, g);

    std::vector<int> comp(boost::num_vertices(g));
    int n = boost::connected_components(g,
        boost::make_iterator_property_map(comp.begin(), boost::get(boost::vertex_index, g)));

    std::cout << "Number of components: " << n << "\n";
    for (std::size_t v = 0; v < comp.size(); ++v) {
        std::cout << "  Vertex " << v << " -> component " << comp[v] << "\n";
    }
}

Number of components: 3
  Vertex 0 -> component 0
  Vertex 1 -> component 0
  Vertex 2 -> component 0
  Vertex 3 -> component 1
  Vertex 4 -> component 1
  Vertex 5 -> component 2
  Vertex 6 -> component 2

(1) Named parameter version

template <class VertexListGraph, class ComponentMap,
          class P, class T, class R>
typename property_traits<ComponentMap>::value_type
connected_components(
    VertexListGraph& G, ComponentMap comp,
    const bgl_named_params<P, T, R>& params = all defaults);

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	An undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.
OUT	`ComponentMap c`	The algorithm computes how many connected components are in the graph, and assigning each component an integer label. The algorithm then records which component each vertex in the graph belongs to by recording the component number in the component property map. The `ComponentMap` type must be a model of Writable Property Map. The value type should be an integer type, preferably the same as the `vertices_size_type` of the graph. The key type must be the graph’s vertex descriptor type.

const Graph& g

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

OUT

ComponentMap c

The algorithm computes how many connected components are in the graph, and assigning each component an integer label. The algorithm then records which component each vertex in the graph belongs to by recording the component number in the component property map. The ComponentMap type must be a model of Writable Property Map. The value type should be an integer type, preferably the same as the vertices_size_type of the graph. The key type must be the graph’s vertex descriptor type.

Named Parameters

Direction Parameter Description

Direction	Parameter	Description
UTIL	`color_map(ColorMap color)`	This is used by the algorithm to keep track of its progress through the graph. The type `ColorMap` must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue. Default: an iterator_property_map created from a `std::vector` of `default_color_type` of size `num_vertices(g)` and using the `i_map` for the index map.
IN	`vertex_index_map(VertexIndexMap i_map)`	This maps each vertex to an integer in the range `[0, num_vertices(g))`. This parameter is only necessary when the default color property map is used. 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. Default: `get(vertex_index, g)`. Note: if you use this default, make sure your graph has an internal `vertex_index` property. For example, `adjacency_list` with `VertexList=listS` does not have an internal `vertex_index` property.

UTIL

color_map(ColorMap color)

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.

vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. 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.
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

(2) Positional version

template <class VertexListGraph, class ComponentMap>
typename property_traits<ComponentMap>::value_type
connected_components(
    const VertexListGraph& g, ComponentMap c);

Equivalent to (1) with every named parameter left at its default. Uses get(vertex_index, g) for the index map and an internally allocated default_color_type color map.

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	An undirected graph. Same concept requirements as (1).
OUT	`ComponentMap c`	Same as (1).

const Graph& g

An undirected graph. Same concept requirements as (1).

OUT

ComponentMap c

Same as (1).

Description

The connected_components() function computes the connected components of an undirected graph using a DFS-based approach. A connected component of an undirected graph is a set of vertices that are all reachable from each other. If the connected components need to be maintained while a graph is growing the disjoint-set based approach of function incremental_components() is faster. For ``static'' graphs this DFS-based approach is faster [5].

The output of the algorithm is recorded in the component property map comp, which will contain numbers giving the component number assigned to each vertex. The total number of components is the return value of the function.

Returns

The total number of connected components, as a value of type property_traits<ComponentMap>::value_type.

Example

The file examples/connected_components.cpp contains an example of calculating the connected components of an undirected graph.

Edit this Page