Yet Another Dijkstra with real data and drawing

Question

I've been assigned to use Dijkstra's algorithm in order to find the shortest path on real data, more specifically on Luxembourg's map.

The map is an .xml file with the following structure.

<nodes>
        <node id="0" longitude="4963454" latitude="621476"/>
        <node id="1" longitude="4959493" latitude="614350"/>
        <node id="2" longitude="4959247" latitude="612096"/>
        ...
</nodes>
<arcs>
        <arc from="0" to="40115" length="57"/>
        <arc from="0" to="40114" length="13"/>
        <arc from="1" to="16852" length="49"/>
        ...
</arcs>

I've got this .xml file alongside all the source files on this repository.

The purpose of the assignment is: given the drawn map, you have to click on 2 different screen locations and get the shortest path between the closest Nodes to those clicks.

Because the assignment wasn't that hard, I focused on elegance, performance, and reusability.

Here's a snippet of the final program.

Now let's dive in the code. I've come up with 4 interface-like classes which would let you make a truly custom Node class.

Earth.hpp

#pragma once

#include <cstdint>

#include "Point2D.hpp"

namespace Localizable
{
    template <typename LatLongType = int32_t>
    class Earth
    {
    public:
        constexpr Earth(LatLongType latitude, LatLongType longitude) noexcept;

        constexpr LatLongType latitude() const noexcept;
        constexpr LatLongType longitutde() const noexcept;

    protected:
        Point2D<LatLongType> _location;
    };

    template <typename LatLongType>
    inline constexpr Earth<LatLongType>::Earth(LatLongType latitude, LatLongType longitude) noexcept
        : _location(latitude, longitude)
    {}

    template <typename LatLongType>
    inline constexpr LatLongType Earth<LatLongType>::latitude() const noexcept
    {
        return _location.x;
    }

    template <typename LatLongType>
    inline constexpr LatLongType Earth<LatLongType>::longitutde() const noexcept
    {
        return _location.y;
    }
}

Screen.hpp

#pragma once 

#include <cstdint>

#include "Point2D.hpp"

namespace Localizable
{
    class Screen
    {
    public:
        constexpr Screen(uint16_t x, uint16_t y) noexcept;

        constexpr uint16_t x() const noexcept;
        constexpr uint16_t y() const noexcept;

    protected:
        Point2D<uint16_t> _location;
    };

    inline constexpr Screen::Screen(uint16_t x, uint16_t y) noexcept
        : _location(x, y)
    {}

    inline constexpr uint16_t Screen::x() const noexcept
    {
        return _location.x;
    }

    inline constexpr uint16_t Screen::y() const noexcept
    {
        return _location.y;
    }
}

Associable.hpp

#pragma once

#include <vector>
#include <memory>

template <typename KeyType>
class Node;

template <typename KeyType>
class Associable
{
protected:
    std::vector<std::weak_ptr<Node<KeyType>>> _neighbours;

    using NeighboursIterator = decltype(std::cbegin(_neighbours));

public:
    void add(std::weak_ptr<Node<KeyType>> neighbour);

    void remove(std::weak_ptr<Node<KeyType>> neighbour);

    constexpr std::pair<NeighboursIterator, NeighboursIterator> getNeighbours() const noexcept
    {
        return std::make_pair(std::cbegin(_neighbours), std::cend(_neighbours));
    }
};

template<typename KeyType>
inline void Associable<KeyType>::add(std::weak_ptr<Node<KeyType>> neighbour)
{
    _neighbours.push_back(neighbour);
}

template<typename KeyType>
inline void Associable<KeyType>::remove(std::weak_ptr<Node<KeyType>> neighbour)
{
    auto it = std::find(std::begin(_neighbours), std::end(_neighbours), neighbour);

    if (it != std::end(_neighbours))
        _neighbours.erase(it);
}

Identifiable.hpp

#pragma once

#include <cstdint>

template <typename IdentifierType = uint16_t>
class Identifiable
{
public:
    constexpr explicit Identifiable(IdentifierType identifier) noexcept;

    constexpr IdentifierType key() const noexcept;

protected:
    IdentifierType _key;
};

template<typename IdentifierType>
inline constexpr Identifiable<IdentifierType>::Identifiable(IdentifierType identifier) noexcept :
    _key(identifier)
{
}

template<typename IdentifierType>
inline constexpr IdentifierType Identifiable<IdentifierType>::key() const noexcept
{
    return _key;
}

Having all of these defined, making the custom Node class for the assignment was easy:

