Strange way of specifying concepts for BFS views

[akrzemi1]

I am taking aside the fact that BFS views are customization points, and that the user customizes them no concept satisfaction is required.

In all other cases, the BFS algorithms default to:

• vertices_breadth_first_search_view
• edges_breadth_first_search_view

First question: the above two as well as bfs_base are declared in namespace graph. Are they intended to be used directly by customers? In other words, do their names have to be standardized and guaranteed to be stable?

My second issue is that the concept constraints on the two views are declared in an unusual way:

template <adjacency_list G, /*...*/>
  requires random_access_range<vertex_range_t<G>> && integral<vertex_id_t<G>>
class vertices_breadth_first_search_view /*...*/

The conjunction of these three concept constraints gives exactly index_adjacency_list, and in fact the base class, bfs_base, is constrained by index_adjacency_list. Why not use index_adjacency_list in constraints consistently?

[pratzl]

I tried to follow what I'd seen in the standard, such as std::ranges::transform_view and std::ranges::views::transform (https://en.cppreference.com/w/cpp/ranges/transform_view). If I incorrectly interpreted that, please let me know.

To answer your first question, yes they would both need to be standardized and both could be used by the customer. It's not clear to me why that pattern has been established in the standard.

For your second question, I agree that index_adjacency_list would be a better usage. What you're pointing out is an older way, before index_adjacency_list existed.

There's also an open question about how to define views and algorithms that support both index_adjacency_list and adjacency_list (e.g. vertices in random_access vs map-like structures). In simpler algorithms, I think it might be possible to support both, but for more complex algorithms it might require specialization. At one time I thought I could use concepts to specialize implementations, but recent work has shown me that I won't be able to do that.

Sent from Outlookhttp://aka.ms/weboutlook

---

From: Andrzej Krzemieński @.> Sent: Saturday, May 17, 2025 2:04 PM To: stdgraph/graph-v2 @.> Cc: Subscribed @.***> Subject: [stdgraph/graph-v2] Strange way of specifying concepts for BFS views (Issue #152)

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

I am taking aside the fact that BFS views are customization points, and that the user customizes them no concept satisfaction is required.

In all other cases, the BFS algorithms default to:

• vertices_breadth_first_search_view
• edges_breadth_first_search_view

First question: the above two as well as bfs_base are declared in namespace graph. Are they intended to be used directly by customers? In other words, do their names have to be standardized and guaranteed to be stable?

My second issue is that the concept constraints on the two views are declared in an unusual way:

template <adjacency_list G, /.../> requires random_access_range<vertex_range_t<G>> && integral<vertex_id_t<G>> class vertices_breadth_first_search_view /.../

The conjunction of these three concept constraints gives exactly index_adjacency_list, and in fact the base class, bfs_base, is constrained by index_adjacency_list. Why not use index_adjacency_list in constraints consistently?

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