[racket] minimum spanning tree

You are making a very good point here, especially the last one, 
which in a sense exposes the folly of Perlis's maxim (it is better
to have one data type with a 100 operations than 10 data types 
with 10 operations each). One, the maxim biases programmers 
and before they know it, they have introduced bad dependences 
and performance problems and whoknowswhat. 

---------------------------------------------------------------

Having said that, I think Ian's point is equally good. So here
is what I am wondering. 

Isn't the case of graphs worth a case study where we define 
a WIDE interface for graphs and their operations, which we 
can do so with contracts. Then we implement it in several 
different ways and conduct performance studies (small and
large). And we advertise, which library is good for which 
kind of scenario. 

I am sure that some data structure person has done this
for C++ or some such language. The Saarbrücken MPI 1 comes
to mind. BUT, I am also sure that we don't have it and that
we would benefit from having one. 

NOW: as we conduct this study, we might be able to articulate
performance "contracts" (that's probably the wrong word) and
possibly learn how to add those to library implementations as
a secondary interface. Doing so would once again distinguish
Racket from other programming languages. 

It is probably a dissertation, possibly more. 



















On Dec 4, 2012, at 5:36 AM, Pierpaolo Bernardi wrote:

> 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.
> 
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4373 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20121205/52954024/attachment-0001.p7s>