Compute the all-pairs shortest path distance matrix and the path reconstruction matrix for a graph g using the Floyd-Warshall algorithm. More...

#include <Floyd_Warshall.H>

Collaboration diagram for Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >:

[legend]

Public Member Functions
constexpr bool	has_negative_cycle () const noexcept
	Check if the graph contains a negative cycle.

const DynMatrix< long > &	get_path_mat () const noexcept
	Get the path reconstruction matrix.

const DynMatrix< Distance_Type > &	get_dist_mat () const noexcept
	Get the distance matrix.

DynArray< Node * >	get_nodes () const noexcept
	Get the array of graph nodes.

Node *	select_node (long i) const noexcept
	Get the graph node at a given matrix index.

long	index_node (Node *p) const
	Return the adjacency-matrix index corresponding to node `p`.

	Floyd_All_Shortest_Paths (const GT &__g, SA &__sa)
	Construct Floyd-Warshall solver for all-pairs shortest paths.

	Floyd_All_Shortest_Paths (const GT &g, SA &&sa=SA())
	Construct Floyd-Warshall solver with rvalue arc filter.

std::string	entry (const Distance_Type &e) const
	Convert a distance value to string representation.

Path< GT >	get_min_path (const long src_idx, const long tgt_idx) const
	Reconstruct the shortest path between two nodes by matrix indices.

Path< GT >	get_min_path (typename GT::Node src, typename GT::Node tgt) const
	Reconstruct the shortest path between two nodes.

Static Public Member Functions
static void	print (const DynMatrix< Distance_Type > &dist)
	Print a distance matrix to standard output.

Private Types
typedef GT::Node	Node

typedef GT::Arc	Arc

typedef Distance::Distance_Type	Distance_Type

Private Attributes
DynArray< Node * >	nodes

GT &	g

const long	n

const Distance_Type	Inf

bool	negative_cycle = false

DynMatrix< long >	path_mat

DynMatrix< Distance_Type >	dist

SA &	sa

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >

Compute the all-pairs shortest path distance matrix and the path reconstruction matrix for a graph g using the Floyd-Warshall algorithm.

This class computes two matrices:

dist: matrix of shortest-path costs between all node pairs. Each entry dist(i,j) stores the minimum total cost to go from the node with index i to the node with index j.
path: path reconstruction matrix. Each entry path(i,j) stores the next node index on a shortest path from i to j. By iterating through path(k,j) you can reconstruct the path. The helper get_min_path() performs this reconstruction.

Floyd-Warshall supports negative edge weights, but it does not work correctly if the graph contains negative cycles. Use Bellman-Ford based algorithms if you suspect negative cycles.

Template parameters:

GT: graph type.
Distance<GT>: arc weight accessor that must provide:
1. Distance<GT>::Distance_Type: the weight type.
2. Distance_Type operator()(typename GT::Arc *a): returns the weight of arc a.
3. Distance<GT>::Max_Distance: a sentinel maximum value that is treated as infinity.
4. Distance<GT>::Zero_Distance: additive identity (usually 0).
SA: arc filter.

See also: dijkstra_min_spanning_tree() dijkstra_min_path() find_path_depth_first() find_min_path() bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definition at line 149 of file Floyd_Warshall.H.

Member Typedef Documentation

◆ Arc

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

typedef GT::Arc Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Arc

private

Definition at line 152 of file Floyd_Warshall.H.

◆ Distance_Type

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

typedef Distance::Distance_Type Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Distance_Type

private

Definition at line 153 of file Floyd_Warshall.H.

◆ Node

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

typedef GT::Node Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Node

private

Definition at line 151 of file Floyd_Warshall.H.

Constructor & Destructor Documentation

◆ Floyd_All_Shortest_Paths() [1/2]

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Floyd_All_Shortest_Paths	(	const GT &	__g,
		SA &	__sa
	)

inline

Construct Floyd-Warshall solver for all-pairs shortest paths.

Computes shortest distances and path reconstruction matrices for all pairs of nodes in the graph using the Floyd-Warshall algorithm. Handles negative weights but detects negative cycles.

Parameters

[in]	__g	Input graph (will be treated as const).
[in]	__sa	Arc filter for considering which arcs to include.

Exceptions

std::invalid_argument	if graph has no nodes.
std::bad_alloc	if memory allocation fails.

Definition at line 242 of file Floyd_Warshall.H.

◆ Floyd_All_Shortest_Paths() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Floyd_All_Shortest_Paths	(	const GT &	g,
		SA &&	sa = `SA()`
	)

inline

Construct Floyd-Warshall solver with rvalue arc filter.

Parameters

[in]	g	Input graph.
[in]	sa	Arc filter (moved).

Definition at line 351 of file Floyd_Warshall.H.

Member Function Documentation

◆ entry()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

std::string Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::entry ( const Distance_Type & e ) const

inline

Convert a distance value to string representation.

Parameters

[in] e Distance value to convert.

Returns: String representation ("Inf" for infinite distances).

Definition at line 360 of file Floyd_Warshall.H.

References Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Inf, and Aleph::maps().

◆ get_dist_mat()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

const DynMatrix< Distance_Type > & Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_dist_mat ( ) const

inlinenoexcept

Get the distance matrix.

The distance matrix contains shortest distances between all pairs of nodes. Entry (i,j) contains the shortest distance from node i to node j.

Returns: Const reference to the distance matrix.

Definition at line 190 of file Floyd_Warshall.H.

References Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::dist.

◆ get_min_path() [1/2]

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_min_path	(	const long	src_idx,
		const long	tgt_idx
	)		const

inline

Reconstruct the shortest path between two nodes by matrix indices.

Uses the path reconstruction matrix to build the shortest path from source to target node.

Parameters

[in]	src_idx	Matrix index of source node.
[in]	tgt_idx	Matrix index of target node.

Returns: Path object containing the shortest path.

Exceptions

std::out_of_range if indices are invalid.

Definition at line 405 of file Floyd_Warshall.H.

References ah_out_of_range_error_if, Aleph::Path< GT >::append_directed(), Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::dist, Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::g, Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::Inf, Aleph::maps(), Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::n, Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::nodes, and Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::path_mat.

Referenced by Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_min_path().

◆ get_min_path() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_min_path	(	typename GT::Node *	src,
		typename GT::Node *	tgt
	)		const

inline

Reconstruct the shortest path between two nodes.

Convenience method that accepts node pointers instead of indices.

Parameters

[in]	src	Pointer to source node.
[in]	tgt	Pointer to target node.

Returns: Path object containing the shortest path.

Exceptions

std::invalid_argument	if either node pointer is null.
std::domain_error	if either node is not found in the graph.

Definition at line 446 of file Floyd_Warshall.H.

References Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_min_path(), and Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::index_node().

◆ get_nodes()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

DynArray< Node * > Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_nodes ( ) const

inlinenoexcept

Get the array of graph nodes.

Returns the sorted array of node pointers used for matrix indexing.

Returns: Const copy of the node pointer array.

Definition at line 202 of file Floyd_Warshall.H.

References Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::nodes.

◆ get_path_mat()

template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>

const DynMatrix< long > & Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >::get_path_mat ( ) const

inlinenoexcept

Get the path reconstruction matrix.

The path matrix contains intermediate nodes for shortest path reconstruction. Entry (i,j) contains the next node index on the shortest path from i to j.