Subject: Re: fyi - if you would like to help this soul...

From: "Terence Wilson" <[email-masked]>
Date: Wed, 29 Mar 1995 09:38:11 -0800

On Mar 29,  7:50am, Osman F. =?ISO-8859-1?Q?G=FCner?= wrote:
> Subject: fyi - if you would like to help this soul...
> From:	IN%"[email-masked]"  "Simon Kilvington" 29-MAR-1995
07:01:58.71
> To:	IN%"[email-masked]"
> CC:
> Subj:	CCL:Ring perception algorithms
>
> Dear all,
>
> 	does anyone have any references to ring perception algorithms?
> All I need to know is whether each bond in a molecule is either cyclic
> or acyclic.  It's fairly easy to think of ways of doing it but I was
> wondering if there are any cunning tricks that have been developed that
> make it faster/use less memory etc.
>
> 	thanks for any help,
>
> 	Si.
>
> ---
> Simon Kilvington, [email-masked]
>-- End of excerpt from Osman F. =?ISO-8859-1?Q?G=FCner?=

Finding the cyclic/acyclic bonds in a graph can be done in polynomial time by
walking the graph to deduce a spanning tree which can then be used to create a
fundamental basis set of rings. Linear combinations of the basis set generate
all possible rings in the graph.

Downs et al. is the most comprehensive survey of ring perception algorithms:

'Review of Ring Perception Algorithms for Chemical Graphs'. Downs et al. JCICS
1989, 29, 172-187.

-- 
"If you love your llama let it lambada."
Terence Wilson [email-masked] [email-masked] 510 357 2222 x1300
MDL Information Systems 14600 Catalina St, San Leandro, Ca 94577, U.S.A.