shortest_paths< GraphTraits, Path_t > Class Template Reference
#include <shortest-paths.h>
Collaboration diagram for shortest_paths< GraphTraits, Path_t >:
Public Types | |
| typedef GraphTraits::graph_t | graph_t |
| typedef GraphTraits::node_t | node_t |
| typedef GraphTraits::edge_t | edge_t |
| typedef Path_t | path_t |
Public Member Functions | |
| shortest_paths (const graph_t &graph, const node_t *given_node, enum shortest_path_sense sense) | |
| path_t | get_shortest_path (const node_t *other_node) const |
| int | get_shortest_distance (const node_t *other_node) const |
Private Attributes | |
| const graph_t & | m_graph |
| enum shortest_path_sense | m_sense |
| auto_vec< int > | m_dist |
| auto_vec< const edge_t * > | m_best_edge |
Detailed Description
template<typename GraphTraits, typename Path_t>
class shortest_paths< GraphTraits, Path_t >
class shortest_paths< GraphTraits, Path_t >
A record of the shortest path for each node relative to a special "given node", either: SPS_FROM_GIVEN_ORIGIN: from the given origin node to each node in a graph, or SPS_TO_GIVEN_TARGET: from each node in a graph to the given target node. The constructor runs Dijkstra's algorithm, and the results are stored in this class.
Member Typedef Documentation
◆ edge_t
template<typename GraphTraits , typename Path_t >
| GraphTraits::edge_t shortest_paths< GraphTraits, Path_t >::edge_t |
◆ graph_t
template<typename GraphTraits , typename Path_t >
| GraphTraits::graph_t shortest_paths< GraphTraits, Path_t >::graph_t |
◆ node_t
template<typename GraphTraits , typename Path_t >
| GraphTraits::node_t shortest_paths< GraphTraits, Path_t >::node_t |
◆ path_t
template<typename GraphTraits , typename Path_t >
| Path_t shortest_paths< GraphTraits, Path_t >::path_t |
Constructor & Destructor Documentation
◆ shortest_paths()
template<typename GraphTraits , typename Path_t >
|
inline |
shortest_paths's constructor. Use Dijkstra's algorithm relative to GIVEN_NODE to populate m_dist and m_best_edge with enough information to be able to generate Path_t instances to give the shortest path... SPS_FROM_GIVEN_ORIGIN: to each node in a graph from the origin node, or SPS_TO_GIVEN_TARGET: from each node in a graph to the target node.
References FOR_EACH_VEC_ELT, gcc_assert, i, INT_MAX, shortest_paths< GraphTraits, Path_t >::m_best_edge, shortest_paths< GraphTraits, Path_t >::m_dist, shortest_paths< GraphTraits, Path_t >::m_graph, shortest_paths< GraphTraits, Path_t >::m_sense, NULL, queue, and SPS_FROM_GIVEN_ORIGIN.
Member Function Documentation
◆ get_shortest_distance()
template<typename GraphTraits , typename Path_t >
|
inline |
Get the shortest distance... SPS_FROM_GIVEN_ORIGIN: ...from given origin node to OTHER_NODE SPS_TO_GIVEN_TARGET: ...from OTHER_NODE to given target node.
◆ get_shortest_path()
template<typename GraphTraits , typename Path_t >
|
inline |
Generate an Path_t instance giving the shortest path between OTHER_NODE and the given node. SPS_FROM_GIVEN_ORIGIN: shortest path from given origin node to OTHER_NODE SPS_TO_GIVEN_TARGET: shortest path from OTHER_NODE to given target node. If no such path exists, return an empty path.
References SPS_FROM_GIVEN_ORIGIN.
Field Documentation
◆ m_best_edge
template<typename GraphTraits , typename Path_t >
|
private |
Referenced by shortest_paths< GraphTraits, Path_t >::shortest_paths().
◆ m_dist
template<typename GraphTraits , typename Path_t >
|
private |
Referenced by shortest_paths< GraphTraits, Path_t >::shortest_paths().
◆ m_graph
template<typename GraphTraits , typename Path_t >
|
private |
Referenced by shortest_paths< GraphTraits, Path_t >::shortest_paths().
◆ m_sense
template<typename GraphTraits , typename Path_t >
|
private |
Referenced by shortest_paths< GraphTraits, Path_t >::shortest_paths().
The documentation for this class was generated from the following file:
