ogdf::AStarSearch< T > Class Template Reference

A-Star informed search algorithm. More...

#include <ogdf/graphalg/AStarSearch.h>

Public Member Functions
	AStarSearch (const bool directed=false, const double maxGap=1, const EpsilonTest &et=EpsilonTest())
	Initializes a new A* search algorithm. More...
T	call (const Graph &graph, const EdgeArray< T > &cost, const node source, const node target, NodeArray< edge > &predecessor, std::function< T(node)> heuristic=[](node) { return T(0);})
	Computes the shortests path between source and target. More...

Private Types
using	NodeQueue = PrioritizedMapQueue< node, T >

Private Member Functions
void	investigateNode (const node v)
bool	validatePath (const node source, const node target) const

Private Attributes
const EdgeArray< T > *	m_cost = nullptr
bool	m_directed
NodeArray< T >	m_distance
EpsilonTest	m_et
NodeArray< bool >	m_folded
std::function< T(node)>	m_heuristic
double	m_maxGap
NodeArray< edge > *	m_predecessor = nullptr
NodeQueue *	m_queue = nullptr

Detailed Description

template<typename T>
class ogdf::AStarSearch< T >

A-Star informed search algorithm.

The algorithm is a generalization the the shortest path algorithm by Dijkstra. It was first described in "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" by Hart, Nilsson and Raphael in 1968.

The algorithm yields an optimal solution to the single pair shortest pair problem. A heuristic for calculating a lower bound on the distance from any node to the target is optional. The algorithm can also be used to compute approximate solutions at a faster pace.

Template Parameters

T	The type of edge cost

Definition at line 57 of file AStarSearch.h.

Member Typedef Documentation

NodeQueue

template<typename T >

using ogdf::AStarSearch< T >::NodeQueue = PrioritizedMapQueue<node, T>

private

Definition at line 59 of file AStarSearch.h.

Constructor & Destructor Documentation

AStarSearch()

template<typename T >

ogdf::AStarSearch< T >::AStarSearch ( const bool  directed = false, const double  maxGap = 1, const EpsilonTest &  et = EpsilonTest()  )

inlineexplicit

Initializes a new A* search algorithm.

Parameters

directed	Whether to traverse edges in both directions
maxGap	The maximal gap between the computed path costs and the optimal solution. The default of 1 leads to an optimal solution.
et	The ogdf::EpsilonTest to be used for comparing edge costs

Definition at line 81 of file AStarSearch.h.

Member Function Documentation

call()

template<typename T >

T ogdf::AStarSearch< T >::call ( const Graph &  graph, const EdgeArray< T > &  cost, const node  source, const node  target, NodeArray< edge > &  predecessor, std::function< T(node)>  heuristic = [](node) { return T(0); }  )

inline

Computes the shortests path between source and target.

Parameters

graph	The graph to investigate
cost	The positive cost of each edge
source	The start of the path to compute
target	The end of the path to compute
predecessor	Will contain the preceding edge of each node in the path predecessor[target] will be nullptr if no path could be found
heuristic	The heuristic to be used. Note that the type ogdf::NodeArray is implicitly applicable here. The default heuristic will always return the trivial lower bound of zero.

Returns

The total length of the found path

Definition at line 101 of file AStarSearch.h.

investigateNode()

template<typename T >

void ogdf::AStarSearch< T >::investigateNode ( const node  v )

inlineprivate

Definition at line 169 of file AStarSearch.h.

validatePath()

template<typename T >

bool ogdf::AStarSearch< T >::validatePath ( const node  source, const node  target  ) const

inlineprivate

Definition at line 145 of file AStarSearch.h.

Member Data Documentation

m_cost

template<typename T >

const EdgeArray<T>* ogdf::AStarSearch< T >::m_cost = nullptr

private

Definition at line 66 of file AStarSearch.h.

m_directed

template<typename T >

bool ogdf::AStarSearch< T >::m_directed

private

Definition at line 61 of file AStarSearch.h.

m_distance

template<typename T >

NodeArray<T> ogdf::AStarSearch< T >::m_distance

private

Definition at line 69 of file AStarSearch.h.

m_et

template<typename T >

EpsilonTest ogdf::AStarSearch< T >::m_et

private

Definition at line 63 of file AStarSearch.h.

m_folded

template<typename T >

NodeArray<bool> ogdf::AStarSearch< T >::m_folded

private

Definition at line 65 of file AStarSearch.h.

m_heuristic

template<typename T >

std::function<T(node)> ogdf::AStarSearch< T >::m_heuristic

private

Definition at line 67 of file AStarSearch.h.

m_maxGap

template<typename T >

double ogdf::AStarSearch< T >::m_maxGap

private

Definition at line 62 of file AStarSearch.h.

m_predecessor

template<typename T >

NodeArray<edge>* ogdf::AStarSearch< T >::m_predecessor = nullptr

private

Definition at line 68 of file AStarSearch.h.

m_queue

template<typename T >

NodeQueue* ogdf::AStarSearch< T >::m_queue = nullptr

private

Definition at line 70 of file AStarSearch.h.

---

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

• include/ogdf/graphalg/AStarSearch.h