Example Program
Breadth-First Search
Breadth-first search through a graph.
A tutorial about breadth-first search.
1#include <iostream>
2#include <seqan/graph_algorithms.h>
3
4using namespace seqan;
5
6int 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    breadth_first_search(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}
SeqAn - Sequence Analysis Library - www.seqan.de