Template Class CDijkstra

Nested Relationships

Nested Types

Class Documentation

template<class TYPE_GRAPH, class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_stdmap>
class CDijkstra

The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) directed graph and all other nodes, generating a spanning tree in the process.

The constructor takes as input the graph (a set of directed edges) and computes the spanning tree. Successive calls to CDijkstra::getShortestPathTo() then return the paths efficiently using that cached tree.

The entire spanning tree can be also retrieved via CDijkstra::getTreeGraph().

Input graphs are represented by instances of (or classes derived from) mrpt::graphs::CDirectedGraph, with nodes indexed by numerical values of type mrpt::graphs::TNodeID.

The second template argument MAPS_IMPLEMENTATION allows choosing between:

See a complete C++ code example.

Useful typedefs

using graph_t = TYPE_GRAPH

The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class

using edge_t = typename graph_t::edge_t

The type of edge data in graph_t

using edge_list_t = std::list<TPairNodeIDs>

A list of edges used to describe a path on the graph

using functor_edge_weight_t = std::function<double(const graph_t &graph, TNodeID const id_from, TNodeID const id_to, const edge_t &edge)>
using functor_on_progress_t = std::function<void(const graph_t &graph, size_t visitedCount)>

Query Dijkstra results

using tree_graph_t = CDirectedTree<const edge_t*>

Type for graph returned by getTreeGraph: a graph like the original input graph, but with edge data being pointers to the original data (to save copy time & memory)

inline std::optional<double> getNodeDistanceToRoot(TNodeID const id) const

Return the distance from the root node to any other node using the Dijkstra-generated tree, or std::nullopt if the node ID is unknown or if it was farther away from root than the maximum topological distance passed in the constructor.

inline const std::set<TNodeID> &getListOfAllNodes() const

Return the set of all known node IDs (actually, a const ref to the internal set object).

inline TNodeID getRootNodeID() const

Return the node ID of the tree root, as passed in the constructor

inline const list_all_neighbors_t &getCachedAdjacencyMatrix() const

Return the adjacency matrix of the input graph, which is cached at construction so if needed later just use this copy to avoid recomputing it

See also

mrpt::graphs::CDirectedGraph::getAdjacencyMatrix

inline void getShortestPathTo(TNodeID const target_node_ID, edge_list_t &out_path) const

Returns the shortest path between the source node passed in the constructor and the given target node. The reconstructed path contains a list of arcs (all of them exist in the graph with the given direction), such as the the first edge starts at the origin passed in the constructor, and the last one contains the given target.

See also

getTreeGraph

Note

An empty list of edges is returned when target equals the source node.

Throws:

std::exception – If the given node was out of the maximum topological search radius passed to the constructor.

inline edge_list_t getShortestPathTo(TNodeID const target_node_ID) const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Note

(new in MRPT 2.4.1)

inline void getTreeGraph(tree_graph_t &out_tree) const

Returns a tree representation of the graph, as determined by the Dijkstra shortest paths from the root node. Note that the annotations on each edge in the tree are “const pointers” to the original graph edge data, so it’s mandatory for the original input graph not to be deleted as long as this tree is used.

See also

getShortestPathTo

inline tree_graph_t getTreeGraph() const

Public Functions

inline CDijkstra(const graph_t &graph, const TNodeID source_node_ID, functor_edge_weight_t functor_edge_weight = functor_edge_weight_t(), functor_on_progress_t functor_on_progress = functor_on_progress_t(), const size_t maximum_distance = std::numeric_limits<size_t>::max())

Constructor which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID.

The graph is given by the set of directed edges, stored in a mrpt::graphs::CDirectedGraph class.

If a function functor_edge_weight is provided, it will be used to compute the weight of edges. Otherwise, all edges weight the unity.

After construction, call getShortestPathTo to get the shortest path to a node or getTreeGraph for the tree representation.

An optional maximum distance (topological hop counts, or per functor_edge_weight if provided) to build the tree up to some limit. Use it if you are not interested in the entire tree.

See also

getShortestPathTo(), getTreeGraph()

Note

maximum_distance was added in MRPT 2.4.1

Throws:

std::exception – If the source nodeID is not found in the graph

Protected Types

using list_all_neighbors_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, std::set<TNodeID>>

A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every node.

using id2pairIDs_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TPairNodeIDs>
using id2dist_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TDistance>
using id2id_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TPrevious>

Protected Attributes

const TYPE_GRAPH &m_cached_graph
const TNodeID m_source_node_ID
id2dist_map_t m_distances

All the distances

std::map<TNodeID, TDistance> m_distances_non_visited
id2id_map_t m_prev_node
id2pairIDs_map_t m_prev_arc
std::set<TNodeID> m_lstNode_IDs
list_all_neighbors_t m_allNeighbors
struct TDistance

Auxiliary struct for topological distances from root node

Public Functions

TDistance() = default
inline TDistance(const double D)
inline const TDistance &operator=(const double D)

Public Members

double dist = std::numeric_limits<double>::max()
struct TPrevious

Auxiliary struct for backward paths

Public Functions

TPrevious() = default

Public Members

TNodeID id = INVALID_NODEID