I have worked on a simple iterative implementation of the common DFS algorithm for my personal template library. The algorithm itself works, but I try to get a feeling for how to seperate the data and some helpers (e.g. the Memoizer) from the algorithm itself. I ended with some template paramters, requesting classes with some special member functions (operator[] for the Memoizer). Now I try to get some feedback if I missed something or if I should do anything different.
Some words to the Memoizer especially: The operator [] shall return a bool reference, or something which can be used as a reference to bool. With that assumption I can prevent the Memoizer to lookup same Vertex twice. The NonMemoizer is just a simple optimization possibility for DirectedGraphs, which doesn't contain any loopbacks. Thus it doesn't matter if the return value isn't a reference. The BitsetMemoizer is just a simple usage example.
The GraphModel doesn't have a base class or something like that; I'm just requesting the template to have a valid member function for "getAdjacentVertices".
PS: I am using VisualStudio 2017 with enabled c++17
#ifndef SL2_GRAPH_DFS_DEPTH_FIRST_SEARCH_HPP
#define SL2_GRAPH_DFS_DEPTH_FIRST_SEARCH_HPP
#pragma once
#include <vector>
#include <utility>
#include <bitset>
namespace sl2::graph::dfs
{
struct NonMemoizer
{
template <class VertexDescriptor>
bool operator [](VertexDescriptor&&) { return false; }
};
template <std::size_t Size>
class BitsetMemoizer
{
private:
std::bitset<Size> m_Check;
public:
template <class VertexDescriptor>
auto operator [](VertexDescriptor&& _v) { return m_Check[_v]; }
};
template <class VertexDescriptor, class GraphModel>
class DepthFirstSearch
{
private:
GraphModel m_GraphModel;
template <class Vertex, class Visitor, class Memoizer>
std::optional<VertexDescriptor> _searchIterative(Vertex&& _start, Visitor&& _visitor, Memoizer&& _memoizer)
{
std::vector<std::pair<VertexDescriptor, int/*depth*/>> m_Stack;
_memoizer[_start] = true;
m_Stack.emplace_back(std::forward<Vertex>(_start), 0);
while (!m_Stack.empty())
{
auto current = m_Stack.back();
m_Stack.pop_back();
if (_visitor(current.first, current.second))
return current.first;
auto curDepth = current.second + 1;
for (auto& v : m_GraphModel.getAdjacentVertices(current.first))
{
if (auto&& result = _memoizer[v]; !result)
{
result = true;
m_Stack.emplace_back(v, curDepth);
}
}
}
return {};
}
public:
DepthFirstSearch(GraphModel _graphModel) :
m_GraphModel(std::move(_graphModel))
{}
template <class Vertex, class Visitor, class Memoizer>
auto search(Vertex&& _start, Visitor&& _visitor, Memoizer&& _memoizer)
{
_searchIterative(std::forward<Vertex>(_start), std::forward<Visitor>(_visitor), std::forward<Memoizer>(_memoizer));
}
};
template <class VertexDescriptor, class GraphModel, class Visitor, class Memoizer = NonMemoizer>
auto search(VertexDescriptor&& _start, GraphModel&& _graphModel, Visitor&& _visitor, Memoizer&& _memoizer = Memoizer())
{
DepthFirstSearch<std::decay_t<VertexDescriptor>, GraphModel> dfs(std::forward<GraphModel>(_graphModel));
return dfs.search(std::forward<VertexDescriptor>(_start), std::forward<Visitor>(_visitor), std::forward<Memoizer>(_memoizer));
}
} // namespace sl2::graph::dfs
#endif // !SL2_GRAPH_DFS_DEPTH_FIRST_SEARCH_HPP