Example Program
Prims Algorithm
Prim's algorithm for computing a minimum spanning tree.
File "graph_algo_tree_prim.cpp"
A tutorial about prim's algorithm.

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

Graph creation: 14 undirected edges {0,1}, {0,6}, ...

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

Two external property maps: Weight and vertex names

16 | unsigned int weights[] = {4, 8, 8, 11, 7, 2, 4, 9, 14, 7, 6, 10, 1, 2 };
17 | char names[] = {'a', 'b', 'c', 'd', 'i', 'e', 'h', 'g', 'f'};
18 | String<int> weightMap;
19 | resizeEdgeMap(g, weightMap, weights);
20 | String<char> nameMap;
21 | resizeVertexMap(g,nameMap, names);

Out-parameter: Predecessor map to recover the tree

22 | String<TVertexDescriptor> predMap;

Prim's algorithm

23 | primsAlgorithm(g, 0, weightMap, predMap);

Console Output

24 | ::std::cout << "Minimum Spanning Tree (Prim's algorithm): " << ::std::endl;
25 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
26 | TVertexIterator it(g);
27 | while(!atEnd(it)) {
28 | ::std::cout << "Path from " << getProperty(nameMap, 0) << " to " << getProperty(nameMap, getValue(it)) << ": ";
29 | _printPath(g,predMap,(TVertexDescriptor) 0, getValue(it), nameMap);
30 | ::std::cout << ::std::endl;
31 | goNext(it);
32 | }
33 | return 0;
34 | }

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

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