fn() stronglyConnectedComponentsDecomposes a directed graph into its strongly connected components.
Decomposes a directed graph into its strongly connected components.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
TSize stronglyConnectedComponents(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
|
A directed graph. Types: Directed Graph |
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 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(nameMap, g, names);
// Compute strongly connected components.
String<unsigned int> component;
stronglyConnectedComponents(component, g);
// 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
Data Races
Thread safety unknown!