Skip to content

alekstheod/tinyspa

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

36 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

tinyspa

Small header only shortest path algorithm implementation by adapting the weight function can be used as a dijkstra or AStar algorithm

Usage:

Define a graph class

  • Graph is a class with the following interface
    • Node type defines the node
    • Weight type defines the weight
    • Weight weight(const Node& from, const Node& to) // calculates the weight for the edge between the nodes from and to
    • Iterator begin(const Node& node) // returns iterator of of predecessors of the given node
    • Iterator end(const Node& node) // returns end iterator of predecessors of the given node
    • bool goal (const Node& cur) // returns true if the goal is reached (destination == cur)

Create a graph

#include <ShortestPath.h>
#include <Queue.h>

#include <vector>
#include <unordered_map>

typedef unsigned int Node;

class Graph {
    public:
    using Node = ::Node;
    using Weight = unsigned int;
    Graph () {
    }

    Weight weight (const Node& from, const Node& to) {
        return 100;
    }

    using Container = typename std::vector< Node >;
    using Iterator = typename Container::const_iterator;

    Iterator begin (const Node& node) {
        return m_graph[node].cbegin ();
    }

    Iterator end (const Node& node) {
        return m_graph[node].cend ();
    }

    // In case of dijkstra return true if cur == m_dest
    bool goal (const Node& cur) {
        return false;
    }

    using GraphMap = std::unordered_map< unsigned int, Container >;
    GraphMap m_graph = {{1, {2, 3}},
                        {2, {5, 6, 7, 3}},
                        {3, {8, 9, 10, 11, 4, 2}},
                        {4, {13, 14, 15, 16}}};
};

Calculate the route

Spa::ShortestPath< Graph, Spa::PrioQueue > algo (graph);
const auto spanningTree = algo.calculate (1);
const auto path = spanningTree.calculate(16);
const auto path2 = spanningTree.calculate(10);

About

Small abstract header only shortest path lib

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published