[racket] minimum spanning tree

On Mon, Dec 3, 2012 at 5:07 PM, J. Ian Johnson <ianj at ccs.neu.edu> wrote:
> Graph algorithms are often meant to be very fast, and different algorithms necessitate different representations. Two popular representations are adjacency lists and shared structures.

The representations usually used in general purpose graphs libraries
are adiacency lists and incidence matrices.

Two good examples that I know of are:  Knuth's Stanford GraphBase
(available from his home page and in published book form), and the
Combinatorica library for Mathematica (code available freely on the
net, manual available as a published book "Computational Discrete
Mathematics" by Skiena & Pemmaraju).

> It also isn't right to call them lists unless you're talking about multigraphs. Indeed successor nodes should be treated as a set, but Racket's sets have quite a bit of overhead, especially for small sets. Should it be fast to compute predecessor nodes? There are too many considerations for there to be just one blessed representation, IMHO.

Linked lists made of cons pairs are not the best data structure for
every possible use of a sequence data structure.  However, we find
this data structure very useful, don't we?  we force them into uses
for which they are not optimal, because of the convenience of having
available a vast library using them. And when we can't fit them to our
purpose we use a more specialized data structure.

I think a similar compromise for a graph data structure would be very useful.

Cheers
P.