On Wed, Nov 30, 2022 at 4:14 AM Marc Nieper-Wißkirchen < [email protected]> 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). > I'm okay with encoding it as a vector, but I think using a procedure is a mistake. > > "Each connection is a list of the form (node dependency dependency ...), > > meaning that dependencies are dependent on node." -> Is this the > > customary order to write the graph? Makefile and similar syntaxes uses > > (node dependency dependency ...) The order is right, but the prose is wrong: it should of course say that *node* depends on *dependencies*. > > "It is an error if the same node (in the sense of =) appears in more > > than one connection." -> Appears at the head of more than one connection? > Yes. > > > > Another procedure that returns each > > https://en.wikipedia.org/wiki/Strongly_connected_component as a list > > should probably be added. > Out of scope, I think. I agree that returning #f is better than signaling an exception: a cyclic graph is not an exceptional situation. Threads like this show that SRFI may not be the right forum for this procedure. After all, toposort can be implemented portably with reasonable efficiency. That doesn't make sense: portable implementations of SRFIs are encouraged per the SRFI spec.
