Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm. More...

#include <Dijkstra.H>

Inheritance diagram for Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >:

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

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

GT::Node *	compute_min_paths_tree (const GT &g, typename GT::Node *start, GT &tree)
	Computes the spanning tree of all shortest paths from the start node.

void	compute_partial_min_paths_tree (const GT &g, typename GT::Node start, typename GT::Node end, GT &tree)
	Computes the partial spanning tree of all shortest paths from start that contains the path from start to end.

bool	paint_partial_min_paths_tree (const GT &g, typename GT::Node start, typename GT::Node end)
	Paints on graph g the partial shortest paths tree starting from start and stopping when the end node is found.

void	paint_min_paths_tree (const GT &g, typename GT::Node *start)
	Paints on graph g the spanning tree of all shortest paths starting from start.

Distance::Distance_Type	find_min_path (const GT &g, typename GT::Node start, typename GT::Node end, Path< GT > &min_path)
	Computes the shortest path between start and end by painting the graph.

void	operator() (const GT &g, typename GT::Node *s, GT &tree)
	Computes the spanning tree of all shortest paths from a given node according to Dijkstra's algorithm.

Distance::Distance_Type	operator() (const GT &g, typename GT::Node s, typename GT::Node e, Path< GT > &path)

bool	has_computation () const noexcept
	Check if a computation has been performed.

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

GT::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.

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

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

Distance::Distance_Type	get_min_path (const GT &tree, typename GT::Node *end, Path< GT > &path)
	Extracts path from tree to end node.

Distance::Distance_Type	copy_painted_min_paths_tree (GT &g, GT &tree)
	Extracts the painted shortest paths tree and puts it in tree.

Public Member Functions inherited from Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
	Shortest_Path_Base (Distance dist=Distance(), SA __sa=SA())
	Default constructor.

bool	has_computation () const noexcept
	Check if a computation has been performed.

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

GT::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.

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

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

Distance::Distance_Type	copy_painted_min_paths_tree (GT &g, GT &tree)
	Extracts the painted shortest paths tree and puts it in tree.

Distance::Distance_Type	get_min_path (const GT &tree, typename GT::Node *end, Path< GT > &path)
	Extracts path from tree to end node.

Private Types
using	Base = Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >

Private Attributes
SA	sa
	Arc filter.

Heap	heap
	Priority queue.

bool	painted
	Whether graph has been painted.

GT *	ptr_g
	Pointer to the graph.

GT::Node *	s
	Start node.

Additional Inherited Members
Public Types inherited from Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
using	Heap = HeapT< GT, Get_Potential_Arc, Heap_Info >

Protected Member Functions inherited from Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
template<class IN , class IA >
void	init (const GT &g, typename GT::Node *start)
	Initialize algorithm state.

template<class DN , class DA >
void	uninit ()
	Cleanup algorithm state.

Distance::Distance_Type	checked_add (const typename Distance::Distance_Type &a, const typename Distance::Distance_Type &b) const
	Checked addition to prevent integer overflow.

Protected Attributes inherited from Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
SA	sa
	Arc filter.

Get_Potential_Arc	get_pot
	Potential accessor.

Heap	heap
	Priority queue.

bool	painted = false
	Whether graph has been painted.

GT *	ptr_g = nullptr
	Pointer to the graph.

GT::Node *	s = nullptr
	Start node.

Detailed Description

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

Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm.

This class handles Dijkstra's algorithm to compute a tree containing of all shortest paths from a node s of a graph g.

The algorithm uses an internal queue whose length is proportional to the number of nodes in the graph.

Dijkstra's algorithm does not work for graphs with negative weights.

The class receives the following template parameters:

GT: graph type.
Distance<GT>: class reading the weight. It should export the following attributes:
typedef Distance<GT>::Distance_Type: Data type. It represents a weight on an arc.
Distance<GT>::Distance_Type operator()(typename GT::Arc *a): returns the weight of arc a.
Itor<GT, SA>: arc iterator type (defaults to Node_Arc_Iterator).
SA: arc filter for internal iterators.
HeapT<GT, Distance, Access>: priority-queue adapter used by the algorithm (defaults to ArcHeap). It must provide put_arc, get_min_arc, is_empty, and empty, and accept an access functor that maps nodes to heap handles.

Note: To use a Fibonacci heap, pass ArcFibonacciHeap as HeapT.

Warning: This class is not thread-safe. Concurrent calls from multiple threads on the same instance require external synchronization.

See also: Find_Path_Depth_First Floyd_All_Shortest_Paths Bellman_Ford_Min_Spanning_Tree AStar_Min_Path

Definition at line 99 of file Dijkstra.H.

Member Typedef Documentation

◆ Base

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

using Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::Base = Shortest_Path_Base<GT, Distance, Itor, SA, HeapT>

private

Definition at line 102 of file Dijkstra.H.

Constructor & Destructor Documentation

◆ Dijkstra_Min_Paths()

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

Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::Dijkstra_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 142 of file Dijkstra.H.

Member Function Documentation

◆ compute_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>, template< class, class, class > class HeapT = ArcHeap>

GT::Node * Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree	(	const GT &	g,
		typename GT::Node *	start,
		GT &	tree
	)

inline

Computes the spanning tree of all shortest paths from the start node.

Parameters

[in]	g	The graph.
[in]	start	The starting node for all shortest paths.
[out]	tree	The spanning tree of all shortest paths starting from start, mapped via cookies to the graph g.

Returns: Pointer to the tree node corresponding to the start node.

Note: For disconnected graphs, the resulting tree spans only the component reachable from start.

Exceptions

