Re: can s-exprs represent a graph without eval?

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   Date: Thu, 19 Jun 2003 10:26:45 -0700
   Subject: can s-exprs represent a graph without eval?
   From: James McCartney <asynth@io.com>
   To: <ll1-discuss@ai.mit.edu>
   
   
   S-exprs can represent trees of data easily. I am wondering if s-exprs, 
   or some other syntax, can be used to represent a graph just on reading, 
   without eval.
   
   I assume something simple could be done where you have a syntax to bind 
   symbols, and then access their bindings. Does Lisp do this already? or 
   is graph data just written as Lisp code and eval'ed?

If you are considering directed graphs, where each node
is represented as a cons cell (each node having outdegree 2)
or as a list (in which case you can have arbitrary outdegree),
then if there is a particular node N from which the entire graph
is reachable, you can do a depth-first search (DFS) from N.
This will define a spanning tree and furthermore every arc A
to a node P such that A is not in the spanning tree is encountered
later in the search than the (unique) arc to P that is in the
spanning tree.

Therefore you can notate a graph by notating the spanning tree
as an S-expression; and every node to which there is an arc that is
not part of the spanning tree is assigned a label; and wherever an
arc occurs that is not a part of the spanning tree, you notate a
reference to the label assigned to the node that is the target
of the arc; and every reference to a label will occur after the
assignment of that label.

In Common Lisp and some dialects of Scheme, the construction
#n=s assigns the label n (an integer) to the S-expression s,
and #n# is a reference to that label.

Clear as mud, eh?  Let's try some examples, using lists as nodes.

Here's the complete graph on three nodes:

#1=(#2=(#3=(#1# #2#) #1#) #3#)

Here's a ring of five nodes:

#1=(((((#1)))))

Here's a graph where node 1 points to nodes 2, 3, and 4,
each node also contains a letter (A, B, C or D), and node
4 additionally points to node 2:

#1=(A #2=(B) #3=(C) #4=(D #2#))

Because three of the assigned labels aren't used, we can
also write it as just

(A #2=(B) (C) (D #2#))

If we want to notate a circular Lisp list, where the list
holds the three items X, Y, and Z, and (eq (cdddr x) x),
we write

#1=(X Y Z . #1#)

--Guy Steele