A breaking and uncomfortable change in the descriptor rewrite

[akrzemi1]

I have a situation when testing the descriptor implementation in branch desc4. The definition of the CPO find_vertex changed significantly, to the extent that my graph representation has the CPO find_vertex valid in branch master, but no longer so on branch desc4.

This is my graph:

namespace MyLibrary 
{

struct MyEdge
{
  std::string content;
  int indexOfTarget;
  
  int target_id(auto&&) const { return indexOfTarget; }
};

struct MyVertex
{
  std::string content;
  std::vector<MyEdge> outEdges;
  
  std::vector<MyEdge> const& edges(auto&&) const { return outEdges; }
};

class MyGraph 
{
  std::vector<MyVertex> _vertices;
  
public:
  std::vector<MyVertex> const& vertices() const { return _vertices; }
};

std::vector<MyEdge> const& edges(MyGraph const& g, int uid) { return g.vertices()[uid].edges(g); }
}

I never had to define find_vertex, because in master there was an if constexpr in the CPO that checked random_access_iterator<vertex_iterator_t<_G>>. In desc4 this has been replaced with a different condition that no longer holds for my graph: random_access_range<_G>. See https://github.com/stdgraph/graph-v2/blob/desc4/include/graph/detail/graph_cpo.hpp#L553.

Is there some fundamental reason why my graph cannot get a default customization for vertex_value or is it ust an oversight?

Interestingly, my graph above models graph::index_adjacency_list, and I can use it with graph::dijkstra_shortest_paths in the simplest cases. Apparently find_vertex is not part of the concept. But the moment I start using a visitor, an if constexpr branch triggers that calls find_vertex and my program no longer compiles. A full example follows.

#include <graph/graph.hpp>
#include <vector>
#include <iostream>
#include <cassert>
#include <graph/algorithm/dijkstra_shortest_paths.hpp>

namespace MyLibrary 
{

struct MyEdge
{
  std::string content;
  int indexOfTarget;
  
  int target_id(auto&&) const { return indexOfTarget; }
};

struct MyVertex
{
  std::string content;
  std::vector<MyEdge> outEdges;
  
  std::vector<MyEdge> const& edges(auto&&) const { return outEdges; }
};

class MyGraph 
{
  std::vector<MyVertex> _vertices;
  
public:
  std::vector<MyVertex> const& vertices() const { return _vertices; }
};

std::vector<MyEdge> const& edges(MyGraph const& g, int uid) { return g.vertices()[uid].edges(g); }
}

class ShowProgress
{
  using G = MyLibrary::MyGraph;
  using VD = graph::vertex_info<graph::vertex_id_t<G>, graph::vertex_reference_t<G>, void>;    
  int vertex_count = 0;

public:   
  void on_discover_vertex(VD const& v)
  {
    if (vertex_count % 3 == 0)
      std::cout << "processing vertex " << v.id << "\n";
    ++vertex_count;
  }
};

auto weight = [](std::tuple<int, double> const& uv) {
  return std::get<1>(uv);
}; 

int main()
{
  std::vector<int> predecessors;
  std::vector<double> distances;
  
  MyLibrary::MyGraph g;

  static_assert(graph::index_adjacency_list<MyLibrary::MyGraph>);
  graph::dijkstra_shortest_paths(g, 0, distances, predecessors, weight, ShowProgress{});
  auto && vtcs = graph::vertices(g);
  

  auto vit = std::ranges::begin(vtcs);
  int id0 = graph::vertex_id(g, *vit);

  assert(id0 == 0);
  auto && edgs = graph::edges(g, *vit);

  auto eit = std::ranges::begin(edgs);
  int id1 = graph::target_id(g, *eit);

  assert(id1 == 1);

  auto wit = graph::find_vertex(g, id1);
  int id1_ = graph::vertex_id(g, *wit);
  assert(id1_ == 1);
}