pele.mindist.find_best_permutation

pele.mindist.find_best_permutation(X1, X2, permlist=None, user_algorithm=None, reshape=True, user_cost_matrix=<function _make_cost_matrix at 0x37f2668>, **kwargs)

find the permutation of the atoms which minimizes the distance |X1-X2|

With all the default parameters, findBestPermutation assumes that X1, X2 are arrays of atoms in 3d space and performs reshaping on the coordinates. However, if you want to pass a 2D system or a custom array with own cost function, you can turn automatic reshaping off.

Parameters :

X1, X2 :

the structures to align

permlist : a list of lists

A list of lists of atoms which are interchangable. e.g. for a 50/50 binary mixture:

permlist = [range(1,natoms/2), range(natoms/2,natoms)]

If permlist is None all atoms are assumed to be permutable.

user_algoriithm : None or callable

you can optionally pass which algorithm to use.

gen_cost_matrix : None or callable

user function to generate the cost matrix

reshape : boolean

shall coordinate reshaping be performed.

box_lengths : float array

array of floats giving the box lengths for periodic boundary conditions. Set to None for no periodic boundary conditions.

Returns :

dist : float

the minimum distance WARNING: THIS IS NOT NECESSARILY CORRECT, IT SHOULD BE RECALCULATED. THIS WILL BE REMOVED IN THE FUTURE.

perm:

a permutation which will best align coords2 with coords1

Notes

For each list of interchangeable atoms in permlist the permutation which minimizes the distance between the two structures is found. This minimimization is done by mapping the problem onto the linear assignment problem which can then be solved using graph theoretic techniques.

http://en.wikipedia.org/wiki/Linear_assignment_problem http://en.wikipedia.org/wiki/Hungarian_algorithm

there are several packages in pypi which solve the linear assignment problem

hungarian : c++ code wrapped in python. scales roughly like natoms**2.5

munkres : completely in python. scales roughly like natoms**3. very slow for natoms > 10

in addition we have wrapped the OPTIM version for use in pele. It uses the sparse version of the Jonker-Volgenant algorithm. Furthermore the cost matrix calculated in a compiled language for an additional speed boost. It scales roughly like natoms**2