fn() stronglyConnectedComponents
Decomposes a directed graph into its strongly connected components.

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

Parameters

g A directed graph. Types: Directed Graph
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.

Return Values

TSize Number of strongly connected components, Size type of g.

Detailed Description

Example

#include <iostream>
#include <seqan/graph_algorithms.h>

using namespace seqan;

int main()
{
    typedef Graph<Directed<> > TGraph;
    typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
    typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
    typedef Size<TGraph>::Type TSize;

    // Create grap with 14 directed edges (1,0), (0,4), ...
    TSize numEdges = 14;
    TVertexDescriptor edges[] = {1,0, 0,4, 2,1, 4,1, 5,1, 6,2, 3,2, 2,3, 7,3, 5,4, 6,5, 5,6, 7,6, 7,7};
    TGraph g;
    addEdges(g, edges, numEdges);
    // Print graph.
    std::cout << g << std::endl;

    // Create external property map with vertex names and assign to graph.
    String<char> nameMap;
    char names[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
    assignVertexMap(g, nameMap, names);

    // Compute strongly connected components.
    String<unsigned int> component;
    stronglyConnectedComponents(g, component);

    // Print result to stdout.
    std::cout << "Strongly Connected Components: \n";
    typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
    TVertexIterator it(g);
    while (!atEnd(it))
    {
        std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": \n"
                  << "Component = " << getProperty(component, getValue(it)) << "\n";
        goNext(it);
    }

    return 0;
}
Adjacency list:
0 -> 4,
1 -> 0,
2 -> 3,1,
3 -> 2,
4 -> 1,
5 -> 6,4,1,
6 -> 5,2,
7 -> 7,6,3,
Edge list:
Source: 0,Target: 4 (Id: 1)
Source: 1,Target: 0 (Id: 0)
Source: 2,Target: 3 (Id: 7)
Source: 2,Target: 1 (Id: 2)
Source: 3,Target: 2 (Id: 6)
Source: 4,Target: 1 (Id: 3)
Source: 5,Target: 6 (Id: 11)
Source: 5,Target: 4 (Id: 9)
Source: 5,Target: 1 (Id: 4)
Source: 6,Target: 5 (Id: 10)
Source: 6,Target: 2 (Id: 5)
Source: 7,Target: 7 (Id: 13)
Source: 7,Target: 6 (Id: 12)
Source: 7,Target: 3 (Id: 8)

Strongly Connected Components: 
Vertex a: 
Component = 3
Vertex b: 
Component = 3
Vertex c: 
Component = 2
Vertex d: 
Component = 2
Vertex e: 
Component = 3
Vertex f: 
Component = 1
Vertex g: 
Component = 1
Vertex h: 
Component = 0