generalize Dijkstra's shortest paths to non-index adjacency lists

[akrzemi1]

This demonstrates how Dijkstra's shortest paths can be made to work on concept adjacency_list (rather than index_adjacency_list) and therefore service graphs with map-like vertex look-up.

This is implemented by adding a new building-block CPO and a corresponding building-block concept for interoperating with output containers, such as predecessor or distances.

CPO:

template <typename Cont, typename UID>
auto* vertex_record(Cont& cont, UID uid);

Were:

• Cont represents a container accessed by uid for holding things like predecessors, distances, visited vertices, component IDs.
• function vertex_record returns a pointer to a record storing information about vertex represented by uid, or nullptr if no such record exists.

Helper alias:

template <typename Cont, typename G>
using record_t = decltype(*vertex_record(std::declval<Cont&>(), std::declval<vertex_id_t<G>>()));

CPO default implementations:

template <std::ranges::random_access_range Cont, typename G>
  requires std::sized_integral<vertex_id_t<G>>
auto* vertex_record(Cont& cont, vertex_id_t<G> uid)
{
    if (0 <= uid && uid < cont.size())
      return cont[uid];
    else
      return nullptr;
}

template <MapLike Cont, typename G>
  requires std::regular<vertex_id_t<G>>
auto* vertex_record(Cont& cont, vertex_id_t<G> uid)
{
      return cont[uid];
}

Helper concept:

template <typename Cont, typename G>
concept record_for = requires(Cont& cont, vertex_id_t<G>& id)
{
  { vertex_record(cont, id) } -> std::regular;

  /*
  requires requires(G g) // semantic requirements
  {
      // for (vertex_iterator_t<G> it : vertices(g))
      //  assert(vertex_record(cont, vertex_id(g, it)) != nullptr); 
  };
  */
};

The declaration of the Dijkstra's algorithm:

template <adjacency_list G,
          input_range    Sources,
          record_for<G>  Distances,
          record_for<G>  Predecessors,
          class WF      = function<record_t<Distances, G>(edge_reference_t<G>)>,
          class Visitor = empty_visitor,
          class Compare = less<record_t<Distances, G>>,
          class Combine = plus<record_t<Distances, G>>>
requires convertible_to<range_value_t<Sources>, vertex_id_t<G>> &&
         convertible_to<vertex_id_t<G>, record_t<Predecessors, G>> &&
         basic_edge_weight_function<G, WF, record_t<Distances, G>, Compare, Combine>
constexpr void dijkstra_shortest_paths(
      G&&            g,
      const Sources& sources,
      Distances&     distances,
      Predecessors&  predecessor,
      WF&&      weight  = [](edge_reference_t<G> uv) { return record_t<Distances, G>(1); },
      Visitor&& visitor = empty_visitor(),
      Compare&& compare = less<record_t<Distances, G>>(),
      Combine&& combine = plus<record_t<Distances, G>>());