Node.hpp

#pragma once

#include "Earth.hpp"
#include "Identifiable.hpp"
#include "Associable.hpp"
#include "Screen.hpp"
#include "Utilities.hpp"

template <typename KeyType = uint16_t>
class Node : public Localizable::Earth<int32_t>, public Identifiable<KeyType>, public Associable<KeyType>, public Localizable::Screen
{
public:
    constexpr Node(KeyType key, int32_t latitude, int32_t longitutde) noexcept;
};

template<typename KeyType>
inline constexpr Node<KeyType>::Node(KeyType key, int32_t latitude, int32_t longitutde) noexcept : 
    Identifiable<KeyType>(key),
    Localizable::Earth<int32_t>(latitude, longitutde),
    Localizable::Screen(Utilities::getScreenCoordinates(1280, 1020, latitude, longitutde)),
    Associable<KeyType>()
{
}

namespace std
{
    template<typename KeyType> struct hash<Node<KeyType>>
    {
        std::size_t operator()(const Node<KeyType>& node) const noexcept
        {
            return std::hash<KeyType>{}(node.key());
        }
    };

    template <typename KeyType> struct equal_to<Node<KeyType>>
    {
        constexpr bool operator()(const Node<KeyType>& lhs, const Node<KeyType>& rhs) const noexcept
        {
            return lhs.key() == rhs.key();
        }
    };
}

template <typename KeyType>
constexpr bool operator == (const Node<KeyType>& lhs, const Node<KeyType>& rhs) noexcept
{
    return lhs.key() == rhs.key();
}


template <typename KeyType>
constexpr bool operator != (const Node<KeyType>& lhs, const Node<KeyType>& rhs) noexcept
{
    return lhs.key() != rhs.key();
}

Then I've integrated my Node class in the Graph class.

Graph.hpp

#pragma once

#include <unordered_map>
#include <vector>

#include "Node.hpp"
#include "Point2D.hpp"

class GraphFactory;

namespace std
{
    template <> struct hash<std::pair<uint16_t, uint16_t>>
    {
        std::size_t operator ()(const std::pair<uint16_t, uint16_t>& pair) const noexcept
        {
            return std::hash<uint16_t>{}(pair.first) + std::hash<uint16_t>{}(pair.second);
        }
    };
}

namespace ShortestPath
{
    template <typename KeyType>
    class Dijkstra;
}

/**
* This Graph implements the Node class using an uint16_t KeyType.
* Feel free to use any other data type for KeyType on your graph.
*/
template <typename KeyType = uint16_t>
class Graph
{
private:

    std::unordered_map<KeyType, std::shared_ptr<Node<KeyType>>> _keyToNode;

    std::unordered_map<std::pair<KeyType, KeyType>, uint16_t> _weights;

    std::unordered_map<Point2D<uint16_t>, std::weak_ptr<Node<KeyType>>> _coordinatesToNode;

    using WeightsIterator = decltype(std::cbegin(_weights));

    using NodesIterator = decltype(std::cbegin(_keyToNode));

public:

    friend class GraphFactory;

    template <typename KeyType>
    friend class ShortestPath::Dijkstra;

public:

    constexpr std::pair<NodesIterator, NodesIterator> nodes() const noexcept
    {
        return std::make_pair(std::cbegin(_keyToNode), std::cend(_keyToNode));
    }

    constexpr std::pair<WeightsIterator, WeightsIterator> arcs() const noexcept
    {
        return std::make_pair(std::cbegin(_weights), std::cend(_weights));
    }

    std::shared_ptr<Node<KeyType>> operator [](KeyType key) const noexcept;

    std::weak_ptr<Node<KeyType>> operator [](Point2D<uint16_t> coordinates) const noexcept;

    uint16_t cost(const std::pair<KeyType, KeyType>& keys) const;

protected:

    template <typename InputKeyMappingIterator, typename InputWeightingIterator, typename CoordinatesMapping>
    Graph(InputKeyMappingIterator keysFirst, InputKeyMappingIterator keysLast,
        InputWeightingIterator weightsFirst, InputWeightingIterator weightsLast,
        CoordinatesMapping coordsFirst, CoordinatesMapping coordsLast);
};

template<typename KeyType>
std::shared_ptr<Node<KeyType>> Graph<KeyType>::operator[](KeyType key) const noexcept
{
    auto it = _keyToNode.find(key);

    return it != std::end(_keyToNode) ? it->second : nullptr;
}

