Example Program
Strongly Connected Components
Computing all strongly-connected-components of a graph.
File "graph_algo_scc.cpp"
A tutorial about the strongly connected component algorithm.

1 | #include <iostream>
2 | #include <seqan/graph_algorithms.h>
3 |
4 | using namespace seqan;
5 |
6 |
7 | int main() {
8 | typedef Graph<Directed<> > TGraph;
9 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
10 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
11 | typedef Size<TGraph>::Type TSize;

Graph creation: 14 directed edges (1,0), (0,4), ...

12 | TSize numEdges = 14;
13 | 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};
14 | TGraph g;
15 | addEdges(g, edges, numEdges);
16 | ::std::cout << g << ::std::endl;

One external property map: Vertex names

17 | String<char> nameMap;
18 | char names[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
19 | resizeVertexMap(g,nameMap, names);

Out-parameter: Map of vertex descriptors to component

20 | String<unsigned int> component;

Strongly Connected Components

21 | stronglyConnectedComponents(g, component);

Console output

22 | ::std::cout << "Strongly Connected Components: " << ::std::endl;
23 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
24 | TVertexIterator it(g);
25 | while(!atEnd(it)) {
26 | ::std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
27 | ::std::cout << "Component = " << getProperty(component, getValue(it)) << ::std::endl;
28 | goNext(it);
29 | }
30 | return 0;
31 | }

See
Graph, stronglyConnectedComponents
SeqAn - Sequence Analysis Library - www.seqan.de

Page built @2012/03/14 16:34:46