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