1 files changed, 43 insertions, 0 deletions
diff --git a/libdevcore/Algorithms.h b/libdevcore/Algorithms.h
index 7fe2472d..34a4dfe5 100644
--- a/libdevcore/Algorithms.h
+++ b/libdevcore/Algorithms.h
@@ -75,4 +75,47 @@ private:
 	V const* m_firstCycleVertex = nullptr;
 };
 
+/**
+ * Generic breadth first search.
+ *
+ * Example: Gather all (recursive) children in a graph starting at (and including) ``root``:
+ *
+ * Node const* root = ...;
+ * std::set<Node> allNodes = BreadthFirstSearch<Node>{{root}}.run([](Node const& _node, auto&& _addChild) {
+ *   // Potentially process ``_node``.
+ *   for (Node const& _child: _node.children())
+ *     // Potentially filter the children to be visited.
+ *     _addChild(_child);
+ * }).visited;
+ *
+ * Note that the order of the traversal is *non-deterministic* (the children are stored in a std::set of pointers).
+ */
+template<typename V>
+struct BreadthFirstSearch
+{
+	/// Runs the breadth first search. The verticesToTraverse member of the struct needs to be initialized.
+	/// @param _forEachChild is a callable of the form [...](V const& _node, auto&& _addChild) { ... }
+	/// that is called for each visited node and is supposed to call _addChild(childNode) for every child
+	/// node of _node.
+	template<typename ForEachChild>
+	BreadthFirstSearch& run(ForEachChild&& _forEachChild)
+	{
+		while (!verticesToTraverse.empty())
+		{
+			V const* v = *verticesToTraverse.begin();
+			verticesToTraverse.erase(verticesToTraverse.begin());
+			visited.insert(v);
+
+			_forEachChild(*v, [this](V const& _vertex) {
+				if (!visited.count(&_vertex))
+					verticesToTraverse.insert(&_vertex);
+			});
+		}
+		return *this;
+	}
+
+	std::set<V const*> verticesToTraverse;
+	std::set<V const*> visited{};
+};
+
 }