# `connected_components`

Graphs: | see below
Properties: | components, color, discover time, finish time
Complexity: | O(V + E)

    (1)
    template <class VertexListGraph, class Visitor,
              class Components>
    typename property_traits< Components >::value_type
    connected_components(VertexListGraph& G, Components c,
                         Visitor v);

    (2)
    template <class VertexListGraph, class Visitor,
              class Components, class Color>
    typename property_traits<Components>::value_type
    connected_components(VertexListGraph& G, Components c,
                         Color color, Visitor v);

    (3)
    template <class VertexListGraph, class Visitor,
              class Components, class DiscoverTime,
              class FinishTime, class Color>
    typename property_traits<Components>::value_type
    connected_components(VertexListGraph& G, Components c,
                         DiscoverTime d, FinishTime f,
                         Color color, Visitor v);

The `connected_component()` function dispatches to two different algorithms depending on whether the graph in question is directed or undirected.

- Computes the strongly connected components of a directed graph using the DFS/transpose/DFS algorithm [1,8].

- Computes the connected components of an undirected graph using a DFS-based approach. If the connected-components are to be calculated over and over while a graph is changing the disjoint-set based approach of function `dynamic_connected_components()` is faster. For ``static'' graphs this DFS-based approach is faster [8].

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

The algorithm requires the use of several property maps: color, discover time, and finish time. There are several versions of this algorithm to accommodate whether you wish to use interior or exterior property maps.

### Where Defined

`boost/graph/connected_components.hpp`

### Definitions

A connected component of an undirected graph is a set of vertices that are all reachable from each other. A strongly connected component of a directed graph G=(V,E) is a maximal set of vertices U which is in V such that for every pair of vertices u and v in U, we have both a path from u to v and path from v to u. That is to say that u and v are reachable from each other.

### Requirements on Types

- The graph type must be a model of VertexListGraph.
- `DiscoverTime` and `FinishTime` must be models of WritablePropertyMap and their value type must be an integer type. Vertex descriptors from the graph should be usable as the key type for these maps.
- The `Color` map must be a ReadWritePropertyMap and the graph's vertex descriptor type should be usable as the map's key type. The value type of the map must be a model of ColorValue.
- The `Components` type must be a model of ReadWritePropertyMap. The value type of the `Components` property map should be an integer type, preferably the same as the `size_type` of the graph. The key type should be the graph's vertex descriptor type.

### Complexity

The time complexity for the strongly connected components algorithm is O(V + E). The time complexity for the connected components algorithm is also O(V + E).

### Example

Calculating the connected components of an undirected graph. The complete source is in file `examples/connected_components.cpp`.

      typedef discover_time_property< finish_time_property
                                    < color_property<> > > VertexProperty;
      typedef adjacency_list <vecS, vecS, undirectedS, VertexProperty> Graph;
      typedef graph_traits<Graph>::vertex_descriptor Vertex;

      const int N = 6;
      Graph G(N);
      add_edge(0, 1, G);
      add_edge(1, 4, G);
      add_edge(4, 0, G);
      add_edge(2, 5, G);

      std::vector<int> c(num_vertices(G));
      int num = connected_components(G, c.begin(),
                  get_color_map(G), null_visitor());

      cout << endl;
      std::vector<int>::iterator i;
      cout << "Total number of components: " << num << endl;
      for (i = c.begin(); i != c.end(); ++i)
        cout << "Vertex " << i - c.begin()
             << " is in component " << *i << endl;
      cout << endl;

The output is:

      Total number of components: 3
      Vertex 0 is in component 1
      Vertex 1 is in component 1
      Vertex 2 is in component 2
      Vertex 3 is in component 3
      Vertex 4 is in component 1
      Vertex 5 is in component 2

Calculating the strongly connected components of a directed graph.

        typedef discover_time_property< finish_time_property
                                      < color_property<> > > VertexProperty;
        typedef adjacency_list< vecS, vecS, directedS, VertexProperty >  Graph;
        const int N = 6;
        Graph G(N);
        add_edge(0, 1, G);
        add_edge(1, 1, G);
        add_edge(1, 3, G);
        add_edge(1, 4, G);
        add_edge(4, 3, G);
        add_edge(3, 4, G);
        add_edge(3, 0, G);
        add_edge(5, 2, G);

        typedef graph_traits<Graph>::vertex_descriptor Vertex;

        std::vector<int> c(N);
        int num = connected_components(G, c.begin(),
          get_color_map(G), null_visitor());

        cout << endl;
        cout << "Total number of components: " << num << endl;
        std::vector<int>::iterator i;
        for (i = c.begin(); i != c.end(); ++i)
          cout << "Vertex " << i - c.begin()
               << " is in component " << *i << endl;
      }

The output is:

      Total number of components: 3
      Vertex 0 is in component 3
      Vertex 1 is in component 3
      Vertex 2 is in component 2
      Vertex 3 is in component 3
      Vertex 4 is in component 3
      Vertex 5 is in component 1

Copyright © 2000 | Jeremy Siek, Univ.of Notre Dame (jsiek@lsc.nd.edu)