Detailed Description

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

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

The constructor takes as input the graph (the set of directed edges) computes all the needed data, then successive calls to getShortestPathTo return the paths efficiently from the root.

The entire generated tree can be also retrieved with getTreeGraph.

Input graphs are represented by instances of (or classes derived from) mrpt::graphs::CDirectedGraph, and node's IDs are uint64_t values, although the type mrpt::graphs::TNodeID is also provided for clarity in the code.

The second template argument MAPS_IMPLEMENTATION allows choosing between a sparse std::map<> representation (using * mrpt::containers::map_traits_stdmap) for several intermediary and final results, and an alternative (using mrpt::containers::map_traits_map_as_vector as argument) dense implementation which is much faster, but can be only used if the TNodeID's start in 0 or a low value.

See <a href="http://www.mrpt.org/Example:Dijkstra_optimal_path_search_in_graphs"

this page for a complete example.

Definition at line 97 of file dijkstra.h.

#include <mrpt/graphs/dijkstra.h>

Classes
struct	TDistance
	Auxiliary struct for topological distances from root node. More...

struct	TPrevious
	Auxiliary struct for backward paths. More...

Public Types
Useful typedefs
using	graph_t = TYPE_GRAPH
	The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class. More...

using	edge_t = typename graph_t::edge_t
	The type of edge data in graph_t. More...

using	edge_list_t = std::list< TPairNodeIDs >
	A list of edges used to describe a path on the graph. More...

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

using	functor_on_progress_t = std::function< void(const graph_t &graph, size_t visitedCount)>

Public Member Functions
	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())
	Constructor which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID. More...

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. More...

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. More...

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

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) More...

double	getNodeDistanceToRoot (const TNodeID id) const
	Return the distance from the root node to any other node using the Dijkstra-generated tree. More...

const std::set< TNodeID > &	getListOfAllNodes () const
	Return the set of all known node IDs (actually, a const ref to the internal set object). More...

TNodeID	getRootNodeID () const
	Return the node ID of the tree root, as passed in the constructor. More...

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. More...

void	getShortestPathTo (const TNodeID 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. More...

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. More...

Member Typedef Documentation

◆ edge_list_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::edge_list_t = std::list<TPairNodeIDs>

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

Definition at line 156 of file dijkstra.h.

◆ edge_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::edge_t = typename graph_t::edge_t

The type of edge data in graph_t.

Definition at line 154 of file dijkstra.h.

◆ functor_edge_weight_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::functor_edge_weight_t = std::function<double( const graph_t& graph, const TNodeID id_from, const TNodeID id_to, const edge_t& edge)>

Definition at line 160 of file dijkstra.h.

◆ functor_on_progress_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::functor_on_progress_t = std::function<void(const graph_t& graph, size_t visitedCount)>

Definition at line 163 of file dijkstra.h.

◆ graph_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::graph_t = TYPE_GRAPH

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

Definition at line 152 of file dijkstra.h.

◆ id2dist_map_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::id2dist_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TDistance>

protected

Definition at line 132 of file dijkstra.h.

◆ id2id_map_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::id2id_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TPrevious>

protected

Definition at line 134 of file dijkstra.h.

◆ id2pairIDs_map_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::id2pairIDs_map_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, TPairNodeIDs>

protected

Definition at line 130 of file dijkstra.h.

◆ list_all_neighbors_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::list_all_neighbors_t = typename MAPS_IMPLEMENTATION::template map<TNodeID, std::set<TNodeID> >

protected

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

Definition at line 128 of file dijkstra.h.

◆ tree_graph_t

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

using mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::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)

Definition at line 439 of file dijkstra.h.

Constructor & Destructor Documentation

◆ CDijkstra()

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

mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::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()`
	)

inline

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.

See also: getShortestPathTo, getTreeGraph

Exceptions

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

Definition at line 184 of file dijkstra.h.

References ASSERT_, INVALID_NODEID, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_allNeighbors, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances_non_visited, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_lstNode_IDs, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_node, and THROW_EXCEPTION_FMT.

Member Function Documentation

◆ getCachedAdjacencyMatrix()

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

const list_all_neighbors_t& mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getCachedAdjacencyMatrix ( ) const

inline

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

Definition at line 402 of file dijkstra.h.

References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_allNeighbors.

◆ getListOfAllNodes()

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

const std::set<TNodeID>& mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getListOfAllNodes ( ) const

inline

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

Definition at line 389 of file dijkstra.h.

References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_lstNode_IDs.

◆ getNodeDistanceToRoot()

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

double mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getNodeDistanceToRoot ( const TNodeID id ) const

inline

Return the distance from the root node to any other node using the Dijkstra-generated tree.

Exceptions

std::exception On unknown node ID

Definition at line 378 of file dijkstra.h.

References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances, and THROW_EXCEPTION.

◆ getRootNodeID()

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

TNodeID mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getRootNodeID ( ) const

inline

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

Definition at line 395 of file dijkstra.h.

References mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID.

◆ getShortestPathTo()

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

void mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getShortestPathTo	(	const TNodeID	target_node_ID,
		edge_list_t &	out_path
	)		const

inline

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.

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

See also: getTreeGraph

Definition at line 418 of file dijkstra.h.

References ASSERT_, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_node, and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID.

◆ getTreeGraph()

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

void mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph ( tree_graph_t & out_tree ) const

inline

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

Definition at line 449 of file dijkstra.h.

References ASSERTMSG_, mrpt::graphs::CDirectedTree< TYPE_EDGES >::clear(), mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children, mrpt::format(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_cached_graph, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc, mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID, and mrpt::graphs::CDirectedTree< TYPE_EDGES >::root.

Here is the call graph for this function:

Member Data Documentation

◆ m_allNeighbors

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

list_all_neighbors_t mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_allNeighbors

protected

Definition at line 144 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getCachedAdjacencyMatrix().

◆ m_cached_graph

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

const TYPE_GRAPH& mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_cached_graph

protected

Definition at line 121 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().

◆ m_distances

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

id2dist_map_t mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances

protected

All the distances.

Definition at line 138 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getNodeDistanceToRoot().

◆ m_distances_non_visited

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

std::map<TNodeID, TDistance> mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_distances_non_visited

protected

Definition at line 140 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra().

◆ m_lstNode_IDs

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

std::set<TNodeID> mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_lstNode_IDs

protected

Definition at line 143 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getListOfAllNodes().

◆ m_prev_arc

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

id2pairIDs_map_t mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_arc

protected

Definition at line 142 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getShortestPathTo(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().

◆ m_prev_node

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

id2id_map_t mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_prev_node

protected

Definition at line 141 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::CDijkstra(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getShortestPathTo().

◆ m_source_node_ID

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

const TNodeID mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::m_source_node_ID

protected

Definition at line 122 of file dijkstra.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getRootNodeID(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getShortestPathTo(), and mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().

Detailed Description

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

Classes

Public Types

Public Member Functions

Protected Types

Protected Attributes

Query Dijkstra results

Member Typedef Documentation

◆ edge_list_t

◆ edge_t

◆ functor_edge_weight_t

◆ functor_on_progress_t

◆ graph_t

◆ id2dist_map_t

◆ id2id_map_t

◆ id2pairIDs_map_t

◆ list_all_neighbors_t

◆ tree_graph_t

Constructor & Destructor Documentation

◆ CDijkstra()

Member Function Documentation

◆ getCachedAdjacencyMatrix()

◆ getListOfAllNodes()

◆ getNodeDistanceToRoot()

◆ getRootNodeID()

◆ getShortestPathTo()

◆ getTreeGraph()

Member Data Documentation

◆ m_allNeighbors

◆ m_cached_graph

◆ m_distances

◆ m_distances_non_visited

◆ m_lstNode_IDs

◆ m_prev_arc

◆ m_prev_node

◆ m_source_node_ID

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