fn() depthFirstSearchImplements a depth-first search on a graph.
Implements a depth-first search on a graph.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void depthFirstSearch(predecessor, discovery, finish, g);
|
Parameters
predecessor
|
A property map.Predecessor subgraph produced by the depth-first search. |
---|---|
discovery
|
A property map.The discovery time of a vertex v. |
finish
|
A property map.The time when v's adjacency list has been fully explored. |
g
|
A graph. Types: Undirected Graph, Directed Graph |
Detailed Description
In contrast to a breadth-first search the depth-first search is repeated from multiple sources if the graph is not connected. Hence, depth-first search produces a depth-first forest. To ensure each vertex ends up in exactly one tree we need not just a distance but a discovery and finishing time.
Example
#include <iostream>
#include <seqan/graph_algorithms.h>
using namespace seqan;
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;
}
Adjacency list: 0 -> 1,3, 1 -> 4, 2 -> 5,4, 3 -> 1, 4 -> 3, 5 -> 5, Edge list: Source: 0,Target: 1 (Id: 1) Source: 0,Target: 3 (Id: 0) Source: 1,Target: 4 (Id: 2) Source: 2,Target: 5 (Id: 4) Source: 2,Target: 4 (Id: 3) Source: 3,Target: 1 (Id: 5) Source: 4,Target: 3 (Id: 6) Source: 5,Target: 5 (Id: 7) Depth-First search: Vertex u: Discovery time = 1,Finishing time = 8,Predecessor = nil Vertex v: Discovery time = 2,Finishing time = 7,Predecessor = u Vertex w: Discovery time = 9,Finishing time = 12,Predecessor = nil Vertex x: Discovery time = 4,Finishing time = 5,Predecessor = y Vertex y: Discovery time = 3,Finishing time = 6,Predecessor = v Vertex z: Discovery time = 10,Finishing time = 11,Predecessor = w
Data Races
Thread safety unknown!