1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <seqan/graph_algorithms.h>
using namespace seqan2;
int main()
{
typedef Graph<Directed<> > TGraph;
typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
typedef Size<TGraph>::Type TSize;
// Create graph with 8 directed edges (0,3), (0,1), ...
TSize numEdges = 8;
TVertexDescriptor edges[] = {0, 3, 0, 1, 1, 4, 2, 4, 2, 5, 3, 1, 4, 3, 5, 5};
TGraph g;
addEdges(g, edges, numEdges);
// Print graph.
std::cout << g << "\n";
// Create external property map for the vertex names and assign to graph.
char names[] = {'u', 'v', 'w', 'x', 'y', 'z'};
String<char> nameMap;
assignVertexMap(nameMap, g, names);
// Perform a DFS search.
String<unsigned int> predMap;
String<unsigned int> discoveryTimeMap;
String<unsigned int> finishingTimeMap;
depthFirstSearch(predMap, discoveryTimeMap, finishingTimeMap, g);
// Write the result to stdout.
std::cout << "Depth-First search: \n";
typedef Iterator<Graph<>, VertexIterator>::Type TVertexIterator;
TVertexIterator it(g);
while (!atEnd(it))
{
std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
std::cout << "Discovery time = " << getProperty(discoveryTimeMap, getValue(it)) << ",";
std::cout << "Finishing time = " << getProperty(finishingTimeMap, getValue(it)) << ",";
typedef Value<String<unsigned int> >::Type TPredVal;
TPredVal pre = getProperty(predMap, getValue(it));
if (pre != getNil<TVertexDescriptor>())
std::cout << "Predecessor = " << getProperty(nameMap, pre) << "\n";
else
std::cout << "Predecessor = nil" << "\n";
goNext(it);
}
return 0;
}
|
