Template Function lupnt::FindShortestPath

Function Documentation

template<typename T, typename U>
std::vector<T> lupnt::FindShortestPath(const T start, const T end, const std::map<std::pair<T, T>, std::function<U>> &map)

Find the shortest sequence of representation/frame nodes connecting start to end via a breadth-first search over the given adjacency map.

Used by the generic state/frame conversion machinery (e.g. StateConverter::Convert in conversions/state_converter.cc) to chain together a sequence of pairwise conversion functions when no direct conversion between two state/coordinate types is registered, by searching the graph of registered pairwise conversions for a path from the source type to the target type.

Parameters:

  • start – Starting node (e.g. source state/frame type)

  • end – Target node (e.g. destination state/frame type)

  • map – Adjacency map: keys are (from, to) node pairs for which a direct conversion function exists; values are unused by the search itself

Returns:

Ordered list of nodes from start to end (inclusive) forming the shortest path; throws (via LUPNT_CHECK) if no path exists