uses a combination of graphs and hashing to determine if two molecules are topologically equivalent, and if so, finds the one by one mapping More...
Classes | |
| struct | graph_type |
| struct | vertex |
| struct | class |
| struct | superclass |
Functions | |
| subroutine, public | hash_molecule (reference, kind_ref, hash) |
| hashes a molecule to a number. Molecules that are the (topologically) the same have the same hash. However, there is a small chance that molecules with the same hash are different | |
| subroutine, public | reorder_graph (reference, unordered, order, matches) |
| If two molecules are topologically the same, finds the ordering that maps the unordered one on the ordered one. | |
| recursive subroutine | spread_superclass (I, isuperclass, superclass_of_atom, class_of_atom, classes, reference) |
| spreads the superclass over all atoms of this class and all their bonded atoms provided that the latter belong to a class which contains more than one element | |
| LOGICAL | matrix_superclass_equal (reference, unordered, order, super, classes) |
| determines of the vertices of this superclass have the same edges | |
| LOGICAL | matrix_equal (reference, unordered, order) |
| determines of the vertices of the full set is equal, i.e. we have the same connectivity graph | |
| INTEGER | hash_kind (me, bonds) |
| creates a hash for an atom based on its own kind and on the kinds of its bonded neighbors | |
| INTEGER | joaat_hash_i (key) |
| generates the hash of an array of integers and the index in the table | |
| subroutine | all_permutations (x, n, q, first) |
Detailed Description
uses a combination of graphs and hashing to determine if two molecules are topologically equivalent, and if so, finds the one by one mapping
- Note:
- the graph isomorphism being solved is a computationally hard one and can not be solved in polynomial time in the general case http://mathworld.wolfram.com/IsomorphicGraphs.html the problem arises if many atoms are topologically equivalent the current algorithm is able to solve the problem for benzene (C6H6) but not for a fullerene (C60). Large systems are not really a problem (JAC). as almost all atoms are topologically unique.
- History
- 09.2006 [Joost VandeVondele]
Function Documentation
| subroutine graphcon::all_permutations | ( | INTEGER,dimension(n) | x, |
| INTEGER | n, | ||
| INTEGER,dimension(n) | q, | ||
| LOGICAL | first | ||
| ) | [private] |
Definition at line 497 of file graphcon.f90.
Referenced by reorder_graph().
Here is the caller graph for this function:
| INTEGER graphcon::hash_kind | ( | INTEGER,intent(in) | me, |
| INTEGER,dimension(:),intent(in) | bonds | ||
| ) | [private] |
creates a hash for an atom based on its own kind and on the kinds of its bonded neighbors
- Note:
- bonds are sorted so that the order of neighbors appearing in the bonded list is not important
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 423 of file graphcon.f90.
References joaat_hash_i().
Referenced by hash_molecule().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine,public graphcon::hash_molecule | ( | TYPE(vertex),dimension(:),intent(in) | reference, |
| INTEGER,dimension(:),intent(out) | kind_ref, | ||
| INTEGER,intent(out) | hash | ||
| ) |
hashes a molecule to a number. Molecules that are the (topologically) the same have the same hash. However, there is a small chance that molecules with the same hash are different
- Parameters:
-
reference IN : molecule with atomic kinds and bonds kind_ref OUT : an atomic hash which is the same for topologically equivalent atoms hash OUT : a hash which is the same for topologically equivalent molecules
- Note:
- Although relatively fast in general, might be quadratic with molecule size for some systems (e.g. linear alkanes)
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 77 of file graphcon.f90.
References hash_kind(), and joaat_hash_i().
Referenced by reorder_graph().
Here is the call graph for this function:
Here is the caller graph for this function:
generates the hash of an array of integers and the index in the table
- Parameters:
-
key an integer array of any length
- Note:
- http://en.wikipedia.org/wiki/Hash_table http://www.burtleburtle.net/bob/hash/doobs.html However, since fortran doesn't have an unsigned 4 byte int we compute it using an integer with the appropriate range we return already the index in the table as a final result
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 454 of file graphcon.f90.
Referenced by hash_kind(), and hash_molecule().
Here is the caller graph for this function:
| LOGICAL graphcon::matrix_equal | ( | TYPE(vertex),dimension(:),intent(in) | reference, |
| TYPE(vertex),dimension(:),intent(in) | unordered, | ||
| INTEGER,dimension(:),intent(in) | order | ||
| ) | [private] |
determines of the vertices of the full set is equal, i.e. we have the same connectivity graph
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 391 of file graphcon.f90.
Referenced by reorder_graph().
Here is the caller graph for this function:
| LOGICAL graphcon::matrix_superclass_equal | ( | TYPE(vertex),dimension(:),intent(in) | reference, |
| TYPE(vertex),dimension(:),intent(in) | unordered, | ||
| INTEGER,dimension(:),intent(in) | order, | ||
| TYPE(superclass),intent(in) | super, | ||
| TYPE(class),dimension(:),intent(in) | classes | ||
| ) | [private] |
determines of the vertices of this superclass have the same edges
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 355 of file graphcon.f90.
Referenced by reorder_graph().
Here is the caller graph for this function:
| subroutine,public graphcon::reorder_graph | ( | TYPE(vertex),dimension(:),intent(in) | reference, |
| TYPE(vertex),dimension(:),intent(in) | unordered, | ||
| INTEGER,dimension(:),intent(out) | order, | ||
| LOGICAL,intent(out) | matches | ||
| ) |
If two molecules are topologically the same, finds the ordering that maps the unordered one on the ordered one.
- Parameters:
-
reference,unordered : molecular description (see type definition) order the mapping reference=order(unordred) if matches=.TRUE. undefined if matches=.FALSE. matches .TRUE. = the ordering was found
- Note:
- See not at the top of the file about why this algorithm might consider molecules with a large number of equivalent atoms as different despite the fact that an ordering could exist for which they are the same
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 130 of file graphcon.f90.
References all_permutations(), hash_molecule(), matrix_equal(), matrix_superclass_equal(), and spread_superclass().
Here is the call graph for this function:
| recursive subroutine graphcon::spread_superclass | ( | INTEGER,intent(in) | i, |
| INTEGER,intent(in) | isuperclass, | ||
| INTEGER,dimension(:),intent(inout) | superclass_of_atom, | ||
| INTEGER,dimension(:),intent(in) | class_of_atom, | ||
| TYPE(class),dimension(:),intent(in) | classes, | ||
| TYPE(vertex),dimension(:),intent(in) | reference | ||
| ) | [private] |
spreads the superclass over all atoms of this class and all their bonded atoms provided that the latter belong to a class which contains more than one element
- History
- 09.2006 created [Joost VandeVondele]
Definition at line 327 of file graphcon.f90.
Referenced by reorder_graph().
Here is the caller graph for this function:
