Graph representation in Dr Scheme

Question

I want to represent a graph in Dr. Scheme in the following manner:

For each node I want to store it's value and a list of adjacent nodes,the problem which i'm having difficulties with is that I want the adjacent nodes to be stored as references to other nodes.

For example: I want node ny to be stored as („NY“ (l p)) where l and p are adjacent nodes,and not as („NY“ („London“ „Paris“)).

Answer 1

The answer depends on whether you want cycles or not -- dealing with them can complicate things. But if you want to do the representation with only lists, then shared is your friend. For example:

(shared ([NY     (list "NY"     (list London Paris))]
         [Paris  (list "Paris"  (list NY))]
         [London (list "London" (list NY))])
  (list NY Paris London))

If your goal is to actually write "real" code, then using your own structs would be much better than lists (but then shared would not work).

For the case of using promises, cycles become easy to do with just letrec. Here's how the above will look in this case:

(letrec ([NY     (list "NY"     (delay (list London Paris)))]
         [Paris  (list "Paris"  (delay (list NY)))]
         [London (list "London" (delay (list NY)))])
  (list NY Paris London))

Alternatively, you can wrap a delay around each occurrence of a city inside the lists.