Am Do., 13. Apr. 2023 um 19:05 Uhr schrieb Arthur A. Gleckler
<xxxxxx@speechcode.com>:
>
> On Thu, Apr 13, 2023, 8:36 AM Marc Nieper-Wißkirchen <xxxxxx@gmail.com> wrote:
>>
>> The most efficient neutral representation of a DAG is probably a
>> vector (v_0 ... v_n-1) of vectors.  In this case, there would be n
>> nodes.  Each single vector v_i is the vector of successors of the i-th
>> node, where the successors are represented by exact integers between 0
>> and n-1.
>
>
> It would be nice to have an abstract interface rather than a concrete implementation — or at least you have an option to use that.

The proposed interface is as abstract as Scheme's use of lists to
model sequences, so I don't see a problem here.

Of course, one can hide everything behind some opaque record type but
then would be no improvement.

 > Also, any representation should allow for edge labels, even if
they're not required.

A library dealing with general graphs and operations on graphs (like
collapsing of edges), etc., would need to deal with it.

A procedure such as the one exported by SRFI 234 doesn't need all
these bells and whistles; I would compare it to sort and vector-sort
of R6RS/SRFI 132 (which also don't speak about abstract sequences).

I would see a general graph library (defining some opaque graph types)
using SRFI 234 to provide topological sorting; other use cases that
need utmost efficiency or don't need fancy graph operations would use
SRFI 234 directly.

Marc