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
4using namespace seqan;
5
6int 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}
SeqAn - Sequence Analysis Library - www.seqan.de
 

Page built @2011/02/08 21:37:01