Pathfinders.hpp - Dijkstra's algorithm

Question

I have this Visual Studio 2022 project, in which I compared the performance of 4 point-to-point shortest path algorithms. This one presents the Dijkstra's algorithm:

#ifndef COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_DIJKSTRA_HPP
#define COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_DIJKSTRA_HPP

#include "DirectedGraph.hpp"
#include "Pathfinders.SharedUtils.hpp"
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <sstream>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace com::github::coderodde::pathfinders {

    using namespace com::github::coderodde::directed_graph;
    using namespace com::github::coderodde::pathfinders::util;

    template<typename Node = int, typename Weight = double>
    Path<Node, Weight>
        runDijkstrasAlgorithm(DirectedGraph<Node>& graph,
            DirectedGraphWeightFunction<Node, Weight>& weight_function,
            Node& source_node,
            Node& target_node) {

        checkTerminalNodes(graph, source_node, target_node);

        std::priority_queue<
            HeapNode<Node, Weight>*,
            std::vector<HeapNode<Node, Weight>*>,
            HeapNodeComparator<Node, Weight>> OPEN;

        std::unordered_set<Node> CLOSED;
        std::unordered_map<Node, Weight> distance_map;
        std::unordered_map<Node, Node*> parent_map;

        OPEN.push(new HeapNode<Node, Weight>(source_node, Weight{}));
        distance_map[source_node] = {};
        parent_map[source_node] = nullptr;

        while (!OPEN.empty()) {
            HeapNode<Node, Weight>* top_heap_node = OPEN.top();
            OPEN.pop();
            Node current_node = top_heap_node->getElement();
            delete top_heap_node;

            if (current_node == target_node) {
                // Found the path:
                cleanPriorityQueue<Node, Weight>(OPEN);
                Path<Node, Weight> path =
                    tracebackPath(
                        target_node,
                        parent_map,
                        weight_function);

                cleanParentMap<Node>(parent_map);
                return path;
            }

            if (CLOSED.contains(current_node)) {
                continue;
            }

            CLOSED.insert(current_node);

            const std::unordered_set<Node>* children =
                graph.getChildNodesOf(current_node);

            for (Node const& child : *children) {
                if (CLOSED.contains(child)) {
                    // The optimal distance from source_node to child
                    // is known. Omit:
                    continue;
                }

                Weight distance =
                    distance_map[current_node] +
                    weight_function.getWeight(current_node, child);

                if (!parent_map.contains(child) 
                    || distance < distance_map[child]) {

                    OPEN.push(new HeapNode<Node, Weight>(child, distance));
                    distance_map[child] = distance;
                    Node* elem_ptr = new Node{ current_node };
                    parent_map[child] = elem_ptr;
                }
            }
        }

        throw PathDoesNotExistException{
            buildPathNotExistsErrorMessage(source_node, target_node) };
    }


} // End on namespace 'com::github::coderodde::pathfinders'.

#endif // COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_DIJKSTRA_HPP

Critique request

I am interested in these:

1. possible undefined behavior,
2. memory leaks,
3. efficiency issues,
4. code readability,
5. idiomacy of the code.

Answer 1

possible undefined behavior,

Don't see any.

memory leaks,

You did not provide all the code so impossible to say definitely.

• It looks like you leak if you don't find a path.
• Looks like you leak children.

ALSO your usage of new is a bad and anti-idiomatic.

efficiency issues,

Nothing pops up.

code readability,

Using all capitols OPEN and CLOSED is not nice (breaks all coding conventions I have seen). All caps is usually reserved for macros.

could use using in a couple of places to simplify the types.

   std::priority_queue<
        HeapNode<Node, Weight>*,
        std::vector<HeapNode<Node, Weight>*>,
        HeapNodeComparator<Node, Weight>> OPEN;

