fn() breadthFirstSearchImplements a breadth-first search on a graph.
Implements a breadth-first search on a graph.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void breadthFirstSearch(predecessor, distance, g, source);
|
Parameters
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. |
g
|
Undirected Graph, Directed Graph |
source
|
A vertex descriptor. The breadth-first search is started from this vertex. Types: VertexDescriptor |
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 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(nameMap, g, names);
// Perform a BFS search starting from vertex with descriptor 1.
String<unsigned int> predMap;
String<unsigned int> distMap;
breadthFirstSearch(predMap, distMap, g, 1);
// 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
Data Races
Thread safety unknown!