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>, **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

permlista 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_algoriithmNone or callable

you can optionally pass which algorithm to use.

gen_cost_matrixNone or callable

user function to generate the cost matrix

reshapeboolean

shall coordinate reshaping be performed.

box_lengthsfloat array

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

Returns:

distfloat

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

use of hungarian here is deprecated, replace with scipy.optimize.linear_sum_assignment

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