bad_alloc	If there is not enough memory.
domain_error	If start is nullptr or g is empty.

Definition at line 170 of file Dijkstra.H.

References ACC, ah_domain_error_if, ARC_BITS, ARC_DIST, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::checked_add(), Aleph::clear_graph(), GTNodeCommon< NodeInfo >::get_info(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::heap, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, NODE_COOKIE, POT, Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::sa, Aleph::Spanning_Tree, TREEARC, and TREENODE.

Referenced by main(), and Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::operator()().

◆ compute_partial_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>, template< class, class, class > class HeapT = ArcHeap>

void Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		GT &	tree
	)

inline

Computes the partial spanning tree of all shortest paths from start that contains the path from start to end.

Parameters

[in]	g	The graph.
[in]	start	The starting node for all shortest paths.
[in]	end	The destination node.
[out]	tree	The spanning tree of all shortest paths starting from start, mapped via cookies to the graph g.

Exceptions

bad_alloc	If there is not enough memory.
domain_error	If start or end is nullptr, or if g is empty.

Definition at line 254 of file Dijkstra.H.

References ACC, ah_domain_error_if, ARC_BITS, ARC_DIST, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::checked_add(), Aleph::clear_graph(), GTNodeCommon< NodeInfo >::get_info(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::heap, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, NODE_COOKIE, POT, Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::sa, Aleph::Spanning_Tree, TREEARC, and TREENODE.

◆ copy_painted_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>, template< class, class, class > class HeapT = ArcHeap>

Distance::Distance_Type Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::copy_painted_min_paths_tree	(	GT &	g,
		GT &	tree
	)

inline

Extracts the painted shortest paths tree and puts it in tree.

Parameters

[in]	g	The previously painted graph.
[out]	tree	The graph where the spanning tree will be copied.

Returns: The total distance of the spanning tree.

Exceptions

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

Definition at line 566 of file shortest_path_common.H.

◆ 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>, template< class, class, class > class HeapT = ArcHeap>

Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::find_min_path	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		Path< GT > &	min_path
	)

inline

Computes the shortest path between start and end by painting the graph.

This is the version with the lowest memory consumption and probably also the fastest.

Parameters

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

Returns: The total cost of the path from start to end.

Exceptions

bad_alloc If there is not enough memory.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 502 of file Dijkstra.H.

References Aleph::DynList< T >::empty(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::get_min_path(), Aleph::maps(), and Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree().

Referenced by Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::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>, template< class, class, class > class HeapT = ArcHeap>

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

inline

Gets the accumulated distance to a node after painting.

After painting the graph with a shortest path tree, this method traverses the path from the start node to the given node and computes the total distance.

Parameters

[in] node The destination node.

Returns: The accumulated distance from start to node.

Exceptions

domain_error If the graph has not been painted or if node is not reachable from the start node.

Note: Time complexity: O(path_length)

Definition at line 480 of file shortest_path_common.H.

◆ get_graph()

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

GT * Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::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 460 of file shortest_path_common.H.

◆ get_min_path() [1/2]

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

Distance::Distance_Type Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::get_min_path	(	const GT &	tree,
		typename GT::Node *	end,
		Path< GT > &	path
	)

inline

Extracts path from tree to end node.

Parameters

[in]	tree	The spanning tree built by compute_min_paths_tree.
[in]	end	Destination node in the original graph.
[out]	path	Path where result will be stored (in original graph).

Returns: The total cost of the path.

Definition at line 585 of file shortest_path_common.H.

◆ get_min_path() [2/2]

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

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

inline

Extracts a shortest path to end from a previously painted graph.

Takes a graph on which shortest paths have been painted and extracts the shortest path to end, storing it in path.

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

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

Definition at line 531 of file shortest_path_common.H.

Referenced by Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::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>, template< class, class, class > class HeapT = ArcHeap>

GT::Node * Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::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 455 of file shortest_path_common.H.

◆ has_computation()

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

bool Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::has_computation ( ) const

inlinenoexcept

Check if a computation has been performed.

Returns: true if a graph has been processed, false otherwise.

Definition at line 445 of file shortest_path_common.H.

◆ is_painted()

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

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

inlinenoexcept

Check if the graph has been painted.

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

Definition at line 450 of file shortest_path_common.H.

◆ operator()() [1/2]

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

void Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::operator()	(	const GT &	g,
		typename GT::Node *	s,
		GT &	tree
	)

inline

Computes the spanning tree of all shortest paths from a given node according to Dijkstra's algorithm.

Parameters

[in]	g	The graph.
[in]	s	The starting node.
[out]	tree	The spanning tree.

Exceptions

bad_alloc If there is not enough memory.

Definition at line 521 of file Dijkstra.H.

References Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), and Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::s.

◆ operator()() [2/2]

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

Distance::Distance_Type Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::operator()	(	const GT &	g,
		typename GT::Node *	s,
		typename GT::Node *	e,
		Path< GT > &	path
	)

inline

Definition at line 527 of file Dijkstra.H.

References Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::find_min_path(), and Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::s.

◆ 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>, template< class, class, class > class HeapT = ArcHeap>

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

inline

Paints on graph g the spanning tree of all shortest paths starting from start.

Parameters

[in]	g	The graph.
[in]	start	The starting node for shortest paths.

Exceptions

bad_alloc	If there is not enough memory.
domain_error	If start is nullptr or g is empty.

Definition at line 424 of file Dijkstra.H.

References ACC, ah_domain_error_if, ARC_BITS, ARC_DIST, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::checked_add(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::heap, IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::painted, PARENT, POT, Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

◆ paint_partial_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>, template< class, class, class > class HeapT = ArcHeap>

bool Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end
	)