fn() breadthFirstSearch
Implements a breadth-first search on a graph.

Defined in <seqan/graph_algorithms.h>
Signature void breadthFirstSearch(g, source, predecessor, distance);

Parameters

g Undirected Graph, Directed Graph
source A vertex descriptor. The breadth-first search is started from this vertex. Types: VertexDescriptor
predecessor A property map. The predecessor map stores implicitly the breadth-first tree.
distance A property map. The distance map indicates at what depth a vertex was discovered.

Detailed Description

Breadth-first search computes the distance from source to all reachable vertices. It also produces a breath-first tree where each node has a predecessor/parent.

Example

#include <iostream>
#include <seqan/graph_algorithms.h>

using namespace seqan;

int main() 
{
    typedef Graph<Undirected<> > TGraph;
    typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
    typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
    typedef Size<TGraph>::Type TSize;

    // Create a graph with 10 undirected edges {0,1}, {0,4}, ...
    TSize numEdges = 10;
    TVertexDescriptor edges[] = {0,1, 0,4, 1,5, 2,5, 2,6, 2,3, 3,6, 3,7, 5,6, 6,7};
    TGraph g;
    addEdges(g, edges, numEdges);
    // Print graph.
    std::cout << g << "\n";

    // Create external property map for the vertex names and assign to graph.
    String<char> nameMap;
    char names[] = {'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};
    assignVertexMap(g,nameMap, names);

    // Perform a BFS search starting from vertex with descriptor 1.
    String<unsigned int> predMap;
    String<unsigned int> distMap;
    breadthFirstSearch(g, 1, predMap, distMap);

    // Write the result to stdout.
    std::cout << "Breadth-First search: \n";
    typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
    TVertexIterator it(g);
    while (!atEnd(it))
    {
        std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
        if (getProperty(distMap, getValue(it))== _getInfinityDistance(distMap))
            SEQAN_FAIL("Should never reach here!");
        else
            std::cout << "Level = " << getProperty(distMap, 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 -> 4,1,
1 -> 5,0,
2 -> 3,6,5,
3 -> 7,6,2,
4 -> 0,
5 -> 6,2,1,
6 -> 7,5,3,2,
7 -> 6,3,
Edge list:
Source: 0,Target: 4 (Id: 1)
Source: 0,Target: 1 (Id: 0)
Source: 1,Target: 5 (Id: 2)
Source: 2,Target: 3 (Id: 5)
Source: 2,Target: 6 (Id: 4)
Source: 2,Target: 5 (Id: 3)
Source: 3,Target: 7 (Id: 7)
Source: 3,Target: 6 (Id: 6)
Source: 5,Target: 6 (Id: 8)
Source: 6,Target: 7 (Id: 9)

Breadth-First search: 
Vertex r: Level = 1, Predecessor = s
Vertex s: Level = 0, Predecessor = nil
Vertex t: Level = 2, Predecessor = w
Vertex u: Level = 3, Predecessor = x
Vertex v: Level = 2, Predecessor = r
Vertex w: Level = 1, Predecessor = s
Vertex x: Level = 2, Predecessor = w
Vertex y: Level = 3, Predecessor = x

See Also