Pathfinding library in C++ with fluent API

Question

Introduction

I have this C++ pathfinding library. My primary requirement is that a client programmer may couple his/her own graph representation and the library will work with that representation.

The only API a client graph node type is to implement is begin() and end() which should return a sequence of neighbors in case of undirected graphs, or a sequence of child nodes in case of directed graphs.

What comes to weight function, my library expects only that the weight type is default-constructible (which must represent the "zero-weight") and a operator>. In my 2nd demo, the weights are \$2 \times 2\$-matrices, for example.

Critique request

Please tell me anything that comes to mind. However, I am most interested in hearing the comments regarding

• const (in)correctness,
• efficiency,
• adherence to C++ programming idioms.

Code

pathfinding.hpp

#ifndef NET_CODERODDE_PATHFINDING_HPP
#define NET_CODERODDE_PATHFINDING_HPP

#include "a_star.hpp"
#include "dijkstra.hpp"
#include "heuristic_function.hpp"
#include "weight_function.hpp"
#include "weighted_path.hpp"

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    class heuristic_function_selector {
    public:
        heuristic_function_selector(
                                Node& source,
                                Node& target,
                                weight_function<Node, Weight>* weight_function)
        :
        m_source{source},
        m_target{target},
        m_weight_function{weight_function} {}

        weighted_path<Node, Weight> without_heuristic_function() {
            return search(m_source, m_target, *m_weight_function);
        }

        weighted_path<Node, Weight>
        with_heuristic_function(
                        heuristic_function<Node, Weight>* heuristic_function) {
            return search(m_source,
                          m_target,
                          *m_weight_function,
                          *heuristic_function);
        }

    private:
        Node m_source;
        Node m_target;
        weight_function<Node, Weight>* m_weight_function;
    };

    template<typename Node, typename Weight>
    class weight_function_selector {
    public:
        weight_function_selector(Node& source, Node& target) :
        m_source{source},
        m_target{target} {}

        heuristic_function_selector<Node, Weight>
        with_weights(weight_function<Node, Weight>* wf) {
            return heuristic_function_selector<Node, Weight>(m_source,
                                                             m_target,
                                                             wf);
        }

    private:
        Node m_source;
        Node m_target;
    };

    template<typename Node, typename Weight>
    class target_node_selector {
    public:
        target_node_selector(Node source) : m_source{source} {}
        weight_function_selector<Node, Weight> to(Node& target) {
            return weight_function_selector<Node, Weight>(m_source, target);
        }

    private:
        Node m_source;
    };

    template<typename Node, typename Weight>
    class source_node_selector {
    public:
        target_node_selector<Node, Weight> from(Node& source) {
            return target_node_selector<Node, Weight>{source};
        }
    };

    template<typename Node, typename Weight>
    source_node_selector<Node, Weight> find_shortest_path() {
        return source_node_selector<Node, Weight>{};
    }

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_HPP

a_star.hpp

#ifndef NET_CODERODDE_PATHFINDING_A_STAR_HPP
#define NET_CODERODDE_PATHFINDING_A_STAR_HPP

