Am Mi., 30. Nov. 2022 um 11:14 Uhr schrieb Marc Nieper-Wißkirchen
<xxxxxx@gmail.com>:
>
> 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).

Hmmm... maybe the latter is not optimal.  The problem is that one
direction may be cheap for a particular graph, and the other direction
is expensive.  An algorithm consuming a graph should be able to tell
which fold is the more efficient one.

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