Example Program
Topological Sort
Topological sort of a graph.
File "graph_algo_topsort.cpp"
A tutorial about topological sort.

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

Graph creation: 9 directed edges (0,3), (0,1), ...

13 | TSize numEdges = 9;
14 | TVertexDescriptor edges[] = {0,3, 0,1, 1,2, 3,2, 5,7, 5,6, 6,7, 6,3, 8,7};
15 | TGraph g;
16 | addEdges(g, edges, numEdges);
17 | ::std::cout << g << ::std::endl;

One external property map: Vertex names

18 | String<std::string> nameMap;
19 | std::string names[] = {"shirt", "tie", "jacket", "belt", "watch", "undershorts", "pants", "shoes", "socks"};
20 | resizeVertexMap(g,nameMap, names);

Out-parameter: Order of vertices

21 | String<TVertexDescriptor> order;

Topological sort

22 | topologicalSort(g, order);

Console output

23 | ::std::cout << "Topological sort: " << ::std::endl;
24 | typedef Iterator<String<TVertexDescriptor> >::Type TStringIterator;
25 | TStringIterator it = begin(order);
26 | TStringIterator itEnd = end(order);
27 | while(it != itEnd) {
28 | ::std::cout << getProperty(nameMap, getValue(it)) << ",";
29 | goNext(it);
30 | }
31 | ::std::cout << ::std::endl;
32 | return 0;
33 | }

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

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