#include <unordered_map>
template<class Vertex>
class BfsVisitor {
public:
BfsVisitor() {
parents_.clear();
}
void ExamineVertex(const Vertex& vertex) {
current_vertex_ = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
if (parents_.empty()) {
current_vertex_ = vertex;
parents_.insert({vertex, current_vertex_});
} else if (parents_.find(vertex) == parents_.end()) {
parents_.insert({vertex, current_vertex_});
}
}
size_t DistanceTo(const Vertex& target) const {
size_t counter = 0;
Vertex current_target = target;
while (true) {
Vertex parent_of_target = parents_.at(current_target);
if (parent_of_target == current_target) {
return counter;
}
++counter;
current_target = parent_of_target;
}
}
Vertex Parent(const Vertex& vertex) const {
return parents_.at(vertex);
}
private:
static std::unordered_map<Vertex, Vertex> parents_;
Vertex current_vertex_;
};
template<typename Vertex>
std::unordered_map<Vertex, Vertex> BfsVisitor<Vertex>::parents_ = std::unordered_map<Vertex, Vertex>();