#include <map>
using std::map;
template<typename Vertex>
class BfsVisitor {
private:
static bool first_vertex;
static Vertex current_vertex;
static map<Vertex, int> dist;
static map<Vertex, Vertex> parent;
public:
BfsVisitor() {
dist = map<Vertex, int>();
parent = map<Vertex, Vertex>();
first_vertex = true;
}
void ExamineVertex(const Vertex& vertex) {
if (first_vertex) {
first_vertex = false;
dist[vertex] = 0;
parent[vertex] = vertex;
current_vertex = vertex;
return;
}
current_vertex = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
dist[vertex] = dist[current_vertex]+1;
parent[vertex] = current_vertex;
}
size_t DistanceTo(const Vertex& target) const {
return dist.at(target);
}
Vertex Parent(const Vertex& vertex) const {
return parent.at(vertex);
}
};
template <typename T>
map<T, int> BfsVisitor<T>::dist = map<T, int>();
template <typename T>
map<T, T> BfsVisitor<T>::parent = map<T, T>();
template <typename T>
bool BfsVisitor<T>::first_vertex = true;
template <typename T>
T BfsVisitor<T>::current_vertex = T();