↰ Return to documentation for file (include/networkit/graph/BFS.hpp)
#ifndef NETWORKIT_GRAPH_BFS_HPP_
#define NETWORKIT_GRAPH_BFS_HPP_
#include <array>
#include <cstddef>
#include <queue>
#include <stdexcept>
#include <vector>
#include <networkit/Globals.hpp>
#include <networkit/graph/Graph.hpp>
#include <networkit/graph/TraversalImpl.hpp>
namespace NetworKit {
namespace Traversal {
namespace Impl {
template <class F, class NodeT>
auto callBFSHandle(F &f, NodeT u, count dist) -> decltype(f(u, dist)) {
return f(u, dist);
}
template <class F, class NodeT>
auto callBFSHandle(F &f, NodeT u, count) -> decltype(f(u)) {
return f(u);
}
} // namespace Impl
template <class InputIt, typename L, class GraphT>
void BFSfrom(const GraphT &G, InputIt first, InputIt last, L handle) {
using NodeT = typename GraphT::NodeT;
std::vector<Visit> marked(static_cast<std::size_t>(G.upperNodeIdBound()), Visit::Unvisited);
std::queue<NodeT> q, qNext;
count dist = 0;
// enqueue start nodes, do not enqueue duplicates
for (; first != last; ++first) {
if (!Impl::isValidNode(G, *first))
throw std::runtime_error("Error: source node not in the graph.");
const std::size_t uIndex = Impl::nodeIndex(*first);
if (marked[uIndex] == Visit::Unvisited) {
q.push(*first);
marked[uIndex] = Visit::Visited;
}
}
while (!q.empty()) {
const auto u = q.front();
q.pop();
// apply function
Impl::callBFSHandle(handle, u, dist);
G.forNeighborsOf(u, [&](NodeT v) {
const std::size_t vIndex = Impl::nodeIndex(v);
if (marked[vIndex] == Visit::Unvisited) {
qNext.push(v);
marked[vIndex] = Visit::Visited;
}
});
if (q.empty() && !qNext.empty()) {
q.swap(qNext);
++dist;
}
}
}
template <typename L, class GraphT>
void BFSfrom(const GraphT &G, typename GraphT::NodeT source, L handle) {
using NodeT = typename GraphT::NodeT;
std::array<NodeT, 1> startNodes{{source}};
BFSfrom(G, startNodes.begin(), startNodes.end(), handle);
}
template <typename L, class GraphT>
void BFSEdgesFrom(const GraphT &G, typename GraphT::NodeT source, L handle) {
using NodeT = typename GraphT::NodeT;
using EdgeWeightT = typename GraphT::EdgeWeightT;
std::vector<Visit> marked(static_cast<std::size_t>(G.upperNodeIdBound()), Visit::Unvisited);
std::queue<NodeT> q;
if (!Impl::isValidNode(G, source))
throw std::runtime_error("Error: source node not in the graph.");
q.push(source); // enqueue root
marked[Impl::nodeIndex(source)] = Visit::Visited;
do {
const auto u = q.front();
q.pop();
// apply function
G.forNeighborsOf(u, [&](NodeT, NodeT v, EdgeWeightT w, edgeid eid) {
const std::size_t vIndex = Impl::nodeIndex(v);
if (marked[vIndex] == Visit::Unvisited) {
handle(u, v, w, eid);
q.push(v);
marked[vIndex] = Visit::Visited;
}
});
} while (!q.empty());
}
} // namespace Traversal
} // namespace NetworKit
#endif // NETWORKIT_GRAPH_BFS_HPP_