Might have been nicer to write as:

    using LocalNode = HeapNode<Node, Weight>*;
    using QueueStorage = std::vector<LocalNode>;
    using Compare = HeapNodeComparator<Node, Weight>;

    using PriorityQueue = std::priority_queue<LocalNode, QueueStorage, Compare>;

    PriorityQueue  OPEN;

idiomacy of the code.

Looks like it should work.
But your usage of new and delete and passing around RAW pointers ins non idiomatic. RAW pointers do not have ownership semantics so it is hard to understand if you need to delete them. Also they are not exception safe so will leak if there are any exceptions in your code.

Modern C++ has moved to using smart_pointer to hold owned pointers and view(s) and references to hold non owned pointers and containers to hold non-polymorphic groups of objects.

BUT I see no need for any dynamic memory management at all, as the containers you use will all handle this very efficiently.

Even in old C++ NVO optimization removed most copies and in modern C++ we have move semantics that makes copy a last resort and simple move operations the common way things get done automatically.

---

Code Review

Nice:

#ifndef COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_DIJKSTRA_HPP
#define COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_DIJKSTRA_HPP

---

#include <algorithm>       // Do you use any algorithms?
#include <sstream>         // Did I miss the string stream.
#include <stdexcept>       // I don't see you creating any exceptions

---

Not sure what these do:

        checkTerminalNodes(graph, source_node, target_node);

                    tracebackPath(
                        target_node,
                        parent_map,
                        weight_function);

                cleanParentMap<Node>(parent_map);

So can't really comment on them.

---

You don't need to use pointers here. There is no polymorphism. So simply add the objects to your queue.

        std::priority_queue<
            HeapNode<Node, Weight>*,
            std::vector<HeapNode<Node, Weight>*>,
            HeapNodeComparator<Node, Weight>> OPEN;

   // Could just as easily have written:

        std::priority_queue<
            HeapNode<Node, Weight>,                 // No Star
            std::vector<HeapNode<Node, Weight>>,    // No Star
            HeapNodeComparator<Node, Weight>> open;

That would have worked better, as you don't need to worry about any memory leaks now.

I would have simplified even more by going.

     using MyHeapNode = std::tupple<Weight, Node>;

Notice the order. :-) The tuple has a built in comparitor so you don't need to define one explicitly for your priority_queue and that simplifies your declaration even further.

      std::priority_queue<MyHeapNode>  open;

---

Sure this is one way.

        OPEN.push(new HeapNode<Node, Weight>(source_node, Weight{}));

But if you had used the above. You could simplify this to:

        open.emplace_back(source_node, Weight{});

---

Stop creating things with new and passing the pointers around.

            const std::unordered_set<Node>* children =
                graph.getChildNodesOf(current_node);

You should return the unordered_set<Node> from getChildNodesOf(). The standard containers implement move semantics, so this will be cheap (and much cheaper than leaking memory).

---

            for (Node const& child : *children) {

                // Premature optimization.
                // But does no harm. So no real complaint.

                if (CLOSED.contains(child)) {
                    // The optimal distance from source_node to child
                    // is known. Omit:
                    continue;
                }

                // Another premature optimization
                // Not causing a bug yet but I can see potential for a
                // a bug in the future.
                //
                // You are defining distance_map[child] even though
                // you don't yet know it is the shortest distance.
                // If some code tries to use 'distance_map' for actual
                // distance calculations you must make sure that the node
                // is also in the `CLOSED` set.
                //
                // You don't enforce this condition in your code so there
                // is a potential for a bug to sneak in later when the
                // function is modified with new requirements.
                if (!parent_map.contains(child) 
                    || distance < distance_map[child]) {

---

        // Even if you throw an exception
        // You still should clean up all the memory you allocated
        // with new.
        //
        // This is exactly why it is rare to see plain `new` and
        // `delete` in modern C++ code. It is usually placed in
        // handeled by smart pointers.
        //
        // OR better to use value semantics (as I showed above.
        throw PathDoesNotExistException{
            buildPathNotExistsErrorMessage(source_node, target_node) };