blib/lib/Chemistry/Canonicalize.pm

filter: Statementstmt 23.2% 20 / 86 Branchbran 0.0% 0 / 14 Conditioncond 0.0% 0 / 8 MC/DCmcdc 0.0% 0 / 5 Subroutinesub 45.4% 5 / 11 Podpod 50.0% 2 / 4 totaltotal 21.0% 27 / 128 CC 22 SCAR 40.7
CC
22
Cov
19%
canonicalize
132.0
canon
42.0
rank_classes
30.0
CRAP 58.7
« blib/lib/Chemistry/Reaction.pm ↑ Summary blib/lib/Chemistry/File/VRML.pm »
1 package Chemistry::Canonicalize;
2  
3 # $Id: Canonicalize.pm,v 1.1.1.1 2004/06/16 19:40:37 ivan Exp $
4 8 $VERSION = '0.10';
5  
6 8 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 8 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 8 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
10 8 ▶use base 'Exporter';
Subroutine BEGIN: called CC=1 SCAR=0.0
11 8 our @EXPORT_OK = qw(canonicalize);
12 8 our %EXPORT_TAGS = ( all => \@EXPORT_OK );
13  
14  
15 =head1 NAME
16  
17 Chemistry::Canonicalize - Number the atoms in a molecule in a unique way
18  
19 =head1 SYNOPSIS
20  
21 use Chemistry::Canonicalize ':all';
22  
23 # $mol is a Chemistry::Mol object
24 canonicalize($mol);
25 print "The canonical number for atom 1 is: ",
26 $mol->atoms(1)->attr("canon/class");
27 print "The symmetry class for for atom 1 is: ",
28 $mol->atoms(1)->attr("canon/symmetry_class");
29  
30 =head1 DESCRIPTION
31  
32 This module provides functions for "canonicalizing" a molecular structure; that
33 is, to number the atoms in a unique way regardless of the input order.
34  
35 The canonicalization algorithm is based on: Weininger, et. al., J. Chem. Inf.
36 Comp. Sci. 29[2], 97-101 (1989)
37  
38 This module is part of the PerlMol project, L<http://www.perlmol.org/>.
39  
40 =head1 ATOM ATTRIBUTES
41  
42 During the canonicalization process, the following attributes are set on each
43 atom:
44  
45 =over
46  
47 =item canon/class
48  
49 The unique canonical number; it is an integer going from 1 to the number of
50 atoms.
51  
52 =item canon/symmetry_class
53  
54 The symmetry class number. Atoms that have the same symmetry class are
55 considered to be topologicaly equivalent. For example, the two methyl carbons
56 on 2-propanol would have the same symmetry class.
57  
58 =back
59  
60 =head1 FUNCTIONS
61  
62 These functions may be exported, although nothing is exported by default.
63  
64 =over
65  
66 =cut
67  
68 8 my @PRIMES = qw( 1
69 2 3 5 7 11 13 17 19 23 29
70 31 37 41 43 47 53 59 61 67 71
71 73 79 83 89 97 101 103 107 109 113
72 127 131 137 139 149 151 157 163 167 173
73 179 181 191 193 197 199 211 223 227 229
74 233 239 241 251 257 263 269 271 277 281
75 283 293 307 311 313 317 331 337 347 349
76 353 359 367 373 379 383 389 397 401 409
77 419 421 431 433 439 443 449 457 461 463
78 467 479 487 491 499 503 509 521 523 541
79 547 557 563 569 571 577 587 593 599 601
80 607 613 617 619 631 641 643 647 653 659
81 661 673 677 683 691 701 709 719 727 733
82 739 743 751 757 761 769 773 787 797 809
83 811 821 823 827 829 839 853 857 859 863
84 877 881 883 887 907 911 919 929 937 941
85 947 953 967 971 977 983 991 997 1009 1013
86 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069
87 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151
88 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223
89 );
90  
91 =item canonicalize($mol, %opts)
92  
93 Canonicalizes the molecule. It adds the canon/class and canon/symmetry class to
94 every atom, as discussed above. This function may take the following options:
95  
96 =over
97  
98 =item sort
99  
100 If true, sort the atoms in the molecule in ascending canonical number order.
101  
102 =item invariants
103  
104 This should be a subroutine reference that takes an atom and returns a number.
105 These number should be based on the topological invariant properties of the
106 atom, such as symbol, charge, number of bonds, etc.
107  
108 =back
109  
110 =cut
111  
112 0 ▶sub canonicalize {
Subroutine canonicalize: not called CC=11 SCAR=48.8
Pod documented
113 0 my ($mol, %opts) = @_;
114  
115 0 ▶ if ($mol->atoms > @PRIMES - 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($mol->atoms > @PRIMES - 1) 0 0 0
116 0 croak "maximum number of atoms exceeded for canonicalization\n";
117 }
118  
119 0 ▶ my $invariants_sub = $opts{invariants} || \&atom_invariants;
Condition0%0/2
$opts{'invariants'} || \&Chemistry::Canonicalize::atom_invariants
l!l
00
MC/DC0%0/1
$opts{'invariants'} || \&Chemistry::Canonicalize::atom_invariants
$opts{'invariants'}
Truth table0%0/2
A
A= $opts{'invariants'}
Aresult
11
00
120  
121 # set up initial classes
122 0 for my $atom ($mol->atoms) {
123 0 $atom->attr("canon/class", $invariants_sub->($atom));
124 0 $atom->attr("canon/prev_class", 1);
125 }
126 #printf "$_: %s\n", $_->attr("canon/class") for $mol->atoms;
127  
128 # run one canonicalization step
129 0 my $atoms;
130 my $n_classes;
131 0 ($atoms, $n_classes) = rank_classes($mol);
132 0 ($atoms, $n_classes) = canon($mol, $n_classes);
133 0 my $n_atom = $mol->atoms;
134  
135 # atoms with the same class are topologically symmetric
136 0 for my $atom ($mol->atoms) {
137 0 $atom->attr("canon/symmetry_class", $atom->attr("canon/class"));
138 }
139 #printf "$_: %s\n", $_->attr("canon/class") for $mol->atoms;
140  
141 # break symmetry to get a canonical numbering
142 0 ▶ while ($n_classes < $n_atom) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n_classes < $n_atom) 0 0 0
143  
144 # multiply all classes by 2
145 0 for my $atom (@$atoms) {
146 0 my $class = $atom->attr("canon/class");
147 0 $atom->attr("canon/class", $class * 2);
148 }
149  
150 # break first tie
151 0 my $last_class = -1;
152 0 my $last_atom;
153 0 for my $atom (@$atoms) {
154 0 my $class = $atom->attr("canon/class");
155 0 ▶ if ($class == $last_class) { # tie
Branch: 1 branch
BranchTrueFalseTotal
if ($class == $last_class) 0 0 0
156 #print "breaking tie for $last_atom\n";
157 0 $last_atom->attr("canon/class", $class - 1);
158 0 last;
159 }
160 0 $last_class = $class;
161 0 $last_atom = $atom;
162 }
163 #printf "$_: %s\n", $_->attr("canon/class") for $mol->atoms;
164 #print "---\n";
165  
166 # run another canonicalization step
167 0 ($atoms, $n_classes) = canon($mol, $n_classes);
168 #printf "$_: %s\n", $_->attr("canon/class") for $mol->atoms;
169 }
170 0 ▶ if ($opts{'sort'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($opts{"sort"}) 0 0 0
171 $mol->sort_atoms(
172 0 ▶ sub { $_[0]->attr("canon/class") <=> $_[1]->attr("canon/class") }
Subroutine __ANON__: not called CC=1 SCAR=6.9
173 0 );
174 }
175 # clean up temporary classes
176 0 $_->del_attr("canon/new_class") for $mol->atoms;
177 0 $n_classes;
178 }
179  
180 0 ▶sub atom_invariants {
Subroutine atom_invariants: not called CC=2 SCAR=12.2
Pod undocumented
181 8 ▶ no warnings 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
182 0 my ($atom) = @_;
183 0 my $n_bonds = $atom->bonds;
184 0 my $valence = 0;
185 0 $valence += $_->order for $atom->bonds;
186 0 my $Z = $atom->Z;
187 0 my $q = $atom->formal_charge + 5;
188 0 return $n_bonds*10_000 + $valence*1000 + $q*100 + $Z;
189 }
190  
191 # atom class comparison function. Only compare the class if the
192 # previous classes are equal
193 0 ▶sub _cmp {
Subroutine _cmp: not called CC=2 SCAR=17.9
194 0 ▶ $a->attr("canon/prev_class") <=> $b->attr("canon/prev_class")
Branch: 1 branch
BranchTrueFalseTotal
$a->attr("canon/prev_class") <=> $b->attr("canon/prev_class") or $a->attr("canon/class") <=> $b->attr("canon/class") 0 0 0
195 or $a->attr("canon/class") <=> $b->attr("canon/class")
196 }
197  
198 0 ▶sub rank_classes {
Subroutine rank_classes: not called CC=5 SCAR=34.0
Pod undocumented
199 0 my ($mol) = @_;
200 0 my @atoms = sort _cmp $mol->atoms; # consider Schwartzian transform?
201 0 my $n = 0;
202 0 local ($a, $b);
203 0 for $b (@atoms) {
204 0 ▶ $n++ if (!$a || _cmp);
Branch: 1 branch
BranchTrueFalseTotal
if not $a or _cmp() 0 0 0
Condition0%0/3
not $a or _cmp()
l!l&&r!l&&!r
000
MC/DC0%0/2
not $a or _cmp()
not $a _cmp()
Truth table0%0/3
not(A) or B
A= not $aB= _cmp()
ABresult
1X1
011
000
205 0 $a = $b;
206 0 $b->attr("canon/new_class", $n);
207 }
208 #use diagnostics;
209 0 for my $atom (@atoms) {
210 0 $atom->attr("canon/class", $atom->attr("canon/new_class"));
211 }
212 0 (\@atoms, $n);
213 }
214  
215 0 ▶sub canon {
Subroutine canon: not called CC=6 SCAR=37.4
Pod documented
216 0 my ($mol, $n) = @_;
217  
218 0 my $old_classes = 0;
219 0 my $n_atom = $mol->atoms;
220 0 my $atoms;
221 0 ▶ while ($n > $old_classes and $n < $n_atom) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n > $old_classes and $n < $n_atom) 0 0 0
Condition0%0/3
$n > $old_classes and $n < $n_atom
!ll&&!rl&&r
000
MC/DC0%0/2
$n > $old_classes and $n < $n_atom
$n > $old_classes $n < $n_atom
Truth table0%0/3
A and B
A= $n > $old_classesB= $n < $n_atom
ABresult
0X0
100
111
222 0 $old_classes = $n;
223 # save current classes
224 0 for my $atom ($mol->atoms) {
225 0 $atom->attr("canon/prev_class", $atom->attr("canon/class"));
226 }
227  
228 # set new class to product of neighbor's primes
229 0 for my $atom ($mol->atoms) {
230 0 my $class = 1;
231 0 for my $neighbor ($atom->neighbors) {
232 0 $class *= $PRIMES[$neighbor->attr("canon/prev_class")];
233 }
234 0 $atom->attr("canon/class", $class);
235 }
236 0 ($atoms, $n) = rank_classes($mol);
237 }
238 0 ($atoms, $n);
239 }
240  
241 8 1;
242  
243 =back
244  
245 =head1 VERSION
246  
247 0.10
248  
249 =head1 TO DO
250  
251 Add some tests.
252  
253 =head1 CAVEATS
254  
255 Currently there is an atom limit of 200 atoms.
256  
257 These algorithm is known to fail to discriminate between non-equivalent atoms
258 for some complicated cases. These are usually highly bridged structures
259 explicitly designed to break canonicalization algorithms; I don't know of any
260 "real-looking structure" (meaning something that someone would actually
261 synthesize or find in nature) that fails, but don't say I didn't warn you!
262  
263 =head1 SEE ALSO
264  
265 L<Chemistry::Mol>, L<Chemistry::Atom>, L<Chemistry::Obj>,
266 L<http://www.perlmol.org/>.
267  
268 =head1 AUTHOR
269  
270 Ivan Tubert E<lt>itub@cpan.orgE<gt>
271  
272 =head1 COPYRIGHT
273  
274 Copyright (c) 2004 Ivan Tubert. All rights reserved. This program is free
275 software; you can redistribute it and/or modify it under the same terms as
276 Perl itself.
277  
278 =cut
279  
« blib/lib/Chemistry/Reaction.pm ↑ Summary blib/lib/Chemistry/File/VRML.pm »