guile-user
[Top][All Lists]

## Re: [wanted] automagic generation of graphs

 From: Jon Wilson Subject: Re: [wanted] automagic generation of graphs Date: Tue, 24 Jul 2007 13:49:14 -0400 User-agent: Thunderbird 1.5.0.12 (X11/20070604)

```Marco Maggi wrote:
```
```Thanks to all. Am I correct in saying that with a form like:

(a . body)

if the symbol 'a' appears in 'body' the graph is cyclic,
while if the symbol does not appear in its own body the
graph is Acyclic?
```
Well, it is immediately obvious that any graph (or digraph) which has such a form has a cycle. So if a graph is acyclic, then no such form appears. But you also want the converse or its contrapositive: if no such form appears, then the graph is acyclic; if a graph is cyclic, then such a form appears.
```
Are you trying to represent graphs or digraphs?

I. you are representing graphs

```
The answer is no. (a (b c) c) contains a cycle a-b-c-a, but does not contain an (a . body) with a in body form.
```

II. you are representing digraphs

```
The answer is provisionally no. (a (b c) (c b)) contains a cycle b->c->b, but no form (a . body) with a in body. However, this graph could also be represented as (a (b (c b)) c), which does contain such a form. Notice that in this latter representation, the first time a node appears, its edge list is given.
```
```
So, if we do not require the edge list to be given at the first appearance of a node, the answer is definitely no. OTOH, if we do make such a requirement, the answer seems to be yes, but I have not proven this to be so.
```
Regards,
Jon

```