Main MRPT website > C++ reference
MRPT logo
Classes | Public Member Functions | Protected Types | Protected Attributes

mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION > Class Template Reference


Detailed Description

template<class TYPE_EDGES, class MAPS_IMPLEMENTATION = map_traits_stdmap>
class mrpt::math::CDijkstra< TYPE_EDGES, 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::math::CDirectedGraph, and node's IDs are uint64_t values, although the type mrpt::utils::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::utils::map_traits_stdmap) for several intermediary and final results, and an alternative (using mrpt::utils::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 this page for a complete example.

Definition at line 59 of file dijkstra.h.

#include <mrpt/math/dijkstra.h>

List of all members.

Classes

struct  TDistance
 Auxiliary struct for topological distances from root node. More...
struct  TPrevious
 Auxiliary struct for backward paths. More...

Public Types

Useful typedefs
typedef
mrpt::math::CDirectedGraph
< TYPE_EDGES > 
graph_t
 The type of a graph with TYPE_EDGES edges.
typedef TYPE_EDGES edge_t
 The type of edge data in graph_t.
typedef std::list< TPairNodeIDsedge_list_t
 A list of edges used to describe a path on the graph.

Public Member Functions

 CDijkstra (const graph_t &graph, const TNodeID source_node_ID, double(*functor_edge_weight)(const graph_t &graph, const TNodeID id_from, const TNodeID id_to, const TYPE_EDGES &edge)=NULL, void(*functor_on_progress)(const graph_t &graph, size_t visitedCount)=NULL)
 Constructor, which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID.

Protected Types

typedef
MAPS_IMPLEMENTATION::template
map< TNodeID, std::set
< TNodeID > > 
list_all_neighbors_t
 A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every node.
typedef
MAPS_IMPLEMENTATION::template
map< TNodeID, TPairNodeIDs
id2pairIDs_map_t
typedef
MAPS_IMPLEMENTATION::template
map< TNodeID, TDistance
id2dist_map_t
typedef
MAPS_IMPLEMENTATION::template
map< TNodeID, TPrevious
id2id_map_t

Protected Attributes

const
mrpt::math::CDirectedGraph
< TYPE_EDGES > & 
m_cached_graph
const TNodeID m_source_node_ID
id2dist_map_t m_distances
 All the distances.
std::map< TNodeID, TDistancem_distances_non_visited
id2id_map_t m_prev_node
id2pairIDs_map_t m_prev_arc
std::set< TNodeIDm_lstNode_IDs
list_all_neighbors_t m_allNeighbors

Query Dijkstra results

typedef CDirectedTree< const
TYPE_EDGES * > 
tree_graph_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)
double getNodeDistanceToRoot (const TNodeID id) const
 Return the distance from the root node to any other node using the Dijkstra-generated tree

Exceptions:
std::exceptionOn unknown node ID.

const std::set< TNodeID > & getListOfAllNodes () const
 Return the set of all known node IDs (actually, a const ref to the internal set object).
TNodeID getRootNodeID () const
 Return the node ID of the tree root, as passed in the constructor.
const list_all_neighbors_tgetCachedAdjacencyMatrix () 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.
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.
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.

Member Typedef Documentation

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef std::list<TPairNodeIDs> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::edge_list_t

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

Definition at line 102 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef TYPE_EDGES mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::edge_t

The type of edge data in graph_t.

Definition at line 101 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef mrpt::math::CDirectedGraph<TYPE_EDGES> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::graph_t

The type of a graph with TYPE_EDGES edges.

Definition at line 100 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef MAPS_IMPLEMENTATION::template map<TNodeID,TDistance> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::id2dist_map_t [protected]

Definition at line 85 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef MAPS_IMPLEMENTATION::template map<TNodeID,TPrevious> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::id2id_map_t [protected]

Definition at line 86 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef MAPS_IMPLEMENTATION::template map<TNodeID,TPairNodeIDs> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::id2pairIDs_map_t [protected]

Definition at line 84 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef MAPS_IMPLEMENTATION::template map<TNodeID, std::set<TNodeID> > mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::list_all_neighbors_t [protected]

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

Definition at line 83 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
typedef CDirectedTree<const TYPE_EDGES*> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::tree_graph_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 296 of file dijkstra.h.


Constructor & Destructor Documentation

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::CDijkstra ( const graph_t graph,
const TNodeID  source_node_ID,
double(*)(const graph_t &graph, const TNodeID id_from, const TNodeID id_to, const TYPE_EDGES &edge)  functor_edge_weight = NULL,
void(*)(const graph_t &graph, size_t visitedCount)  functor_on_progress = NULL 
) [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::math::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::exceptionIf the source nodeID is not found in the graph

Definition at line 118 of file dijkstra.h.

References ASSERT_, ASSERTMSG_, mrpt::math::CDirectedGraph< TYPE_EDGES >::getAdjacencyMatrix(), mrpt::math::CDirectedGraph< TYPE_EDGES >::getAllNodes(), INVALID_NODEID, MRPT_END, MRPT_START, and THROW_EXCEPTION_CUSTOM_MSG1.


Member Function Documentation

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
const list_all_neighbors_t& mrpt::math::CDijkstra< TYPE_EDGES, 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::math::CDirectedGraph::getAdjacencyMatrix

Definition at line 264 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
const std::set<TNodeID>& mrpt::math::CDijkstra< TYPE_EDGES, 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 258 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
double mrpt::math::CDijkstra< TYPE_EDGES, 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::exceptionOn unknown node ID.

Definition at line 251 of file dijkstra.h.

References THROW_EXCEPTION.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
TNodeID mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::getRootNodeID ( ) const [inline]

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

Definition at line 261 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
void mrpt::math::CDijkstra< TYPE_EDGES, 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 273 of file dijkstra.h.

References ASSERT_.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
void mrpt::math::CDijkstra< TYPE_EDGES, 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 303 of file dijkstra.h.

References ASSERTMSG_, mrpt::math::CDirectedTree< TYPE_EDGES >::clear(), mrpt::math::CDirectedTree< TYPE_EDGES >::edges_to_children, mrpt::format(), and mrpt::math::CDirectedTree< TYPE_EDGES >::root.


Member Data Documentation

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
list_all_neighbors_t mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_allNeighbors [protected]

Definition at line 94 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
const mrpt::math::CDirectedGraph<TYPE_EDGES>& mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_cached_graph [protected]

Definition at line 79 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
id2dist_map_t mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_distances [protected]

All the distances.

Definition at line 89 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
std::map<TNodeID,TDistance> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_distances_non_visited [protected]

Definition at line 90 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
std::set<TNodeID> mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_lstNode_IDs [protected]

Definition at line 93 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
id2pairIDs_map_t mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_prev_arc [protected]

Definition at line 92 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
id2id_map_t mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_prev_node [protected]

Definition at line 91 of file dijkstra.h.

template<class TYPE_EDGES , class MAPS_IMPLEMENTATION = map_traits_stdmap>
const TNodeID mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::m_source_node_ID [protected]

Definition at line 80 of file dijkstra.h.




Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011