4
\$\begingroup\$

some words in forehand: Unfortunately this post is very long, thus I decided to put the whole and compilable code into an online compiler. The link is at the end of this post.

In the last few days I have been working on my new graph searcher implementation. I tried to create a similar interface like the std::search functions and implemented each algorithm as a separate searcher. At least that was the first idea. After I have implemented the first searcher (Breadth first search) I broke it down and implemented the base part as a GenericSearcher class with some template parameters.

The searcher objects

In the end four different make_... functions were created:

  • make_breadth_first_searcher
  • make_depth_first_searcher
  • make_dijkstra_searcher
  • make_astar_searcher

As already mentioned, the GenericSearcher-class is the core of this implementation. It has an operator() overload and must return its last visited vertex (as an optional).

template <class TVertexType, class TNodeData, class TNodeCreator, class TNodeCompare>
class GenericSearcher
{
public:
    using NodeDataType = TNodeData;
    using VertexType = TVertexType;
    using NodeType = Node<TVertexType, TNodeData>;

    explicit GenericSearcher(TNodeCreator _nodeCreator = TNodeCreator(), TNodeCompare _nodeComp = TNodeCompare()) :
        m_NodeCreator(std::move(_nodeCreator)),
        m_NodeComp(std::move(_nodeComp))
    {
    }

    template <class TNeighbourSearcher, class TOpenList, class TClosedList>
    std::optional<NodeType> operator ()(TNeighbourSearcher& _neighbourSearcher, TOpenList& _openList, TClosedList& _closedList)
    {
        if (std::empty(_openList))
            return std::nullopt;
        auto node = _openList.take_node(m_NodeComp);
        _closedList.insert(node, m_NodeComp);
        _neighbourSearcher(node,
            [&node, &_openList, &_closedList, &nodeComp = m_NodeComp, &nodeCreator = m_NodeCreator]
        (const auto& _vertex)
        {
            if (!_closedList.contains(_vertex))
            {
                _openList.insert({ _vertex, nodeCreator(node, _vertex) }, nodeComp);
            }
        }
        );
        return node;
    }

private:
    TNodeCreator m_NodeCreator;
    TNodeCompare m_NodeComp;
};

There are two derived types, which only simplify the template deductions and the construction of the specific searchers:

template <class TCostCalculator, class TVertexType, typename = std::enable_if_t<std::is_invocable_v<TCostCalculator, const TVertexType&, const TVertexType&>>>
using CostCalculatorResult = std::invoke_result_t<TCostCalculator, const TVertexType&, const TVertexType&>;

// generalization for breadth- and depth-first-searcher
template <class TVertexType, class TCostType, class TNodeCompare>
struct StaticCostSearcher :
    public GenericSearcher<TVertexType, BaseNodeData<TVertexType, TCostType>, IncrementalCostChildNodeCreator<TCostType>, TNodeCompare>
{
private:
    using super = GenericSearcher<TVertexType, BaseNodeData<TVertexType, TCostType>, IncrementalCostChildNodeCreator<TCostType>, TNodeCompare>;

public:
    StaticCostSearcher(TNodeCompare _nodeComp) :
        super({ { 1 }, { 0 } }, std::move(_nodeComp))
    {}
};

// generalization for dijkstra- and astar-searcher
template <class TVertexType, class TCostCalculator, class THeuristicCalculator, class TNodeCompare, typename TCostType = detail::CostCalculatorResult<TCostCalculator, TVertexType>>
struct CalculatedCostSearcher :
    public GenericSearcher<TVertexType, BaseNodeData<TVertexType, TCostType>, GenericNodeCreator<TCostCalculator, THeuristicCalculator>, TNodeCompare>
{
private:
    using super = GenericSearcher<TVertexType, BaseNodeData<TVertexType, TCostType>, GenericNodeCreator<TCostCalculator, THeuristicCalculator>, TNodeCompare>;

    static_assert(std::is_same_v<TCostType, detail::CostCalculatorResult<TCostCalculator, TVertexType>>,
        "You are not allowed to change the TCostType template parameter.");
    static_assert(std::is_same_v<detail::CostCalculatorResult<THeuristicCalculator, TVertexType>, detail::CostCalculatorResult<TCostCalculator, TVertexType>>,
        "TCostCalculator and THeuristicCalculator must return the same type.");

public:
    CalculatedCostSearcher(TCostCalculator _costCalculator, THeuristicCalculator _heuristicCalculator, TNodeCompare _nodeComp) :
        super({ std::move(_costCalculator), std::move(_heuristicCalculator) }, std::move(_nodeComp))
    {
    }
};

