fn() connectedComponents
Decomposes an undirected graph into its connected components.

Defined in <seqan/graph_algorithms.h>
Signature TSize connectedComponents(components, g);

Parameters

components A property map. Each vertex is mapped to a component id. If two vertices share the same id they are in the same component.
g An undirected graph. Types: Undirected Graph

Return Values

TSize The number of components.

Detailed Description

Examples

A simple example on how to use this function.

// Build Input.
Graph<Undirected<> > graph;
for (unsigned i = 0; i < 5; ++i)
    addVertex(graph);
addEdge(graph, 0, 1);
addEdge(graph, 0, 3);
addEdge(graph, 2, 4);
String<unsigned> components;
unsigned numComponents = 0;

// Call Algorithm.
numComponents = connectedComponents(g, components);

// Print Result.
std::cout << "Number of components: " << numComponents << std::endl;
std::cout << std::endl << "Vertex -> Component" << std::endl;
for (unsigned i = 0; i < length(components); ++i)
    std::cout << i << " -> " << components[i] << std::endl;

The output now is:

Number of components: 2

Vertex -> Component
0 -> 0
1 -> 0
2 -> 1
3 -> 0
4 -> 1

Data Races

Thread safety unknown!