Am Do., 13. Apr. 2023 um 19:05 Uhr schrieb Arthur A. Gleckler <s...@speechcode.com>: > > On Thu, Apr 13, 2023, 8:36 AM Marc Nieper-Wißkirchen <marc.nie...@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
