templated Depth-FirstSearch algorithm

Question

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

Answer 1

Why take ownership of the graph?

Since this is an operation on a graph, it seems to me it would be better suited to operating on a const reference of a graph, rather than taking ownership of the graph or a copy of it.

Why is this a class?

I see no reason why this couldn't be a free-floating function.

Memoizer does not memoize

Your memoizer does not perform memoization, it's a visitation cache. You should name that type appropriately.

Memoizer is not optional

Since you are using a stack for the operations, you could very easily end up in an infinite loop when using the NonMemoizer. This wouldn't be an issue when traversing a tree, but a visitation cache is useless when visiting a tree in the first place sooo...

Memoizer lifetime

I'm having trouble wrapping my head around the setup for the memoizer. You are accepting a memoizer instance as parameter, which would imply that you want to be able to reuse the memoizer in subsequent calls. However the data inside the memoizer only makes sense for a single given start->end pair, which you wouldn't ever lookup twice in a row since you have the result after the first call.

What I'm getting at is that the memoizer feels like it should be a local variable inside _searchIterative(), not something that is passed to it.

Memoizer interface enforcement.

What if the memoizer types returned bool instances instead of references? Your code would still compile, but not function as expected.

Duck typing is great for this type of dependency injection, but this is walking a very fine line, and you would really need some form of compile-time sanity check.

Too trigger happy on forwarding

Forwarding is used when you don't know how you'll be using the objects. However, you do, so your interface should reflect that in order to help the compiler.

• If you will only read from the object, grab by const reference
• If you will maintain an instance of the object, grab by value
• etc...

You are already doing the right thing in DepthFirstSearch's constructor, so I don't know why you were so trigger happy elsewhere.

template <class VertexDescriptor, class GraphModel, class Visitor, class 
Memoizer = NonMemoizer>
auto search(VertexDescriptor&& _start, GraphModel&& _graphModel, Visitor&& _visitor, Memoizer&& _memoizer = Memoizer())

//should be

template <class VertexDescriptor, class GraphModel, class Visitor, class 
Memoizer = NonMemoizer>
auto search(VertexDescriptor const& _start, GraphModel _graphModel, Visitor const& _visitor, Memoizer _memoizer = Memoizer())

Minor nitpick:

• I prefer using std::nullopt instead of {} for returning empty optionals, it's clearer at the call site.