| Example Program Strongly Connected Components Computing all strongly-connected-components of a graph. 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;
|
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;
|
17 | String<char> nameMap;
| 18 | char names[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
| 19 | assignVertexMap(g,nameMap, names);
|
20 | String<unsigned int> component;
|
21 | stronglyConnectedComponents(g, component);
|
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 | }
|
|