Hi everyone,

apologies for dropping in unannounced, I'm not sure what the protocol for
participation is.

I just had a couple of comments to add on the algorithm naming topic.

The value of having std::sort and std::stable_sort is ease of use -- a user
doesn't have to deliberate when they want to get on with the task of
sorting arbitrary data. But for the users with specific requirements such
as sorting many small arrays, or not caring about the worst-case scenario,
they have to pay the cost of generality.
>From memory, some standard implementations have "insertion_sort" in there,
but it's not in ::std, so it's not available to the user.

C++17 introduced an overload of std::search that takes a searcher object
such as std::boyer_moore or std::boyer_moore_horspool, and also provided
the std::default_searcher class that just does the basic algorithm. (Of
course they retained the original interface to std::search too.)

>From these examples, I'm suggesting why not have both? I mean, have
std::dijkstra and std::bellman_ford, etc, but also have the
std::shortest_path(_variant) names that default to the most generally
pleasing (whatever that means) algorithm. That would satisfy the users that
want to choose their algorithm explicitly and the users that want the
language to choose the best algorithm for the problem. You might even
design it like std::search, so that the algorithm is passed as a solver to
the single interface, i.e. a user might call
std::shortest_path(std::dijkstra{}, ...) to explicitly use Dijkstra's
algorithm to solve that problem; if the user doesn't explicitly choose a
solver then the default is used.

Cheers.

Jeremy


On Sat, 15 Apr 2023 at 02:28, Phil Ratzloff via SG19 <sg19_at_[hidden]>
wrote:

> (Adding Andrew – he’s had problems getting added to the SG19 reflector)
>
>
>
>
>
> *From:* SG19 <sg19-bounces_at_[hidden]> *On Behalf Of *Oliver Rosten
> via SG19
> *Sent:* Friday, April 14, 2023 8:50 AM
> *To:* Jens Maurer <jens.maurer_at_[hidden]>
> *Cc:* Oliver Rosten <oliver.rosten_at_[hidden]>; sg19_at_[hidden]
> *Subject:* Re: [SG19] D1709: Graph Proposal
>
>
>
> *EXTERNAL*
>
> I think there are some other considerations to bear in mind, which were
> briefly touched on last night.
>
>
>
> To what extent can the problem of dispatch be dealt with implicitly? What
> I'm getting at here is that in *some* instances an appropriate concept
> could do the trick. For example, consider the simple cases where the
> weights are
>
> (i) int
>
> (ii) unsigned int
>
>
>
> There is enough info to always correctly and optimally dispatch case (ii).
> The first case is harder. In general, we can't assume that Dijskstra will
> work and so by default we should dispatch to e.g. Bellman-Ford. However,
> clients may wish to explicitly override this if they *know* that none of
> the weights are actually negative.
>
>
>
> Perhaps this implies a set of functions
>
>
>
> shortest_path (constrained to accept graph-like types satisfying enough
> requirements for implicit dispatch)
>
> shortest_path_semi_positive_weights (ideally with a nicer name)
>
> shortest_path_negative_weights (ditto)
>
>
>
> Oliver
>
>
>
> PS Out of curiosity, what is your objection to overload sets? I tend to
> find them easier to work with in generic code since it's easy to create
> maps from types to types. However, I typically find maps from types to
> function invocations more fiddly and a bit clumsier.
>
>
>
> On Fri, 14 Apr 2023 at 08:34, Jens Maurer <jens.maurer_at_[hidden]> wrote:
>
>
>
> On 13/04/2023 22.54, Oliver Rosten via SG19 wrote:
> > Hi folks,
> >
> > Further to today's meeting I wanted to add a further thought about
> standardizing explicitly named algorithms, such as Dijksrta's.
> >
> > To recap:
> >
> > 1. I expressed worry with this direction as I think we should be
> standardizing what algorithms do, rather than how they do it. I drew an
> analogy with sort and stable_sort: this is what is standardized, not
> quick_sort, merge_sort etc. Therefore, my preference is the shortest_path
> 'driver' approach.
> >
> > 2. A counter-argument was given that users may wish to specify a
> particular algorithm since e.g. Dijkstra's is inappropriate if there are
> negative weights.
> >
> > That's pretty much where we left it at the meeting.
> >
> > However, I think what point 2 is really highlighting is that the
> shortest_path 'driver' algorithm should be sufficiently flexible to
> disambiguate things like this (and this is true regardless of whether there
> are explicitly named alternatives). For example, I could imagine an
> overload set with a tag parameter indicating whether there are negative
> weights.
>
> Agreed with the general idea, but please let's not have overload sets
> with tag parameters if we're not dealing with a constructor and we're
> not dealing with an open-ended set of possibilities.
>
> It's "sort" and "stable_sort", thus it should be
> "shortest_path_positive_weights"
> and "shortest_path" (details of names tbd), i.e. functions are
> differentiated by name.
>
> Jens
>
> --
> SG19 mailing list
> SG19_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
>