Example Program
Breadth-First Search
Breadth-first search through a graph.
File "graph_algo_bfs.cpp"
A tutorial about breadth-first search.

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

Graph creation: 10 undirected edges {0,1}, {0,4}, ...

12 | TSize numEdges = 10;
13 | TVertexDescriptor edges[] = {0,1, 0,4, 1,5, 2,5, 2,6, 2,3, 3,6, 3,7, 5,6, 6,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[] = {'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};
19 | resizeVertexMap(g,nameMap, names);

Out-parameters: Predecessor and distance map

20 | String<unsigned int> predMap;
21 | String<unsigned int> distMap;

Breadth-frist search from vertex 1

22 | breadthFirstSearch(g, 1, predMap, distMap);

Console output

23 | ::std::cout << "Breadth-First search: " << ::std::endl;
24 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
25 | TVertexIterator it(g);
26 | while(!atEnd(it)) {
27 | ::std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
28 | if (getProperty(distMap, getValue(it))== _getInfinityDistance(distMap)) {
29 | ::std::cout << "Not reachable!";
30 | } else {
31 | ::std::cout << "Level = " << getProperty(distMap, getValue(it));
32 | }
33 | typedef Value<String<unsigned int> >::Type TPredVal;
34 | TPredVal pre = getProperty(predMap, getValue(it));
35 | if (pre != getNil<TVertexDescriptor>()) {
36 | ::std::cout << ", Predecessor = " << getProperty(nameMap, pre) << ::std::endl;
37 | } else {
38 | ::std::cout << ", Predecessor = nil" << ::std::endl;
39 | }
40 | goNext(it);
41 | }
42 | return 0;
43 | }

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

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