#include "child_node_iterator.hpp"
#include "heuristic_function.hpp"
#include "path_not_found_exception.hpp"
#include "weighted_path.hpp"
#include "weight_function.hpp"
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    struct node_holder {
        Node* m_node;
        Weight m_f;

        node_holder(Node* node, Weight f) : m_node{node}, m_f{f} {}
    };

    template<typename Node, typename Weight, typename Cmp>
    void remove_and_delete_all_node_holders(
                std::priority_queue<node_holder<Node, Weight>*,
                                            std::vector<node_holder<Node, Weight>*>,
                                            Cmp>& open) {
        while (!open.empty()) {
            node_holder<Node, Weight>* current_node_holder = open.top();
            open.pop();
            delete current_node_holder;
        }
    }

    template<typename Node, typename Weight>
    weighted_path<Node, Weight>
    traceback_path(Node& target,
                   std::unordered_map<Node*, Node*>& parents,
                   weight_function<Node, Weight>& w) {
        std::vector<Node*> path;
        Node* current_node = &target;

        while (current_node) {
            path.push_back(current_node);
            current_node = parents[current_node];
        }

        std::reverse(path.begin(), path.end());

        Weight total_weight {};

        for (size_t i = 0; i < path.size() - 1; ++i) {
            total_weight += w(*path[i], *path[i + 1]);
        }

        return weighted_path<Node, Weight>(path, total_weight);
    }

    template<typename Node, typename Weight>
    weighted_path<Node, Weight> search(Node& source,
                                       Node& target,
                                       weight_function<Node, Weight>& w,
                                       heuristic_function<Node, Weight>& h) {

        auto cmp = [](node_holder<Node, Weight>* nh1,
                      node_holder<Node, Weight>* nh2) {
            return nh1->m_f > nh2->m_f;
        };

        std::priority_queue<node_holder<Node, Weight>*,
                            std::vector<node_holder<Node, Weight>*>,
                            decltype(cmp)> open(cmp);

        std::unordered_set<Node*> closed;
        std::unordered_map<Node*, Node*> parents;
        std::unordered_map<Node*, Weight> distances;

        open.push(new node_holder<Node, Weight>(&source, Weight{}));
        parents[&source] = nullptr;
        distances[&source] = Weight{};

        while (!open.empty()) {
            Node* current_node = open.top()->m_node;
            open.pop();

            if (*current_node == target) {
                remove_and_delete_all_node_holders(open);
                return traceback_path(*current_node, parents, w);
            }

            if (closed.find(current_node) != closed.end()) {
                continue;
            }

            closed.insert(current_node);

            for (Node& child_node : *current_node) {
                if (closed.find(&child_node) != closed.end()) {
                    continue;
                }

                Weight tentative_distance = distances[current_node] +
                w(*current_node, child_node);

                if (distances.find(&child_node) == distances.end()
                    || distances[&child_node] > tentative_distance) {
                    open.push(new node_holder<Node, Weight>(
                                        &child_node,
                                        tentative_distance + h(child_node)));
                    distances[&child_node] = tentative_distance;
                    parents[&child_node] = current_node;
                }
            }
        }

        remove_and_delete_all_node_holders(open);
        throw path_not_found_exception<Node>(source, target);
    }
} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_A_STAR_HPP

dijkstra.hpp

#ifndef NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP
#define NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP

#include "a_star.hpp"
#include "heuristic_function.hpp"

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename DistanceType>
    class zero_heuristic :
    public virtual heuristic_function<Node, DistanceType> {

    public:
        DistanceType operator()(const Node& target) const {
            DistanceType zero{};
            return zero;
        }
    };

    template<typename Node, typename Weight>
    weighted_path<Node, Weight> search(Node& source,
                                       Node& target,
                                       weight_function<Node, Weight>& w) {
        zero_heuristic<Node, Weight> h;
        return search(source, target, w, h);
    }

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP

child_node_iterator.hpp

