| 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
$opts{"min"} or $opts{"size"}
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"}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 113 | 0 | ▶ | my $max_size = $opts{max} || $opts{size}; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Condition0%0/3
$opts{'max'} || $opts{'size'}
MC/DC0%0/2
$opts{'max'} || $opts{'size'}
$opts{'max'}
$opts{'size'}
Truth table0%0/3
A || B
A= $opts{'max'}B= $opts{'size'}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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'} || []
MC/DC0%0/1
$opts{'exclude'} || []
$opts{'exclude'}
Truth table0%0/2
A
A= $opts{'exclude'}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 122 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 123 | 0 | ▶ | if ($origin->isa("Chemistry::Bond")) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 134 | 0 | my $from = $paths{$a}[-2]; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 135 | 0 | ▶ | print "at $a from $from\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 140 | 0 | ▶ | print " -> $nei\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 141 | 0 | ▶ | if ($paths{$nei}) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 142 | 0 | ▶ | print "found a path collision... " if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition0%0/9
$paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size and !$max_size || $size <= $max_size
$paths{$nei}[1] != $paths{$a}[1] and $size >= $min_size
not $max_size or $size <= $max_size
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 147 | and $size >= $min_size | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 148 | and !$max_size || $size <= $max_size) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 149 | { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 150 | 0 | ▶ | print "VALID\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 151 | 0 | my @atoms = (@{$paths{$a}}, reverse @{$paths{$nei}}); | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 152 | 0 | ▶ | print "RING = ", print_path(\@atoms) if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 153 | 0 | pop @atoms; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 154 | 0 | ▶ | if ($used_end_nodes{$atoms[1]} and !$opts{mirror}) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$used_end_nodes{$atoms[1]} and not $opts{"mirror"}
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"}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 155 | 0 | ▶ | print "skipping redundant ring\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition0%0/3
$required_bond and not grep({$_ eq $required_bond;} @bonds)
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)
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 161 | 0 | and not grep {$_ eq $required_bond} @bonds) { | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 162 | 0 | ▶ | print "does not include required bond\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 163 | 0 | next; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 164 | } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 165 | 0 | ▶ | if (contains_ring(\@atoms, \@rings)) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 166 | 0 | ▶ | print "contains another ring\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 180 | } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 181 | } else { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 182 | 0 | ▶ | if (!$max_size || @{$paths{$a}} < ($max_size / 2) + 0.1) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
not $max_size or @{$paths{$a};} < $max_size / 2 + "0.1"
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"
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 183 | 0 | push @q, $nei; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 184 | 0 | ▶ | print " pushing path\n" if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 188 | } else { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 189 | 0 | ▶ | print "path too long; " if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 190 | 0 | ▶ | print print_path($paths{$a}) if $DEBUG; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition33%1/3
not $opts{"sssr"} and @rings > $n_rings
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 270 | 0 | ▶ | $n_rings++ if $rings[$n_rings]->atoms == $rings[$n_rings-1]->atoms; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 285 | 26 | $visited->{$bond} = 1; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 286 | 26 | ▶ | if ($visited->{$nei}) { # closed ring | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||