And here are the make functions:

template <class TVertexType, class TNodeCompare = std::less<>>
auto make_breadth_first_searcher(TNodeCompare _nodeComp = TNodeCompare())
{
    return detail::StaticCostSearcher<TVertexType, int, TNodeCompare>(std::move(_nodeComp));
}

template <class TVertexType, class TNodeCompare = std::greater<>>
auto make_depth_first_searcher(TNodeCompare _nodeComp = TNodeCompare())
{
    return detail::StaticCostSearcher<TVertexType, int, TNodeCompare>(std::move(_nodeComp));
}

template <class TVertexType, class TCostCalculator, class TNodeCompare = std::less<>>
auto make_dijkstra_searcher(TCostCalculator _costCalculator, TNodeCompare _nodeComp = TNodeCompare())
{
    using CostType = detail::CostCalculatorResult<TCostCalculator, TVertexType>;
    return detail::CalculatedCostSearcher<TVertexType, TCostCalculator, detail::ConstantCost<CostType>, TNodeCompare>(std::move(_costCalculator), { 0 }, std::move(_nodeComp));
}

template <class TVertexType, class TCostCalculator, class THeuristicCalculator, class TNodeCompare = std::less<>>
auto make_astar_searcher(TCostCalculator _costCalculator, THeuristicCalculator _heuristicCalculator, TNodeCompare _nodeComp = TNodeCompare())
{
    return detail::CalculatedCostSearcher<TVertexType, TCostCalculator, THeuristicCalculator, TNodeCompare>(std::move(_costCalculator), std::move(_heuristicCalculator), std::move(_nodeComp));
}

The algorithms:

namespace detail
{
    template <class TVertexType, class TClosedList>
    std::optional<std::vector<TVertexType>> _extract_path(const TVertexType& _vertex, const TClosedList& _closedList)
    {
        if (auto curNode = _closedList.find(_vertex))
        {
            std::vector<TVertexType> path{ _vertex };
            while (curNode && curNode->parent)
            {
                path.emplace_back(*curNode->parent);
                curNode = _closedList.find(*curNode->parent);
            }
            std::reverse(std::begin(path), std::end(path));
            return path;
        }
        return std::nullopt;
    }

    template <class TVertexType, class UnaryFunction, class TNeighbourSearcher, class TPathFinder, class TOpenList, class TClosedList>
    std::optional<TVertexType> _conditional_visit(const TVertexType& _from, UnaryFunction&& _func, TNeighbourSearcher& _neighbourSearcher, TPathFinder& _pathFinder, TOpenList& _openList, TClosedList& _closedList)
    {
        using NodeData = typename TPathFinder::NodeDataType;
        assert(std::empty(_openList) && std::empty(_closedList));
        _openList.insert({ _from, NodeData() }, std::less<>()); // because the openList will be empty, we can insert a default constructed node and pass a dummy compare function
        while (auto current = _pathFinder(_neighbourSearcher, _openList, _closedList))
        {
            if (_func(*current))
                return current->vertex;
        }
        return std::nullopt;
    }

    template <class TVertexType, class TCallable, typename = std::enable_if_t<std::is_invocable_r_v<bool, TCallable, const TVertexType&>>>
    bool _reached_destination(const TVertexType& _current, TCallable&& _func)
    {
        return _func(_current);
    }

    template <class TVertexType>
    bool _reached_destination(const TVertexType& _current, const TVertexType& _destination)
    {
        return _current == _destination;
    }
} // namespace detail

template <class TVertexType, class UnaryFunction, class TNeighbourSearcher, class TPathFinder, class TOpenList = DefaultNodeMap<TPathFinder>, class TClosedList = DefaultNodeMap<TPathFinder>>
void visit(const TVertexType& _from, UnaryFunction&& _func, TNeighbourSearcher&& _neighbourSearcher, TPathFinder&& _pathFinder,
    TOpenList _openList = TOpenList(), TClosedList _closedList = TClosedList())
{
    auto condFunc = [&_func](const auto& _node)
    {
        _func(_node);
        return false;
    };
    detail::_conditional_visit(_from, condFunc, _neighbourSearcher, _pathFinder, _openList, _closedList);
}

