blib/lib/Chemistry/Ring/Find.pm

filter: Statementstmt 30.8% 42 / 136 Branchbran 9.6% 6 / 62 Conditioncond 3.2% 1 / 31 MC/DCmcdc 0.0% 0 / 17 Subroutinesub 62.5% 5 / 8 Podpod 40.0% 2 / 5 totaltotal 21.6% 56 / 259 CC 50 SCAR 66.6
CC
50
Cov
21%
find_ring
1260.0
contains_ring
42.0
find_rings
8.5
CRAP 779.7
↑ Summary blib/lib/Chemistry/MidasPattern.pm »
1 package Chemistry::Ring::Find;
2  
3 9 $VERSION = 0.19;
4 # $Id: Find.pm,v 1.1.1.1 2005/03/29 23:57:36 itubert Exp $
5  
6 =head1 NAME
7  
8 Chemistry::Ring::Find - Find the rings (cycles) in a molecule
9  
10 =head1 SYNOPSIS
11  
12 use Chemistry::Ring::Find ':all';
13  
14 # find the smallest ring containing $atom
15 my $ring = find_ring($atom);
16  
17 # find all the rings containing $bond
18 my @rings = find_ring($bond, all => 1);
19  
20 # see below for more options
21  
22 # find the six 4-atom rings in cubane
23 @rings = find_rings($cubane);
24  
25 # find a cubane SSSR with five rings
26 @rings = find_rings($cubane, sssr => 1);
27  
28 =head1 DESCRIPTION
29  
30 The Chemistry::Ring::Find module implements a breadth-first ring finding
31 algorithm, and it can find all rings that contain a given atom or bond, the
32 Smallest Set of Smallest Rings (SSSR), or the "almost SSSR", which is an
33 unambiguous set of rings for cases such as cubane.The algorithms are based on
34 ideas from:
35  
36 1) Leach, A. R.; Dolata, D. P.; Prout, P. Automated Conformational Analysis and
37 Structure Generation: Algorithms for Molecular Perception J. Chem. Inf. Comput.
38 Sci. 1990, 30, 316-324
39  
40 2) Figueras, J. Ring perception using breadth-first search. J. Chem. Inf.
41 Comput. Sci. 1996, 36, 986-991.
42  
43 Ref. 2 is only used for find_ring, not for find_rings, because it has been
44 shown that the overall SSSR method in ref 2 has bugs. Ref 1 inspired
45 find_rings, which depends on find_ring.
46  
47 This module is part of the PerlMol project, L<http://www.perlmol.org/>.
48  
49 =head1 FUNCTIONS
50  
51 These functions may be exported explicitly, or all by using the :all tag, but
52 nothing is exported by default.
53  
54 =over
55  
56 =cut
57  
58  
59 9 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
60 9 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
61 9 ▶use Chemistry::Ring;
Subroutine BEGIN: called CC=1 SCAR=0.0
62  
63 9 our @ISA = qw(Exporter);
64 9 our @EXPORT_OK = qw(find_ring find_rings);
65 9 our %EXPORT_TAGS = ( all => \@EXPORT_OK );
66  
67 9 our $DEBUG = 0;
68  
69 =item find_ring($origin, %opts)
70  
71 Find the smallest ring containg $origin, which may be either an atom or a bond.
72 Returns a Chemistry::Ring object. Options:
73  
74 =over
75  
76 =item all
77  
78 If true, find all the rings containing $origin. If false, return the first ring
79 found. Defaults to false. "All" is supposed to include only "simple" rings,
80 that is, rings that are not a combination of smaller rings.
81  
82 =item min
83  
84 Only find rings with a the given minimum size. Defaults to zero.
85  
86 =item max
87  
88 Only find rings up to the given maximium size. Defaults to unlimited size.
89  
90 =item size
91  
92 Only find rings with this size. Same as setting min and max to the same size.
93 Default: unspecified.
94  
95 =item exclude
96  
97 An array reference containing a list of atoms that must NOT be present in the
98 ring. Defaults to the empty list.
99  
100 =item mirror
101  
102 If true, find each ring twice (forwards and backwards). Defaults to false.
103  
104 =back
105  
106 =cut
107  
108 # $origin is an atom
109 # options: min, max, size, all, mirror, exclude
110 0 ▶sub find_ring {
Subroutine find_ring: not called CC=35 SCAR=71.4
Pod documented
111 0 my ($origin, %opts) = @_;
112 0 ▶ my $min_size = $opts{min} || $opts{size} || 0;
Condition0%0/5
$opts{'min'} || $opts{'size'} || 0
l!l
00
$opts{"min"} or $opts{"size"}
l!l&&r!l&&!r
000
MC/DC0%0/2
$opts{'min'} || $opts{'size'} || 0
$opts{"min"} $opts{"size"}
Truth table0%0/3
A or B
A= $opts{"min"}B= $opts{"size"}
ABresult
1X1
011
000
113 0 ▶ my $max_size = $opts{max} || $opts{size};
Condition0%0/3
$opts{'max'} || $opts{'size'}
l!l&&r!l&&!r
000
MC/DC0%0/2
$opts{'max'} || $opts{'size'}
$opts{'max'} $opts{'size'}
Truth table0%0/3
A || B
A= $opts{'max'}B= $opts{'size'}
ABresult
1X1
011
000
114 0 my %paths;
115 my %bond_paths;
116 0 my @q;
117 0 my @rings;
118 0 my %used_end_nodes;
119 0 my $required_bond;
120 0 my %exclude;
121 0 ▶ @exclude{ @{$opts{exclude} || []} } = ();
Condition0%0/2
$opts{'exclude'} || []
l!l
00
MC/DC0%0/1
$opts{'exclude'} || []
$opts{'exclude'}
Truth table0%0/2
A
A= $opts{'exclude'}
Aresult
11
00
122  
123 0 ▶ if ($origin->isa("Chemistry::Bond")) {
Branch: 1 branch
BranchTrueFalseTotal
if ($origin->isa("Chemistry::Bond")) 0 0 0
124 0 $required_bond = $origin;
125 0 ($origin) = $origin->atoms;
126 }
127 0 @q = ($origin);
128 0 $paths{$origin} = [$origin];
129 0 $bond_paths{$origin} = [];
130 # $path{$atom} means how to get to $atom from $origin
131  
132 0 my $a;
133 0 ▶ while ($a = shift @q) {
Branch: 1 branch
BranchTrueFalseTotal
if ($a = shift @q) 0 0 0
134 0 my $from = $paths{$a}[-2];
135 0 ▶ print "at $a from $from\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
136 0 for my $bn ($a->bonds_neighbors($from)) {
137 0 my $nei = $bn->{to};
138 0 my $bond = $bn->{bond};
139 0 ▶ next if exists $exclude{$nei};
Branch: 1 branch
BranchTrueFalseTotal
if exists $exclude{$nei} 0 0 0
140 0 ▶ print " -> $nei\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
141 0 ▶ if ($paths{$nei}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($paths{$nei}) { } 0 0 0
142 0 ▶ print "found a path collision... " if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
143 # check to make sure that the ring really started at $origin
144 # and the size is what was requested
145 0 my $size = @{$paths{$nei}} + @{$paths{$a}} - 1;
146 0 ▶ if($paths{$nei}[1] != $paths{$a}[1]
Branch: 1 branch
BranchTrueFalseTotal
if ($paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size and !$max_size || $size <= $max_size) { } 0 0 0
Condition0%0/9
$paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size and !$max_size || $size <= $max_size
!ll&&!rl&&r
000
$paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size
!ll&&!rl&&r
000
not $max_size or $size <= $max_size
l!l&&r!l&&!r
000
MC/DC0%0/4
$paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size and !$max_size || $size <= $max_size
$paths{$nei}[1] != $paths{$a}[1] $size >= $min_size not $max_size $size <= $max_size
Truth table0%0/5
A and B and not(C) or D
A= $paths{$nei}[1] != $paths{$a}[1]B= $size >= $min_sizeC= not $max_sizeD= $size <= $max_size
ABCDresult
0XXX0
10XX0
11000
111X1
11011
147 and $size >= $min_size
148 and !$max_size || $size <= $max_size)
149 {
150 0 ▶ print "VALID\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
151 0 my @atoms = (@{$paths{$a}}, reverse @{$paths{$nei}});
152 0 ▶ print "RING = ", print_path(\@atoms) if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
153 0 pop @atoms;
154 0 ▶ if ($used_end_nodes{$atoms[1]} and !$opts{mirror}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($used_end_nodes{$atoms[1]} and not $opts{"mirror"}) 0 0 0
Condition0%0/3
$used_end_nodes{$atoms[1]} and not $opts{"mirror"}
!ll&&!rl&&r
000
MC/DC0%0/2
$used_end_nodes{$atoms[1]} and not $opts{"mirror"}
$used_end_nodes{$atoms[1]} not $opts{"mirror"}
Truth table0%0/3
A and not(B)
A= $used_end_nodes{$atoms[1]}B= not $opts{"mirror"}
ABresult
0X0
100
111
155 0 ▶ print "skipping redundant ring\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
156 0 next; # don't want to find rings twice
157 }
158 0 my @bonds = (@{$bond_paths{$a}}, $bond,
159 0 reverse @{$bond_paths{$nei}});
160 0 ▶ if ($required_bond
Branch: 1 branch
BranchTrueFalseTotal
if ($required_bond and not grep({$_ eq $required_bond;} @bonds)) 0 0 0
Condition0%0/3
$required_bond and not grep({$_ eq $required_bond;} @bonds)
!ll&&!rl&&r
000
MC/DC0%0/2
$required_bond and not grep({$_ eq $required_bond;} @bonds)
$required_bond not grep({$_ eq $required_bond;} @bonds)
Truth table0%0/3
A and not(B)
A= $required_bondB= not grep({$_ eq $required_bond;} @bonds)
ABresult
0X0
100
111
161 0 and not grep {$_ eq $required_bond} @bonds) {
162 0 ▶ print "does not include required bond\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
163 0 next;
164 }
165 0 ▶ if (contains_ring(\@atoms, \@rings)) {
Branch: 1 branch
BranchTrueFalseTotal
if (contains_ring(\@atoms, \@rings)) 0 0 0
166 0 ▶ print "contains another ring\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
167 0 next;
168 }
169 0 my $r = Chemistry::Ring->new;
170 0 $r->add_atom(@atoms);
171 0 $r->add_bond(@bonds);
172 0 ▶ return $r unless $opts{all}; # FOUND VALID RING
Branch: 1 branch
BranchTrueFalseTotal
unless $opts{"all"} 0 0 0
173 0 push @rings, $r;
174 0 $used_end_nodes{$atoms[-1]} = 1;
175 #@used_nodes{@atoms} = ();
176 } else {
177 print "NOT VALID",
178 0 print_path( [@{$paths{$a}},
179 0 ▶ reverse @{$paths{$nei->id}}]) if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
180 }
181 } else {
182 0 ▶ if (!$max_size || @{$paths{$a}} < ($max_size / 2) + 0.1) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $max_size or @{$paths{$a};} < $max_size / 2 + 0.1) { } 0 0 0
Condition0%0/3
not $max_size or @{$paths{$a};} < $max_size / 2 + "0.1"
l!l&&r!l&&!r
000
MC/DC0%0/2
not $max_size or @{$paths{$a};} < $max_size / 2 + "0.1"
not $max_size @{$paths{$a};} < $max_size / 2 + "0.1"
Truth table0%0/3
not(A) or B
A= not $max_sizeB= @{$paths{$a};} < $max_size / 2 + "0.1"
ABresult
1X1
011
000
183 0 push @q, $nei;
184 0 ▶ print " pushing path\n" if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
185 0 $paths{$nei} = [@{$paths{$a}}, $nei];
186 0 $bond_paths{$nei} = [@{$bond_paths{$a}}, $bond];
187 0 ▶ print print_path($paths{$nei}) if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
188 } else {
189 0 ▶ print "path too long; " if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
190 0 ▶ print print_path($paths{$a}) if $DEBUG;
Branch: 1 branch
BranchTrueFalseTotal
if $Chemistry::Ring::Find::DEBUG 0 0 0
191 #path too long
192 }
193 }
194 }
195 }
196 0 @rings;
197 }
198  
199  
200 0 ▶sub print_path {
Subroutine print_path: not called CC=2 SCAR=17.9
Pod undocumented
201 0 my $p = shift;
202 0 my $ret = " PATH: ";
203 0 for my $a (@$p) {
204 0 $ret .= "$a - ";
205 }
206 0 $ret .= "\n";
207 }
208  
209 # contains_ring($atoms, $rings)
210 # returns true if one of the rings in the array ref $rings is a proper subset
211 # of the atom list in the array ref $atom.
212 0 ▶sub contains_ring {
Subroutine contains_ring: not called CC=6 SCAR=37.4
Pod undocumented
213 0 my ($atoms, $rings) = @_;
214 0 my %seen;
215 0 @seen{@$atoms} = ();
216 0 for my $ring (@$rings) {
217 0 my $unique_atoms = $ring->atoms;
218 0 ▶ next if $unique_atoms >= @$atoms; # ring is same size or bigger
Branch: 1 branch
BranchTrueFalseTotal
if $unique_atoms >= @$atoms 0 0 0
219 # make sure that $ring has at least one atom not in $atoms
220 0 for my $atom ($ring->atoms) {
221 0 ▶ if (exists $seen{$atom}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $seen{$atom}) { } 0 0 0
222 0 $unique_atoms--;
223 } else {
224 0 last; # there's at least one unique atom!
225 }
226 }
227 0 ▶ return 1 unless $unique_atoms;
Branch: 1 branch
BranchTrueFalseTotal
unless $unique_atoms 0 0 0
228 }
229 0 0;
230 }
231  
232 =item @rings = find_rings($mol, %options)
233  
234 Find "all" the rings in the molecule. In general it return the Smallest Set of
235 Smallest Rings (SSSR). However, since it is well known that the SSSR is not
236 unique for molecules such as cubane (where the SSSR consists of five
237 unspecified four-member rings, even if the symmetry of the molecule would
238 suggest that the six faces of the cube are equivalent), in such cases
239 find_rings will return a non-ambiguous "non-smallest" set of smallest rings,
240 unless the "sssr" option is given. For example,
241  
242 @rings = find_rings($cubane);
243 # returns SIX four-member rings
244  
245 @rings = find_rings($cubane, sssr => 1);
246 # returns FIVE four-member rings (an unspecified subset of
247 # the six rings above.)
248  
249 =cut
250  
251 14 ▶sub find_rings {
Subroutine find_rings: called CC=7 SCAR=21.4
Pod documented
252 14 my ($mol, %opts) = @_;
253 14 my $visited = {};
254 14 my @ring_bonds;
255 14 for my $atom ($mol->atoms) {
256 40 ▶ next if $visited->{$atom};
Branch: 1 branch
BranchTrueFalseTotal
if $visited->{$atom} 26 14 40
257 14 push @ring_bonds, find_ring_bonds($mol, \%opts, $atom, $visited);
258 }
259 14 my @rings;
260 14 my $n_rings = @ring_bonds;
261 #print "cyclomatic number=$n_rings\n";
262 14 for my $ring_bond (@ring_bonds) {
263 0 push @rings, find_ring($ring_bond, all => 1)
264 }
265 14 my %seen;
266 0 my @ring_keys = map { join " ", sort $_->atoms } @rings;
267 14 @seen{@ring_keys} = @rings;
268 0 @rings = sort { $a->atoms <=> $b->atoms } values %seen;
269 14 ▶ if (!$opts{sssr} and @rings > $n_rings) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $opts{"sssr"} and @rings > $n_rings) 0 14 14
Condition33%1/3
not $opts{"sssr"} and @rings > $n_rings
!ll&&!rl&&r
0140
MC/DC0%0/2
not $opts{"sssr"} and @rings > $n_rings
not $opts{"sssr"} @rings > $n_rings
Truth table33%1/3
not(A) and B
A= not $opts{"sssr"}B= @rings > $n_rings
ABresult
0X0
100
111
270 0 ▶ $n_rings++ if $rings[$n_rings]->atoms == $rings[$n_rings-1]->atoms;
Branch: 1 branch
BranchTrueFalseTotal
if $rings[$n_rings]->atoms == $rings[$n_rings - 1]->atoms 0 0 0
271 }
272 14 splice @rings, $n_rings;
273 14 @rings;
274 }
275  
276 40 ▶sub find_ring_bonds {
Subroutine find_ring_bonds: called CC=4 SCAR=13.9
Pod undocumented
277 40 my ($mol, $opts, $atom, $visited) = @_;
278  
279 40 my @ring_bonds;
280 40 $visited->{$atom} = 1;
281 40 for my $bn ($atom->bonds_neighbors) {
282 52 my $nei = $bn->{to};
283 52 my $bond = $bn->{bond};
284 52 ▶ next if $visited->{$bond};
Branch: 1 branch
BranchTrueFalseTotal
if $visited->{$bond} 26 26 52
285 26 $visited->{$bond} = 1;
286 26 ▶ if ($visited->{$nei}) { # closed ring
Branch: 1 branch
BranchTrueFalseTotal
if ($visited->{$nei}) { } 0 26 26
287 #print "closing ring\n";
288 0 push @ring_bonds, $bond;
289 } else {
290 26 push @ring_bonds,
291 find_ring_bonds($mol, $opts, $nei, $visited);
292 }
293 }
294 40 @ring_bonds;
295 }
296  
297 9 1;
298  
299 =back
300  
301 =head1 BUGS
302  
303 The "all" option in find_ring doesn't quite work as expected. It finds all
304 simple rings and some bridged rings. It never finds fused rings (which is good).
305  
306 =head1 VERSION
307  
308 0.19
309  
310 =head1 SEE ALSO
311  
312 L<Chemistry::Ring>, L<http://www.perlmol.org>.
313  
314 =head1 AUTHOR
315  
316 Ivan Tubert-Brohman E<lt>itub@cpan.orgE<gt>
317  
318 =head1 COPYRIGHT
319  
320 Copyright (c) 2005 Ivan Tubert-Brohman. All rights reserved. This program is
321 free software; you can redistribute it and/or modify it under the same terms as
322 Perl itself.
323  
324 =cut
325  
↑ Summary blib/lib/Chemistry/MidasPattern.pm »