Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

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
 
NodeQueuem_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
TThe type of edge cost

Definition at line 54 of file AStarSearch.h.

Member Typedef Documentation

◆ NodeQueue

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

Definition at line 56 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
directedWhether to traverse edges in both directions
maxGapThe maximal gap between the computed path costs and the optimal solution. The default of 1 leads to an optimal solution.
etThe ogdf::EpsilonTest to be used for comparing edge costs

Definition at line 79 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
graphThe graph to investigate
costThe positive cost of each edge
sourceThe start of the path to compute
targetThe end of the path to compute
predecessorWill contain the preceding edge of each node in the path predecessor[target] will be nullptr if no path could be found
heuristicThe 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 174 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 63 of file AStarSearch.h.

◆ m_directed

template<typename T >
bool ogdf::AStarSearch< T >::m_directed
private

Definition at line 58 of file AStarSearch.h.

◆ m_distance

template<typename T >
NodeArray<T> ogdf::AStarSearch< T >::m_distance
private

Definition at line 66 of file AStarSearch.h.

◆ m_et

template<typename T >
EpsilonTest ogdf::AStarSearch< T >::m_et
private

Definition at line 60 of file AStarSearch.h.

◆ m_folded

template<typename T >
NodeArray<bool> ogdf::AStarSearch< T >::m_folded
private

Definition at line 62 of file AStarSearch.h.

◆ m_heuristic

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

Definition at line 64 of file AStarSearch.h.

◆ m_maxGap

template<typename T >
double ogdf::AStarSearch< T >::m_maxGap
private

Definition at line 59 of file AStarSearch.h.

◆ m_predecessor

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

Definition at line 65 of file AStarSearch.h.

◆ m_queue

template<typename T >
NodeQueue* ogdf::AStarSearch< T >::m_queue = nullptr
private

Definition at line 67 of file AStarSearch.h.


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