graph::shortest_path::AStar Class Reference

#include <AStar.hpp>

Static Public Member Functions
template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &)>, typename F2 = std::function<void(const TNode &, const typename TGraph::edge_type::weight_type &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPath (const TGraph &graph, const TNode &start, const TNode &goal, F1 f_heuristic, F2 f_user=[](const TNode &, const typename TGraph::edge_type::weight_type &) {})
template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &, const TNode &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathRegistration (const TGraph &graph, const TNode &start, const TNode &goal, F1 f_heuristic)
template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &)>, typename F2 = std::function<typename TGraph::edge_type::weight_type(const TNode &)>, typename F3 = std::function<void(const TNode &, const typename TGraph::edge_type::weight_type &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathBidirectional (const TGraph &graph, const TNode &start, const TNode &goal, F1 f_heuristic_forward, F2 f_heuristic_backward, F3 f_user=[](const TNode &, const typename TGraph::edge_type::weight_type &) {})
template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &, const TNode &)>>
static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type >	findPathBidirectionalRegistration (const TGraph &graph, const TNode &start, const TNode &goal, F1 f_heuristic)

Member Function Documentation

findPath()

template<typename TGraph , typename TNode , typename F1 , typename F2 >

ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::AStar::findPath ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F1  f_heuristic, F2  f_user = [](const TNode &,                          const typename TGraph::edge_type::weight_type &) {}  )

static

Find the shortest path using AStar algorithm from the start node to the goal node in the graph.

Whenever node is opened, f_user is called with two parameters (the opened node and value of currently shortest path).

The heuristic function must be admissible and monotone.

Parameters

graph	to explore.
start	initial node.
goal	final node.
f_heuristic	heuristic function which accept node and return edge_type::weight_type.
f_user	function which is called for every opened node with value of currently shortest path.

Returns

pair where first := shortest path := distance of path, if there is no such path vector is empty and distance std::numeric_limits<edge_type:weight_type>::max().

Note

TEdge of graph must follow graph::edge::WeightedEdge interface.

See also

graph::edge_type::WeightedEdge.

Exceptions

std::out_of_range

if graph contains an edge with a negative weight.

Here is the call graph for this function:

Here is the caller graph for this function:

findPathBidirectional()

template<typename TGraph , typename TNode , typename F1 , typename F2 , typename F3 >

ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::AStar::findPathBidirectional ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F1  f_heuristic_forward, F2  f_heuristic_backward, F3  f_user = [](const TNode &,                                       const typename TGraph::edge_type::weight_type &) {}  )

static

Find the shortest path using AStar algorithm from the start node to the goal node in the graph. This algorithm is run in both direction, from start and also from goal.

Whenever node is opened, f_user is called with two parameters (the opened node and value of currently shortest path).

The heuristic function must be admissible and monotone.

Parameters

graph	to explore.
start	initial node.
goal	final node.
f_heuristic_forward	front-to-end (node->goal) heuristic function which accept node and return edge_type::weight_type.
f_heuristic_backward	front-to-end (node->start) heuristic function which accept node and return edge_type::weight_type.
f_user	function which is called for every opened node with value of currently shortest path.

Returns

pair where first := shortest path := distance of path, if there is no such path vector is empty and distance std::numeric_limits<edge_type:weight_type>::max().

Note

TEdge of graph must follow graph::edge::WeightedEdge interface.

See also

graph::edge_type::WeightedEdge.

Exceptions

std::out_of_range

if graph contains an edge with a negative weight.

Here is the call graph for this function:

Here is the caller graph for this function:

findPathBidirectionalRegistration()

template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &, const TNode &)>>

static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::AStar::findPathBidirectionalRegistration ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F1  f_heuristic  )

inlinestatic

Here is the call graph for this function:

findPathRegistration()

template<typename TGraph , typename TNode , typename F1 = std::function<typename TGraph::edge_type::weight_type(const TNode &, const TNode &)>>

static ext::pair< ext::vector< TNode >, typename TGraph::edge_type::weight_type > graph::shortest_path::AStar::findPathRegistration ( const TGraph &  graph, const TNode &  start, const TNode &  goal, F1  f_heuristic  )

inlinestatic

Here is the call graph for this function:

---

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

• alib2graph_algo/src/shortest_path/AStar.hpp