shortest_paths.hpp File Reference

Shortest-path result types, wrappers, and deprecated compatibility aliases. More...

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include "graph.hpp"

Include dependency graph for shortest_paths.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	nxpp::SingleSourceShortestPathResult< NodeID, Distance >
	Result container for single-source shortest-path routines. More...

Typedefs
template<typename Distance >
using	nxpp::shortest_path_calc_type = std::conditional_t< std::is_integral_v< Distance >, double, Distance >

Functions
template<typename Distance >
Distance	nxpp::normalize_weighted_distance (Distance value)
template<typename Distance , typename CalcDistance >
Distance	nxpp::convert_shortest_path_distance (CalcDistance value)
template<typename GraphWrapper >
auto	nxpp::shortest_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
	Deprecated free-function alias for G.shortest_path(source, target).
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_shortest_paths (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::single_source_dijkstra (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper >
auto	nxpp::shortest_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
	Deprecated free-function alias for G.shortest_path(source, target, weight).
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
template<typename GraphWrapper >
double	nxpp::shortest_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
	Deprecated free-function alias for G.shortest_path_length(source, target).
template<typename GraphWrapper >
double	nxpp::shortest_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
	Deprecated free-function alias for G.shortest_path_length(source, target, weight).
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dijkstra_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::bellman_ford_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::bellman_ford_shortest_paths (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::single_source_bellman_ford (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::bellman_ford_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::bellman_ford_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::bellman_ford_path_length (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &weight)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::dag_shortest_paths (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::floyd_warshall_all_pairs_shortest_paths (const GraphWrapper &G)
template<typename GraphWrapper > requires (GraphWrapper::has_builtin_edge_weight)
auto	nxpp::floyd_warshall_all_pairs_shortest_paths_map (const GraphWrapper &G)

Detailed Description

Shortest-path result types, wrappers, and deprecated compatibility aliases.

Function Documentation

shortest_path() [1/2]

template<typename GraphWrapper >

auto nxpp::shortest_path	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id
	)

Deprecated free-function alias for G.shortest_path(source, target).

Parameters

G	Graph wrapper on which to compute the unweighted shortest path.
source_id	Source node ID.
target_id	Target node ID.

Returns

The same node-path vector returned by G.shortest_path(...).

References nxpp::shortest_path().

Referenced by nxpp::shortest_path(), nxpp::shortest_path(), nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::shortest_path(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::shortest_path_length().

shortest_path() [2/2]

template<typename GraphWrapper >

auto nxpp::shortest_path	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	weight
	)

Deprecated free-function alias for G.shortest_path(source, target, weight).

Parameters

G	Graph wrapper on which to compute the weighted shortest path.
source_id	Source node ID.
target_id	Target node ID.
weight	Weight selector string forwarded to the graph method.

Returns

The same node-path vector returned by G.shortest_path(...).

References nxpp::shortest_path().

shortest_path_length() [1/2]

template<typename GraphWrapper >

double nxpp::shortest_path_length	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id
	)

Deprecated free-function alias for G.shortest_path_length(source, target).

Parameters

G	Graph wrapper on which to compute the unweighted path length.
source_id	Source node ID.
target_id	Target node ID.

Returns

The same path length returned by G.shortest_path_length(...).

References nxpp::shortest_path_length().

Referenced by nxpp::shortest_path_length(), nxpp::shortest_path_length(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::shortest_path_length().

shortest_path_length() [2/2]

template<typename GraphWrapper >

double nxpp::shortest_path_length	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	weight
	)

Deprecated free-function alias for G.shortest_path_length(source, target, weight).

Parameters

G	Graph wrapper on which to compute the weighted path length.
source_id	Source node ID.
target_id	Target node ID.
weight	Weight selector string forwarded to the graph method.

Returns

The same path length returned by G.shortest_path_length(...).

References nxpp::shortest_path_length().