Am Mi., 30. Nov. 2022 um 10:52 Uhr schrieb Shiro Kawai <xxxxxx@gmail.com>:
>
> On Tue, Nov 29, 2022 at 11:14 PM Marc Nieper-Wißkirchen <xxxxxx@gmail.com> wrote:
>>
>> For large graphs, vectors are much more efficient than lists (both in
>> locality and in size).  To increase the applicability of SRFI 234,
>> graphs should be encoded as vectors (or, possibly even better, by some
>> procedure).
>
>
> In another library of Gauche I used procedures to represent graphs: https://practical-scheme.net/gauche/man/gauche-refe/Calculate-dominator-tree.html
> It is required abstraction for a particular use case that prompted the creation of the library.   It's been working well, for it does not require users to adapt their representation into what the library requires.  On the other hand, I felt it cumbersome when the data I had was simple enough to be written in an S-expression yet I had to prepare access procedures.
>
> It might be useful if we create an implementation-agnostic graph representation that bundles related access procedures, much like comparators.   But that will be another story (and better to be explored in individual implementations before starting srfi).

This sounds like a good idea to me.  Can we put SRFI 234 dormant until
such a directed-graph type is fleshed out?

At a minimum, such a dg type should expose a comparator (for the
nodes) and a fold over all nodes.  This fold calls a procedure PROC
that takes the current node, a fold procedure for the current node's
successors, and the accumulator.  Probably there should also be a fold
of the opposite graph (where the inner fold goes through the
predecessors).

> For this srfi, I can see both simple list representation and accessor-procedure representation are useful for the users (vector representation may be covered by procedures).   Maybe we can have the procedural one as a primitive interface and list one as a utility on top of the procedural one?

Following the Unix philosophy, topological sort should only do one
thing.  Let accept a graph object; let the user be explicit about
converting a listy structure into a graph object (the dg library
should have such procedures).  As has been pointed out in this thread,
there is more than one way to represent a dg graph by a list of lists.

Marc