1 package Fingerprints::PathLengthFingerprints;
   2 #
   3 # File: PathLengthFingerprints.pm
   4 # Author: Manish Sud <msud@san.rr.com>
   5 #
   6 # Copyright (C) 2025 Manish Sud. All rights reserved.
   7 #
   8 # This file is part of MayaChemTools.
   9 #
  10 # MayaChemTools is free software; you can redistribute it and/or modify it under
  11 # the terms of the GNU Lesser General Public License as published by the Free
  12 # Software Foundation; either version 3 of the License, or (at your option) any
  13 # later version.
  14 #
  15 # MayaChemTools is distributed in the hope that it will be useful, but without
  16 # any warranty; without even the implied warranty of merchantability of fitness
  17 # for a particular purpose.  See the GNU Lesser General Public License for more
  18 # details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public License
  21 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
  22 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
  23 # Boston, MA, 02111-1307, USA.
  24 #
  25 
  26 use strict;
  27 use Carp;
  28 use Exporter;
  29 use TextUtil ();
  30 use MathUtil ();
  31 use Fingerprints::Fingerprints;
  32 use Molecule;
  33 use AtomTypes::AtomicInvariantsAtomTypes;
  34 use AtomTypes::DREIDINGAtomTypes;
  35 use AtomTypes::EStateAtomTypes;
  36 use AtomTypes::FunctionalClassAtomTypes;
  37 use AtomTypes::MMFF94AtomTypes;
  38 use AtomTypes::SLogPAtomTypes;
  39 use AtomTypes::SYBYLAtomTypes;
  40 use AtomTypes::TPSAAtomTypes;
  41 use AtomTypes::UFFAtomTypes;
  42 
  43 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
  44 
  45 @ISA = qw(Fingerprints::Fingerprints Exporter);
  46 @EXPORT = qw();
  47 @EXPORT_OK = qw();
  48 
  49 %EXPORT_TAGS = (all  => [@EXPORT, @EXPORT_OK]);
  50 
  51 # Setup class variables...
  52 my($ClassName);
  53 _InitializeClass();
  54 
  55 # Overload Perl functions...
  56 use overload '""' => 'StringifyPathLengthFingerprints';
  57 
  58 # Class constructor...
  59 sub new {
  60   my($Class, %NamesAndValues) = @_;
  61 
  62   # Initialize object...
  63   my $This = $Class->SUPER::new();
  64   bless $This, ref($Class) || $Class;
  65   $This->_InitializePathLengthFingerprints();
  66 
  67   $This->_InitializePathLengthFingerprintsProperties(%NamesAndValues);
  68 
  69   return $This;
  70 }
  71 
  72 # Initialize object data...
  73 #
  74 sub _InitializePathLengthFingerprints {
  75   my($This) = @_;
  76 
  77   # Type of fingerprint to generate...
  78   #
  79   # PathLengthBits - A bit vector indicating presence/absence of atom paths
  80   # PathLengthCount - A vector containing count of atom paths
  81   #
  82   $This->{Type} = '';
  83 
  84   # Type of vector: FingerprintsBitVector or FingerprintsVector
  85   $This->{VectorType} = '';
  86 
  87   # Set default mininum, maximum, and default size. Although any arbitrary size can
  88   # be specified, bit vector used to store bits work on a vector size which is
  89   # power of 2 and additonal bits are automatically added and cleared.
  90   #
  91   $This->{Size} = 1024;
  92 
  93   $This->{MinSize} = 32;
  94   $This->{MaxSize} = 2**32;
  95 
  96   # Minimum and maximum path lengths to use for fingerprints generation...
  97   $This->{MinLength} = 1;
  98   $This->{MaxLength} = 8;
  99 
 100   # Numner of bits to set for each atom path for FingerprintsBitVector...
 101   $This->{NumOfBitsToSetPerPath} = 1;
 102 
 103   # Atom identifier type to use for path atoms during fingerprints generation...
 104   #
 105   # Currently supported values are: AtomicInvariantsAtomTypes, DREIDINGAtomTypes,
 106   # EStateAtomTypes, FunctionalClassAtomTypes, MMFF94AtomTypes, SLogPAtomTypes,
 107   # SYBYLAtomTypes, TPSAAtomTypes, UFFAtomTypes
 108   #
 109   $This->{AtomIdentifierType} = '';
 110 
 111   # Atom types assigned to atoms...
 112   %{$This->{AssignedAtomTypes}} = ();
 113 
 114   # For molecules containing rings, atom paths starting from each atom can be traversed in four
 115   # different ways:
 116   #
 117   # . Atom paths without any rings and sharing of bonds in traversed paths.
 118   # . Atom paths containing rings and without any sharing of bonds in traversed paths
 119   # . All possible atom paths without any rings and sharing of bonds in traversed paths
 120   # . All possible atom paths containing rings and with sharing of bonds in traversed paths.
 121   #
 122   # Atom path traversal is terminated at the last ring atom. For molecules containing no rings,
 123   # first two and last two types described above are equivalent.
 124   #
 125   # AllowSharedBonds and AllowRings variables allow generation of differen types of paths
 126   # to be used for fingerprints generation.
 127   #
 128   # In addition to atom symbols, bond symbols are also used to generate a string
 129   # for atom paths. These atom paths strings are hased to a 32 bit integer key which
 130   # in turn is used as a seed for a random number generation in range of 1 to fingerprint
 131   # size for setting corresponding bit in bit vector.
 132   #
 133   # UseBondSymbols variable allow generation of atom path strings and consequently fingerprints.
 134   #
 135   # Combination of AllowSharedBonds, AllowRings, and UseBondSymbols allow generation of
 136   # 8 different types of path length fingerprints:
 137   #
 138   # AllowSharedBonds    AllowRings    UseBondSymbols    PathLengthFingerprintsType
 139   #
 140   # No                  No            Yes                AtomPathsNoCyclesWithBondSymbols
 141   # No                  Yes           Yes                AtomPathsWithCyclesWithBondSymbols
 142   #
 143   # Yes                 No            Yes                AllAtomPathsNoCyclesWithBondSymbols
 144   # Yes                 Yes           Yes                AllAtomPathsWithCyclesWithBondSymbols [ DEFAULT ]
 145   #
 146   # No                  No            No                 AtomPathsNoCyclesNoBondSymbols
 147   # No                  Yes           No                 AtomPathsWithCyclesNoBondSymbols
 148   #
 149   # Yes                 No            No                 AllAtomPathsNoCyclesNoBondSymbols
 150   # Yes                 Yes           No                 AllAtomPathsWithCyclesNoWithBondSymbols
 151   #
 152   #
 153 
 154   # By default, atom paths starting from atoms are allowed to share bonds already traversed...
 155   $This->{AllowSharedBonds} = 1;
 156 
 157   # By default rings are included in paths...
 158   $This->{AllowRings} = 1;
 159 
 160   # By default bond symbols are included in atom path strings...
 161   $This->{UseBondSymbols} = 1;
 162 
 163   # By default only structurally unique atom paths are used for generation
 164   # atom path strings...
 165   $This->{UseUniquePaths} = 1;
 166 
 167   # Random number generator to use during generation of fingerprints bit-vector
 168   # string: Perl CORE::rand or MayaChemTools MathUtil::random function.
 169   #
 170   # The random number generator implemented in MayaChemTools is a variant of
 171   # linear congruential generator (LCG) as described by Miller et al. [ Ref 120 ].
 172   # It is also referred to as Lehmer random number generator or Park-Miller
 173   # random number generator.
 174   #
 175   # Unlike Perl's core random number generator function rand, the random number
 176   # generator implemented in MayaChemTools, MathUtil::random,  generates consistent
 177   # random values across different platformsfor a specific random seed and leads
 178   # to generation of portable fingerprints bit-vector strings.
 179   #
 180   $This->{UsePerlCoreRandom} = 1;
 181 
 182   # Bond symbols to use during generation of atom path strings...
 183   %{$This->{BondOrderToSymbol}} = ();
 184   %{$This->{BondOrderToSymbol}} = ('1' => '', '1.5' => ':', '2' => '=', '3' => '#');
 185 
 186   # BondSymbols map to use for bonded atom IDs to use during atom path strings...
 187   %{$This->{BondSymbols}} = ();
 188 
 189   # Path atom IDs to remove duplicate paths...
 190   %{$This->{UniqueLinearAtomPathsIDs}} = ();
 191   %{$This->{UniqueCyclicAtomPathsIDs}} = ();
 192 
 193   # Reference to all the atom paths upto specified path length...
 194   $This->{AtomPathsRef} = '';
 195 
 196   # Atom paths strings created using specified atom types and bond symbols...
 197   %{$This->{AtomPathsStrings}} = ();
 198 }
 199 
 200 # Initialize class ...
 201 sub _InitializeClass {
 202   #Class name...
 203   $ClassName = __PACKAGE__;
 204 }
 205 
 206 # Initialize object properties....
 207 sub _InitializePathLengthFingerprintsProperties {
 208   my($This, %NamesAndValues) = @_;
 209 
 210   my($Name, $Value, $MethodName);
 211   while (($Name, $Value) = each  %NamesAndValues) {
 212     $MethodName = "Set${Name}";
 213     $This->$MethodName($Value);
 214   }
 215 
 216   # Make sure molecule object was specified...
 217   if (!exists $NamesAndValues{Molecule}) {
 218     croak "Error: ${ClassName}->New: Object can't be instantiated without specifying molecule...";
 219   }
 220 
 221   if (!exists $NamesAndValues{Type}) {
 222     croak "Error: ${ClassName}->New: Object can't be instantiated without specifying Type...";
 223   }
 224 
 225   if (!exists $NamesAndValues{AtomIdentifierType}) {
 226     croak "Error: ${ClassName}->New: Object can't be instantiated without specifying AtomIdentifierType...";
 227   }
 228 
 229   # Make sure it's power of 2...
 230   if (exists $NamesAndValues{Size}) {
 231     if (!TextUtil::IsNumberPowerOfNumber($NamesAndValues{Size}, 2)) {
 232       croak "Error: ${ClassName}->New: Specified size value, $NamesAndValues{Size}, must be power of 2...";
 233     }
 234   }
 235 
 236   if ($This->{Type} =~ /^PathLengthBits$/i) {
 237     $This->_InitializePathLengthBits();
 238   }
 239   elsif ($This->{Type} =~ /^PathLengthCount$/i) {
 240     $This->_InitializePathLengthCount();
 241   }
 242   else {
 243     croak "Error: ${ClassName}->_InitializePathLengthFingerprintsProperties: Unknown PathLength type: $This->{Type}; Supported PathLength type : PathLengthBits or PathLengthCount......";
 244   }
 245 
 246   return $This;
 247 }
 248 
 249 # Initialize PathLength bits...
 250 #
 251 sub _InitializePathLengthBits {
 252   my($This) = @_;
 253 
 254   # Vector type...
 255   $This->{VectorType} = 'FingerprintsBitVector';
 256 
 257   $This->_InitializeFingerprintsBitVector();
 258 
 259   return $This;
 260 }
 261 
 262 # Initialize PathLength key count...
 263 #
 264 sub _InitializePathLengthCount {
 265   my($This) = @_;
 266 
 267   # Vector type and type of values...
 268   $This->{VectorType} = 'FingerprintsVector';
 269   $This->{FingerprintsVectorType} = 'NumericalValues';
 270 
 271   $This->_InitializeFingerprintsVector();
 272 
 273   return $This;
 274 }
 275 
 276 # Set type...
 277 #
 278 sub SetType {
 279   my($This, $Type) = @_;
 280 
 281   if ($This->{Type}) {
 282     croak "Error: ${ClassName}->SetType: Can't change type:  It's already set...";
 283   }
 284 
 285   if ($Type =~ /^PathLengthBits$/i) {
 286     $This->{Type} = 'PathLengthBits';;
 287   }
 288   elsif ($Type =~ /^PathLengthCount$/i) {
 289     $This->{Type} = 'PathLengthCount';;
 290   }
 291   else {
 292     croak "Error: ${ClassName}->SetType: Unknown PathLength keys: $Type; Supported PathLength types: PathLengthBits or PathLengthCount...";
 293   }
 294   return $This;
 295 }
 296 
 297 # Disable vector type change...
 298 #
 299 sub SetVectorType {
 300   my($This, $Type) = @_;
 301 
 302   croak "Error: ${ClassName}->SetVectorType: Can't change vector type...";
 303 
 304   return $This;
 305 }
 306 
 307 # Disable vector type change...
 308 #
 309 sub SetFingerprintsVectorType {
 310   my($This, $Type) = @_;
 311 
 312   croak "Error: ${ClassName}->SetFingerprintsVectorType: Can't change fingerprints vector type...";
 313 
 314   return $This;
 315 }
 316 
 317 # Set atom identifier type to use for path length atom identifiers...
 318 #
 319 sub SetAtomIdentifierType {
 320   my($This, $IdentifierType) = @_;
 321 
 322   if ($IdentifierType !~ /^(AtomicInvariantsAtomTypes|DREIDINGAtomTypes|EStateAtomTypes|FunctionalClassAtomTypes|MMFF94AtomTypes|SLogPAtomTypes|SYBYLAtomTypes|TPSAAtomTypes|UFFAtomTypes)$/i) {
 323     croak "Error: ${ClassName}->SetAtomIdentifierType: Specified value, $IdentifierType, for AtomIdentifierType is not vaild. Supported types in current release of MayaChemTools: AtomicInvariantsAtomTypes, DREIDINGAtomTypes, EStateAtomTypes, FunctionalClassAtomTypes, MMFF94AtomTypes, SLogPAtomTypes, SYBYLAtomTypes, TPSAAtomTypes, and UFFAtomTypes.";
 324   }
 325 
 326   if ($This->{AtomIdentifierType}) {
 327     croak "Error: ${ClassName}->SetAtomIdentifierType: Can't change atom identifier type:  It's already set...";
 328   }
 329 
 330   $This->{AtomIdentifierType} = $IdentifierType;
 331 
 332   # Initialize atom identifier type information...
 333   $This->_InitializeAtomIdentifierTypeInformation();
 334 
 335   return $This;
 336 }
 337 
 338 # Set minimum path length...
 339 #
 340 sub SetMinLength {
 341   my($This, $Value) = @_;
 342 
 343   if (!TextUtil::IsPositiveInteger($Value)) {
 344     croak "Error: ${ClassName}->SetMinLength: MinLength value, $Value, is not valid:  It must be a positive integer...";
 345   }
 346   $This->{MinLength} = $Value;
 347 
 348   return $This;
 349 }
 350 
 351 # Set maximum path length...
 352 #
 353 sub SetMaxLength {
 354   my($This, $Value) = @_;
 355 
 356   if (!TextUtil::IsPositiveInteger($Value)) {
 357     croak "Error: ${ClassName}->SetMaxLength: MaxLength value, $Value, is not valid:  It must be a positive integer...";
 358   }
 359   $This->{MaxLength} = $Value;
 360 
 361   return $This;
 362 }
 363 
 364 # Set number of bits to set for each path...
 365 #
 366 sub SetNumOfBitsToSetPerPath {
 367   my($This, $Value) = @_;
 368 
 369   if (!TextUtil::IsPositiveInteger($Value)) {
 370     croak "Error: ${ClassName}->SetNumOfBitsToSetPerPath: NumOfBitsToSetPerPath value, $Value, is not valid:  It must be a positive integer...";
 371   }
 372   $This->{NumOfBitsToSetPerPath} = $Value;
 373 
 374   return $This;
 375 }
 376 
 377 # Generate fingerprints description...
 378 #
 379 sub GetDescription {
 380   my($This) = @_;
 381 
 382   # Is description explicity set?
 383   if (exists $This->{Description}) {
 384     return $This->{Description};
 385   }
 386 
 387   # Generate fingerprints description...
 388 
 389   return "$This->{Type}:$This->{AtomIdentifierType}:MinLength$This->{MinLength}:MaxLength$This->{MaxLength}";
 390 }
 391 
 392 # Generate path length fingerprints...
 393 #
 394 sub GenerateFingerprints {
 395   my($This) = @_;
 396 
 397   if ($This->{MinLength} > $This->{MaxLength}) {
 398     croak "Error: ${ClassName}->GenerateFingerprints: No fingerpritns generated: MinLength, $This->{MinLength}, must be <= MaxLength, $This->{MaxLength}...";
 399   }
 400 
 401   # Cache appropriate molecule data...
 402   $This->_SetupMoleculeDataCache();
 403 
 404   # Assign atom types to all atoms...
 405   if (!$This->_AssignAtomTypes()) {
 406     carp "Warning: ${ClassName}->GenerateFingerprints: $This->{AtomIdentifierType} fingerprints generation didn't succeed: Couldn't assign valid $This->{AtomIdentifierType} to all atoms...";
 407     return $This;
 408   }
 409 
 410   # Setup bond symbol map...
 411   if ($This->{UseBondSymbols}) {
 412     $This->_InitializeBondSymbols();
 413   }
 414 
 415   # Generate appropriate atom paths...
 416   $This->_GenerateAtomPathsUpToMaxLength();
 417 
 418   # Initialize atom path strings...
 419   $This->_InitializeAtomPathsStrings();
 420 
 421   # Generate appropriate atom path strings for unique atom paths...
 422   $This->_GenerateAtomPathsStrings();
 423 
 424   # Set final fingerprints...
 425   $This->_SetFinalFingerprints();
 426 
 427   # Clear cached molecule data...
 428   $This->_ClearMoleculeDataCache();
 429 
 430   return $This;
 431 }
 432 
 433 # Assign appropriate atom types to all atoms...
 434 #
 435 sub _AssignAtomTypes {
 436   my($This) = @_;
 437   my($SpecifiedAtomTypes, $Atom, $AtomID, $IgnoreHydrogens);
 438 
 439   %{$This->{AssignedAtomTypes}} = ();
 440   $IgnoreHydrogens = 0;
 441 
 442   $SpecifiedAtomTypes = undef;
 443 
 444   IDENTIFIERTYPE: {
 445     if ($This->{AtomIdentifierType} =~ /^AtomicInvariantsAtomTypes$/i) {
 446       $SpecifiedAtomTypes = new AtomTypes::AtomicInvariantsAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens, 'AtomicInvariantsToUse' => $This->{AtomicInvariantsToUse});
 447       last IDENTIFIERTYPE;
 448     }
 449 
 450     if ($This->{AtomIdentifierType} =~ /^DREIDINGAtomTypes$/i) {
 451       $SpecifiedAtomTypes = new AtomTypes::DREIDINGAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 452       last IDENTIFIERTYPE;
 453     }
 454 
 455     if ($This->{AtomIdentifierType} =~ /^EStateAtomTypes$/i) {
 456       $SpecifiedAtomTypes = new AtomTypes::EStateAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 457       last IDENTIFIERTYPE;
 458     }
 459 
 460     if ($This->{AtomIdentifierType} =~ /^FunctionalClassAtomTypes$/i) {
 461       $SpecifiedAtomTypes = new AtomTypes::FunctionalClassAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens, 'FunctionalClassesToUse' => $This->{FunctionalClassesToUse});
 462       last IDENTIFIERTYPE;
 463     }
 464 
 465     if ($This->{AtomIdentifierType} =~ /^MMFF94AtomTypes$/i) {
 466       $SpecifiedAtomTypes = new AtomTypes::MMFF94AtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 467       last IDENTIFIERTYPE;
 468     }
 469 
 470     if ($This->{AtomIdentifierType} =~ /^SLogPAtomTypes$/i) {
 471       $SpecifiedAtomTypes = new AtomTypes::SLogPAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 472       last IDENTIFIERTYPE;
 473     }
 474     if ($This->{AtomIdentifierType} =~ /^SYBYLAtomTypes$/i) {
 475       $SpecifiedAtomTypes = new AtomTypes::SYBYLAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 476       last IDENTIFIERTYPE;
 477     }
 478 
 479     if ($This->{AtomIdentifierType} =~ /^TPSAAtomTypes$/i) {
 480       $SpecifiedAtomTypes = new AtomTypes::TPSAAtomTypes('Molecule' => $This->{Molecule}, 'IgnorePhosphorus' => 0, 'IgnoreSulfur' => 0);
 481       last IDENTIFIERTYPE;
 482     }
 483 
 484     if ($This->{AtomIdentifierType} =~ /^UFFAtomTypes$/i) {
 485       $SpecifiedAtomTypes = new AtomTypes::UFFAtomTypes('Molecule' => $This->{Molecule}, 'IgnoreHydrogens' => $IgnoreHydrogens);
 486       last IDENTIFIERTYPE;
 487     }
 488 
 489     croak "Error: ${ClassName}->_AssignAtomTypes: Unknown atom indentifier type $This->{AtomIdentifierType}...";
 490   }
 491 
 492   # Assign atom types...
 493   $SpecifiedAtomTypes->AssignAtomTypes();
 494 
 495   # Make sure atom types assignment is successful...
 496   if (!$SpecifiedAtomTypes->IsAtomTypesAssignmentSuccessful()) {
 497     return undef;
 498   }
 499 
 500   # Collect assigned atom types...
 501   ATOM: for $Atom (@{$This->{Atoms}}) {
 502     $AtomID = $Atom->GetID();
 503     $This->{AssignedAtomTypes}{$AtomID} = $SpecifiedAtomTypes->GetAtomType($Atom);
 504   }
 505 
 506   return $This;
 507 }
 508 
 509 # Setup bond symbol map for atoms to speed up generation of path length identifiers
 510 # during fingerprints generation...
 511 #
 512 sub _InitializeBondSymbols {
 513   my($This) = @_;
 514   my($Atom1, $Atom2, $AtomID1, $AtomID2, $Bond, $BondSymbol, $BondOrder);
 515 
 516   %{$This->{BondSymbols}} = ();
 517 
 518   if (!$This->{UseBondSymbols}) {
 519     return $This;
 520   }
 521 
 522   for $Bond ($This->{Molecule}->GetBonds()) {
 523     $BondOrder = $Bond->GetBondOrder();
 524     $BondSymbol = $Bond->IsAromatic() ? ':' : (exists($This->{BondOrderToSymbol}{$BondOrder}) ? $This->{BondOrderToSymbol}{$BondOrder} : $BondOrder);
 525     ($Atom1, $Atom2) = $Bond->GetAtoms();
 526     $AtomID1 = $Atom1->GetID(); $AtomID2 = $Atom2->GetID();
 527     if ($AtomID1 > $AtomID2) {
 528       ($AtomID1, $AtomID2) =  ($AtomID2, $AtomID1);
 529     }
 530 
 531     if (!exists $This->{BondSymbols}{$AtomID1}) {
 532       %{$This->{BondSymbols}{$AtomID1}} = ();
 533     }
 534     $This->{BondSymbols}{$AtomID1}{$AtomID2} = $BondSymbol;
 535   }
 536   return $This;
 537 }
 538 
 539 # Get appropriate atom paths with length up to MaxLength...
 540 #
 541 sub _GenerateAtomPathsUpToMaxLength {
 542   my($This) = @_;
 543   my($PathLength, $AllowRings, $Molecule, $AtomPathsRef);
 544 
 545   $PathLength = $This->{MaxLength};
 546   $AllowRings = $This->{AllowRings};
 547   $Molecule = $This->{Molecule};
 548 
 549   if ($This->{AllowSharedBonds}) {
 550     $AtomPathsRef =  $Molecule->GetAllAtomPathsWithLengthUpto($PathLength, $AllowRings);
 551   }
 552   else {
 553     $AtomPathsRef = $Molecule->GetAtomPathsWithLengthUpto($PathLength, $AllowRings);
 554   }
 555   $This->{AtomPathsRef} = $AtomPathsRef;
 556 
 557   return $This;
 558 }
 559 
 560 # Initialize atom paths strings at various pathlength levels...
 561 #
 562 sub _InitializeAtomPathsStrings {
 563   my($This) = @_;
 564   my($PathLength);
 565 
 566   %{$This->{AtomPathsStrings}} = ();
 567 
 568   for $PathLength ($This->{MinLength} .. $This->{MaxLength}) {
 569     %{$This->{AtomPathsStrings}{$PathLength}} = ();
 570   }
 571 
 572   return $This;
 573 }
 574 
 575 # Generate appropriate atom path strings for unique atom paths...
 576 #
 577 sub _GenerateAtomPathsStrings {
 578   my($This, $PathAtomsRef) = @_;
 579   my($PathLength, $MinPathLength, $UseUniquePaths);
 580 
 581   $MinPathLength = $This->{MinLength};
 582   $UseUniquePaths = $This->{UseUniquePaths};
 583 
 584   PATHATOMS: for $PathAtomsRef (@{$This->{AtomPathsRef}}) {
 585     $PathLength = scalar @{$PathAtomsRef};
 586     if ($PathLength < $MinPathLength) {
 587       next PATHATOMS;
 588     }
 589     if ($UseUniquePaths) {
 590       $This->_GenerateAtomPathStringUsingUniquePath($PathAtomsRef);
 591     }
 592     else {
 593       $This->_GenerateAtomPathString($PathAtomsRef);
 594     }
 595   }
 596   return $This;
 597 }
 598 
 599 # Generate atom path string using unique path...
 600 #
 601 sub _GenerateAtomPathStringUsingUniquePath {
 602   my($This, $PathAtomsRef) = @_;
 603 
 604   if ($This->{AllowRings} && $This->_DoesAtomPathContainsCycle($PathAtomsRef)) {
 605     $This->_GenerateAtomPathStringUsingUniquePathContainingCycle($PathAtomsRef);
 606   }
 607   else {
 608     $This->_GenerateAtomPathStringUsingUniqueLinearPath($PathAtomsRef);
 609   }
 610   return $This;
 611 }
 612 
 613 # Generate atom path string for specified path containing no cycle...
 614 #
 615 sub _GenerateAtomPathStringUsingUniqueLinearPath {
 616   my($This, $PathAtomsRef) = @_;
 617 
 618   # Is it a unique linear atom path?
 619   #
 620   if (!$This->_IsUniqueLinearAtomPath($PathAtomsRef)) {
 621     return $This;
 622   }
 623   $This->_GenerateAtomPathString($PathAtomsRef);
 624 
 625   return $This;
 626 }
 627 
 628 # Is it a structurally unique linear path?
 629 #
 630 # For a path to be structurally unique, all of its atom IDs must be diffferent from any
 631 # earlier path atom IDs. In order to generate atom path atom ID invariant of the atom
 632 # order in the molecule, atom IDs are sorted numerically before generating the path ID.
 633 #
 634 # Notes:
 635 #   . Atom path ID doesn't reflect the order of atoms in the atom path.
 636 #
 637 sub _IsUniqueLinearAtomPath {
 638   my($This, $PathAtomsRef) = @_;
 639   my($AtomPathID, $PathLength, @PathAtomIDs);
 640 
 641   @PathAtomIDs = ();
 642   @PathAtomIDs = map { $_->GetID(); } @{$PathAtomsRef};
 643 
 644   $AtomPathID = join '-', sort { $a <=> $b } @PathAtomIDs;
 645   if (exists $This->{UniqueLinearAtomPathsIDs}{$AtomPathID}) {
 646     return 0;
 647   }
 648 
 649   # It's a unique atom path...
 650   $This->{UniqueLinearAtomPathsIDs}{$AtomPathID} = 1;
 651 
 652   return 1;
 653 }
 654 
 655 # Generate atom path string for specified path containing a cycle...
 656 #
 657 sub _GenerateAtomPathStringUsingUniquePathContainingCycle {
 658   my($This, $PathAtomsRef) = @_;
 659 
 660   # Is it a unique atom path containing a cycle?
 661   #
 662   if (!$This->_IsUniqueAtomPathContainingCycle($PathAtomsRef)) {
 663     return $This;
 664   }
 665 
 666   my($CycleClosingPathAtomIndex);
 667   ($CycleClosingPathAtomIndex) = $This->_GetAtomPathCycleClosingAtomIndex($PathAtomsRef);
 668 
 669   if ($CycleClosingPathAtomIndex == 0) {
 670     $This->_GenerateUniqueAtomPathStringForPathCycle($PathAtomsRef);
 671   }
 672   else {
 673     $This->_GenerateUniqueAtomPathStringForPathContainingCycle($PathAtomsRef, $CycleClosingPathAtomIndex);
 674   }
 675   return $This;
 676 }
 677 
 678 # Generate a unique atom path string for a cyclic path by generating atom path
 679 # strings for all possible paths in the cycle and keeping the lexicographically smallest
 680 # one.
 681 #
 682 # Although all the paths enumerated during atom path string generation are also
 683 # present in the intial paths list, but structural uniqueness check would detect
 684 # 'em earlier and this method ends being invoked only once for the first cyclic path.
 685 #
 686 # For atom paths containg same atom types and bond symbols, atom path strings
 687 # would be same for the paths.
 688 #
 689 sub _GenerateUniqueAtomPathStringForPathCycle {
 690   my($This, $PathAtomsRef) = @_;
 691 
 692   if ($This->_AreAllPathAtomsSymbolsSame($PathAtomsRef) && $This->_AreAllPathBondSymbolsSame($PathAtomsRef)) {
 693     return $This->_GenerateAtomPathString($PathAtomsRef);
 694   }
 695 
 696   # Generate all possible atom path strings and select the lexicographically smallest one...
 697   my($Index, $PathLength, $FinalAtomPathString, $FirstAtomPathString, $LastIndex, $FirstPartIndex, $FirstPartStartIndex, $FirstPartEndIndex, $SecondPartIndex, $SecondPartStartIndex, $SecondPartEndIndex, $AtomPathSymbolsRef, $AtomPathString, $ReverseAtomPathString, @FirstPartPathAtoms, @SecondPartPathAtoms, @PathAtoms);
 698 
 699   $PathLength = scalar @{$PathAtomsRef};
 700   $LastIndex = $PathLength - 1;
 701 
 702   $FinalAtomPathString = '';
 703   $FirstAtomPathString = 1;
 704 
 705   @FirstPartPathAtoms = (); @SecondPartPathAtoms = (); @PathAtoms = ();
 706 
 707   for $Index (0 .. ($LastIndex - 1)) {
 708     @FirstPartPathAtoms = (); @SecondPartPathAtoms = (); @PathAtoms = ();
 709 
 710     $FirstPartStartIndex = 0; $FirstPartEndIndex = $Index - 1;
 711     $SecondPartStartIndex = $Index; $SecondPartEndIndex = $LastIndex - 1;
 712 
 713     # Get first part atoms...
 714     for $FirstPartIndex ($FirstPartStartIndex .. $FirstPartEndIndex) {
 715       push @FirstPartPathAtoms, $PathAtomsRef->[$FirstPartIndex];
 716     }
 717 
 718     # Get second part atoms...
 719     for $SecondPartIndex ($SecondPartStartIndex .. $SecondPartEndIndex) {
 720       push @SecondPartPathAtoms, $PathAtomsRef->[$SecondPartIndex];
 721     }
 722 
 723     # Get final list of path atoms...
 724     if (@SecondPartPathAtoms) {
 725       push @PathAtoms, @SecondPartPathAtoms;
 726     }
 727     if (@FirstPartPathAtoms) {
 728       push @PathAtoms, @FirstPartPathAtoms;
 729     }
 730 
 731     # Complete the cycle by adding first atom as the last atom...
 732     push @PathAtoms, $PathAtomsRef->[$SecondPartStartIndex];
 733 
 734     # Generate atom path string...
 735     $AtomPathSymbolsRef = $This->_GenerateAtomPathSymbols(\@PathAtoms);
 736 
 737     $AtomPathString = join '', @{$AtomPathSymbolsRef};
 738     $ReverseAtomPathString = join '', reverse @{$AtomPathSymbolsRef};
 739 
 740     if ($ReverseAtomPathString le $AtomPathString) {
 741       $AtomPathString = $ReverseAtomPathString;
 742     }
 743 
 744     # Update final atom path string...
 745 
 746     if ($FirstAtomPathString) {
 747       $FirstAtomPathString = 0;
 748       $FinalAtomPathString = $AtomPathString;
 749     }
 750     else {
 751       if ($AtomPathString le $FinalAtomPathString) {
 752         $FinalAtomPathString = $AtomPathString;
 753       }
 754     }
 755   }
 756 
 757   # Set final atom path string...
 758   #
 759   if (exists $This->{AtomPathsStrings}{$PathLength}{$FinalAtomPathString}) {
 760     $This->{AtomPathsStrings}{$PathLength}{$FinalAtomPathString} += 1;
 761   }
 762   else {
 763     $This->{AtomPathsStrings}{$PathLength}{$FinalAtomPathString} = 1;
 764   }
 765 
 766   return $This;
 767 }
 768 
 769 #
 770 # Generate a unique atom path string for paths containing a cycle closed by
 771 # the specified atom index and the last atom index.
 772 #
 773 # The following methodology is used to generate atom path string which is
 774 # independemt of initial atom ordering:
 775 #   . Generate atom paths string from first atom to the atom before the first cycle
 776 #     closing atom.
 777 #   . Generate atom path string from atoms from first cycle closing atom index to
 778 #     the last path atom in both forward and reverse order. And select the lexicographically
 779 #     smallest atom path string.
 780 #   . Combine atom path string generated in first step with second step to generate
 781 #     final atom path string.
 782 #
 783 sub _GenerateUniqueAtomPathStringForPathContainingCycle {
 784   my($This, $PathAtomsRef, $CycleClosingAtomIndex) = @_;
 785   my($Index, $PathLength, $LastIndex, $LinearPartStartIndex, $LinearPartEndIndex, $CyclicPartStartIndex, $CyclicPartEndIndex, $CyclicPartAtomPathSymbolsRef, $CyclicPartAtomPathString, $ReverseCyclicPartAtomPathString, $AtomPathString, $AtomPathSymbolsRef, @CyclicPartPathAtoms, @PathAtoms);
 786 
 787   $PathLength = scalar @{$PathAtomsRef};
 788   $LastIndex = $PathLength - 1;
 789 
 790   @PathAtoms = ();
 791 
 792   # Get path atoms corresponding to linear  part of the path...
 793   $LinearPartStartIndex = 0; $LinearPartEndIndex = $CycleClosingAtomIndex - 1;
 794 
 795   for $Index ($LinearPartStartIndex .. $LinearPartEndIndex) {
 796     push @PathAtoms, $PathAtomsRef->[$Index];
 797   }
 798 
 799   # Get atoms correcponding to cyclic part of the path...
 800   @CyclicPartPathAtoms = ();
 801   $CyclicPartStartIndex = $CycleClosingAtomIndex; $CyclicPartEndIndex = $LastIndex;
 802 
 803   for $Index ($CyclicPartStartIndex .. $CyclicPartEndIndex) {
 804     push @CyclicPartPathAtoms, $PathAtomsRef->[$Index];
 805   }
 806 
 807   # Setup a lexicographically smaller atom path string for cyclic part...
 808 
 809   $CyclicPartAtomPathSymbolsRef = $This->_GenerateAtomPathSymbols(\@CyclicPartPathAtoms);
 810   $CyclicPartAtomPathString = join '', @{$CyclicPartAtomPathSymbolsRef};
 811   $ReverseCyclicPartAtomPathString = join '', reverse @{$CyclicPartAtomPathSymbolsRef};
 812 
 813   # Setup atom path corresponding to linear part and lexigraphicall smaller cyclic part...
 814 
 815   if ($ReverseCyclicPartAtomPathString le $CyclicPartAtomPathString) {
 816     push @PathAtoms, reverse @CyclicPartPathAtoms;
 817   }
 818   else {
 819     push @PathAtoms, @CyclicPartPathAtoms;
 820   }
 821 
 822   # Setup final atom path string...
 823 
 824   $AtomPathSymbolsRef = $This->_GenerateAtomPathSymbols(\@PathAtoms);
 825   $AtomPathString = join '', @{$AtomPathSymbolsRef};
 826 
 827   if (exists $This->{AtomPathsStrings}{$PathLength}{$AtomPathString}) {
 828     $This->{AtomPathsStrings}{$PathLength}{$AtomPathString} += 1;
 829   }
 830   else {
 831     $This->{AtomPathsStrings}{$PathLength}{$AtomPathString} = 1;
 832   }
 833 
 834   return $This;
 835 }
 836 
 837 # Does atom path contain a cycle?
 838 #
 839 # For an atom path to contain cycle, it must satisfy the following conditions:
 840 #   . Pathlength >= 3
 841 #   . Last atom ID is equal to first atom ID or some other atom ID besides itself
 842 #
 843 sub _DoesAtomPathContainsCycle {
 844   my($This, $PathAtomsRef) = @_;
 845   my($PathLength);
 846 
 847   $PathLength = scalar @{$PathAtomsRef};
 848   if ($PathLength <= 2) {
 849     return 0;
 850   }
 851 
 852   my($AtomIndex, $LastAtomIndex, $Atom, $AtomID, $LastAtom, $LastAtomID);
 853 
 854   $LastAtomIndex = $PathLength - 1;
 855   $LastAtom = $PathAtomsRef->[$LastAtomIndex];
 856   $LastAtomID = $LastAtom->GetID();
 857 
 858   # Look for atomID similar to last atom ID...
 859   for $AtomIndex (0 .. ($LastAtomIndex - 1)) {
 860     $Atom =  $PathAtomsRef->[$AtomIndex];
 861     $AtomID = $Atom->GetID();
 862 
 863     if ($AtomID == $LastAtomID) {
 864       # It's a cycle...
 865       return 1;
 866     }
 867   }
 868   return 0;
 869 }
 870 
 871 # Get atom path cycle closing atom index...
 872 #
 873 sub _GetAtomPathCycleClosingAtomIndex {
 874   my($This, $PathAtomsRef) = @_;
 875   my($AtomIndex, $LastAtomIndex, $Atom, $AtomID, $LastAtom, $LastAtomID, $PathLength);
 876 
 877   $PathLength = scalar @{$PathAtomsRef};
 878 
 879   $LastAtomIndex = $PathLength - 1;
 880   $LastAtom = $PathAtomsRef->[$LastAtomIndex]; $LastAtomID = $LastAtom->GetID();
 881 
 882   # Look for atomID similar to last atom ID...
 883   for $AtomIndex (0 .. ($LastAtomIndex - 1)) {
 884     $Atom =  $PathAtomsRef->[$AtomIndex]; $AtomID = $Atom->GetID();
 885 
 886     if ($AtomID == $LastAtomID) {
 887       # It's a cycle closing atom...
 888       return $AtomIndex;
 889     }
 890   }
 891   return undef;
 892 }
 893 
 894 # Is it a structurally unique path containing a cycle?
 895 #
 896 # For atom paths containing cycles, last atom ID is either equal to first atom ID or
 897 # some other atom ID besides itself.
 898 #
 899 # In order to determine its structurally unqiue independent of initial atom ordering,
 900 # the following methodolgy is used:
 901 #
 902 #   . For paths with same first and atom IDs:
 903 #      . Remove the last atom ID from atom path
 904 #      . Sort atom IDs in the path
 905 #      . Add first atom ID from the sorted list to the end of list to complete the cycle
 906 #      . Generate a atom path ID
 907 #      . Use final path ID to track uniqueness of path containing cycle.
 908 #
 909 #   . For paths with last atom ID equal to some other atom ID besidies itself:
 910 #      . Sort atom IDs in atom path
 911 #      . Generate atom path ID and use it to track unqiueness of atom paths.
 912 #
 913 sub _IsUniqueAtomPathContainingCycle {
 914   my($This, $PathAtomsRef) = @_;
 915   my($PathLength, $AtomPathID, $FirstAtom, $LastAtom, $FirstAtomID, $LastAtomID, @PathAtomIDs, @SortedPathAtomIDs);
 916 
 917   @PathAtomIDs = ();
 918   @PathAtomIDs = map { $_->GetID(); } @{$PathAtomsRef};
 919 
 920   $PathLength = scalar @{$PathAtomsRef};
 921 
 922   $FirstAtom = $PathAtomsRef->[0]; $FirstAtomID = $FirstAtom->GetID();
 923   $LastAtom = $PathAtomsRef->[$PathLength - 1]; $LastAtomID = $LastAtom->GetID();
 924 
 925   if ($FirstAtomID == $LastAtomID) {
 926     pop @PathAtomIDs;
 927 
 928     @SortedPathAtomIDs = ();
 929     @SortedPathAtomIDs = sort { $a <=> $b } @PathAtomIDs;
 930 
 931     push @SortedPathAtomIDs, $SortedPathAtomIDs[0];
 932 
 933     $AtomPathID = join '-', @SortedPathAtomIDs;
 934   }
 935   else {
 936     $AtomPathID = join '-', sort { $a <=> $b } @PathAtomIDs;
 937   }
 938 
 939   if (exists $This->{UniqueCyclicAtomPathsIDs}{$AtomPathID}) {
 940     return 0;
 941   }
 942 
 943   # It's a unique atom path containing a cycle...
 944   $This->{UniqueCyclicAtomPathsIDs}{$AtomPathID} = 1;
 945 
 946   return 1;
 947 }
 948 
 949 # Generate atom path string for specified atom path...
 950 #
 951 sub _GenerateAtomPathString {
 952   my($This, $PathAtomsRef) = @_;
 953   my($PathLength, $AtomPathString, $ReverseAtomPathString, $AtomPathSymbolsRef);
 954 
 955   $PathLength = scalar @{$PathAtomsRef};
 956 
 957   # Generate path atom and bond symbols...
 958   #
 959   $AtomPathSymbolsRef = $This->_GenerateAtomPathSymbols($PathAtomsRef);
 960 
 961   # Check presence of path using path ID created by atom path symbols...
 962   $AtomPathString = join '', @{$AtomPathSymbolsRef};
 963   if (exists $This->{AtomPathsStrings}{$PathLength}{$AtomPathString}) {
 964     $This->{AtomPathsStrings}{$PathLength}{$AtomPathString} += 1;
 965     return $This;
 966   }
 967 
 968   # Check presence of reverse path using path ID created by atom path symbols...
 969   #
 970   $ReverseAtomPathString = join '', reverse @{$AtomPathSymbolsRef};
 971   if (exists $This->{AtomPathsStrings}{$PathLength}{$ReverseAtomPathString}) {
 972     $This->{AtomPathsStrings}{$PathLength}{$ReverseAtomPathString} += 1;
 973     return $This;
 974   }
 975 
 976   # Use lexicographically smaller atom path string as PathID...
 977   #
 978   if ($AtomPathString le $ReverseAtomPathString) {
 979     $This->{AtomPathsStrings}{$PathLength}{$AtomPathString} = 1;
 980   }
 981   else {
 982     $This->{AtomPathsStrings}{$PathLength}{$ReverseAtomPathString} = 1;
 983   }
 984   return $This;
 985 }
 986 
 987 #  Are atom types for all path atoms same?
 988 #
 989 sub _AreAllPathAtomsSymbolsSame {
 990   my($This, $PathAtomsRef) = @_;
 991   my($Index, $Atom, $AtomID, $AtomType, $FirstAtomType);
 992 
 993   $Atom = $PathAtomsRef->[0]; $AtomID = $Atom->GetID();
 994   $FirstAtomType = $This->{AssignedAtomTypes}{$AtomID};
 995 
 996   for $Index (1 .. $#{$PathAtomsRef}) {
 997     $Atom = $PathAtomsRef->[$Index]; $AtomID = $Atom->GetID();
 998     $AtomType = $This->{AssignedAtomTypes}{$AtomID};
 999 
1000     if ($AtomType ne $FirstAtomType) {
1001       return 0;
1002     }
1003   }
1004   return 1;
1005 }
1006 
1007 #  Are bond symbols for all path bonds same?
1008 #
1009 sub _AreAllPathBondSymbolsSame {
1010   my($This, $PathAtomsRef) = @_;
1011   my($Index, $Atom, $BondedAtom, $AtomID, $BondedAtomID, $BondAtomID1, $BondAtomID2, $FirstBondSymbol, $BondSymbol);
1012 
1013   # During no usage of bond symbols, just ignore them and assume they are same...
1014   if (!$This->{UseBondSymbols}) {
1015     return 1;
1016   }
1017 
1018   $Atom = $PathAtomsRef->[0]; $BondedAtom = $PathAtomsRef->[1];
1019   $AtomID = $Atom->GetID(); $BondedAtomID = $BondedAtom->GetID();
1020 
1021   ($BondAtomID1, $BondAtomID2) = ($AtomID < $BondedAtomID) ? ($AtomID, $BondedAtomID) : ($BondedAtomID, $AtomID);
1022   $FirstBondSymbol = $This->{BondSymbols}{$BondAtomID1}{$BondAtomID2};
1023 
1024   for $Index (1 .. ($#{$PathAtomsRef} - 1)) {
1025     $Atom = $PathAtomsRef->[$Index]; $BondedAtom = $PathAtomsRef->[$Index + 1];
1026     $AtomID = $Atom->GetID(); $BondedAtomID = $BondedAtom->GetID();
1027 
1028     ($BondAtomID1, $BondAtomID2) = ($AtomID < $BondedAtomID) ? ($AtomID, $BondedAtomID) : ($BondedAtomID, $AtomID);
1029     $BondSymbol = $This->{BondSymbols}{$BondAtomID1}{$BondAtomID2};
1030 
1031     if ($BondSymbol ne $FirstBondSymbol) {
1032       return 0;
1033     }
1034   }
1035   return 1;
1036 }
1037 
1038 # Generate atom path symbols...
1039 #
1040 sub _GenerateAtomPathSymbols {
1041   my($This, $PathAtomsRef) = @_;
1042   my($Atom, $AtomID, @AtomPathSymbols);
1043 
1044   @AtomPathSymbols = ();
1045 
1046   if (@{$PathAtomsRef} == 1) {
1047     $Atom = $PathAtomsRef->[0]; $AtomID = $Atom->GetID();
1048     push @AtomPathSymbols, $This->{AssignedAtomTypes}{$AtomID};
1049     return \@AtomPathSymbols;
1050   }
1051 
1052   # Ignore bond information...
1053   if (!$This->{UseBondSymbols}) {
1054     for $Atom (@{$PathAtomsRef}) {
1055       $AtomID = $Atom->GetID();
1056       push @AtomPathSymbols, $This->{AssignedAtomTypes}{$AtomID};
1057     }
1058     return \@AtomPathSymbols;
1059   }
1060 
1061   # Use atoms and bonds to generate atom path string...
1062   my($Index, $BondedAtom, $BondedAtomID, $BondAtomID1, $BondAtomID2);
1063 
1064   # Process atom type of first atom in path...
1065   $Atom = $PathAtomsRef->[0]; $AtomID = $Atom->GetID();
1066   push @AtomPathSymbols, $This->{AssignedAtomTypes}{$AtomID};
1067 
1068   for $Index (0 .. ($#{$PathAtomsRef} - 1)) {
1069     $Atom = $PathAtomsRef->[$Index]; $BondedAtom = $PathAtomsRef->[$Index + 1];
1070     $AtomID = $Atom->GetID(); $BondedAtomID = $BondedAtom->GetID();
1071 
1072     ($BondAtomID1, $BondAtomID2) = ($AtomID < $BondedAtomID) ? ($AtomID, $BondedAtomID) : ($BondedAtomID, $AtomID);
1073     push @AtomPathSymbols, $This->{BondSymbols}{$BondAtomID1}{$BondAtomID2};
1074 
1075     # Process atom type of next atom in path...
1076     push @AtomPathSymbols, $This->{AssignedAtomTypes}{$BondedAtomID};
1077   }
1078   return \@AtomPathSymbols;
1079 }
1080 
1081 # Set final fingerprits...
1082 #
1083 sub _SetFinalFingerprints {
1084   my($This) = @_;
1085 
1086   # Mark successful generation of fingerprints...
1087   $This->{FingerprintsGenerated} = 1;
1088 
1089   if ($This->{Type} =~ /^PathLengthBits$/i) {
1090     $This->_SetFinalFingerprintsBitVector();
1091   }
1092   elsif ($This->{Type} =~ /^PathLengthCount$/i) {
1093     $This->_SetFinalFingerprintsVector();
1094   }
1095 
1096   return $This;
1097 }
1098 
1099 # Set final fingerprits bit vector...
1100 #
1101 sub _SetFinalFingerprintsBitVector {
1102   my($This) = @_;
1103   my($PathLength, $Size, $AtomPathString, $AtomPathHashCode, $AtomPathBitPos, $FingerprintsBitVector, $SkipBitPosCheck, $NumOfBitsToSetPerPath, $SetBitNum);
1104 
1105   $FingerprintsBitVector = $This->{FingerprintsBitVector};
1106 
1107   $Size = $This->{Size};
1108 
1109   $SkipBitPosCheck = 1;
1110   $NumOfBitsToSetPerPath = $This->{NumOfBitsToSetPerPath};
1111 
1112   for $PathLength (keys %{$This->{AtomPathsStrings}}) {
1113     for $AtomPathString (keys %{$This->{AtomPathsStrings}{$PathLength}}) {
1114       $AtomPathHashCode = TextUtil::HashCode($AtomPathString);
1115 
1116       # Set random number seed...
1117       if ($This->{UsePerlCoreRandom}) {
1118         CORE::srand($AtomPathHashCode);
1119       }
1120       else {
1121         MathUtil::srandom($AtomPathHashCode);
1122       }
1123 
1124       for $SetBitNum (1 .. $NumOfBitsToSetPerPath) {
1125         $AtomPathBitPos = $This->{UsePerlCoreRandom} ? int(CORE::rand($Size)) : int(MathUtil::random($Size));
1126         $FingerprintsBitVector->SetBit($AtomPathBitPos, $SkipBitPosCheck);
1127       }
1128     }
1129   }
1130   return $This;
1131 }
1132 
1133 # Set final fingerprits vector...
1134 #
1135 sub _SetFinalFingerprintsVector {
1136   my($This) = @_;
1137   my($PathLength, $AtomPathString, $FingerprintsVector, $AtomPathCount, @Values, @ValueIDs);
1138 
1139   @Values = ();
1140   @ValueIDs = ();
1141 
1142   for $PathLength (sort { $a <=> $b } keys %{$This->{AtomPathsStrings}}) {
1143     for $AtomPathString (sort keys %{$This->{AtomPathsStrings}{$PathLength}}) {
1144       $AtomPathCount = $This->{AtomPathsStrings}{$PathLength}{$AtomPathString};
1145 
1146       push @Values, $AtomPathCount;
1147       push @ValueIDs, $AtomPathString;
1148     }
1149   }
1150 
1151   # Add PathLengthIDs and values to fingerprint vector...
1152   $This->{FingerprintsVector}->AddValueIDs(\@ValueIDs);
1153   $This->{FingerprintsVector}->AddValues(\@Values);
1154 
1155   return $This;
1156 }
1157 
1158 # Cache  appropriate molecule data...
1159 #
1160 sub _SetupMoleculeDataCache {
1161   my($This) = @_;
1162 
1163   # Get all atoms...
1164   @{$This->{Atoms}} = $This->GetMolecule()->GetAtoms();
1165 
1166   return $This;
1167 }
1168 
1169 # Clear cached molecule data...
1170 #
1171 sub _ClearMoleculeDataCache {
1172   my($This) = @_;
1173 
1174   # Clear atoms...
1175   @{$This->{Atoms}} = ();
1176 
1177   # Clear path atoms..
1178   $This->{AtomPathsRef} = '';
1179 
1180   return $This;
1181 }
1182 
1183 # Set atomic invariants to use atom identifiers...
1184 #
1185 sub SetAtomicInvariantsToUse {
1186   my($This, @Values) = @_;
1187   my($FirstValue, $TypeOfFirstValue, $AtomicInvariant, $SpecifiedAtomicInvariant, $AtomicInvariantValue, @SpecifiedAtomicInvariants, @AtomicInvariantsToUse);
1188 
1189   if (!@Values) {
1190     carp "Warning: ${ClassName}->SetAtomicInvariantsToUse: No values specified...";
1191     return;
1192   }
1193 
1194   $FirstValue = $Values[0];
1195   $TypeOfFirstValue = ref $FirstValue;
1196 
1197   @SpecifiedAtomicInvariants = ();
1198   @AtomicInvariantsToUse = ();
1199 
1200   if ($TypeOfFirstValue =~ /^ARRAY/) {
1201     push @SpecifiedAtomicInvariants, @{$FirstValue};
1202   }
1203   else {
1204     push @SpecifiedAtomicInvariants, @Values;
1205   }
1206 
1207   # Make sure specified AtomicInvariants are valid...
1208   for $SpecifiedAtomicInvariant (@SpecifiedAtomicInvariants) {
1209     if (!AtomTypes::AtomicInvariantsAtomTypes::IsAtomicInvariantAvailable($SpecifiedAtomicInvariant)) {
1210       croak "Error: ${ClassName}->SetAtomicInvariantsToUse: Specified atomic invariant, $SpecifiedAtomicInvariant, is not supported...\n ";
1211     }
1212     $AtomicInvariant = $SpecifiedAtomicInvariant;
1213     push @AtomicInvariantsToUse, $AtomicInvariant;
1214   }
1215 
1216   # Set atomic invariants to use...
1217   @{$This->{AtomicInvariantsToUse}} = ();
1218   push @{$This->{AtomicInvariantsToUse}}, @AtomicInvariantsToUse;
1219 
1220   return $This;
1221 }
1222 
1223 # Set functional classes to use for atom identifiers...
1224 #
1225 sub SetFunctionalClassesToUse {
1226   my($This, @Values) = @_;
1227   my($FirstValue, $TypeOfFirstValue, $FunctionalClass, $SpecifiedFunctionalClass, @SpecifiedFunctionalClasses, @FunctionalClassesToUse);
1228 
1229   if (!@Values) {
1230     carp "Warning: ${ClassName}->SetFunctionalClassesToUse: No values specified...";
1231     return;
1232   }
1233 
1234   if ($This->{AtomIdentifierType} !~ /^FunctionalClassAtomTypes$/i) {
1235     carp "Warning: ${ClassName}->SetFunctionalClassesToUse: FunctionalClassesToUse can't be set for InitialAtomIdentifierType of $This->{AtomIdentifierType}...";
1236     return;
1237   }
1238 
1239   $FirstValue = $Values[0];
1240   $TypeOfFirstValue = ref $FirstValue;
1241 
1242   @SpecifiedFunctionalClasses = ();
1243   @FunctionalClassesToUse = ();
1244 
1245   if ($TypeOfFirstValue =~ /^ARRAY/) {
1246     push @SpecifiedFunctionalClasses, @{$FirstValue};
1247   }
1248   else {
1249     push @SpecifiedFunctionalClasses, @Values;
1250   }
1251 
1252   # Make sure specified FunctionalClasses are valid...
1253   for $SpecifiedFunctionalClass (@SpecifiedFunctionalClasses) {
1254     if (!AtomTypes::FunctionalClassAtomTypes::IsFunctionalClassAvailable($SpecifiedFunctionalClass)) {
1255       croak "Error: ${ClassName}->SetFunctionalClassesToUse: Specified functional class, $SpecifiedFunctionalClass, is not supported...\n ";
1256     }
1257     push @FunctionalClassesToUse, $SpecifiedFunctionalClass;
1258   }
1259 
1260   # Set functional classes to use...
1261   @{$This->{FunctionalClassesToUse}} = ();
1262   push @{$This->{FunctionalClassesToUse}}, @FunctionalClassesToUse;
1263 
1264   return $This;
1265 }
1266 
1267 # Initialize atom indentifier type information...
1268 #
1269 # Current supported values:
1270 #
1271 # AtomicInvariantsAtomTypes, DREIDINGAtomTypes, EStateAtomTypes, FunctionalClassAtomTypes,
1272 # MMFF94AtomTypes, SLogPAtomTypes, SYBYLAtomTypes, TPSAAtomTypes, UFFAtomTypes
1273 #
1274 sub _InitializeAtomIdentifierTypeInformation {
1275   my($This) = @_;
1276 
1277   if ($This->{AtomIdentifierType} =~ /^AtomicInvariantsAtomTypes$/i) {
1278     $This->_InitializeAtomicInvariantsAtomTypesInformation();
1279   }
1280   elsif ($This->{AtomIdentifierType} =~ /^FunctionalClassAtomTypes$/i) {
1281     $This->_InitializeFunctionalClassAtomTypesInformation();
1282   }
1283   elsif ($This->{AtomIdentifierType} =~ /^(DREIDINGAtomTypes|EStateAtomTypes|MMFF94AtomTypes|SLogPAtomTypes|SYBYLAtomTypes|TPSAAtomTypes|UFFAtomTypes)$/i) {
1284     # Nothing to do for now...
1285   }
1286   else {
1287     croak "Error: ${ClassName}->_InitializeAtomIdentifierTypeInformation: Unknown atom indentifier type $This->{AtomIdentifierType}...";
1288   }
1289 
1290   return $This;
1291 }
1292 
1293 # Initialize atomic invariants atom types to use for generating atom identifiers...
1294 #
1295 # Let:
1296 #   AS = Atom symbol corresponding to element symbol
1297 #
1298 #   X<n>   = Number of non-hydrogen atom neighbors or heavy atoms attached to atom
1299 #   BO<n> = Sum of bond orders to non-hydrogen atom neighbors or heavy atoms attached to atom
1300 #   LBO<n> = Largest bond order of non-hydrogen atom neighbors or heavy atoms attached to atom
1301 #   SB<n> = Number of single bonds to non-hydrogen atom neighbors or heavy atoms attached to atom
1302 #   DB<n> = Number of double bonds to non-hydrogen atom neighbors or heavy atoms attached to atom
1303 #   TB<n> = Number of triple bonds to non-hydrogen atom neighbors or heavy atoms attached to atom
1304 #   H<n>   = Number of implicit and explicit hydrogens for atom
1305 #   Ar     = Aromatic annotation indicating whether atom is aromatic
1306 #   RA     = Ring atom annotation indicating whether atom is a ring
1307 #   FC<+n/-n> = Formal charge assigned to atom
1308 #   MN<n> = Mass number indicating isotope other than most abundant isotope
1309 #   SM<n> = Spin multiplicity of atom. Possible values: 1 (singlet), 2 (doublet) or 3 (triplet)
1310 #
1311 # Then:
1312 #
1313 #   Atom type generated by AtomTypes::AtomicInvariantsAtomTypes class corresponds to:
1314 #
1315 #     AS.X<n>.BO<n>.LBO<n>.<SB><n>.<DB><n>.<TB><n>.H<n>.Ar.RA.FC<+n/-n>.MN<n>.SM<n>
1316 #
1317 # Except for AS which is a required atomic invariant in atom types, all other atomic invariants are
1318 # optional. Default atomic invariants used for AtomID are: AS, X<n>, BO<n>, H<n>, FC<+n/-n>.
1319 # AtomID specification doesn't include atomic invariants with zero or undefined values.
1320 #
1321 sub _InitializeAtomicInvariantsAtomTypesInformation {
1322   my($This) = @_;
1323 
1324   # Default atomic invariants to use for generating atom neighborhood atom IDs: AS, X, BO, H, FC
1325   #
1326   @{$This->{AtomicInvariantsToUse}} = ();
1327   @{$This->{AtomicInvariantsToUse}} = ('AS', 'X', 'BO', 'H', 'FC');
1328 
1329   return $This;
1330 }
1331 
1332 # Initialize functional class atom types, generated by AtomTypes::FunctionalClassAtomTypes
1333 # class, to use for generating atom identifiers...
1334 #
1335 # Let:
1336 #   HBD: HydrogenBondDonor
1337 #   HBA: HydrogenBondAcceptor
1338 #   PI :  PositivelyIonizable
1339 #   NI : NegativelyIonizable
1340 #   Ar : Aromatic
1341 #   Hal : Halogen
1342 #   H : Hydrophobic
1343 #   RA : RingAtom
1344 #   CA : ChainAtom
1345 #
1346 # Then:
1347 #
1348 #   Functiononal class atom type specification for an atom corresponds to:
1349 #
1350 #     Ar.CA.H.HBA.HBD.Hal.NI.PI.RA
1351 #
1352 #   Default functional classes used are: HBD, HBA, PI, NI, Ar, Hal
1353 #
1354 #   FunctionalAtomTypes are assigned using the following definitions [ Ref 60-61, Ref 65-66 ]:
1355 #
1356 #     HydrogenBondDonor: NH, NH2, OH
1357 #     HydrogenBondAcceptor: N[!H], O
1358 #     PositivelyIonizable: +, NH2
1359 #     NegativelyIonizable: -, C(=O)OH, S(=O)OH, P(=O)OH
1360 #
1361 sub _InitializeFunctionalClassAtomTypesInformation {
1362   my($This) = @_;
1363 
1364   # Default functional class atom typess to use for generating atom identifiers
1365   # are: HBD, HBA, PI, NI, Ar, Hal
1366   #
1367   @{$This->{FunctionalClassesToUse}} = ();
1368   @{$This->{FunctionalClassesToUse}} = ('HBD', 'HBA', 'PI', 'NI', 'Ar', 'Hal');
1369 
1370   return $This;
1371 }
1372 
1373 # Return a string containg data for PathLengthFingerprints object...
1374 #
1375 sub StringifyPathLengthFingerprints {
1376   my($This) = @_;
1377   my($PathLengthsFingerprintsString);
1378 
1379   # Type of fingerprint...
1380   $PathLengthsFingerprintsString = "Fingerprint type: $This->{Type}; AtomIdentifierType: $This->{AtomIdentifierType}";
1381 
1382   # Path length...
1383   $PathLengthsFingerprintsString .= "; MinPathLength: $This->{MinLength}; MaxPathLength: $This->{MaxLength}";
1384 
1385   # Fingerprint generation control...
1386   my($AllowSharedBonds, $AllowRings, $UseBondSymbols, $UseUniquePaths);
1387 
1388   $AllowSharedBonds = $This->{AllowSharedBonds} ? "Yes" : "No";
1389   $AllowRings = $This->{AllowRings} ? "Yes" : "No";
1390   $UseBondSymbols = $This->{UseBondSymbols} ? "Yes" : "No";
1391   $UseUniquePaths = $This->{UseBondSymbols} ? "Yes" : "No";
1392 
1393   $PathLengthsFingerprintsString .= "; UseUniquePaths: $UseUniquePaths; AllowSharedBonds: $AllowSharedBonds; AllowRings: $AllowRings; UseBondSymbols: $UseBondSymbols";
1394 
1395   if ($This->{AtomIdentifierType} =~ /^AtomicInvariantsAtomTypes$/i) {
1396     my($AtomicInvariant, @AtomicInvariants, @AtomicInvariantsOrder, %AvailableAtomicInvariants);
1397 
1398     @AtomicInvariantsOrder = AtomTypes::AtomicInvariantsAtomTypes::GetAtomicInvariantsOrder();
1399     %AvailableAtomicInvariants = AtomTypes::AtomicInvariantsAtomTypes::GetAvailableAtomicInvariants();
1400 
1401     for $AtomicInvariant (@AtomicInvariantsOrder) {
1402       push @AtomicInvariants, "$AtomicInvariant: $AvailableAtomicInvariants{$AtomicInvariant}";
1403     }
1404 
1405     $PathLengthsFingerprintsString .= "; AtomicInvariantsToUse: <" . TextUtil::JoinWords(\@{$This->{AtomicInvariantsToUse}}, ", ", 0) . ">";
1406     $PathLengthsFingerprintsString .= "; AtomicInvariantsOrder: <" . TextUtil::JoinWords(\@AtomicInvariantsOrder, ", ", 0) . ">";
1407     $PathLengthsFingerprintsString .= "; AvailableAtomicInvariants: <" . TextUtil::JoinWords(\@AtomicInvariants, ", ", 0) . ">";
1408   }
1409   elsif ($This->{AtomIdentifierType} =~ /^FunctionalClassAtomTypes$/i) {
1410     my($FunctionalClass, @FunctionalClasses, @FunctionalClassesOrder, %AvailableFunctionalClasses);
1411 
1412     @FunctionalClassesOrder = AtomTypes::FunctionalClassAtomTypes::GetFunctionalClassesOrder();
1413     %AvailableFunctionalClasses = AtomTypes::FunctionalClassAtomTypes::GetAvailableFunctionalClasses();
1414 
1415     for $FunctionalClass (@FunctionalClassesOrder) {
1416       push @FunctionalClasses, "$FunctionalClass: $AvailableFunctionalClasses{$FunctionalClass}";
1417     }
1418 
1419     $PathLengthsFingerprintsString .= "; FunctionalClassesToUse: <" . TextUtil::JoinWords(\@{$This->{FunctionalClassesToUse}}, ", ", 0) . ">";
1420     $PathLengthsFingerprintsString .= "; FunctionalClassesOrder: <" . TextUtil::JoinWords(\@FunctionalClassesOrder, ", ", 0) . ">";
1421     $PathLengthsFingerprintsString .= "; AvailableFunctionalClasses: <" . TextUtil::JoinWords(\@FunctionalClasses, ", ", 0) . ">";
1422   }
1423 
1424   if ($This->{Type} =~ /^PathLengthBits$/i) {
1425     # Size...
1426     $PathLengthsFingerprintsString .= "; Size: $This->{Size}; MinSize: $This->{MinSize}; MaxSize: $This->{MaxSize}";
1427 
1428     # NumOfBitsToSetPerPath...
1429     $PathLengthsFingerprintsString .= "; NumOfBitsToSetPerPath: $This->{NumOfBitsToSetPerPath}";
1430 
1431     # Fingerprint bit density and num of bits set...
1432     my($NumOfSetBits, $BitDensity);
1433     $NumOfSetBits = $This->{FingerprintsBitVector}->GetNumOfSetBits();
1434     $BitDensity = $This->{FingerprintsBitVector}->GetFingerprintsBitDensity();
1435     $PathLengthsFingerprintsString .= "; NumOfOnBits: $NumOfSetBits; BitDensity: $BitDensity";
1436 
1437     $PathLengthsFingerprintsString .= "; FingerprintsBitVector: < $This->{FingerprintsBitVector} >";
1438   }
1439   elsif ($This->{Type} =~ /^PathLengthCount$/i) {
1440     $PathLengthsFingerprintsString .= "; FingerprintsVector: < $This->{FingerprintsVector} >";
1441   }
1442 
1443   return $PathLengthsFingerprintsString;
1444 }
1445