Do not use type deduction when invoking visitor functions

[akrzemi1]

The implementation of the algorithms, use type deduction when invoking member functions of the visitors, as in:

if constexpr (has_on_discover_vertex<G, Visitor>) {
  visitor.on_discover_vertex({source, *find_vertex(g, source)}); // <-- no type of the argument
}

See https://github.com/stdgraph/graph-v2/blob/master/include/graph/algorithm/dijkstra_shortest_paths.hpp#L142.

As a consequence, I cannot my visitor like this:

struct MyVisitor
{
  void on_discover_vertex(auto const& v)
  {
    process(v.id);
  }
};

Even though I have satisfied all the requirements of a visitor.

[pratzl]

I think there are a couple of issues.

The implementation in dijkstra_shortest_paths should be more explicit: if constexpr (has_on_discover_vertex<G, Visitor>) { visitor.on_discover_vertex( vertex_info<vertex_id<G>, vertex_reference_t<G>>{source, *find_vertex(g, source)}); }

Your example for MyVisitor::on_discover_vertex(auto const& v) accepts any type for v. It should also require a parameter of vertex_info<vertex_id<G>, vertex_reference_t<G>>&. The concept checks for this and will execute if it matches the pattern expected in the concept. I see the ambiguity. Since the presence of on_discover_vertex is optional, I'm not sure what to do to make things better. Suggestions?

Sent from Outlookhttp://aka.ms/weboutlook

---

From: Andrzej Krzemieński @.> Sent: Sunday, July 13, 2025 11:17 AM To: stdgraph/graph-v2 @.> Cc: Subscribed @.***> Subject: [stdgraph/graph-v2] Do not use type deduction when invoking visitor functions (Issue #179)

[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 created an issue (stdgraph/graph-v2#179)https://github.com/stdgraph/graph-v2/issues/179

The implementation of the algorithms, use type deduction when invoking member functions of the visitors, as in:

if constexpr (has_on_discover_vertex<G, Visitor>) { visitor.on_discover_vertex({source, *find_vertex(g, source)}); // <-- no type of the argument }

See https://github.com/stdgraph/graph-v2/blob/master/include/graph/algorithm/dijkstra_shortest_paths.hpp#L142.

As a consequence, I cannot my visitor like this:

struct MyVisitor { void on_discover_vertex(auto const& v) { process(v.id); } };

Even though I have satisfied all the requirements of a visitor.

— Reply to this email directly, view it on GitHubhttps://github.com/stdgraph/graph-v2/issues/179, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB7NKEXZY5OAZ4ZZFFG3QKT3IJ2CBAVCNFSM6AAAAACBND5XZGVHI2DSMVQWIX3LMV43ASLTON2WKOZTGIZDMNJYGEZDKMQ. You are receiving this because you are subscribed to this thread.

[akrzemi1]

I think I disagree with the above analysis. This declaration of a visitor:

struct MyVisitor
{
  void on_discover_vertex(auto const& v)
  {
    process(v.id);
  }
};

It is lousy. I would never recommend writing a declaration like this in a production code. But it certainly satisfies the concept as declared:

template <class G, class Visitor>
concept has_on_discover_vertex = // For exposition only
      requires(Visitor& v, vertex_info<vertex_id_t<G>, vertex_reference_t<G>, void> vdesc) {
        { v.on_discover_vertex(vdesc) };
      };

The concept -- as usual -- expresses the following expectation: if I have an object of type vertex_info<...>, can I pass it to member function on_discover_vertex and expect it to compile? And MyVisitor certainly satisfies this. The contract is very clear. It is the implementation of the algorithm that uses more than what the contract describes.

You could change the concept to say:

template <class G, class Visitor>
concept has_on_discover_vertex = 
      requires(Visitor& vis, vertex_info<vertex_id_t<G>, vertex_reference_t<G>, void> vdesc) {
        { vis.on_discover_vertex(vdesc) };
      } &&
     requires(Visitor& vis, vertex_id_t<G> uid, vertex_reference_t<G> u) {
        { vis.on_discover_vertex({uid, u}) };
      }

And then the concept would favor the algorithm implementer's freedom. But I would not recommend this. I think it is fair when a generic library author takes more burden on them, and the user is given the maximum reasonable freedom.

[pratzl]

I agree that the library should be as flexible as is reasonably possible. In your last example, I'm trying to understand what the type passed in the second example is. There's no named struct/class. Maybe this something in the language I'm not familiar with?

Even though it would work with your visitor example, you said wouldn't recommend it. What would you recommend?

[akrzemi1]

In the following description I will use terms "library author" and "library user".

When I say that a library should be flexible I mean that it should be maximally flexible for the user at the cost of being inflexible for the author. I see a concept -- for instance has_on_discover_vertex -- as a contract between the user and the author:

• The user commits that their types will satisfy the concept but no more than that.
• The author commits that that they will only use the user types in the ways described by the concept and no other.

In my example above, in the second requires-expression of the concept, I am using the brace-initialization syntax and its properties that I do not need to specify the type being initialized if it can be unambiguously deduced from the context:

struct A
{
    int i;
    int j;
};

void f(A a) {}

template <typename T>
void g(T a) {}

int main()
{
    f({1, 2}); // OK, deduced type `A` from the function parameter type
    g({1, 2}); // error: the type could not be deduced
}

https://godbolt.org/z/rvd93vYYj

The graph-v2 already uses this type deduction property when it invokes visitors. For instance, see https://github.com/stdgraph/graph-v2/blob/master/include/graph/algorithm/dijkstra_shortest_paths.hpp#L142. The bug that I am reporting here is that the library author does not abide by the contract expressed in the concept graph::has_on_discover_vertex only allows the author to pass the argument when the author already has the type. The concept doesn't grant the author permission to trigger the type deduction from the brace-initialization. The author is using the user provided type (the visitor) out of contract. I find this unacceptable, and I see two ways to resolve this:

1. Either relax the concept so that what the author does (triggering the type deduction from the brace-initialization) becomes part of the contract. (This is what the second requires-expression in my above example does.) (This will render MyVisitor not conformant to with the concept.)
2. Change the implementation of dijkstra_shortest_paths so that it only uses operations allowed by the concept, and therefore never triggers the type deduction from the brace initialization, and therefore allows the users to provide on_discover_vertex as a function template.

I recommend implementing #2 because it favors the user's freedom over the author's freedom.