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