[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: address@hidden, address@hidden*Subject*: Re: can s-exprs represent a graph without eval?*From*: Guy Steele - Sun Microsystems Labs <address@hidden>*Date*: Thu, 19 Jun 2003 15:51:38 -0400 (EDT)*Reply-to*: Guy Steele - Sun Microsystems Labs <address@hidden>*Sender*: 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

- Prev by Date:
**Re: can s-exprs represent a graph without eval?** - Next by Date:
**Re: can s-exprs represent a graph without eval?** - Previous by thread:
**Why Images Bother People (or, at least me)** - Next by thread:
**Re: can s-exprs represent a graph without eval?** - Index(es):