Marc Nieper-Wißkirchen <xxxxxx@gmail.com> writes:
> https://github.com/scheme-libraries/scheme-libraries/blob/main/lib/scheme-libraries/graph-coloring.sls

I now got to read the interface, but it does not feel like a good match
for topological sort to me. Too far detached from primitive values and
too much construction needed for the happy path of enumerable, hashable
values.

Different from graph coloring, the output here is just an ordered list,
the input just needs uni-directional connections, and we don’t need to
track metadata on the nodes.

But there is a way to keep this simple: enable using index values by
adding an optional argument with a vector to look up the actual values.

For non-comparable or non-hashable values, the solution is then to pass
an edgelist of the index-values into the vector (which are by definition
comparable and hashable).

This also has the advantage of keeping the memory footprint of the
data used in the topological sort minimal, so using index-values is also
useful in the case of very large graphs.

The interfaces would then be:

(define topological-sort
  (case-lambda
    ((graph) (topological-sort-impl nodes equal? #f))
    ((graph eq) (topological-sort-impl nodes eq #f))
    ((graph eq nodelist) (topological-sort-impl nodes eq v))))

and

(define edgelist->graph
  (case-lambda
    ((edgelist) (edgelist->graph-impl edgelist assoc))
    ((edgelist asc) (edgelist->graph-impl edgelist asc))))

edgelist->graph does not actually need an equals implementation, but the
version of assoc which matches the eq of the sort: assoc, assv, or assq.

Do you see a fundamental flaw in this?
(aside from not matching the style you’d use)

Best wishes,
Arne

PS: for the exception I agree with your reasoning. I’ll remove the
    exception throwing version.