template <class TVertexType, class TDestination, class TNeighbourSearcher, class TPathFinder, class TOpenList = DefaultNodeMap<TPathFinder>, class TClosedList = DefaultNodeMap<TPathFinder>>
std::optional<std::vector<TVertexType>> find_path(const TVertexType& _from, TDestination&& _destination, TNeighbourSearcher&& _neighbourSearcher, TPathFinder&& _pathFinder,
    TOpenList _openList = TOpenList(), TClosedList _closedList = TClosedList())
{
    if (auto lastNode = detail::_conditional_visit(_from, [&_destination](const auto& _node) { return detail::_reached_destination(_node.vertex, _destination); }, _neighbourSearcher, _pathFinder, _openList, _closedList))
    {
        return detail::_extract_path(*lastNode, _closedList);
    }
    return std::nullopt;
}

The algorithms are the next part. There are currently two of them, but I can't imagine any other. At least they cover my needs very well. The visit function visits every reachable node; in which sequence depends on the passed searcher. The find_path functions returns the path from starting point to the given destination - if there is any. My intention was to distinguish between start == destination and not reachable. Therefore I use again an std::optional. As a little trick, I added the possibility to pass a function object as destination.

The node objects

namespace graph
{
    template <class TVertexType, class CostType>
    struct BaseNodeData
    {
        std::optional<TVertexType> parent;
        CostType cost;

        friend bool operator <(const BaseNodeData& _lhs, const BaseNodeData& _rhs)
        {
            return _lhs.cost < _rhs.cost;
        }

        friend bool operator >(const BaseNodeData& _lhs, const BaseNodeData& _rhs)
        {
            return _lhs.cost > _rhs.cost;
        }
    };

    template <class TVertexType, class CostType>
    struct HeuristicNodeData
    {
        std::optional<TVertexType> parent;
        CostType cost;
        CostType heuristic;

        int combined_cost() const
        {
            return cost + heuristic;
        }

        friend bool operator <(const HeuristicNodeData& _lhs, const HeuristicNodeData& _rhs)
        {
            return _lhs.combined_cost() < _rhs.combined_cost();
        }

        friend bool operator >(const HeuristicNodeData& _lhs, const HeuristicNodeData& _rhs)
        {
            return _lhs.combined_cost() > _rhs.combined_cost();
        }
    };

    template <class TVertexType, class TNodeData>
    struct Node
    {
        TVertexType vertex;
        TNodeData data;
    };
} // namespace graph

The Node struct is a combination of the location (the vertex) and the current data (cost, parent, ...). I like to call those properties by name, that's the reason why I avoided a std::tuple like structure. Perhaps that's a little bit old-school, but in my opinion it makes the code much easier to understand.

There are two different NodeData types:

  • BaseNodeData
  • HeuristicNodeData

I know, those names are horrible, perhaps anybody has better ideas? Three of the currently implemented searcher make use of the BaseNodeData; only the AStar uses the HeuristicNodeData objects.

NodeContainer

As you might know, we have to store the visited nodes in a container like structure. To offer the most flexibility and make the algorithm easier to run by default, I decided to use a std::unordered_map object in my abstraction. If the user knows it better, he can simply pass an other object (with the same interface) and can do some pretty optimizations. An example for 2d maps will be attached to this post.

template <class TMap>
class NodeMap
{
public:
    using VertexType = typename TMap::key_type;
    using NodeDataType = typename TMap::mapped_type;
    using NodeType = Node<VertexType, NodeDataType>;

    explicit NodeMap(TMap _map = TMap()) :
        m_Nodes(std::move(_map))
    {
    }

    template <class TNodeCompare>
    void insert(NodeType _node, TNodeCompare&& _nodeComp)
    {
        if (auto result = m_Nodes.insert({ _node.vertex, _node.data });
            !result.second && _nodeComp(_node.data, result.first->second))
        {
            result.first->second = _node.data;
        }
    }

    template <class TNodeCompare>
    NodeType take_node(TNodeCompare&& _nodeComp)
    {
        auto itr = std::min_element(std::begin(m_Nodes), std::end(m_Nodes),
            [&_nodeComp](const auto& _lhs, const auto& _rhs) { return _nodeComp(_lhs.second, _rhs.second); }
        );
        assert(itr != std::end(m_Nodes));
        auto node = std::move(*itr);
        m_Nodes.erase(itr);
        return { node.first, node.second };
    }

    const NodeDataType* find(const VertexType& _key) const
    {
        auto itr = m_Nodes.find(_key);
        return std::end(m_Nodes) == itr ? nullptr : &itr->second;
    }

    bool contains(const VertexType& _key) const
    {
        return m_Nodes.count(_key) != 0;    // ToDo: use std::unordered_map::contains in C++20
    }

    bool empty() const
    {
        return std::empty(m_Nodes);
    }

private:
    TMap m_Nodes;
};

