Property map, traits and visitor syntax

[Becheler]

Story

joaquintides opened the discussion with a precise diagnosis: property maps are a beautiful abstraction that becomes painful at the call site. Every BGL user eventually writes something like this:

dijkstra_shortest_paths(
    g, vertex(0, g),
    predecessor_map(make_iterator_property_map(
        p.begin(), get(vertex_index, g))).
    distance_map(make_iterator_property_map(
        d.begin(), get(vertex_index, g))));

He proposed a composing operator >> that would reduce property map construction to:

g >> vertex_index >> p

A proof of concept already exists at godbolt.org/z/as6rxW6M8, written with C++20 concepts but likely backportable to C++14. The operator works at the property map construction level, independently of how the maps are passed to the algorithm. Even if named parameters (predecessor_map(...), distance_map(...)) are eventually deprecated in favour of a positional or range-based API, the >> construction shorthand remains useful.

Note: there are ongoing thoughts among the maintainers about deprecating named parameters entirely. The card is not about that question. It is about making property map construction less painful regardless of what the algorithm call site ends up looking like.

joaquintides also noted that graph_traits<G>::vertex_descriptor could be replaced with type aliases like vertex_descriptor_t<G>, following the pattern already established in the standard library.

Arnaud raised the same question about visitor composition, which suffers from the same deeply nested boilerplate:

boost::breadth_first_search(G, s,
   boost::make_bfs_visitor(
     std::make_pair(boost::record_distances(d, boost::on_tree_edge()),
     std::make_pair(boost::record_predecessors(p.begin(),
                                               boost::on_tree_edge()),
                    copy_graph(G_copy, boost::on_examine_edge()))))
);

Dream solution

• Property map construction at the call site is concise and readable via >>.
• Type aliases exist for all common graph_traits members.
• Visitor composition is equally clean.
• Everything is C++14 compatible and independent of whatever replaces named parameters.

Starting point

joaquintides's comment in discussion #466
Godbolt proof of concept
Old property map docs
New property map docs
New traits docs

Intermediary objective (45 min)

Read joaquintides's comment and study the Godbolt proof of concept. Then answer in writing:

1. Does the >> operator cover all common property map use cases, or are there cases it cannot express?
2. What would it take to backport it from C++20 concepts to C++14?
3. Which graph_traits members are most commonly used and deserve a type alias first?
4. Does the composing operator idea extend naturally to visitor composition, or does that require a different approach?

[joaquintides]

For your reference, this is the full presentation I gave this morning:
BGL API pain points and modernization ideas.pdf

[sloriot]

Output from the Working group with @jaakkojarvi:

point 1 & 2

We agree that the current version requires too much understanding that typical use cases does not require (does the user needs to know at the beginning what is a iterator property map?).

We are not really keen on overloading operators. Since anyway what your overloading is providing is a random access property map, it seems that the most straight forward usage would be to only pass a random access container in the named parameter. Then internally, you can build yourself the "true" property map. Bonus point, if the graph does not have an index property, you can build a hash map (or map) to create that index map, and that index map will be used for all the property maps given as named parameter.

It would then become:

dijkstra_shortest_paths(
    g, vertex(0, g),
    predecessor_map(p).
    distance_map(d));

This puts the stress of handling the random container as a property map to the developer side, but we can easily create internal helper classes that would deal with it. That way for advanced usage, where the user does provided its own property map, you can handle in a simple way that situation too (static dispatching).

About concepts, making it work with c++14 in this scenario does not seems to be an issue.

point 3

Can be done easily and is very convenient in some cases, but the old naming should be kept anyway (at least for backward compatibility and it also makes it clear that all the types come from the same class). If we do it, we should do all descriptors and iterators + category (systematic for all).

point 4

Having a named parameter for each function in the visitor concept seems to be clearer from a syntax point of view and user point of view, and even the developer it removes the need of a special struct for storing the lambda.

The code would end up with the following:

breadth_first_search(g, vertex(0, g), 
                     bfs_discover_vertex([] (auto v, const auto& /*g*/) {
                       std::cout << " discovered " << v << "\n";
                     }).
                     bfs_tree_edge([] (auto e, const auto& g) {
                       std::cout << " tree edge " << source(e, g)
                       << " -> " << target(e, g) << "\n";
                     })
);