#include <mrpt/math/dijkstra.h>
Classes | |
struct | TDistance |
struct | TPrevious |
Public Types | |
typedef size_t | TNodeID |
The type for node IDs. | |
typedef std::list< std::pair < TNodeID, TNodeID > > | TListEdges |
A list of edges used to describe a path on the graph. | |
Public Member Functions | |
CDijkstra (const mrpt::math::CDirectedGraph< TYPE_EDGES > &graph, const TNodeID &source_node_ID, double(*functor_edge_weight)(const TYPE_EDGES &edge)=NULL) | |
Constructor, which takes the input graph and executes the entire Dijkstra algorithm. | |
void | getShortestPathTo (const TNodeID target_node_ID, TListEdges &out_path) const |
Returns the shortest path between the source node passed in the constructor and the given target node. | |
Static Public Attributes | |
static const TNodeID | INVALID_TNODEID = static_cast<TNodeID>(-1) |
Protected Attributes | |
std::map< TNodeID, TDistance > | d |
std::map< TNodeID, TPrevious > | previous |
std::map< TNodeID, std::pair < TNodeID, TNodeID > > | previous_arcs |
std::map< TNodeID, bool > | visited |
TNodeID | m_source_node_ID |
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 very efficiently.
Graphs are represented by instances of (or classes derived from) mrpt::math::CDirectedGraph , and node's IDs are size_t values, although the type TNodeID is also provided for clarity.
See this page on the wiki for a complete example.
Definition at line 51 of file dijkstra.h.
typedef std::list<std::pair<TNodeID,TNodeID> > mrpt::math::CDijkstra< TYPE_EDGES >::TListEdges |
typedef size_t mrpt::math::CDijkstra< TYPE_EDGES >::TNodeID |
mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra | ( | const mrpt::math::CDirectedGraph< TYPE_EDGES > & | graph, | |
const TNodeID & | source_node_ID, | |||
double(*)(const TYPE_EDGES &edge) | functor_edge_weight = NULL | |||
) | [inline] |
Constructor, which takes the input graph and executes the entire Dijkstra algorithm.
The graph is given by its directed edges with a class such as:
map< pair<size_t,size_t>, TYPE_EDGES> myGraph;
If a function "functor_edge_weight" is provided which returns the weight of any given edge, then it will be used. Otherwise, all edges will weight equally.
std::exception | If the source nodeID is not found in the graph |
Definition at line 99 of file dijkstra.h.
References ASSERT_, mrpt::math::CDijkstra< TYPE_EDGES >::d, mrpt::math::CDirectedGraph< TYPE_EDGES >::edges, mrpt::math::CDirectedGraph< TYPE_EDGES >::end(), mrpt::math::CDirectedGraph< TYPE_EDGES >::getAllNodes(), mrpt::math::CDirectedGraph< TYPE_EDGES >::getNeighborsOf(), MRPT_TRY_END, MRPT_TRY_START, mrpt::math::CDijkstra< TYPE_EDGES >::previous, mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs, THROW_EXCEPTION_CUSTOM_MSG1, and mrpt::math::CDijkstra< TYPE_EDGES >::visited.
void mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo | ( | const TNodeID | target_node_ID, | |
TListEdges & | 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.
Definition at line 198 of file dijkstra.h.
References ASSERT_, mrpt::math::CDijkstra< TYPE_EDGES >::m_source_node_ID, mrpt::math::CDijkstra< TYPE_EDGES >::previous, and mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs.
std::map<TNodeID,TDistance> mrpt::math::CDijkstra< TYPE_EDGES >::d [protected] |
Definition at line 78 of file dijkstra.h.
Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra().
const TNodeID mrpt::math::CDijkstra< TYPE_EDGES >::INVALID_TNODEID = static_cast<TNodeID>(-1) [static] |
Definition at line 57 of file dijkstra.h.
TNodeID mrpt::math::CDijkstra< TYPE_EDGES >::m_source_node_ID [protected] |
Definition at line 82 of file dijkstra.h.
Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo().
std::map<TNodeID,TPrevious> mrpt::math::CDijkstra< TYPE_EDGES >::previous [protected] |
Definition at line 79 of file dijkstra.h.
Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra(), and mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo().
std::map<TNodeID, std::pair<TNodeID,TNodeID> > mrpt::math::CDijkstra< TYPE_EDGES >::previous_arcs [protected] |
Definition at line 80 of file dijkstra.h.
Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra(), and mrpt::math::CDijkstra< TYPE_EDGES >::getShortestPathTo().
std::map<TNodeID, bool> mrpt::math::CDijkstra< TYPE_EDGES >::visited [protected] |
Definition at line 81 of file dijkstra.h.
Referenced by mrpt::math::CDijkstra< TYPE_EDGES >::CDijkstra().
Page generated by Doxygen 1.5.9 for MRPT 0.7.1 SVN: at Mon Aug 17 22:21:34 EDT 2009 |