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.

The advantage of this representation is that it is efficient in space
and time and that the implementation is free to use whatever tools
(e.g., hash tables) for which an abstract equivalence predicate
wouldn't suffice.

All other interfaces should be derived from this (or left to the user,
depending on their particular graph representation).

Am Di., 11. Apr. 2023 um 08:43 Uhr schrieb Dr. Arne Babenhauserheide
<xxxxxx@web.de>:
>
> Hi,
>
> I’m currently taking count of what needs to be done, so I went through
> the mailing list and took notes.
>
> As a first step I got the tests working on all included implementations
> but chicken (installing s7rs for chicken failed for me).
>
> These notes are not final yet, but I thought they could interest you.
> I’d be glad to get your comments:
>
> - [ ] utility to convert node + deps to graph: https://srfi-email.schemers.org/srfi-234/msg/21350510/
> - [ ] procedure that returns each
>   https://en.wikipedia.org/wiki/Strongly_connected_component as a list
>   should probably be added.
> - [ ] add a test case from https://issues.guix.gnu.org/58198
>   :      libnewsboat
>   :    /   |
>   :   |  regex-rs
>   :   |    |
>   :   strprintf.
> - [ ] discuss whether exception or #f for cyclic graphs. https://srfi-email.schemers.org/srfi-234/msg/20897186/
>   - argument for #false:  https://srfi-email.schemers.org/srfi-234/msg/20488634/
>   - maybe return (values #f message) in an error case and provide a
> version that raises message as exception. #false is preferred by John
> Cowan, the second value would be useful to provide information about
> cycles to developers.
> https://srfi-email.schemers.org/srfi-234/msg/21664156/
> - [ ] define the default for ~=~ — use =equal?=
> - [ ] Specify in the spec =circular-graph?=, =circular-graph-message=, =circular-graph-cycle= https://srfi-email.schemers.org/srfi-234/msg/21391924/
> - [ ] Note that this does topological sorting with simple edgelists.
> - [ ] Change to returning vectors for large graphs? https://srfi-email.schemers.org/srfi-234/msg/21391724/
>
> My plan is now to tackle them one by one to get topological sorting done.
>
> Best wishes,
> Arne
> --
> Unpolitisch sein
> heißt politisch sein,
> ohne es zu merken.
> draketo.de