(Adding Andrew – he’s had problems getting added to the SG19 reflector)


From: SG19 <sg19-bounces_at_[hidden]ocpp.org> 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]<mailto: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