#ifndef NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP
#define NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node>
    class child_node_iterator {

    public:
        virtual child_node_iterator<Node>& operator++() = 0;
        virtual Node& operator*()                       = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // End of NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP.

heuristic_function.hpp

#ifndef NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP
#define NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename DistanceType>
    class heuristic_function {

    public:
        virtual DistanceType operator()(const Node& target) const = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // End of NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP.

path_not_found_exception.hpp

#ifndef NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP
#define NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

#include <sstream>
#include <stdexcept>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node>
    class path_not_found_exception : public virtual std::logic_error {
    public:
        path_not_found_exception(const Node& source,
                                 const Node& target)
        :
        std::logic_error{""},
        m_source{&source},
        m_target{&target}
        {}

        const char* what() {
            std::stringstream ss;
            ss << "A path from source {" << *m_source << "} to target {"
               << *m_target << "} not found.";
            return ss.str().c_str();
        }

    private:
        const Node* m_source;
        const Node* m_target;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

weight_function.hpp

#ifndef NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP
#define NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename WeightType>
    class weight_function {

    public:
        virtual WeightType operator()(const Node& a, const Node& b) = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP

weighted_path.hpp

#ifndef NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP
#define NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP

#include <iostream>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    class weighted_path {
    public:
        weighted_path(std::vector<Node*> path_vector, Weight total_weight)
        :
        m_path_vector{path_vector},
        m_total_weight{total_weight}
        {}

        Node& node_at(size_t index) {
            return *m_path_vector->at(index);
        }

        Weight total_weight() const {
            return m_total_weight;
        }

    private:
        std::vector<Node*> m_path_vector;
        Weight             m_total_weight;

        friend std::ostream& operator<<(std::ostream& out, weighted_path& path) {
            std::string separator{};
            out << "[";

            for (Node* node : path.m_path_vector) {
                out << separator;
                separator = ", ";
                out << *node;
            }

            return out << "]";
        }
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP

main.cpp

#include "pathfinding.hpp"
#include "child_node_iterator.hpp"
#include "path_not_found_exception.hpp"

#include <cstdlib>
#include <functional>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>

using net::coderodde::pathfinding::child_node_iterator;
using net::coderodde::pathfinding::heuristic_function;
using net::coderodde::pathfinding::weight_function;
using net::coderodde::pathfinding::weighted_path;
using net::coderodde::pathfinding::find_shortest_path;
using net::coderodde::pathfinding::path_not_found_exception;

// This is just a sample graph node type. The only requirement for coupling it
// with the search algorithms is 'bool operator==(const grid_node& other) const'
// and 'begin()' + 'end()' for iterating over the child nodes.
class grid_node {
private:

    class grid_node_neighbor_iterator : public child_node_iterator<grid_node> {
    private:
        std::vector<grid_node*>* m_neighbor_vector;
        std::size_t m_index;

    public:
        grid_node_neighbor_iterator(std::vector<grid_node*>* neighbor_vector,
                                    std::size_t index)
        :
        m_neighbor_vector{neighbor_vector},
        m_index{index} {}

        ~grid_node_neighbor_iterator() {
            delete m_neighbor_vector;
        }

        grid_node_neighbor_iterator& operator++() {
            ++m_index;
            return *this;
        }

        bool operator==(grid_node_neighbor_iterator& other) const {
            return m_index == other.m_index;
        }

        bool operator!=(grid_node_neighbor_iterator& other) const {
            return m_index != other.m_index;
        }

        grid_node& operator*() {
            return *m_neighbor_vector->at(m_index);
        }
    };

public:

    grid_node(int x, int y, bool traversable);

    void set_top_neighbor    (grid_node& neighbor);
    void set_bottom_neighbor (grid_node& neighbor);
    void set_left_neighbor   (grid_node& neighbor);
    void set_right_neighbor  (grid_node& neighbor);

    bool operator==(const grid_node& other) {
        return m_x == other.m_x && m_y == other.m_y;
    }

    grid_node_neighbor_iterator begin() {
        std::vector<grid_node*>* neighbor_vector =
        new std::vector<grid_node*>;

        if (m_top_neighbor && m_top_neighbor->m_traversable) {
            neighbor_vector->push_back(m_top_neighbor);
        }

        if (m_bottom_neighbor && m_bottom_neighbor->m_traversable) {
            neighbor_vector->push_back(m_bottom_neighbor);
        }

        if (m_left_neighbor && m_left_neighbor->m_traversable) {
            neighbor_vector->push_back(m_left_neighbor);
        }

        if (m_right_neighbor && m_right_neighbor->m_traversable) {
            neighbor_vector->push_back(m_right_neighbor);
        }

        return grid_node_neighbor_iterator(neighbor_vector, 0);
    }

    grid_node_neighbor_iterator end() {
        std::size_t neighbor_count = 0;

        if (m_top_neighbor && m_top_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_bottom_neighbor && m_bottom_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_left_neighbor && m_left_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_right_neighbor && m_right_neighbor->m_traversable) {
            neighbor_count++;
        }

        return grid_node_neighbor_iterator(nullptr, neighbor_count);
    }

    // Heuristic function must know the coordinates:
    friend class grid_node_heuristic_function;

    // For printing to, say, cout:
    friend std::ostream& operator<<(std::ostream& out, const grid_node& gn);

    // std::hash and std::equal_to so that the internal unordered_* data
    // structures may work with grid nodes via pointers:
    friend class std::hash<grid_node*>;
    friend class std::equal_to<grid_node*>;

private:

    int m_x;
    int m_y;

    bool   m_traversable;

    grid_node* m_top_neighbor;
    grid_node* m_bottom_neighbor;
    grid_node* m_left_neighbor;
    grid_node* m_right_neighbor;
};

grid_node::grid_node(int x, int y, bool traversable)
:
m_x{x},
m_y{y},
m_traversable{traversable}
{
    m_top_neighbor    = nullptr;
    m_bottom_neighbor = nullptr;
    m_left_neighbor   = nullptr;
    m_right_neighbor  = nullptr;
}

void grid_node::set_top_neighbor(grid_node& neighbor)
{
    m_top_neighbor = &neighbor;
}

void grid_node::set_bottom_neighbor(grid_node& neighbor)
{
    m_bottom_neighbor = &neighbor;
}

void grid_node::set_left_neighbor(grid_node& neighbor)
{
    m_left_neighbor = &neighbor;
}

void grid_node::set_right_neighbor(grid_node& neighbor)
{
    m_right_neighbor = &neighbor;
}

std::ostream& operator<<(std::ostream& out, const grid_node& gn)
{
    out << "{x=" << gn.m_x << ", y=" << gn.m_y << "}";
    return out;
}

// This class will be used as an EDGE WEIGHT:
class matrix {
public:
    matrix(int a1, int a2, int b1, int b2)
    :
    m_a1{a1},
    m_a2{a2},
    m_b1{b1},
    m_b2{b2}
    {}

    matrix() : matrix{0, 0, 0, 0} {}

    int determinant() const {
        return m_a1 * m_b2 - m_a2 * m_b1;
    }

    matrix operator+(const matrix& other) {
        return matrix{m_a1 + other.m_a1,
                      m_a2 + other.m_a2,
                      m_b1 + other.m_b1,
                      m_b2 + other.m_b2};
    }

    matrix& operator+=(const matrix& other) {
        m_a1 += other.m_a1;
        m_a2 += other.m_a2;
        m_b1 += other.m_b1;
        m_b2 += other.m_b2;
        return *this;
    }

    bool operator>(const matrix& other) {
        return abs(determinant()) > abs(other.determinant());
    }

    friend std::ostream& operator<<(std::ostream& out, const matrix& m) {
        return out << "{{" << m.m_a1 << ", " << m.m_a2 << "}, {"
                   << m.m_b1 << ", " << m.m_b2 << "}}";
    }

    friend class grid_node_heuristic_function;
    friend class std::hash<grid_node*>;
    friend class std::equal_to<grid_node*>;

private:
    int m_a1;
    int m_a2;
    int m_b1;
    int m_b2;
};

// A graph node type whose edge weights are matrix. This is just a demonstration
// of flexibility of the library.
class matrix_node {
private:

    class matrix_node_child_iterator :
    public child_node_iterator<matrix_node> {

    private:
        std::size_t m_index;
        std::vector<matrix_node*>* m_matrix_node_pointer_vector;

    public:
        matrix_node_child_iterator(
                        std::vector<matrix_node*>& matrix_node_pointer_vector,
                        std::size_t index)
        : m_matrix_node_pointer_vector{&matrix_node_pointer_vector},
          m_index{index} {}

        matrix_node_child_iterator& operator++() {
            m_index++;
            return *this;
        }

        bool operator!=(const matrix_node_child_iterator& other) {
            return m_index != other.m_index;
        }

        matrix_node& operator*() {
            return *m_matrix_node_pointer_vector->at(m_index);
        }
    };

public:

    matrix_node(size_t id) : m_id{id} {}

    bool operator==(const matrix_node& other) const {
        return m_id == other.m_id;
    }

    void add_neighbor(matrix_node& neighbor) {
        m_neighbors.push_back(&neighbor);
    }

    matrix_node_child_iterator begin() {
        return matrix_node_child_iterator(m_neighbors, 0);
    }

    matrix_node_child_iterator end() {
        return matrix_node_child_iterator(m_neighbors, m_neighbors.size());
    }

private:

    friend class std::hash<matrix_node>;
    friend class std::equal_to<matrix_node>;
    friend std::ostream& operator<<(std::ostream& out, const matrix_node& n);

    std::vector<matrix_node*> m_neighbors;
    size_t m_id;
};

std::ostream& operator<<(std::ostream& out, const matrix_node& node) {
    return out << "{id=" << node.m_id << "}";
}

namespace std {
    template<>
    struct hash<matrix_node> {
        std::size_t operator()(const matrix_node& node) const {
            return node.m_id;
        }
    };

    template<>
    struct equal_to<matrix_node> {
        bool operator()(const matrix_node& a, const matrix_node& b) const {
            return a.m_id == b.m_id;
        }
    };
}

class grid_node_weight_function :
public virtual weight_function<grid_node, int>
{
public:
    int operator()(const grid_node& a, const grid_node& b) {
        return 1;
    }
};

class grid_node_heuristic_function :
public virtual heuristic_function<grid_node, int>
{
public:
    grid_node_heuristic_function(const grid_node source)
    :
    m_source{source}
    {}

    int operator()(const grid_node& target) const {
        // Manhattan-distance:
        return abs(m_source.m_x - target.m_x) + abs(m_source.m_y - target.m_y);
    }

private:
    grid_node m_source;
};

class matrix_node_weight_function :
public virtual weight_function<matrix_node, matrix>
{
public:
    std::unordered_map<matrix_node, matrix>&
    operator[](const matrix_node& node) {
        return m_map[node];
    }

    matrix operator()(const matrix_node& tail, const matrix_node& head) override {
        return m_map[tail][head];
    }

private:
    std::unordered_map<matrix_node,
    std::unordered_map<matrix_node, matrix>> m_map;
};

namespace std {

    template<>
    struct hash<grid_node*> {
        std::size_t operator()(const grid_node* gn) const {
            return gn->m_x ^ gn->m_y;
        }
    };

    template<>
    struct equal_to<grid_node*> {
        bool operator()(const grid_node* a, const grid_node* b) const {
            return a->m_x == b->m_x && a->m_y == b->m_y;
        }
    };
}

int main(int argc, const char * argv[]) {
    std::vector<std::vector<int>> maze = {
        { 0, 0, 0, 1, 0, 0 },
        { 0, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0 },
        { 1, 1, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0 },
        { 0, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0 },
    };

    std::vector<std::vector<grid_node>> grid_node_maze;

    for (size_t y = 0; y < maze.size(); ++y) {
        std::vector<grid_node> grid_node_maze_row;

        for (size_t x = 0; x < maze[y].size(); ++x) {
            grid_node_maze_row.push_back(grid_node(x, y, maze[y][x] != 1));
        }

        grid_node_maze.push_back(grid_node_maze_row);
    }

    for (size_t y = 0; y < grid_node_maze.size(); ++y) {
        for (int x = 0; x < grid_node_maze[0].size() - 1; ++x) {
            grid_node_maze[y][x].set_right_neighbor(grid_node_maze[y][x + 1]);
        }

        for (int x = 1; x < grid_node_maze[0].size(); ++x) {
            grid_node_maze[y][x].set_left_neighbor(grid_node_maze[y][x - 1]);
        }
    }

    for (size_t x = 0; x < grid_node_maze[0].size(); ++x) {
        for (int y = 0; y < grid_node_maze.size() - 1; ++y) {
            grid_node_maze[y][x].set_bottom_neighbor(grid_node_maze[y + 1][x]);
        }

        for (int y = 1; y < grid_node_maze.size(); ++y) {
            grid_node_maze[y][x].set_top_neighbor(grid_node_maze[y - 1][x]);
        }
    }

    grid_node_weight_function grid_node_wf;
    grid_node_heuristic_function grid_node_hf(grid_node_maze[6][5]);

    try {
        auto path = find_shortest_path<grid_node, int>()
                    .from(grid_node_maze[0][0])
                    .to(grid_node_maze[6][5])
                    .with_weights(&grid_node_wf)
                    .with_heuristic_function(&grid_node_hf);
        std::cout << path << "\n";
        std::cout << "Final maze distance: " << path.total_weight() << "\n";
    } catch (path_not_found_exception<grid_node>& ex) {
        std::cerr << ex.what() << "\n";
    }

    ////////// MATRIX DEMO ///////////
    matrix_node a{1};
    matrix_node b{2};
    matrix_node c{3};
    matrix_node d{4};
    matrix_node e{5};

    matrix_node_weight_function matrix_wf;

    matrix mab{1,   2,  3, 4};
    matrix mac{1,  -2, -3, 4};
    matrix mbc{2,   2,  1, 3};
    matrix mcd{5,  10,  7, 8};
    matrix mce{4,   0,  1, 3};
    matrix mde{1, -10,  9, 2};

    matrix_wf[a][b] = mab; a.add_neighbor(b);
    matrix_wf[a][c] = mac; a.add_neighbor(c);
    matrix_wf[b][c] = mbc; b.add_neighbor(c);
    matrix_wf[c][d] = mcd; c.add_neighbor(d);
    matrix_wf[c][e] = mce; c.add_neighbor(e);
    matrix_wf[d][e] = mde; d.add_neighbor(e);

    try {
        weighted_path<matrix_node, matrix> path
        = find_shortest_path<matrix_node, matrix>()
            .from(a)
            .to(e)
            .with_weights(&matrix_wf)
            .without_heuristic_function();

        std::cout << path << "\n";
        std::cout << "Final matrix length: " << path.total_weight() << "\n";
    } catch (path_not_found_exception<matrix_node>& ex) {
        std::cerr << ex.what() << "\n";
    }
}

Answer 1

1.) Issues in path_not_found_exception

1.1) You require nodes to be output streamable in path_not_found_exception::what()

You did not state this requirement in your description. Visualising nodes is not your concern here.

1.2) Don't store naked pointers to Node objects, they might dangle

You only store a pointer to the nodes but you do not control at what time this exception is being caught. These pointers might dangle at the time this exception will be accessed. Since you do not require Nodes to be copyable (it might be generally too expensive anyway) you have no chance to store a node here.

#ifndef NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP
#define NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

#include <stdexcept>

namespace net {
namespace coderodde {
namespace pathfinding {

    struct path_not_found_exception: std::logic_error {
        path_not_found_exception()
          : std::logic_error {
              "There exist no path between the source and target nodes"
            }
        {}
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

2.) Don't use abstract base classes for function objects

2.1) Use std::function<Weight(Node)> instead of abstract base class weight_function<Weight, Node>

2.2) Use std::function<Distance(Node)> instead of abstract base class heuristic_function<Distance, Node>

[ Note: Or just take these as template parameters only. ]

The rationale is that the way you do it is intrusive and a client has to define adapter classes to use your library. Since your abstract base classes only require virtual operator()(...) you are better of with std::function<Ret(Args...)> which is just such a wrapper around any function-like type.

Defining abstract base classes here might also introduce a lot of subtle misuses and errors. For example: you do not define a virtual destructor! Since you do not store your function objects polymorphically it seems to be okay in this case (and might leak otherwise), but on the other hand you take pointers to such objects without nullptr-checks... and your selector classes invite users to misuse them by letting the pointers dangle.

I have no experience with fluent interfaces but I do not like this particular example. You gain pretty much nothing but a code bloat -- one selector-class for each parameter plus it seems to be easy to misuse. Maybe one can generate selector classes and avoid code repetition with Herb Sutter's announced metaclasses. IDK.

3.) Don't use an abstract base class to require a ForwardIterator

Just rely on substitution errors or constrain your Node type with Concepts / std::enable_if + std::void_t. This adds again unnecessary coupling for the client to your library.

4.) Issues in A*-search()

