The support for map-lookup-like adjacency lists

[akrzemi1]

I find that a lot of discussion for graphs is from academia or high-performance computing, where vertices are in random access containers with integral indices. It's simple and straight forward and is typically very high performance. However, I believe graphs come in far bigger varieties that don't fall within those constraints.
I've worked with graphs for 30 years that are embedded in applications where the application requirements dictate that they can't use an integral index, and they are not stored in contiguous memory. For instance, in a persisted graph that changes over time, there needs to be a way to incrementally add new vertices and edges and retain their identify over multiple sessions.
The product I've been working on for 10 years is a distributed graph for entity resolution with its own query capability. The user needs to add and delete vertices, and a simplified Id is made up of {network rank, type, rowid}. I would like to be able to use the library for my work.
Even if the algorithms in the library don't apply, I'd like to be able to use the framework to write my own algorithms against my "graph database" which can have billions of vertices and edges. If I'm required to transform the data into a form where I'm mapping the vertex id to an integral index and copy the relevant data to a temporary data structures where vertices are in a random_access range, it will be far more expensive than running the algorithm directly on the existing data for many algorithms, especially if its only touching a small subset of the vertices (e.g. shortest paths could exhibit that, depending on the characteristics of the graph).
Before descriptors we introduced, I was thinking we'd need to have different specializations for each algorithm, so you're headed in the same direction I was thinking. I haven't eliminated the potential requirement of specialization, but I think it might be possible to have a single implementation.
For Dijkstra, consider that map and unordered_map have operator[], which is semantically similar to operator[] for a random access container for distances. There are some differences, but I think they're minor and could be accommodated at compile-time. It's something that needs experimentation to see if it could actually work or not. If it's not obvious, I'm saying is that the distances range would have the same characteristics as the vertices range.

First of all, your use case is very valuable, and for one, it deserves to be described in the graph papers.

I acknowledge the need to have an adjacency list with a map-like vertex look-up. But it is still not clear to me what you want to do about this adjacency list representation in the graph-v2 library.

You say:

Even if the algorithms in the library don't apply, I'd like to be able to use the framework to write my own algorithms against my "graph database".

So, you want to write your own algorithm, you have your own graph representation. What do you need this library for then?

• Just the concept and nothing more? (this seems unnecessary)
• Just the views and nothing more?

You say:

For Dijkstra, consider that map and unordered_map have operator[] [...]

So it looks like you consider an option that graph-v2 algorithms (such as dijkstra_shortest_paths) would support your graph representation. In that case, I note that the algorithm requires not only traversing the graph, but also recording the visited nodes in the output parameter, such as predecessor. So concept (non-index) adjacency_list is not enough: you would also need to have a concept for recording a visited node in the collection of nodes.

Anyway, my general observation is that this library should have either of the two answers to the question of supporting non-index adjacency lists:

• either it is simply out of scope,
• or graph-v2 has a clear picture how the full support for it would look like (even i it is not fully implemented just yet).

But, in my opinion, it would be wrong to have a half-measure solution, such as having concept adjacency_list but no prove or no signal that the library would be able to do anything with non-index adjacency lists.

[akrzemi1]

I think that the map-like adjacency list representation could work without introducing new graph concepts. I think that algorithms could operate both on both index-based and map-like adjacency lists using a single concept adjacency_list.

Pull request #173 demonstrates how this would work for Dijkstra's shortest paths.

It could be achieved via one building-block customization point + a building block concept for interoperating with 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>>());