#pragma once
#include <map>
template<typename Vertex>
class BfsVisitor {
public:
BfsVisitor() {
distance.clear();
parent.clear();
is_start = true;
}
void ExamineVertex(const Vertex& vertex) {
current_v = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
parent[vertex] = is_start ? vertex : current_v;
distance[vertex] = is_start ? 0 : distance[current_v] + 1;
is_start = false;
}
size_t DistanceTo(const Vertex& target) const {
return distance[target];
}
Vertex Parent(const Vertex& vertex) const {
return parent[vertex];
}
private:
static bool is_start;
static Vertex current_v;
static std::map<Vertex, Vertex> parent;
static std::map<Vertex, size_t> distance;
};
template <typename Vertex>
std::map<Vertex, size_t> BfsVisitor<Vertex>::distance
= std::map<Vertex, size_t>();
template <typename Vertex>
std::map<Vertex, Vertex> BfsVisitor<Vertex>::parent
= std::map<Vertex, Vertex>();
template <typename Vertex>
bool BfsVisitor<Vertex>::is_start = true;
template <typename Vertex>
Vertex BfsVisitor<Vertex>::current_v = Vertex();