template<typename KeyType>
inline std::weak_ptr<Node<KeyType>> Graph<KeyType>::operator[](Point2D<uint16_t> coordinates) const noexcept
{
    auto it = _coordinatesToNode.find(coordinates);

    return it != std::end(_coordinatesToNode) ? it->second : std::weak_ptr<Node<KeyType>>();
}

template<typename KeyType>
inline uint16_t Graph<KeyType>::cost(const std::pair<KeyType, KeyType>& keys) const
{
    const auto&[firstKey, secondKey] = keys;

    if (auto it = _weights.find(std::make_pair(firstKey, secondKey)); it != std::end(_weights))
        return it->second;


    if (auto it = _weights.find(std::make_pair(secondKey, firstKey)); it != std::end(_weights))
        return it->second;

    static constexpr uint16_t kDefaultValue = 0;
    return kDefaultValue;
}

template<typename KeyType>
template<typename InputKeyMappingIterator, typename InputWeightingIterator, typename CoordinatesMapping>
inline Graph<KeyType>::Graph(InputKeyMappingIterator keysFirst, InputKeyMappingIterator keysLast, 
    InputWeightingIterator weightsFirst, InputWeightingIterator weightsLast, 
    CoordinatesMapping coordsFirst, CoordinatesMapping coordsLast) :
    _keyToNode(keysFirst, keysLast),
    _weights(weightsFirst, weightsLast),
    _coordinatesToNode(coordsFirst, coordsLast)
{
}

The reason I'm returning a pair of iterators instead of the whole container is because of encapsulation and abstraction reasons. Why would anyone care that the Graph class is using a HashTable to retain the nodes?

The final code snippet I'm exposing is the trivial Dijkstra implementation.

#pragma once

#include "Graph.hpp"

#include <queue>
#include <stdexcept>

namespace ShortestPath
{
    template <typename KeyType = uint16_t>
    class Dijkstra
    {
    private:
        std::vector<Node<KeyType>> _path;

    public:
        explicit Dijkstra(const Graph<KeyType>& graph, const std::shared_ptr<Node<KeyType>>& source,
            const std::shared_ptr<Node<KeyType>>& destination);

        constexpr std::pair<decltype(std::cbegin(_path)), decltype(std::cend(_path))> path() const noexcept
        {
            return std::make_pair(std::cbegin(_path), std::cend(_path));
        }

    private:
        void computeShortestPath(const Graph<KeyType>& graph);

        void populatePath() noexcept;

        const std::weak_ptr<Node<KeyType>> _source;
        const std::weak_ptr<Node<KeyType>> _destination;

        std::unordered_map<Node<KeyType>, Node<KeyType>> _cameFrom;
        std::unordered_map<Node<KeyType>, uint16_t> _cost;
    };


    template<typename KeyType>
    inline Dijkstra<KeyType>::Dijkstra(const Graph<KeyType>& graph,
        const std::shared_ptr<Node<KeyType>>& source, 
        const std::shared_ptr<Node<KeyType>>& destination) :
        _source(source),
        _destination(destination)
    {
        computeShortestPath(graph);
        populatePath();
    }

    template<typename KeyType>
    inline void Dijkstra<KeyType>::computeShortestPath(const Graph<KeyType> & graph)
    {
        using Location = std::pair<Node<KeyType>, uint16_t>;

        auto compareLocations = [](const Location& lhs, const Location& rhs)
        {
            return lhs.second > rhs.second;
        };

        std::priority_queue<Location, std::vector<Location>, decltype(compareLocations)> discoveredNodes(compareLocations);

        static constexpr uint16_t kDefaultDistanceCost = 0;
        discoveredNodes.push(std::make_pair(*_source.lock(), kDefaultDistanceCost));

        _cameFrom.insert(std::make_pair(*_source.lock(), *_source.lock()));
        _cost[*_source.lock()] = kDefaultDistanceCost;

        while (!discoveredNodes.empty())
        {
            Location currentLocation = discoveredNodes.top();
            discoveredNodes.pop();

            if (auto destination = _destination.lock();
                currentLocation.first.key() == destination->key())
                return;


            auto locationFromGraph = graph[currentLocation.first.key()];

            auto[first, last] = locationFromGraph->getNeighbours();

            for (; first != last; ++first)
            {
                auto neighbour = *((*first).lock());
                uint16_t newCost = _cost[currentLocation.first] +
                    graph.cost(std::make_pair(currentLocation.first.key(), neighbour.key()));

                if (_cost.find(neighbour) == std::end(_cost) || newCost < _cost[neighbour])
                {
                    _cost[neighbour] = newCost;
                    _cameFrom.insert(std::make_pair(neighbour, currentLocation.first));
                    discoveredNodes.push(std::make_pair(neighbour, newCost));
                }
            }

        }

        throw std::domain_error("No path was found.\n");
    }
    template<typename KeyType>
    inline void Dijkstra<KeyType>::populatePath() noexcept
    {
        Node<KeyType> currentNode = *_destination.lock();
        const Node<KeyType> sourceNode = *_source.lock();

        while (currentNode != sourceNode)
        {
            _path.push_back(currentNode);
            currentNode = _cameFrom.at(currentNode);
        }

        _path.push_back(sourceNode);
    }
}