4.1) search(from, to) is not a good name.

I suggest something that indicate what you search for (an element? a path!) Suggestions:

• a_star
• astar_search (thats how boost calls it)
• find_path
• shortest_path
• min_path
• find_min_path
• ...

If I read search I do expect to search for a node. But take this as a weak complain only. Naming is hard.

4.2) Nodes should be passed by const-reference or Node&& (if you really need to modify Nodes when accessing its children)

The way you declare your search method makes it impossible to search in read-only graphs. I suggest something like

template <typename Node, typename WeightFn, typename DistFn>
weighted_path<Node, std::invoke_result_t<WeightFn, Node>> // pre C++17: std::result_of_t<WeightFn(Node)>
search(const Node&, const Node&, WeightFn, DistFn);

4.3) Don't use new and delete but std::unique_ptr if you must... (you have memory leaks)

[ Note: You do not have to use any heap allocation in your case. ]

Because of improper use of remove_and_delete_all_node_holders(...) you have at least two leaks (checkable with valgrind)

Valgrind output

=52599== HEAP SUMMARY:
==52599==     in use at exit: 22,691 bytes in 185 blocks
==52599==   total heap usage: 436 allocs, 251 frees, 42,475 bytes allocated
==52599== 
==52599== 16 bytes in 1 blocks are definitely lost in loss record 3 of 47
==52599==    at 0x1000EF616: malloc (in /usr/local/Cellar/valgrind/3.13.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==52599==    by 0x1001DAE2D: operator new(unsigned long) (in /usr/lib/libc++abi.dylib)
==52599==    by 0x10001438E: net::coderodde::pathfinding::weighted_path<grid_node, int> net::coderodde::pathfinding::search<grid_node, int>(grid_node&, grid_node&, net::coderodde::pathfinding::weight_function<grid_node, int>&, net::coderodde::pathfinding::heuristic_function<grid_node, int>&) (in ./a_star)
==52599==    by 0x100004709: net::coderodde::pathfinding::heuristic_function_selector<grid_node, int>::with_heuristic_function(net::coderodde::pathfinding::heuristic_function<grid_node, int>*) (in ./a_star)
==52599==    by 0x100003AAF: main (in ./a_star)
==52599== 
==52599== 24 bytes in 1 blocks are definitely lost in loss record 8 of 47
==52599==    at 0x1000EF616: malloc (in /usr/local/Cellar/valgrind/3.13.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==52599==    by 0x1001DAE2D: operator new(unsigned long) (in /usr/lib/libc++abi.dylib)
==52599==    by 0x10002AFEE: net::coderodde::pathfinding::weighted_path<matrix_node, matrix> net::coderodde::pathfinding::search<matrix_node, matrix>(matrix_node&, matrix_node&, net::coderodde::pathfinding::weight_function<matrix_node, matrix>&, net::coderodde::pathfinding::heuristic_function<matrix_node, matrix>&) (in ./a_star)
==52599==    by 0x10002A591: net::coderodde::pathfinding::weighted_path<matrix_node, matrix> net::coderodde::pathfinding::search<matrix_node, matrix>(matrix_node&, matrix_node&, net::coderodde::pathfinding::weight_function<matrix_node, matrix>&) (in ./a_star)
==52599==    by 0x100006DD1: net::coderodde::pathfinding::heuristic_function_selector<matrix_node, matrix>::without_heuristic_function() (in ./a_star)
==52599==    by 0x1000040F5: main (in ./a_star)
==52599== 
==52599== 72 bytes in 3 blocks are definitely lost in loss record 26 of 47
==52599==    at 0x1000EF616: malloc (in /usr/local/Cellar/valgrind/3.13.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==52599==    by 0x1001DAE2D: operator new(unsigned long) (in /usr/lib/libc++abi.dylib)
==52599==    by 0x10002D7FB: net::coderodde::pathfinding::weighted_path<matrix_node, matrix> net::coderodde::pathfinding::search<matrix_node, matrix>(matrix_node&, matrix_node&, net::coderodde::pathfinding::weight_function<matrix_node, matrix>&, net::coderodde::pathfinding::heuristic_function<matrix_node, matrix>&) (in ./a_star)
==52599==    by 0x10002A591: net::coderodde::pathfinding::weighted_path<matrix_node, matrix> net::coderodde::pathfinding::search<matrix_node, matrix>(matrix_node&, matrix_node&, net::coderodde::pathfinding::weight_function<matrix_node, matrix>&) (in ./a_star)
==52599==    by 0x100006DD1: net::coderodde::pathfinding::heuristic_function_selector<matrix_node, matrix>::without_heuristic_function() (in ./a_star)
==52599==    by 0x1000040F5: main (in ./a_star)
==52599== 
==52599== 272 bytes in 17 blocks are definitely lost in loss record 36 of 47
==52599==    at 0x1000EF616: malloc (in /usr/local/Cellar/valgrind/3.13.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==52599==    by 0x1001DAE2D: operator new(unsigned long) (in /usr/lib/libc++abi.dylib)
==52599==    by 0x100016B01: net::coderodde::pathfinding::weighted_path<grid_node, int> net::coderodde::pathfinding::search<grid_node, int>(grid_node&, grid_node&, net::coderodde::pathfinding::weight_function<grid_node, int>&, net::coderodde::pathfinding::heuristic_function<grid_node, int>&) (in ./a_star)
==52599==    by 0x100004709: net::coderodde::pathfinding::heuristic_function_selector<grid_node, int>::with_heuristic_function(net::coderodde::pathfinding::heuristic_function<grid_node, int>*) (in ./a_star)
==52599==    by 0x100003AAF: main (in ./a_star)

Why is that? Whenever you move a pointer from open to close you move its ownership to close, but you never free any pointers form close, only from open.

This

        if (*current_node == target) {
            remove_and_delete_all_node_holders(open);
            return traceback_path(*current_node, parents, w);
        }

should at least be

        if (*current_node == target) {
            remove_and_delete_all_node_holders(open);
            remove_and_delete_all_node_holders(close);
            return traceback_path(*current_node, parents, w);
        }

and after the while loop you should replace open with close (since open is empty...).

Hopefully you see how erroneous this manual memory management gets. Thats why smart pointers got invented.

In fact, you do not need any dynamic memory at all here. You can just copy node_holder by value, I think.

Just define your queue as

    auto cmp = [](node_holder<Node, Weight> nh1, node_holder<Node, Weight> nh2) {
        return nh1.m_f > nh2.m_f;
    };

    using priority_queue_t = std::priority_queue<
        node_holder<Node, Weight>, 
        std::vector<node_holder<Node, Weight>>,
        decltype(cmp)>;
    priority_queue_t open{cmp};

and insert by simple constructing and copying

    // loop ..
    while (!open.empty()) {
        node_holder<Node, Weight> current_node = open.top();
        open.pop();
        // ...
        close.push_back(current_node);
        // ...
           open.push({&child_node, tentative_distance + h(child_node)});

Note that copying node_holder is very cheap since its only a (pointer, integer)-pair and doesn't have any ownership associated with.

---

A note on performance

As for the performance. I can not imagine that this is a particular fast implementation. You use std::unordered_map a lot (which means a lot of scattered allocation) your memory access patterns are not very cache friendly and so on. But this is a VERY hard problem to solve generally for all graphs since it is so dependent on its details. Boost.Graph solves this with a lot of trait classes and a Visitor concept and is IMO quite hard to use too... and these guys have a lot more experience than both of us.

A cheap trick one can do to boost its performance is to supply an allocator-overload to your function. This way you could preallocate a memory arena or even use the stack.