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(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