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
>
>