template <class TPathFinder>
using DefaultNodeMap = NodeMap<std::unordered_map<typename TPathFinder::VertexType, typename TPathFinder::NodeDataType>>;

Both algorithms use two different container, which need different member functions. The NodeMap function above combines the open- and closed-list abstraction into a single one, but you'll be able to pass two different containers-classes.

necessary user definitions

That's one of the most brain melting points I encountered. If you try to generalize such algorithms which highly depend on user implemented data structures, there is no real work you can do to make the algorithm run instant. The user has to feed the interfaces but I tried to make it as simple as possible. Every searcher needs a NeighbourFinder which has to call a callback for every neighbour of the passed node. Here is a short example:

std::vector<int> nodes{ 1, 2, 3, 4, 5, 6, 7 };
std::vector<std::pair<int, int>> connections
{
    { 1, 2 },
    { 2, 3 },
    { 2, 4 },
    { 4, 5 },
    { 3, 6 },
    { 3, 7 },
    { 6, 7 },
    { 7, 1 }
};

auto neighbourFinder = [&connections](const auto& _node, auto&& _callback)
{
    auto next = [itr = std::begin(connections), end = std::end(connections)](const auto& _vertex) mutable -> std::optional<int>
    {
        itr = std::find_if(itr, end, [&_vertex](const auto& _pair) { return _pair.first == _vertex || _pair.second == _vertex; });
        if (itr != end)
        {
            auto result = itr->first == _vertex ? itr->second : itr->first;
            ++itr;
            return result;
        }
        return std::nullopt;
    };

    while (auto neigh = next(_node.vertex))
        _callback(*neigh);
};

Well, the neighbourFinder lambda simply extracts all remote nodes for the passed node. It is not necessary to keep track of the already visited nodes; that's the task of the NodeContainer(s). I use the callback here to bypass the need of returning a std::vector. That might be a premature optimization, but I think it's a common style.

And that's it for the two easier searcher. Here is a short example, how to print every visited node:

auto printNode = [](const auto& _nodeInfo) { std::cout << "vertex: " << _nodeInfo.vertex << " parent_vertex: " << _nodeInfo.data.parent.value_or(-1) << " cost: " << _nodeInfo.data.cost << std::endl; };
std::cout << "Breadth first visit: " << std::endl;
graph::visit(2, printNode, neighbourFinder, graph::make_breadth_first_searcher<int>());
std::cout << std::endl << "Depth first visit: " << std::endl;
graph::visit(2, printNode, neighbourFinder, graph::make_depth_first_searcher<int>());

for the dijkstra it's necessary to define a costCalculator object:

// this is only a little helper function which prints the found path; don't mind to much about it.
template <class TVertexType, class TDestination, class TNeighbourSearcher, class TPathFinder, class TOpenList = graph::DefaultNodeMap<std::decay_t<TPathFinder>>,
    class TClosedList = graph::DefaultNodeMap<std::decay_t<TPathFinder>>>
void search_path_and_print(TVertexType _from, TDestination&& _to, TNeighbourSearcher&& _neighbourSearcher, TPathFinder&& _pathFinder, TOpenList _openList = TOpenList(), TClosedList _closedList = TClosedList())
{
    if (auto path = graph::find_path(_from, std::forward<TDestination>(_to), std::forward<TNeighbourSearcher>(_neighbourSearcher), std::forward<TPathFinder>(_pathFinder), std::move(_openList), std::move(_closedList)))
    {
        for (const auto& node : *path)
        {
            std::cout << node << std::endl;
        }
    }
}


std::cout << std::endl << "Dijkstra search: " << std::endl;
search_path_and_print(1, 6, neighbourFinder, graph::make_dijkstra_searcher<int>([](const auto& _from, const auto& _to) { return _to; }));

Yes, we simply return the value of the next node as cost. As I said, it's an example.

And last but not least, we need a heuristicCalculator for the A* searcher.

auto constantCost = [](const auto& _from, const auto& _to) { return 1; };
    search_path_and_print(1, 6, neighbourFinder, graph::make_astar_searcher<int>(constantCost, constantCost));

That simply returns 1 for both; the cost calculation (first parameter) and the heuristic calculation (second).

Final Words:

Thank you for reading through this wall of text, I would be happy if you have any suggestions and/or improvements for me. Feel free to comment on the coding style and the design itself; everything will be helpful for me ;)

If anyone is interested, I push the whole code plus a little 2d example (inclusive a more optimized NodeContainer class) here: https://wandbox.org/permlink/ldhD95ItWSkoXI8T

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.