stdgraph
Why is `vertices_breadth_first_search` a CPO?
In the current implementation vertices_breadth_first_search is a customization-point object. Are programmers supposed to plug their own implementations for their own types? What is the motivation?
I think your referring to the graph::views::vertices_breadth_first_search . That's a good question. FWIW P3129 Graph Views doesn't specify that the views are customization points.
I believe the views in ranges are customization points, so I was just following the pattern already established.
How might customization points be useful for the views? If someone has a better bfs algorithm for the bfs view then they could plug it into the infrastructure and consumers could use it without knowing.
Sent from Outlookhttp://aka.ms/weboutlook
From: Andrzej Krzemieński @.>
Sent: Saturday, May 17, 2025 1:01 PM
To: stdgraph/graph-v2 @.>
Cc: Subscribed @.***>
Subject: [stdgraph/graph-v2] Why is vertices_breadth_first_search a CPO? (Issue #151)
[https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 created an issue (stdgraph/graph-v2#151)https://github.com/stdgraph/graph-v2/issues/151
In the current implementation vertices_breadth_first_search is a customization-point object. Are programmers supposed to plug their own implementations for their own types? What is the motivation?
— Reply to this email directly, view it on GitHubhttps://github.com/stdgraph/graph-v2/issues/151, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB7NKEXQE7POMLG2JBG6B5L265TQNAVCNFSM6AAAAAB5KYWXU6VHI2DSMVQWIX3LMV43ASLTON2WKOZTGA3TAOJTGY3TIOI. You are receiving this because you are subscribed to this thread.
If someone has a better bfs algorithm for the bfs view then they could plug it into the infrastructure and consumers could use it without knowing.
But is it really a motivation? Following this reasoning one could also make dijkstra_shortest_paths a customization point.
The specification of the Standard Library uses name "customization point objects" to denote function objects in namespace views, but these "customization point objects" in namespace views do not allow the users to customize anything. For instance, see https://eel.is/c++draft/range.repeat.overview. That is, there are customization point objects in the Standard Library that are meant to be customized, but not these in namespace views.
The goal of these "customization point objects" is for them to be objects rather than functions, because this prevents the ADL. The ADL prevention is essential for the ranges library, because its names (e.g., find) compete with the same names in the original STL in namespace std. Names from Graph, especially the long ones, like breadth_first_search do not compete with any other names, so the motivation for doing these objects is gone.
I have found a useful article on the matter: https://brevzin.github.io/c++/2020/12/19/cpo-niebloid/.
I have talked to a number of Library folks in the Sofia meeting and they confirm. The Standard Library uses a misleading name "customization point object" to denote the idea that we want function objects that represent functions in order to:
- control the ADL,
- be able to pass them as arguments to other function templates.
Programmers being able to customize for their types based on CPOs is just a side benefit for a small subset of them.