| 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 |
| 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;
|
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;
|
17 | String<char> nameMap;
| 18 | char names[] = {'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};
| 19 | assignVertexMap(g,nameMap, names);
|
20 | String<unsigned int> predMap;
| 21 | String<unsigned int> distMap;
|
22 | breadthFirstSearch(g, 1, predMap, distMap);
|
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 | }
|
|