Base class providing common infrastructure for shortest path algorithms. More...

#include <shortest_path_common.H>

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

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

Classes
struct	Arc_Info
	Information stored in arc cookies for painting version. More...

struct	Destroy_Arc
	Arc cleanup for painting version. More...

struct	Destroy_Node
	Node cleanup for painting version. More...

struct	Destroy_Tree_Arc
	Arc cleanup and mapping for tree-building version. More...

struct	Destroy_Tree_Node
	Node cleanup and mapping for tree-building version. More...

struct	Get_Potential_Arc
	Functor to get arc potential for heap ordering. More...

struct	Heap_Info
	Functor to access heap node handle from node cookie. More...

struct	Initialize_Arc
	Arc initialization for painting version. More...

struct	Initialize_Node
	Node initialization for painting version. More...

struct	Initialize_Tree_Arc
	Arc initialization for tree-building version. More...

struct	Initialize_Tree_Node
	Node initialization for tree-building version. More...

struct	Node_Info
	Information stored in node cookies for painting version. More...

struct	Total
	Distance totalizer class for path copying. More...

struct	Tree_Arc_Info
	Extended arc info with tree arc mapping. More...

struct	Tree_Node_Info
	Extended node info with tree node mapping. More...

Public Types
using	Heap = HeapT< GT, Get_Potential_Arc, Heap_Info >

Public Member Functions
	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.

Protected Member Functions
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
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, template< typename, class > class Itor, class SA, template< class, class, class > class HeapT>
class Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >

Base class providing common infrastructure for shortest path algorithms.

This template class encapsulates shared functionality between Dijkstra's algorithm, A*, and similar shortest path algorithms. It provides:

Cookie structures for storing algorithm state in nodes/arcs
Initialize/Destroy functors for memory management
Common state management (init/uninit, painted flag, etc.)
Distance calculation from painted paths

Template Parameters

GT	Graph type.
Distance	Distance accessor functor.
Itor	Arc iterator template.
SA	Arc filter for iterators.
HeapT	Priority queue template.

Definition at line 164 of file shortest_path_common.H.

Member Typedef Documentation

◆ Heap

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

using Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Heap = HeapT<GT, Get_Potential_Arc, Heap_Info>

Definition at line 354 of file shortest_path_common.H.

Constructor & Destructor Documentation

◆ Shortest_Path_Base()

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

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

inline

Default constructor.

Parameters

dist	Distance functor for arc weights.
__sa	Arc filter for iterators.

Definition at line 431 of file shortest_path_common.H.

Member Function Documentation

◆ checked_add()

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

Distance::Distance_Type Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::checked_add	(	const typename Distance::Distance_Type &	a,
		const typename Distance::Distance_Type &	b
	)		const

inlineprotected

Checked addition to prevent integer overflow.

Parameters

a	First operand.
b	Second operand.

Returns: Sum of a and b.

Exceptions

std::overflow_error If overflow would occur.

Definition at line 415 of file shortest_path_common.H.

References Aleph::shortest_path_detail::checked_add().

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

◆ copy_painted_min_paths_tree()

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

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.

References ah_domain_error_if, Aleph::maps(), and Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::painted.

◆ get_distance()

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

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.

References ah_domain_error_if, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::maps(), NODE_COOKIE, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::painted, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::s, Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

◆ get_graph()

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

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.

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

◆ get_min_path() [1/2]

template<class GT , class Distance , template< typename, class > class Itor, class SA , template< class, class, class > class HeapT>

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).