pele.mindist.permutational_alignment#

pele.mindist.permutational_alignment.find_permutations_munkres()[source]

def find_permutations_munkres(X1, X2, make_cost_matrix=_make_cost_matrix):

For a given set of positions X1 and X2, find the best permutation of the atoms in X2.

The positions must already be reshaped to reflect the dimensionality of the system!

Use an implementation of the Hungarian Algorithm in the Python package index (PyPi) called munkres (another name for the algorithm). The hungarian algorithm time scales as O(n^3), much faster than the O(n!) from looping through all permutations.

http://en.wikipedia.org/wiki/Hungarian_algorithm http://pypi.python.org/pypi/munkres/1.0.5.2

another package, hungarian, implements the same routine in comiled C http://pypi.python.org/pypi/hungarian/ When I first downloaded this package I got segfaults. The problem for me was casing an integer pointer as (npy_intp *). I may add the corrected version to pele at some point

pele.mindist.permutational_alignment.find_permutations_OPTIM()[source]

Source

def find_permutations_OPTIM(X1, X2, box_lengths=None, make_cost_matrix=None):

use OPTIM’s minperm() routine to calculate the optimum permutation

pele.mindist.permutational_alignment.find_best_permutation()[source]

Source

def find_best_permutation(
    X1,
    X2,
    permlist=None,
    user_algorithm=None,
    reshape=True,
    user_cost_matrix=_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

pele.mindist.permutational_alignment.optimize_permutations()[source]

Source

def optimize_permutations(
    X1,
    X2,
    permlist=None,
    user_algorithm=None,
    recalculate_distance=_cartesian_distance,
    box_lengths=None,
    **kwargs
):

return the best alignment of the structures X1 and X2 after optimizing permutations

Parameters:

X1, X2

the structures to align. X1 will be left unchanged.

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)]

user_algoriithmNone or callable

you can optionally pass which algorithm to use to optimize the permutations the structures

gen_cost_matrixNone or callable

user function to generate the cost matrix

recalculate_distancecallable

function to compute the distance of the optimized coords. If None is passed then the distance is not recalculated and the returned distance is unreliable.

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
X1, X2new:: the optimized coordinates