On 12/05/2025 23.53, Phil Ratzloff via SG19 wrote:
> I wasn't aware of the compile-time requirements for Mandates, so that definitely needs to be moved into pre-conditions.
>
> If the pre-conditions aren't valid then an exception must be thrown, so that developers can rely on the behavior.

What?

Please read [description] in the standard, it explains all this.

Jens


> There has been discussion of whether exceptions should be thrown or not, largely based on whether the library supports Freestanding or not. Because algorithms depend on the queue and stack containers that don't support Freestanding, and because memory allocation is often required that can throw bad_alloc, there's no reason to support Freestanding and exceptions are acceptable.
>
> The reason to throw exceptions is an increased concern of safety in the industry. Most pre-conditions have a O(1) complexity, which is a one-time check when an algorithm is entered and is well work the cost. Considering Dijkstra's Shortest Paths, a check is made for negative weights which requires O(n). This is a question of safety and correctness. As a comparison, boost graph throws an exception on negative weights, so I feel we're in good company to add this check also.
>
> When thinking about the Preconditions and Throws sections, they're directly related to each other and it feels like they're redundant in some cases. Is it reasonable to simply say that an exception is thrown when a precondition isn't met, and remove the matching entry in Throws?
>
> I think adding these items to the algorithms paper makes sense.
> Thanks for your input.
>
>
> ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> *From:* SG19 on behalf of Andrzej Krzemienski via SG19
> *Sent:* Friday, May 09, 2025 4:35 AM
> *To:* sg19_at_[hidden]
> *Cc:* Andrzej Krzemienski
> *Subject:* [isocpp-sg19] Graph algorithms -- feedback on the specification of the algorithms
>
> */EXTERNAL/*
>
> Hi All,
> I am new to this group, so I do not know how such feedback should be delivered. I didn't have time to report the issue in yesterday's call, so let me do it over email.
>
> I think that it is a design question how the graph algorithms should respond to the "questionable" input values, such as non-existent vertex index, or not properly initialized function output parameters.
>
> Take for instance `dijkstra_shortest_paths` specified in wg21.link/p3128. It specifies:
>
> 1 Mandates:
> —(1.1) 0 <= source < num_vertices(graph) for the single-source version.
> —(1.2) 0 <= source < num_vertices(graph), for each source in sources, for the multi-source version.
> —(1.3) The weight function w must return a non-negative value.
>
> 2 Preconditions:
> —(2.1) distances[i] = shortest_path_infinite_distance() for 0 <= i < num_vertices(g).
> —(2.2) predecessors[i] = i for 0 <= i < num_vertices(g).
>
> 4 Throws:
> —(4.1) An out_of_range exception is thrown in the following cases:
> —(4.1.1) size(distances)< size(vertices(g))
> —(4.1.2) size(predecessor)< size(vertices(g))
> —(4.1.3) source is not in the range 0 <= source < num_vertices(graph).
> —(4.1.4) The weight function returns a negative value. This check is not made if the weight value type is an unsigned integral type.
>
> First of all, section "Mandates" only specifies compile-time checkable properties, and puts a hard requirement on the implementations to check the indicated conditions *at compile time*, for instance by using static_assert. The current conditions 1.1, 1.2, 1.3 are clearly not compile-time-checkable, so this is a bug in specification.
>
> But more importantly, regarding the condition `0 <= source < num_vertices(graph)` you have to make the choice:
> 1. Are the implementations *required* to check the condition and throw an exception when it is not met, so that the programmers can rely on this exception, and can "safely" pass bad indexes and expect predictable behavior?
> 2. Or are the implementations free to assume that the users always pass the correct values of `source`? This means that they can check the condition, but do not have to. If they check, they can either throw an exception, or launch a debugger, or terminate the program with a core dump. If the programmer passes the bad value of `source` they are guaranteed nothing, and it can even be undefined behavior.
>
> It is important that the paper documents this choice and the rationale for it. It is an important design decision. And then based on this decision, you either list the conditions under section "Preconditions" or you don't.
> If you list this under section "Precondition" it means #2 above, and you can no longer say that an exception is thrown in this case.
>
> The following links describe what Mandates and Precoonditions mean in detail:
> * https://eel.is/c++draft/description#structure.specifications-3.2 <https://protect.checkpoint.com/v2/r01/___https://eel.is/c++draft/description%23structure.specifications-3.2___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjYxZDZlOWY3YjRkNDQ0ODdlNWMxZTMwNzNlYzQ5Mjc6Nzo0MzFiOjdhYzEyZWUxZDg0OTQxNmZmMjkwNDI2MTZkYjAzZWU0MzAzYzdmMzFkMjBiYmM4NWI2YTA5NDBkOTBhYTY5MmI6aDpUOk4>
> * https://eel.is/c++draft/description#structure.specifications-3.3 <https://protect.checkpoint.com/v2/r01/___https://eel.is/c++draft/description%23structure.specifications-3.3___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjYxZDZlOWY3YjRkNDQ0ODdlNWMxZTMwNzNlYzQ5Mjc6NzphZGJmOjhhYWRlNmY3NDI1ODk5NDgwYjJhNzY5MTVmZmUxNmQwOGMwYThmZjRkNzk3ODdmNDM4YWEzMWI2NDQ3OGUyODY6aDpUOk4>
>
> I recorded this issue in https://github.com/stdgraph/P1709/issues/113 <https://github.com/stdgraph/P1709/issues/113>
>
> Regards,
> &rzej;
>