On Mon, Dec 3, 2012 at 5:07 PM, J. Ian Johnson <i...@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
