Dial's algorithm for shortest paths with integer weights. More...

#include <Dial.H>

Collaboration diagram for Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >:

Classes
class	Dial_Init_Guard
	RAII guard for Dial initialization and cleanup. More...

struct	Node_Info

Public Types
using	Distance_Type = typename Distance::Distance_Type

using	Node = typename GT::Node

using	Arc = typename GT::Arc

Public Member Functions
	Dial_Min_Paths (Distance dist=Distance(), SA __sa=SA())
	Constructor.

bool	is_painted () const noexcept
	Check if the graph has been painted.

Node *	get_start_node () const noexcept
	Get the start node of the last computation.

GT *	get_graph () const noexcept
	Get the graph of the last computation.

void	paint_min_paths_tree (const GT &g, Node *start)
	Paints the shortest paths tree on the graph from start.

Distance_Type	get_distance (Node *node)
	Gets the accumulated distance to a node after painting.

Distance_Type	get_min_path (Node *end, Path< GT > &path)
	Extracts a shortest path from a previously painted graph.

Distance_Type	find_min_path (const GT &g, Node start, Node end, Path< GT > &path)
	Computes the shortest path from start to end.

Distance_Type	operator() (const GT &g, Node start, Node end, Path< GT > &path)
	Computes shortest path (operator interface).

Private Member Functions
void	reset_state_after_failure () noexcept

void	init (const GT &g)

void	uninit_paint ()

void	uninit_discard ()

Distance_Type	find_max_weight (const GT &g)

void	run_dial (const GT &g, Node start, Node end=nullptr)

Private Attributes
SA	sa

Distance	distance

bool	painted = false

GT *	ptr_g = nullptr

Node *	s = nullptr

Static Private Attributes
static constexpr size_t	Max_Sane_Buckets = 16u * 1024u * 1024u

static constexpr Distance_Type	Inf

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >

Dial's algorithm for shortest paths with integer weights.

This class computes shortest paths in graphs where every edge weight is a non-negative integer.

Dial's algorithm runs in O(V*C + E) time vs Dijkstra with a heap in O((V+E) log V), where C is the maximum edge weight. Use Dial when V*C + E << (V+E) log V (equivalently V*C << (V+E) log V). As a practical rule of thumb, Dial is especially effective on sparse graphs (small E) with small integer edge weights (small C).

The class receives the following template parameters:

GT: graph type (List_Graph, List_SGraph, Array_Graph, etc.).
Distance: class reading the weight from an arc. Must export Distance_Type (which must be integral) and operator()(Arc*).
Itor: arc iterator template (defaults to Node_Arc_Iterator).
SA: arc filter for internal iterators.

Warning: All arc weights must be non-negative integers. The Distance_Type must be an integral type.

Note: This algorithm works for both directed and undirected graphs.

See also: Dijkstra_Min_Paths For general non-negative weights.; Zero_One_BFS For 0/1 weights.

Definition at line 125 of file Dial.H.

Member Typedef Documentation

◆ Arc

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Arc = typename GT::Arc

Definition at line 130 of file Dial.H.

◆ Distance_Type

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Distance_Type = typename Distance::Distance_Type

Definition at line 128 of file Dial.H.

◆ Node

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Node = typename GT::Node

Definition at line 129 of file Dial.H.

Constructor & Destructor Documentation

◆ Dial_Min_Paths()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Dial_Min_Paths	(	Distance	dist = `Distance()`,
		SA	__sa = `SA()`
	)

inline

Constructor.

Parameters

[in]	dist	Distance functor for arc weights.
[in]	__sa	Arc filter for iterators.

Definition at line 406 of file Dial.H.

Member Function Documentation

◆ find_max_weight()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::find_max_weight ( const GT & g )

inlineprivate

Definition at line 264 of file Dial.H.

References ah_domain_error_if, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), and w.

Referenced by Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::run_dial().

◆ find_min_path()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::find_min_path	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Computes the shortest path from start to end.

