# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

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.

## 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< boolm_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
 T The type of edge cost

Definition at line 54 of file AStarSearch.h.

## ◆ NodeQueue

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

Definition at line 56 of file AStarSearch.h.

## ◆ 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 78 of file AStarSearch.h.

## ◆ 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 98 of file AStarSearch.h.

## ◆ investigateNode()

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

Definition at line 166 of file AStarSearch.h.

## ◆ m_cost

template<typename T >
 const EdgeArray* 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 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 ogdf::AStarSearch< T >::m_folded
private

Definition at line 62 of file AStarSearch.h.

## ◆ m_heuristic

template<typename T >
 std::function 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* 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: