ShortestPaths< graph_t, policy_t > Class Template Reference

The shortest paths from a collection of sources to all points in a graph. More...

#include <Graph.hpp>

Inheritance diagram for ShortestPaths< graph_t, policy_t >:

Public Types
typedef graph_t::node_t	node_t
	The node type. More...
typedef graph_t::neighborhood_t::const_iterator	edge_iter_t
	The iterator type used in the paths. More...

Public Member Functions
void	print_path (std::ostream &os, node_t i) const
	Print shortest path to node i to the output stream. More...
void	compute_with_root (node_t new_root)
	Compute all paths using given root. More...
bool	disconnected (node_t) const
	Checks if node is connected to any one of the sources. More...

Public Attributes
std::vector< std::vector< edge_iter_t > >	paths
	The shortest paths from the sources to all nodes. More...
std::vector< node_t >	root_per_path
	The source of each path. More...

Protected Member Functions
	ShortestPaths (const graph_t &G)
	Constructor computes the shortest paths given the graph. More...

Protected Attributes
const graph_t &	G
	Constant reference to the graph. More...
std::vector< size_t >	distance_policy
	The distance from a source to a node, computed by some policy (eg weight) More...
std::vector< std::pair< node_t, edge_iter_t > >	previous
	previous[i]=(node,edge) where node is 1 step closer to the source and edge connects node to i More...
node_t	root
	The root (source) of the graph being considered. More...

Friends
template<typename _graph , typename _pol >
std::ostream &	operator<< (std::ostream &, const ShortestPaths< _graph, _pol > &)

Detailed Description

template<typename graph_t, typename policy_t>
class mackey::ShortestPaths< graph_t, policy_t >

The shortest paths from a collection of sources to all points in a graph.

Template Parameters

graph_t	The type of directed graph
policy_t	The policy that determines what we are minimizing against (eg total weight or number of color changes)

Implementation of the Dijkstra algorithm (without decrease key), using the policy to determine if we should update the distance
Specify the policy via CRTP: have policy_t inherit from this class Policy examples include MinLength and MinColorsLength

Member Typedef Documentation

node_t

typedef graph_t::node_t node_t

The node type.

edge_iter_t

typedef graph_t::neighborhood_t::const_iterator edge_iter_t

The iterator type used in the paths.

Constructor & Destructor Documentation

ShortestPaths()

ShortestPaths ( const graph_t &  G )

protected

Constructor computes the shortest paths given the graph.

Member Function Documentation

print_path()

void print_path	(	std::ostream &	os,
		node_t	i
	)		const

Print shortest path to node i to the output stream.

compute_with_root()

void compute_with_root

(

node_t

new_root

)

Compute all paths using given root.

disconnected()

bool disconnected

(

node_t

)

const

Checks if node is connected to any one of the sources.

Returns

Returns true if given node is disconnected and false if connected

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  , const ShortestPaths< _graph, _pol > &    )

friend

Member Data Documentation

paths

std::vector<std::vector<edge_iter_t> > paths

The shortest paths from the sources to all nodes.

Stored as a sequence of iterators

Warning

Do not invalidate the iterators by changing the graph!

root_per_path

std::vector<node_t> root_per_path

The source of each path.

G

const graph_t& G

protected

Constant reference to the graph.

distance_policy

std::vector<size_t> distance_policy

protected

The distance from a source to a node, computed by some policy (eg weight)

previous

std::vector<std::pair<node_t, edge_iter_t> > previous

protected

previous[i]=(node,edge) where node is 1 step closer to the source and edge connects node to i

root

node_t root

protected

The root (source) of the graph being considered.

---

The documentation for this class was generated from the following file:

• Graph.hpp