Function breadthFirstSearchImpl

Graph/BreadthFirstSearch.h:96–173

 */
template <class Graph, class VertexSet, class ColorMap, class Visitor>
static inline void breadthFirstSearchImpl(
	const VertexSet& startVertices, const Graph& g, bool undirected,
	ColorMap& colorMap, Visitor& visitor)
{
	typedef typename boost::graph_traits<Graph>::vertex_descriptor V;
	typedef typename boost::graph_traits<Graph>::edge_descriptor E;
	typedef typename boost::graph_traits<Graph>::in_edge_iterator IEIt;
	typedef typename boost::graph_traits<Graph>::out_edge_iterator OEIt;

	typedef typename VertexSet::const_iterator VertexListConstIt;

	typedef typename property_traits<ColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;

	/* breadth-first search queue */
	boost::queue<V> queue;

	BFSVisitorResult result;
	IEIt iei, iei_end;
	OEIt oei, oei_end;

	/* push start vertices onto search queue */

	for (VertexListConstIt it = startVertices.begin(); it != startVertices.end(); ++it) {
		ColorValue color = get(colorMap, *it);
		if (color == Color::white()) {
			result = visitor.discover_vertex(*it, g);
			if (result == BFS_SKIP_ELEMENT)
				continue;
			else if (result == BFS_ABORT_SEARCH)
				return;
			put(colorMap, *it, Color::gray());
		}
		/*
		 * note: vertex may already be black if user is reusing colorMap across
		 * multiple searches
		 */
		if (color != Color::black()) {
			queue.push(*it);
		}
	}

	/* do breadth first search */

	while (!queue.empty()) {

		V u = queue.top();
		queue.pop();
		result = visitor.examine_vertex(u, g);
		if (result == BFS_SKIP_ELEMENT)
			continue;
		else if (result == BFS_ABORT_SEARCH)
			return;

		for (boost::tie(oei, oei_end) = out_edges(u, g); oei != oei_end; ++oei) {
			const E& e = *oei;
			result = bfsVisitEdge(e, true, g, queue, colorMap, visitor);
			if (result == BFS_ABORT_SEARCH)