A* algorithm for finding the shortest path between two nodes. More...

#include <AStar.H>

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

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

Public Member Functions
	AStar_Min_Path (Distance dist=Distance(), Heuristic __heuristic=Heuristic(), SA __sa=SA())
	Constructor.

GT::Node *	compute_partial_path (const GT &g, typename GT::Node start, typename GT::Node end, GT &tree)
	Computes the shortest path from start to end using A*.

bool	paint_partial_path (const GT &g, typename GT::Node start, typename GT::Node end)
	Paints the shortest path from start to end on the graph using A*.

Distance::Distance_Type	find_path (const GT &g, typename GT::Node start, typename GT::Node end, Path< GT > &path)
	Finds the shortest path from start to end using A*.

GT::Node *	compute_path (const GT &g, typename GT::Node start, typename GT::Node end, GT &tree)
	Alias for compute_partial_path (backward compatibility).

bool	paint_path (const GT &g, typename GT::Node start, typename GT::Node end)
	Alias for paint_partial_path (backward compatibility).

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 from start to end (without a heuristic).

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 (without heuristic).

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 (without heuristic).

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

void	operator() (const GT &g, typename GT::Node *s, GT &tree)
	Computes the spanning tree of all shortest paths.

Distance::Distance_Type	operator() (const GT &g, typename GT::Node s, typename GT::Node e, Path< GT > &path)
	Finds shortest path using A* heuristic.

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 Member Functions
void	check_heuristic_admissibility (typename GT::Node node, typename GT::Node goal, const typename Distance::Distance_Type &actual_cost)

Private Attributes
Heuristic	heuristic

bool	validate_heuristic = true

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>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>, template< class, class, class > class HeapT = ArcHeap>
class Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >

A* algorithm for finding the shortest path between two nodes.

This class implements the A* algorithm to find the shortest path from a source node start to a destination node end in a weighted graph.

A* uses a heuristic function h(n) that estimates the cost from node n to the goal. The algorithm expands nodes in order of f(n) = g(n) + h(n) where g(n) is the actual cost from start to n.

For the algorithm to find optimal paths, the heuristic must be admissible (never overestimate the true cost) and consistent (satisfy h(n) <= d(n,m) + h(m) for any edge n->m).

This class also provides Dijkstra-compatible methods (compute_min_paths_tree, paint_min_paths_tree) that use zero heuristic for computing all shortest paths from a source.

Method Categories

A* Methods (with heuristic, for single-target search):

find_path() - Find shortest path start->end (recommended)
compute_partial_path() - Same but builds tree structure
paint_partial_path() - Same but marks on original graph

Dijkstra Methods (no heuristic, for multi-target search):

find_min_path() - Find path without heuristic
compute_min_paths_tree() - Build complete shortest paths tree
paint_min_paths_tree() - Mark complete tree on graph
compute_partial_min_paths_tree() - Build partial tree until target found
paint_partial_min_paths_tree() - Mark partial tree on graph

The "partial" methods stop as soon as the target node is reached, while "complete" methods explore all reachable nodes.

The class receives the following template parameters:

GT: graph type.
Distance<GT>: class reading the weight.
Heuristic<GT, Distance>: heuristic functor.
Itor<GT, SA>: arc iterator type (defaults to Node_Arc_Iterator).
SA: arc filter for internal iterators.
HeapT<GT, Distance, Access>: priority-queue adapter.

Note: To use a Fibonacci heap, pass ArcFibonacciHeap as HeapT.; Reusability: This class can be reused for multiple searches. Each call to find_path(), compute_*(), or paint_*() clears state.

Warning: This class is not thread-safe. Concurrent calls require external synchronization.; Negative weights: This algorithm does NOT support graphs with negative edge weights. Use Bellman-Ford for such graphs. Behavior with negative weights is undefined.; Inadmissible heuristics: If the heuristic overestimates (violates admissibility), A* may return suboptimal paths. In debug mode, validation checks are performed when possible.

See also: Dijkstra_Min_Paths Floyd_All_Shortest_Paths Bellman_Ford_Min_Paths

Definition at line 155 of file AStar.H.

Member Typedef Documentation

◆ Base

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

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

private

Definition at line 158 of file AStar.H.

Constructor & Destructor Documentation

◆ AStar_Min_Path()

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

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

inline

Constructor.

Parameters

[in]	dist	Distance functor for arc weights.
[in]	__heuristic	Heuristic functor for estimating remaining cost.
[in]	__sa	Arc filter for iterators.

Definition at line 225 of file AStar.H.

Member Function Documentation

◆ check_heuristic_admissibility()

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

void Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::check_heuristic_admissibility	(	typename GT::Node *	node,
		typename GT::Node *	goal,
		const typename Distance::Distance_Type &	actual_cost
	)

inlineprivate

Definition at line 199 of file AStar.H.

References Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heuristic, Aleph::maps(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::validate_heuristic.

◆ compute_min_paths_tree()

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

GT::Node * Aleph::AStar_Min_Path< GT, Distance, Heuristic, 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.

This method uses zero heuristic, making it equivalent to Dijkstra's algorithm. Use this when you need the complete shortest paths tree from a source to all reachable nodes.

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 525 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APOT, ARC_BITS, ATREEARC, ATREENODE, 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::AStar_Min_Path< GT, Distance, Heuristic, 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, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::operator()().

◆ compute_partial_min_paths_tree()

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

void Aleph::AStar_Min_Path< GT, Distance, Heuristic, 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 from start to end (without a heuristic).

Uses Dijkstra's algorithm (zero heuristic) but stops when end is reached.

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	tree	The partial spanning tree.

Exceptions

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

Definition at line 609 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APOT, ARC_BITS, ATREEARC, ATREENODE, 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::AStar_Min_Path< GT, Distance, Heuristic, 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, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

◆ compute_partial_path()

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

GT::Node * Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		GT &	tree
	)