Paints the graph (stopping early when end is found) and extracts the path.

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path (empty if no path exists).

Returns: The total cost, or max value if no path exists.

Exceptions

domain_error	If start or end is nullptr, g is empty, or any arc weight is negative.
overflow_error	If maximum possible distance exceeds Distance_Type range or during distance accumulation.
runtime_error	If bucket count exceeds safety limit.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(V + E + V*C) where C is max edge weight.

Definition at line 547 of file Dial.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Path< GT >::empty(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::get_min_path(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Inf, Aleph::init, IS_NODE_VISITED, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::painted, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::run_dial(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::s, Aleph::Spanning_Tree, and Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::uninit_paint().

Referenced by Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::operator()().

◆ get_distance()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::get_distance ( Node * node )

inline

Gets the accumulated distance to a node after painting.

Parameters

[in] node The destination node.

Returns: The shortest distance from start to node.

Exceptions

domain_error If the graph has not been painted, node is null, node is not reachable from the start, or path reconstruction fails.

Note: Time complexity: O(path_length)

Definition at line 471 of file Dial.H.

References ah_domain_error_if, Aleph::and, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_connected_node(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_COOKIE, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::painted, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::ptr_g, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::s, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::sa, and Aleph::Spanning_Tree.

◆ get_graph()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GT * Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::get_graph ( ) const

inlinenoexcept

Get the graph of the last computation.

Returns: Pointer to the graph, or nullptr if no computation done.

Definition at line 425 of file Dial.H.

References Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::ptr_g.

◆ get_min_path()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::get_min_path	(	Node *	end,
		Path< GT > &	path
	)

inline

Extracts a shortest path from a previously painted graph.

Parameters

[in]	end	Destination node of the path.
[out]	path	Path where the shortest path will be stored.

Returns: The total cost of the path.

Exceptions

domain_error	If the graph has not been painted.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(path_length)

Definition at line 520 of file Dial.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::painted, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::ptr_g, and Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::s.

Referenced by Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::find_min_path().

◆ get_start_node()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Node * Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::get_start_node ( ) const

inlinenoexcept

Get the start node of the last computation.

Returns: Pointer to the start node, or nullptr if no computation done.

Definition at line 420 of file Dial.H.

References Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::s.

◆ init()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::init ( const GT & g )

inlineprivate

Definition at line 208 of file Dial.H.

References NODE_COOKIE, Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::ptr_g, GraphCommon< GT, Node, Arc >::reset_bit(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::reset_state_after_failure(), Aleph::Spanning_Tree, and Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::uninit_discard().

◆ is_painted()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::is_painted ( ) const

inlinenoexcept

Check if the graph has been painted.

Returns: true if a painting method was called, false otherwise.

Definition at line 415 of file Dial.H.

References Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::painted.

◆ operator()()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::operator()	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Computes shortest path (operator interface).

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path.

Returns: The total cost, or max value if no path exists.

Exceptions

domain_error	If start or end is nullptr, g is empty, or any arc weight is negative.
overflow_error	If maximum possible distance exceeds Distance_Type range or during distance accumulation.
runtime_error	If bucket count exceeds safety limit.
bad_alloc	If there is not enough memory.

Definition at line 587 of file Dial.H.

References Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::find_min_path().

◆ paint_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::paint_min_paths_tree	(	const GT &	g,
		Node *	start
	)

inline

Paints the shortest paths tree on the graph from start.

After calling this method, NODE_COOKIE(p) stores the parent node in the shortest path tree, and the Spanning_Tree bit is set on nodes and arcs that belong to the tree.

Parameters

[in]	g	The graph.
[in]	start	The starting node.

Exceptions

domain_error	If start is nullptr, g is empty, or any arc weight is negative.
overflow_error	If maximum possible distance exceeds Distance_Type range or during distance accumulation.
runtime_error	If bucket count exceeds safety limit.
bad_alloc	If there is not enough memory.