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(g, predecessor, discovery, finish);
|
Parameters
g
|
A graph. Types: Undirected Graph, Directed Graph |
---|---|
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. |
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 EdgeDescriptor<TGraph>::Type TEdgeDescriptor; 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(g,nameMap, names); // Perform a DFS search. String<unsigned int> predMap; String<unsigned int> discoveryTimeMap; String<unsigned int> finishingTimeMap; depthFirstSearch(g, predMap, discoveryTimeMap, finishingTimeMap); // 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