[racket] shortest paths, resource allocation/scheduling

From: Geoffrey S. Knauth (geoff at knauth.org)
Date: Mon Dec 5 10:00:43 EST 2011

I'm wondering if there is something in the now very rich set of Racket libraries that already does this.  Let's say I have 5 points {A,B,C,D,E}.  I want to interconnect all of them:

{AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF}

That's 15 edges rather than the 5x5=25 that a dumb interconnect would do.  To start, I just need to track and sort the edge weights, and AB is the same as BA.

I can write the code to do this easily enough, but then it occurred to me Racket might already have something that does this with a single function call.

In actual fact I have 121 points (Pennsylvania public airports plus a maintenance facility in New Jersey).

Geoff

P.S.  In 2006 I asked if there was a graph theory library and Jens Axel Søgaard kindly sent me some code, but I can't immediately find it to see if his code answered this question.

P.P.S.  I found the following Perl module:

http://search.cpan.org/~jhi/Graph-0.94/lib/Graph.pod

which looks like the beginning of a graph module I'd look for in Racket.  Maybe I or someone else can implement something like that in Racket.




Posted on the users mailing list.