| Example Program Depth-First Search Depth-first search through a graph. File "graph_algo_dfs.cpp" This code example illustrates a depth-first search.
1 |
2 | #include <seqan/graph.h>
3 | #include <iostream>
4 |
5 | using namespace seqan;
6 |
7 |
8 | int main()
9 | {
10 | typedef Graph<Directed<> > TGraph;
11 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
12 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
13 | typedef Size<TGraph>::Type TSize;
Graph creation: 8 directed edges (0,3), (0,1), ...
14 | TSize numEdges = 8;
15 | TVertexDescriptor edges[] = {0,3, 0,1, 1,4, 2,4, 2,5, 3,1, 4,3, 5,5};
16 | TGraph g;
17 | addEdges(g, edges, numEdges);
18 | std::cout << g << ::std::endl;
One external property map: Vertex names
19 | char names[] = {'u', 'v', 'w', 'x', 'y', 'z'};
20 | String<char> nameMap;
21 | resizeVertexMap(g,nameMap, names);
Out-parameters: Predecessor and discovery maps
22 | String<unsigned int> predMap;
23 | String<unsigned int> discoveryTimeMap;
24 | String<unsigned int> finishingTimeMap;
Depth-frist search
25 | depth_first_search(g, predMap, discoveryTimeMap, finishingTimeMap);
Console output
26 | std::cout << "Depth-First search: " << ::std::endl;
27 | typedef Iterator<Graph<>, VertexIterator>::Type TVertexIterator;
28 | TVertexIterator it(g);
29 | while(!atEnd(it)) {
30 | std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
31 | std::cout << "Discovery time = " << getProperty(discoveryTimeMap, getValue(it)) << ",";
32 | std::cout << "Finishing time = " << getProperty(finishingTimeMap, getValue(it)) << ",";
33 | typedef Value<String<unsigned int> >::Type TPredVal;
34 | TPredVal pre = getProperty(predMap, getValue(it));
35 | if (pre != getNilPredecessor(g)) {
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 depth_first_search, Graph SeqAn - Sequence Analysis Library - www.seqan.de