#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 >

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 >

typedef GraphTraits::edge_t shortest_paths< GraphTraits, Path_t >::edge_t

◆ graph_t

template<typename GraphTraits , typename Path_t >

typedef GraphTraits::graph_t shortest_paths< GraphTraits, Path_t >::graph_t

◆ node_t

template<typename GraphTraits , typename Path_t >

typedef GraphTraits::node_t shortest_paths< GraphTraits, Path_t >::node_t

◆ path_t

template<typename GraphTraits , typename Path_t >

typedef Path_t shortest_paths< GraphTraits, Path_t >::path_t

Constructor & Destructor Documentation

◆ shortest_paths()

template<typename GraphTraits , typename Path_t >

shortest_paths< GraphTraits, Path_t >::shortest_paths	(	const graph_t &	graph,
		const node_t *	given_node,
		enum shortest_path_sense	sense )

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, ggc_alloc(), 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 >

int shortest_paths< GraphTraits, Path_t >::get_shortest_distance ( const node_t * other_node ) const

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.

References ggc_alloc().

◆ get_shortest_path()

template<typename GraphTraits , typename Path_t >

Path_t shortest_paths< GraphTraits, Path_t >::get_shortest_path ( const node_t * other_node ) const

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 ggc_alloc(), and SPS_FROM_GIVEN_ORIGIN.