graphcon Module Reference

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...

Data Types
type	graph_type
type	vertex

Functions/Subroutines
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.

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]

Author

Joost VandeVondele

Function/Subroutine Documentation

hash_molecule()

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

History

09.2006 created [Joost VandeVondele]

Note

Although relatively fast in general, might be quadratic with molecule size for some systems (e.g. linear alkanes)

Definition at line 79 of file graphcon.F.

Here is the call graph for this function:

Here is the caller graph for this function:

reorder_graph()

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	molecular description (see type definition)
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

History

09.2006 created [Joost VandeVondele]

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

Definition at line 133 of file graphcon.F.

Here is the call graph for this function:

Here is the caller graph for this function: