| Example Program Breadth-First Search Breadth-first search through a graph. File "graph_algo_bfs.cpp" This code example illustrates a breadth-first search.
1 |
2 | #include <seqan/graph_algorithms.h>
3 | #include <iostream>
4 |
5 | using namespace seqan;
6 |
7 | int main()
8 | {
9 | typedef Graph<Undirected<> > TGraph;
10 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
11 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
12 | typedef Size<TGraph>::Type TSize;
Graph creation: 10 undirected edges {0,1}, {0,4}, ...
13 | TSize numEdges = 10;
14 | TVertexDescriptor edges[] = {0,1, 0,4, 1,5, 2,5, 2,6, 2,3, 3,6, 3,7, 5,6, 6,7};
15 | TGraph g;
16 | addEdges(g, edges, numEdges);
17 | std::cout << g << ::std::endl;
One external property map: Vertex names
18 | String<char> nameMap;
19 | char names[] = {'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};
20 | resizeVertexMap(g,nameMap, names);
Out-parameters: Predecessor and distance map
21 | String<unsigned int> predMap;
22 | String<unsigned int> distMap;
Breadth-frist search from vertex 1
23 | breadth_first_search(g, 1, predMap, distMap);
Console output
24 | std::cout << "Breadth-First search: " << ::std::endl;
25 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
26 | TVertexIterator it(g);
27 | while(!atEnd(it)) {
28 | std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
29 | if (getProperty(distMap, getValue(it))== _getInfinityDistance(distMap)) {
30 | std::cout << "Not reachable!";
31 | } else {
32 | std::cout << "Level = " << getProperty(distMap, getValue(it));
33 | }
34 | typedef Value<String<unsigned int> >::Type TPredVal;
35 | TPredVal pre = getProperty(predMap, getValue(it));
36 | if (pre != getNil<TVertexDescriptor>()) {
37 | std::cout << ", Predecessor = " << getProperty(nameMap, pre) << ::std::endl;
38 | } else {
39 | std::cout << ", Predecessor = nil" << ::std::endl;
40 | }
41 | goNext(it);
42 | }
43 | return 0;
44 | }
See breadth_first_search, Graph SeqAn - Sequence Analysis Library - www.seqan.de