Lyybnyz is a Common Lisp library to manipulate directed graphs while maintaining them in minimized form using an incrementally efficient algorithm. For a less telegraphic statement of the problem, see Guido Tack's notes.
I have written a paper, "Hash-Consing Digraphs," giving an incrementally efficient algorithm for calculation of the relational coarsest partition. It is probably too long to publish conventionally, so perhaps it can be considered a tech report. To find the most recent draft, look here.
The algorithm in the paper is a revised version of the algorithm used in lyybnyz-0.2. As in lyybnyz-0.1, the algorithm replays classification of frontier vertices through a priority queue, randomizes the Hopcroft trick, and uses the randomized trick to balance a hop tree. As in lyybnyz-0.2, because the edges aren't labelled so the graph can't be preprocessed into a graph of small-outdegree vertices, the algorithm uses various differential trickiness to avoid iterating over or copying entire edge collections.
This release is less portable than lyybnyz-0.1, but considerably improved otherwise.
The algorithm has been considerably improved, and now the library can now minimize graphs containing vertices whose edge collections behave like sets, not just the tuples handled by the earlier release. In the terminology used by Paige and Tarjan (SIAM J. Comput. 16:973-989, 1987), the library now solves the relational coarsest partition problem.
As a practical improvement, the library is now structured as multiple semi-independent subsystems, not one monolithic unit, so that application programs can load only part of the library if they choose. Too bad that I inadvertently implemented that unportably!
The unportability is that the system can be built automatically on sbcl but not clisp for stupid reasons involving defsystem. This should be easy to fix. However, I am dithering about design decisions about the most flexible and least ugly way to fix them. Any fix is likely to involve tediously moving files around, rewriting require-ish statements, and perhaps even changing names used in the public interface. I would prefer to get such changes right without too many tries.
Two files are associated with the release, the software (as CL code and HTML documentation) and some very very rough draft typeset (LaTeX/Postscript) papers describing the algorithms and data structures in a language-independent way. Both are tar archives compressed with bzip2.
This release is a prototype based on a novel unreviewed algorithm, as slow as molasses and as clumsy as a particularly clumsy thing, but perhaps interesting in a world where alternatives seem to be glacially slow.
this release as output from *nix tar compressed with bzip2:
lyybnyz-0.1.tar.bz2
this release as uncompressed output from *nix tar:
lyybnyz-0.1.tar