All in all, what do you think?

Did I use smart pointers properly?

Answer 1

code:

• Longitude is misspelled as longitutde a few times.

• Use std::int32_t etc. instead of int32_t. The C versions are in the global namespace, but the C++ ones are in namespace std.

• In the Graph class _keyToNode and _coordinatesToNode duplicate data already contained in the Node class (key and screen coordinates respectively). We can either:

  1. use an unordered_set and supply custom Hash and KeyEquals types as template arguments or

  2. move these data out of the Node class.

• A named function (e.g. FindNode) may be preferable to overloading the Graph::operator[] (the user may have preconceptions as to what operator[] should do on failure to find a node).

• The protected Graph constructor is a bit weird. Is there any special reason to restrict the construction of a Graph to derived objects / friends, and allow the GraphFactory access to all private class members? If not, just leave the constructor public.

• The std::pair<uint16_t, uint16_t> hash function could probably use a better technique to combine hashes.

---

concepts:

C++ has the notion of concepts, where classes of different types may adhere to the same static interface. These currently exist in the form of named requirements, and will soon be in the language itself.

While a concept itself may be named something like Associable, this label refers to the static interface, and not to a concrete class. A more suitable name for the class itself would be Associates or simply Neighbours, and the class would adhere to the Associable concept by providing the appropriate static interface (functions, members, typedefs, etc.).

Template classes or functions would then expect to receive types that adhere to the relevant concept. In this case, the Graph class might instead be templated on Node, and expect it to be e.g. Associable and Identifiable.

Anywya, since the classes shown above are concrete classes, I'd recommend naming them more like this:

• Localizable::Earth -> EarthCoords
• Localizable::Screen -> ScreenCoords
• Associable -> Neighbours
• Identifiable -> Id

Note that there's no actual relationship between Localizable::Earth and Localizable::Screen so there's no reason for them to share a namespace.

---

pointers:

std::shared_ptr implies shared ownership. This is seldom something we actually want or need, as it makes object lifetime much harder to determine.

In this case, there doesn't seem to be any sharing going on. As long as we ensure the lifetime of a Node object is longer than the lifetimes of any Node*s that refer to it, we can use raw pointers safely. In other words, the std::shared_ptr<Node> in the Graph class can be changed to std::unique_ptr<Node>, and all of the std::weak_ptr<Node>s can be Node*s.

Note, however, that we don't actually need to use pointers here at all. We can simply store the node index instead.

---

Graph:

The Graph doesn't need to know about most of what's in the Node class. The minimal data required for a Graph is an adjacency list. Grouping this together with the edge weights into a WeightedGraph is reasonable:

template<class IndexT, class WeightT, class IndexPairHashT = std::hash<std::pair<IndexT, IndexT>>>
struct WeightedGraph
{
    std::unordered_map<IndexT, std::vector<IndexT>> _adjacency;
    std::unordered_map<std::pair<IndexT, IndexT>, WeightT, IndexPairHashT> _edgeWeights;
};

The Graph now depends only on the index type and weight type, and we're free to store nodes however we want (or not at all) outside of it, which is a lot more flexible.

Note that the screen coordinates are unrelated to the Graph. (In fact, we might want a separate data structure to accelerate finding the nearest point to a mouse click, like a PointQuadTree<ScreenCoords, NodeIndex>.)

---

Dijkstra algorithm:

• This should be a free function, not a class. It could return the path as a std::vector<Node>, or a struct containing the path and any additional data needed.
• It shouldn't throw on failure to find a path (it's would be quite reasonable to encounter unconnected nodes, and we shouldn't use exceptions for flow control).

---

misc:

Your xml file has latitude and longitude switched around! I think the data may also be horizontally (longitudinally) stretched, but I could be wrong about that.