inline

Computes the shortest path from start to end using A*.

Builds a partial spanning tree containing the shortest path from start to end, stopping as soon as end is reached.

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	tree	The partial tree containing the path, mapped to g.

Returns: Pointer to tree node corresponding to end, or nullptr if no path exists.

Exceptions

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

Definition at line 261 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APOT, ARC_BITS, ATREEARC, ATREENODE, 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(), h, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heap, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heuristic, 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, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_path().

◆ compute_path()

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

GT::Node * Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_path	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		GT &	tree
	)

inline

Alias for compute_partial_path (backward compatibility).

Definition at line 492 of file AStar.H.

References Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path().

◆ copy_painted_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_min_path	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		Path< GT > &	min_path
	)

inline

Computes shortest path by painting the graph (without heuristic).

Dijkstra-compatible interface.

Parameters

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

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

Exceptions

bad_alloc If there is not enough memory.

Definition at line 883 of file AStar.H.

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

◆ find_path()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_path	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		Path< GT > &	path
	)

inline

Finds the shortest path from start to end using A*.

This is the recommended entry point for A* with heuristic. It paints the graph and extracts the path in one call.

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

bad_alloc If there is not enough memory.

Definition at line 474 of file AStar.H.

References Aleph::Path< GT >::empty(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::get_min_path(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::operator()().

◆ get_distance()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_min_path(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_path().

◆ get_start_node()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, 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>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>, template< class, class, class > class HeapT = ArcHeap>

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

inline

Computes the spanning tree of all shortest paths.

Dijkstra-compatible operator interface.

Parameters

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

Definition at line 907 of file AStar.H.

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

◆ operator()() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::operator()	(	const GT &	g,
		typename GT::Node *	s,
		typename GT::Node *	e,
		Path< GT > &	path
	)

inline

Finds shortest path using A* heuristic.

Parameters

[in]	g	The graph.
[in]	s	The starting node.
[in]	e	The destination node.
[out]	path	The shortest path.

Returns: The total cost.

Definition at line 920 of file AStar.H.

References Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_path(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::s.

◆ paint_min_paths_tree()

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

void Aleph::AStar_Min_Path< GT, Distance, Heuristic, 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 (without heuristic).

Uses Dijkstra's algorithm (zero heuristic).

Parameters

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

Exceptions

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

Definition at line 806 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APARENT, APOT, ARC_BITS, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heap, IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::painted, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

◆ paint_partial_min_paths_tree()

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

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

inline

Paints on graph g the partial shortest paths tree (without heuristic).

Uses Dijkstra's algorithm but stops when end is reached.

Parameters

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

Returns: true if end was found, false otherwise.

Exceptions

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

Definition at line 708 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APARENT, APOT, ARC_BITS, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heap, IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::painted, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_min_path().

◆ paint_partial_path()

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

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

inline

Paints the shortest path from start to end on the graph using A*.

This is the memory-efficient version that marks the path directly on the graph using spanning tree bits.

Parameters

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

Returns: true if a path was found, false otherwise.

Exceptions

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

Definition at line 373 of file AStar.H.

References AACC, AARC_DIST, ah_domain_error_if, APARENT, APOT, ARC_BITS, 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(), h, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heap, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heuristic, IS_ARC_VISITED, Aleph::HTList::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::painted, Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::sa, and Aleph::Spanning_Tree.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::find_path(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_path().

◆ paint_path()

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

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

inline

Alias for paint_partial_path (backward compatibility).

Definition at line 499 of file AStar.H.

References Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

Member Data Documentation

◆ heap

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

Heap Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::heap

private

Priority queue.

Definition at line 363 of file shortest_path_common.H.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

◆ heuristic

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

Heuristic Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::heuristic

private

Definition at line 193 of file AStar.H.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::check_heuristic_admissibility(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

◆ painted

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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 >::painted

private

Whether graph has been painted.

Definition at line 364 of file shortest_path_common.H.

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

◆ ptr_g

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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 >::ptr_g

private

Pointer to the graph.

Definition at line 365 of file shortest_path_common.H.

◆ s

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, 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 >::s

private

Start node.

Definition at line 366 of file shortest_path_common.H.

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

◆ sa

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

SA Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::sa

private

Arc filter.

Definition at line 361 of file shortest_path_common.H.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, 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::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), and Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path().

◆ validate_heuristic

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

bool Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::validate_heuristic = true

private

Definition at line 197 of file AStar.H.

Referenced by Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::check_heuristic_admissibility().

The documentation for this class was generated from the following file:

AStar.H

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Method Categories

Member Typedef Documentation

◆ Base

Constructor & Destructor Documentation

◆ AStar_Min_Path()

Member Function Documentation

◆ check_heuristic_admissibility()

◆ compute_min_paths_tree()

◆ compute_partial_min_paths_tree()

◆ compute_partial_path()

◆ compute_path()

◆ copy_painted_min_paths_tree()

◆ find_min_path()

◆ find_path()

◆ get_distance()

◆ get_graph()

◆ get_min_path() [1/2]

◆ get_min_path() [2/2]

◆ get_start_node()

◆ has_computation()

◆ is_painted()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ paint_min_paths_tree()

◆ paint_partial_min_paths_tree()

◆ paint_partial_path()

◆ paint_path()

Member Data Documentation

◆ heap

◆ heuristic

◆ painted

◆ ptr_g

◆ s

◆ sa

◆ validate_heuristic