graph::shortest_path::GreedyBestFS Class Reference

#include <GreedyBestFS.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)

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::GreedyBestFS::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 Greedy Best-first search algorithm from the start node to the goal node in the graph.

Note

The founded path is not necessary the optimal one.

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

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:

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::GreedyBestFS::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/GreedyBestFS.hpp