fn() depthFirstSearch
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!

See Also