• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

materialsproject / pymatgen / 4075885785

pending completion
4075885785

push

github

Shyue Ping Ong
Merge branch 'master' of github.com:materialsproject/pymatgen

96 of 96 new or added lines in 27 files covered. (100.0%)

81013 of 102710 relevant lines covered (78.88%)

0.79 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.67
/pymatgen/analysis/ewald.py
1
# Copyright (c) Pymatgen Development Team.
2
# Distributed under the terms of the MIT License.
3

4
"""
1✔
5
This module provides classes for calculating the Ewald sum of a structure.
6
"""
7

8
from __future__ import annotations
1✔
9

10
import bisect
1✔
11
from copy import copy, deepcopy
1✔
12
from datetime import datetime
1✔
13
from math import log, pi, sqrt
1✔
14
from typing import Any
1✔
15
from warnings import warn
1✔
16

17
import numpy as np
1✔
18
from monty.json import MSONable
1✔
19
from scipy import constants
1✔
20
from scipy.special import comb, erfc
1✔
21

22
from pymatgen.core.structure import Structure
1✔
23

24
__author__ = "Shyue Ping Ong, William Davidson Richard"
1✔
25
__copyright__ = "Copyright 2011, The Materials Project"
1✔
26
__credits__ = "Christopher Fischer"
1✔
27
__version__ = "1.0"
1✔
28
__maintainer__ = "Shyue Ping Ong"
1✔
29
__email__ = "shyuep@gmail.com"
1✔
30
__status__ = "Production"
1✔
31
__date__ = "Aug 1 2012"
1✔
32

33

34
class EwaldSummation(MSONable):
1✔
35
    """
36
    Calculates the electrostatic energy of a periodic array of charges using
37
    the Ewald technique.
38

39

40
    Ref:
41
    Ewald summation techniques in perspective: a survey
42
    Abdulnour Y. Toukmaji and John A. Board Jr.
43
    DOI: 10.1016/0010-4655(96)00016-1
44
    URL: http://www.ee.duke.edu/~ayt/ewaldpaper/ewaldpaper.html
45

46
    This matrix can be used to do fast calculations of Ewald sums after species
47
    removal.
48

49
    E = E_recip + E_real + E_point
50

51
    Atomic units used in the code, then converted to eV.
52
    """
53

54
    # Converts unit of q*q/r into eV
55
    CONV_FACT = 1e10 * constants.e / (4 * pi * constants.epsilon_0)
1✔
56

57
    def __init__(
1✔
58
        self,
59
        structure,
60
        real_space_cut=None,
61
        recip_space_cut=None,
62
        eta=None,
63
        acc_factor=12.0,
64
        w=1 / 2**0.5,
65
        compute_forces=False,
66
    ):
67
        """
68
        Initializes and calculates the Ewald sum. Default convergence
69
        parameters have been specified, but you can override them if you wish.
70

71
        Args:
72
            structure (Structure): Input structure that must have proper
73
                Species on all sites, i.e. Element with oxidation state. Use
74
                Structure.add_oxidation_state... for example.
75
            real_space_cut (float): Real space cutoff radius dictating how
76
                many terms are used in the real space sum. Defaults to None,
77
                which means determine automagically using the formula given
78
                in gulp 3.1 documentation.
79
            recip_space_cut (float): Reciprocal space cutoff radius.
80
                Defaults to None, which means determine automagically using
81
                the formula given in gulp 3.1 documentation.
82
            eta (float): The screening parameter. Defaults to None, which means
83
                determine automatically.
84
            acc_factor (float): No. of significant figures each sum is
85
                converged to.
86
            w (float): Weight parameter, w, has been included that represents
87
                the relative computational expense of calculating a term in
88
                real and reciprocal space. Default of 0.7 reproduces result
89
                similar to GULP 4.2. This has little effect on the total
90
                energy, but may influence speed of computation in large
91
                systems. Note that this parameter is used only when the
92
                cutoffs are set to None.
93
            compute_forces (bool): Whether to compute forces. False by
94
                default since it is usually not needed.
95
        """
96
        self._s = structure
1✔
97
        self._charged = abs(structure.charge) > 1e-8
1✔
98
        self._vol = structure.volume
1✔
99
        self._compute_forces = compute_forces
1✔
100

101
        self._acc_factor = acc_factor
1✔
102
        # set screening length
103
        self._eta = eta or (len(structure) * w / (self._vol**2)) ** (1 / 3) * pi
1✔
104
        self._sqrt_eta = sqrt(self._eta)
1✔
105

106
        # acc factor used to automatically determine the optimal real and
107
        # reciprocal space cutoff radii
108
        self._accf = sqrt(log(10**acc_factor))
1✔
109

110
        self._rmax = real_space_cut or self._accf / self._sqrt_eta
1✔
111
        self._gmax = recip_space_cut or 2 * self._sqrt_eta * self._accf
1✔
112

113
        # The next few lines pre-compute certain quantities and store them.
114
        # Ewald summation is rather expensive, and these shortcuts are
115
        # necessary to obtain several factors of improvement in speedup.
116
        self._oxi_states = [compute_average_oxidation_state(site) for site in structure]
1✔
117

118
        self._coords = np.array(self._s.cart_coords)
1✔
119

120
        # Define the private attributes to lazy compute reciprocal and real
121
        # space terms.
122
        self._initialized = False
1✔
123
        self._recip = None
1✔
124
        self._real, self._point = None, None
1✔
125
        self._forces = None
1✔
126

127
        # Compute the correction for a charged cell
128
        self._charged_cell_energy = (
1✔
129
            -EwaldSummation.CONV_FACT / 2 * np.pi / structure.volume / self._eta * structure.charge**2
130
        )
131

132
    def compute_partial_energy(self, removed_indices):
1✔
133
        """
134
        Gives total Ewald energy for certain sites being removed, i.e. zeroed
135
        out.
136
        """
137
        total_energy_matrix = self.total_energy_matrix.copy()
1✔
138
        for i in removed_indices:
1✔
139
            total_energy_matrix[i, :] = 0
1✔
140
            total_energy_matrix[:, i] = 0
1✔
141
        return sum(sum(total_energy_matrix))
1✔
142

143
    def compute_sub_structure(self, sub_structure, tol: float = 1e-3):
1✔
144
        """
145
        Gives total Ewald energy for an sub structure in the same
146
        lattice. The sub_structure must be a subset of the original
147
        structure, with possible different charges.
148

149
        Args:
150
            substructure (Structure): Substructure to compute Ewald sum for.
151
            tol (float): Tolerance for site matching in fractional coordinates.
152

153
        Returns:
154
            Ewald sum of substructure.
155
        """
156
        total_energy_matrix = self.total_energy_matrix.copy()
×
157

158
        def find_match(site):
×
159
            for test_site in sub_structure:
×
160
                frac_diff = abs(np.array(site.frac_coords) - np.array(test_site.frac_coords)) % 1
×
161
                frac_diff = [abs(a) < tol or abs(a) > 1 - tol for a in frac_diff]
×
162
                if all(frac_diff):
×
163
                    return test_site
×
164
            return None
×
165

166
        matches = []
×
167
        for i, site in enumerate(self._s):
×
168
            matching_site = find_match(site)
×
169
            if matching_site:
×
170
                new_charge = compute_average_oxidation_state(matching_site)
×
171
                old_charge = self._oxi_states[i]
×
172
                scaling_factor = new_charge / old_charge
×
173
                matches.append(matching_site)
×
174
            else:
175
                scaling_factor = 0
×
176
            total_energy_matrix[i, :] *= scaling_factor
×
177
            total_energy_matrix[:, i] *= scaling_factor
×
178

179
        if len(matches) != len(sub_structure):
×
180
            output = ["Missing sites."]
×
181
            for site in sub_structure:
×
182
                if site not in matches:
×
183
                    output.append(f"unmatched = {site}")
×
184
            raise ValueError("\n".join(output))
×
185

186
        return sum(sum(total_energy_matrix))
×
187

188
    @property
1✔
189
    def reciprocal_space_energy(self):
1✔
190
        """
191
        The reciprocal space energy.
192
        """
193
        if not self._initialized:
1✔
194
            self._calc_ewald_terms()
×
195
            self._initialized = True
×
196
        return sum(sum(self._recip))
1✔
197

198
    @property
1✔
199
    def reciprocal_space_energy_matrix(self):
1✔
200
        """
201
        The reciprocal space energy matrix. Each matrix element (i, j)
202
        corresponds to the interaction energy between site i and site j in
203
        reciprocal space.
204
        """
205
        if not self._initialized:
1✔
206
            self._calc_ewald_terms()
×
207
            self._initialized = True
×
208
        return self._recip
1✔
209

210
    @property
1✔
211
    def real_space_energy(self):
1✔
212
        """
213
        The real space energy.
214
        """
215
        if not self._initialized:
1✔
216
            self._calc_ewald_terms()
1✔
217
            self._initialized = True
1✔
218
        return sum(sum(self._real))
1✔
219

220
    @property
1✔
221
    def real_space_energy_matrix(self):
1✔
222
        """
223
        The real space energy matrix. Each matrix element (i, j) corresponds to
224
        the interaction energy between site i and site j in real space.
225
        """
226
        if not self._initialized:
1✔
227
            self._calc_ewald_terms()
×
228
            self._initialized = True
×
229
        return self._real
1✔
230

231
    @property
1✔
232
    def point_energy(self):
1✔
233
        """
234
        The point energy.
235
        """
236
        if not self._initialized:
1✔
237
            self._calc_ewald_terms()
×
238
            self._initialized = True
×
239
        return sum(self._point)
1✔
240

241
    @property
1✔
242
    def point_energy_matrix(self):
1✔
243
        """
244
        The point space matrix. A diagonal matrix with the point terms for each
245
        site in the diagonal elements.
246
        """
247
        if not self._initialized:
1✔
248
            self._calc_ewald_terms()
×
249
            self._initialized = True
×
250
        return self._point
1✔
251

252
    @property
1✔
253
    def total_energy(self):
1✔
254
        """
255
        The total energy.
256
        """
257
        if not self._initialized:
1✔
258
            self._calc_ewald_terms()
1✔
259
            self._initialized = True
1✔
260
        return sum(sum(self._recip)) + sum(sum(self._real)) + sum(self._point) + self._charged_cell_energy
1✔
261

262
    @property
1✔
263
    def total_energy_matrix(self):
1✔
264
        """
265
        The total energy matrix. Each matrix element (i, j) corresponds to the
266
        total interaction energy between site i and site j.
267

268
        Note that this does not include the charged-cell energy, which is only important
269
        when the simulation cell is not charge balanced.
270
        """
271
        if not self._initialized:
1✔
272
            self._calc_ewald_terms()
1✔
273
            self._initialized = True
1✔
274

275
        totalenergy = self._recip + self._real
1✔
276
        for i, energy in enumerate(self._point):
1✔
277
            totalenergy[i, i] += energy
1✔
278
        return totalenergy
1✔
279

280
    @property
1✔
281
    def forces(self):
1✔
282
        """
283
        The forces on each site as a Nx3 matrix. Each row corresponds to a
284
        site.
285
        """
286
        if not self._initialized:
1✔
287
            self._calc_ewald_terms()
×
288
            self._initialized = True
×
289

290
        if not self._compute_forces:
1✔
291
            raise AttributeError("Forces are available only if compute_forces is True!")
×
292
        return self._forces
1✔
293

294
    def get_site_energy(self, site_index):
1✔
295
        """Compute the energy for a single site in the structure
296

297
        Args:
298
            site_index (int): Index of site
299
        ReturnS:
300
            (float) - Energy of that site"""
301
        if not self._initialized:
1✔
302
            self._calc_ewald_terms()
×
303
            self._initialized = True
×
304

305
        if self._charged:
1✔
306
            warn("Per atom energies for charged structures not supported in EwaldSummation")
×
307
        return np.sum(self._recip[:, site_index]) + np.sum(self._real[:, site_index]) + self._point[site_index]
1✔
308

309
    def _calc_ewald_terms(self):
1✔
310
        """
311
        Calculates and sets all Ewald terms (point, real and reciprocal)
312
        """
313
        self._recip, recip_forces = self._calc_recip()
1✔
314
        self._real, self._point, real_point_forces = self._calc_real_and_point()
1✔
315
        if self._compute_forces:
1✔
316
            self._forces = recip_forces + real_point_forces
1✔
317

318
    def _calc_recip(self):
1✔
319
        """
320
        Perform the reciprocal space summation. Calculates the quantity
321
        E_recip = 1/(2PiV) sum_{G < Gmax} exp(-(G.G/4/eta))/(G.G) S(G)S(-G)
322
        where
323
        S(G) = sum_{k=1,N} q_k exp(-i G.r_k)
324
        S(G)S(-G) = |S(G)|**2
325

326
        This method is heavily vectorized to utilize numpy's C backend for
327
        speed.
328
        """
329
        numsites = self._s.num_sites
1✔
330
        prefactor = 2 * pi / self._vol
1✔
331
        erecip = np.zeros((numsites, numsites), dtype=np.float_)
1✔
332
        forces = np.zeros((numsites, 3), dtype=np.float_)
1✔
333
        coords = self._coords
1✔
334
        rcp_latt = self._s.lattice.reciprocal_lattice
1✔
335
        recip_nn = rcp_latt.get_points_in_sphere([[0, 0, 0]], [0, 0, 0], self._gmax)
1✔
336

337
        frac_coords = [fcoords for (fcoords, dist, i, img) in recip_nn if dist != 0]
1✔
338

339
        gs = rcp_latt.get_cartesian_coords(frac_coords)
1✔
340
        g2s = np.sum(gs**2, 1)
1✔
341
        expvals = np.exp(-g2s / (4 * self._eta))
1✔
342
        grs = np.sum(gs[:, None] * coords[None, :], 2)
1✔
343

344
        oxistates = np.array(self._oxi_states)
1✔
345

346
        # create array where q_2[i,j] is qi * qj
347
        qiqj = oxistates[None, :] * oxistates[:, None]
1✔
348

349
        # calculate the structure factor
350
        sreals = np.sum(oxistates[None, :] * np.cos(grs), 1)
1✔
351
        simags = np.sum(oxistates[None, :] * np.sin(grs), 1)
1✔
352

353
        for g, g2, gr, expval, sreal, simag in zip(gs, g2s, grs, expvals, sreals, simags):
1✔
354
            # Uses the identity sin(x)+cos(x) = 2**0.5 sin(x + pi/4)
355
            m = (gr[None, :] + pi / 4) - gr[:, None]
1✔
356
            np.sin(m, m)
1✔
357
            m *= expval / g2
1✔
358

359
            erecip += m
1✔
360

361
            if self._compute_forces:
1✔
362
                pref = 2 * expval / g2 * oxistates
1✔
363
                factor = prefactor * pref * (sreal * np.sin(gr) - simag * np.cos(gr))
1✔
364

365
                forces += factor[:, None] * g[None, :]
1✔
366

367
        forces *= EwaldSummation.CONV_FACT
1✔
368
        erecip *= prefactor * EwaldSummation.CONV_FACT * qiqj * 2**0.5
1✔
369
        return erecip, forces
1✔
370

371
    def _calc_real_and_point(self):
1✔
372
        """
373
        Determines the self energy -(eta/pi)**(1/2) * sum_{i=1}^{N} q_i**2
374
        """
375
        fcoords = self._s.frac_coords
1✔
376
        forcepf = 2.0 * self._sqrt_eta / sqrt(pi)
1✔
377
        coords = self._coords
1✔
378
        numsites = self._s.num_sites
1✔
379
        ereal = np.empty((numsites, numsites), dtype=np.float_)
1✔
380

381
        forces = np.zeros((numsites, 3), dtype=np.float_)
1✔
382

383
        qs = np.array(self._oxi_states)
1✔
384

385
        epoint = -(qs**2) * sqrt(self._eta / pi)
1✔
386

387
        for i in range(numsites):
1✔
388
            nfcoords, rij, js, _ = self._s.lattice.get_points_in_sphere(
1✔
389
                fcoords, coords[i], self._rmax, zip_results=False
390
            )
391

392
            # remove the rii term
393
            inds = rij > 1e-8
1✔
394
            js = js[inds]
1✔
395
            rij = rij[inds]
1✔
396
            nfcoords = nfcoords[inds]
1✔
397

398
            qi = qs[i]
1✔
399
            qj = qs[js]
1✔
400

401
            erfcval = erfc(self._sqrt_eta * rij)
1✔
402
            new_ereals = erfcval * qi * qj / rij
1✔
403

404
            # insert new_ereals
405
            for k in range(numsites):
1✔
406
                ereal[k, i] = np.sum(new_ereals[js == k])
1✔
407

408
            if self._compute_forces:
1✔
409
                nccoords = self._s.lattice.get_cartesian_coords(nfcoords)
1✔
410

411
                fijpf = qj / rij**3 * (erfcval + forcepf * rij * np.exp(-self._eta * rij**2))
1✔
412
                forces[i] += np.sum(
1✔
413
                    np.expand_dims(fijpf, 1) * (np.array([coords[i]]) - nccoords) * qi * EwaldSummation.CONV_FACT,
414
                    axis=0,
415
                )
416

417
        ereal *= 0.5 * EwaldSummation.CONV_FACT
1✔
418
        epoint *= EwaldSummation.CONV_FACT
1✔
419
        return ereal, epoint, forces
1✔
420

421
    @property
1✔
422
    def eta(self):
1✔
423
        """
424
        Returns: eta value used in Ewald summation.
425
        """
426
        return self._eta
×
427

428
    def __str__(self):
1✔
429
        if self._compute_forces:
×
430
            output = [
×
431
                "Real = " + str(self.real_space_energy),
432
                "Reciprocal = " + str(self.reciprocal_space_energy),
433
                "Point = " + str(self.point_energy),
434
                "Total = " + str(self.total_energy),
435
                "Forces:\n" + str(self.forces),
436
            ]
437
        else:
438
            output = [
×
439
                "Real = " + str(self.real_space_energy),
440
                "Reciprocal = " + str(self.reciprocal_space_energy),
441
                "Point = " + str(self.point_energy),
442
                "Total = " + str(self.total_energy),
443
                "Forces were not computed",
444
            ]
445
        return "\n".join(output)
×
446

447
    def as_dict(self, verbosity: int = 0) -> dict:
1✔
448
        """
449
        Json-serialization dict representation of EwaldSummation.
450

451
        Args:
452
            verbosity (int): Verbosity level. Default of 0 only includes the
453
                matrix representation. Set to 1 for more details.
454
        """
455
        d = {
1✔
456
            "@module": type(self).__module__,
457
            "@class": type(self).__name__,
458
            "structure": self._s.as_dict(),
459
            "compute_forces": self._compute_forces,
460
            "eta": self._eta,
461
            "acc_factor": self._acc_factor,
462
            "real_space_cut": self._rmax,
463
            "recip_space_cut": self._gmax,
464
            "_recip": None if self._recip is None else self._recip.tolist(),
465
            "_real": None if self._real is None else self._real.tolist(),
466
            "_point": None if self._point is None else self._point.tolist(),
467
            "_forces": None if self._forces is None else self._forces.tolist(),
468
        }
469

470
        return d
1✔
471

472
    @classmethod
1✔
473
    def from_dict(cls, d: dict[str, Any], fmt: str | None = None, **kwargs) -> EwaldSummation:
1✔
474
        """Create an EwaldSummation instance from JSON-serialized dictionary.
475

476
        Args:
477
            d (dict): Dictionary representation
478
            fmt (str, optional): Unused. Defaults to None.
479

480
        Returns:
481
            EwaldSummation: class instance
482
        """
483
        summation = cls(
1✔
484
            structure=Structure.from_dict(d["structure"]),
485
            real_space_cut=d["real_space_cut"],
486
            recip_space_cut=d["recip_space_cut"],
487
            eta=d["eta"],
488
            acc_factor=d["acc_factor"],
489
            compute_forces=d["compute_forces"],
490
        )
491

492
        # set previously computed private attributes
493
        if d["_recip"] is not None:
1✔
494
            summation._recip = np.array(d["_recip"])
1✔
495
            summation._real = np.array(d["_real"])
1✔
496
            summation._point = np.array(d["_point"])
1✔
497
            summation._forces = np.array(d["_forces"])
1✔
498
            summation._initialized = True
1✔
499

500
        return summation
1✔
501

502

503
class EwaldMinimizer:
1✔
504
    """
505
    This class determines the manipulations that will minimize an Ewald matrix,
506
    given a list of possible manipulations. This class does not perform the
507
    manipulations on a structure, but will return the list of manipulations
508
    that should be done on one to produce the minimal structure. It returns the
509
    manipulations for the n lowest energy orderings. This class should be used
510
    to perform fractional species substitution or fractional species removal to
511
    produce a new structure. These manipulations create large numbers of
512
    candidate structures, and this class can be used to pick out those with the
513
    lowest Ewald sum.
514

515
    An alternative (possibly more intuitive) interface to this class is the
516
    order disordered structure transformation.
517

518
    Author - Will Richards
519
    """
520

521
    ALGO_FAST = 0
1✔
522
    ALGO_COMPLETE = 1
1✔
523
    ALGO_BEST_FIRST = 2
1✔
524

525
    """
526
    ALGO_TIME_LIMIT: Slowly increases the speed (with the cost of decreasing
527
    accuracy) as the minimizer runs. Attempts to limit the run time to
528
    approximately 30 minutes.
529
    """
530
    ALGO_TIME_LIMIT = 3
1✔
531

532
    def __init__(self, matrix, m_list, num_to_return=1, algo=ALGO_FAST):
1✔
533
        """
534
        Args:
535
            matrix: A matrix of the Ewald sum interaction energies. This is stored
536
                in the class as a diagonally symmetric array and so
537
                self._matrix will not be the same as the input matrix.
538
            m_list: list of manipulations. each item is of the form
539
                (multiplication fraction, number_of_indices, indices, species)
540
                These are sorted such that the first manipulation contains the
541
                most permutations. this is actually evaluated last in the
542
                recursion since I'm using pop.
543
            num_to_return: The minimizer will find the number_returned lowest
544
                energy structures. This is likely to return a number of duplicate
545
                structures so it may be necessary to overestimate and then
546
                remove the duplicates later. (duplicate checking in this
547
                process is extremely expensive)
548
        """
549
        # Setup and checking of inputs
550
        self._matrix = copy(matrix)
1✔
551
        # Make the matrix diagonally symmetric (so matrix[i,:] == matrix[:,j])
552
        for i in range(len(self._matrix)):
1✔
553
            for j in range(i, len(self._matrix)):
1✔
554
                value = (self._matrix[i, j] + self._matrix[j, i]) / 2
1✔
555
                self._matrix[i, j] = value
1✔
556
                self._matrix[j, i] = value
1✔
557

558
        # sort the m_list based on number of permutations
559
        self._m_list = sorted(m_list, key=lambda x: comb(len(x[2]), x[1]), reverse=True)
1✔
560

561
        for mlist in self._m_list:
1✔
562
            if mlist[0] > 1:
1✔
563
                raise ValueError("multiplication fractions must be <= 1")
×
564
        self._current_minimum = float("inf")
1✔
565
        self._num_to_return = num_to_return
1✔
566
        self._algo = algo
1✔
567
        if algo == EwaldMinimizer.ALGO_COMPLETE:
1✔
568
            raise NotImplementedError("Complete algo not yet implemented for EwaldMinimizer")
×
569

570
        self._output_lists = []
1✔
571
        # Tag that the recurse function looks at each level. If a method
572
        # sets this to true it breaks the recursion and stops the search.
573
        self._finished = False
1✔
574

575
        self._start_time = datetime.utcnow()
1✔
576

577
        self.minimize_matrix()
1✔
578

579
        self._best_m_list = self._output_lists[0][1]
1✔
580
        self._minimized_sum = self._output_lists[0][0]
1✔
581

582
    def minimize_matrix(self):
1✔
583
        """
584
        This method finds and returns the permutations that produce the lowest
585
        Ewald sum calls recursive function to iterate through permutations
586
        """
587
        if self._algo in (EwaldMinimizer.ALGO_FAST, EwaldMinimizer.ALGO_BEST_FIRST):
1✔
588
            return self._recurse(self._matrix, self._m_list, set(range(len(self._matrix))))
1✔
589
        return None
×
590

591
    def add_m_list(self, matrix_sum, m_list):
1✔
592
        """
593
        This adds an m_list to the output_lists and updates the current
594
        minimum if the list is full.
595
        """
596
        if self._output_lists is None:
1✔
597
            self._output_lists = [[matrix_sum, m_list]]
×
598
        else:
599
            bisect.insort(self._output_lists, [matrix_sum, m_list])
1✔
600
        if self._algo == EwaldMinimizer.ALGO_BEST_FIRST and len(self._output_lists) == self._num_to_return:
1✔
601
            self._finished = True
1✔
602
        if len(self._output_lists) > self._num_to_return:
1✔
603
            self._output_lists.pop()
1✔
604
        if len(self._output_lists) == self._num_to_return:
1✔
605
            self._current_minimum = self._output_lists[-1][0]
1✔
606

607
    def best_case(self, matrix, m_list, indices_left):
1✔
608
        """
609
        Computes a best case given a matrix and manipulation list.
610

611
        Args:
612
            matrix: the current matrix (with some permutations already
613
                performed)
614
            m_list: [(multiplication fraction, number_of_indices, indices,
615
                species)] describing the manipulation
616
            indices: Set of indices which haven't had a permutation
617
                performed on them.
618
        """
619
        m_indices = []
1✔
620
        fraction_list = []
1✔
621
        for m in m_list:
1✔
622
            m_indices.extend(m[2])
1✔
623
            fraction_list.extend([m[0]] * m[1])
1✔
624

625
        indices = list(indices_left.intersection(m_indices))
1✔
626

627
        interaction_matrix = matrix[indices, :][:, indices]
1✔
628

629
        fractions = np.zeros(len(interaction_matrix)) + 1
1✔
630
        fractions[: len(fraction_list)] = fraction_list
1✔
631
        fractions = np.sort(fractions)
1✔
632

633
        # Sum associated with each index (disregarding interactions between
634
        # indices)
635
        sums = 2 * np.sum(matrix[indices], axis=1)
1✔
636
        sums = np.sort(sums)
1✔
637

638
        # Interaction corrections. Can be reduced to (1-x)(1-y) for x,y in
639
        # fractions each element in a column gets multiplied by (1-x), and then
640
        # the sum of the columns gets multiplied by (1-y) since fractions are
641
        # less than 1, there is no effect of one choice on the other
642
        step1 = np.sort(interaction_matrix) * (1 - fractions)
1✔
643
        step2 = np.sort(np.sum(step1, axis=1))
1✔
644
        step3 = step2 * (1 - fractions)
1✔
645
        interaction_correction = np.sum(step3)
1✔
646

647
        if self._algo == self.ALGO_TIME_LIMIT:
1✔
648
            elapsed_time = datetime.utcnow() - self._start_time
×
649
            speedup_parameter = elapsed_time.total_seconds() / 1800
×
650
            avg_int = np.sum(interaction_matrix, axis=None)
×
651
            avg_frac = np.average(np.outer(1 - fractions, 1 - fractions))
×
652
            average_correction = avg_int * avg_frac
×
653

654
            interaction_correction = average_correction * speedup_parameter + interaction_correction * (
×
655
                1 - speedup_parameter
656
            )
657

658
        best_case = np.sum(matrix) + np.inner(sums[::-1], fractions - 1) + interaction_correction
1✔
659

660
        return best_case
1✔
661

662
    @classmethod
1✔
663
    def get_next_index(cls, matrix, manipulation, indices_left):
1✔
664
        """
665
        Returns an index that should have the most negative effect on the
666
        matrix sum
667
        """
668
        # pylint: disable=E1126
669
        f = manipulation[0]
1✔
670
        indices = list(indices_left.intersection(manipulation[2]))
1✔
671
        sums = np.sum(matrix[indices], axis=1)
1✔
672
        if f < 1:
1✔
673
            next_index = indices[sums.argmax(axis=0)]
1✔
674
        else:
675
            next_index = indices[sums.argmin(axis=0)]
1✔
676

677
        return next_index
1✔
678

679
    def _recurse(self, matrix, m_list, indices, output_m_list=None):
1✔
680
        """
681
        This method recursively finds the minimal permutations using a binary
682
        tree search strategy.
683

684
        Args:
685
            matrix: The current matrix (with some permutations already
686
                performed).
687
            m_list: The list of permutations still to be performed
688
            indices: Set of indices which haven't had a permutation
689
                performed on them.
690
        """
691
        # check to see if we've found all the solutions that we need
692
        if self._finished:
1✔
693
            return
1✔
694

695
        if output_m_list is None:
1✔
696
            output_m_list = []
1✔
697

698
        # if we're done with the current manipulation, pop it off.
699
        while m_list[-1][1] == 0:
1✔
700
            m_list = copy(m_list)
1✔
701
            m_list.pop()
1✔
702
            # if there are no more manipulations left to do check the value
703
            if not m_list:
1✔
704
                matrix_sum = np.sum(matrix)
1✔
705
                if matrix_sum < self._current_minimum:
1✔
706
                    self.add_m_list(matrix_sum, output_m_list)
1✔
707
                return
1✔
708

709
        # if we won't have enough indices left, return
710
        if m_list[-1][1] > len(indices.intersection(m_list[-1][2])):
1✔
711
            return
1✔
712

713
        if len(m_list) == 1 or m_list[-1][1] > 1:
1✔
714
            if self.best_case(matrix, m_list, indices) > self._current_minimum:
1✔
715
                return
1✔
716

717
        index = self.get_next_index(matrix, m_list[-1], indices)
1✔
718

719
        m_list[-1][2].remove(index)
1✔
720

721
        # Make the matrix and new m_list where we do the manipulation to the
722
        # index that we just got
723
        matrix2 = np.copy(matrix)
1✔
724
        m_list2 = deepcopy(m_list)
1✔
725
        output_m_list2 = copy(output_m_list)
1✔
726

727
        matrix2[index, :] *= m_list[-1][0]
1✔
728
        matrix2[:, index] *= m_list[-1][0]
1✔
729
        output_m_list2.append([index, m_list[-1][3]])
1✔
730
        indices2 = copy(indices)
1✔
731
        indices2.remove(index)
1✔
732
        m_list2[-1][1] -= 1
1✔
733

734
        # recurse through both the modified and unmodified matrices
735

736
        self._recurse(matrix2, m_list2, indices2, output_m_list2)
1✔
737
        self._recurse(matrix, m_list, indices, output_m_list)
1✔
738

739
    @property
1✔
740
    def best_m_list(self):
1✔
741
        """
742
        Returns: Best m_list found.
743
        """
744
        return self._best_m_list
1✔
745

746
    @property
1✔
747
    def minimized_sum(self):
1✔
748
        """
749
        Returns: Minimized sum
750
        """
751
        return self._minimized_sum
1✔
752

753
    @property
1✔
754
    def output_lists(self):
1✔
755
        """
756
        Returns: output lists.
757
        """
758
        return self._output_lists
1✔
759

760

761
def compute_average_oxidation_state(site):
1✔
762
    """
763
    Calculates the average oxidation state of a site
764

765
    Args:
766
        site: Site to compute average oxidation state
767

768
    Returns:
769
        Average oxidation state of site.
770
    """
771
    try:
1✔
772
        avg_oxi = sum(sp.oxi_state * occu for sp, occu in site.species.items() if sp is not None)
1✔
773
        return avg_oxi
1✔
774
    except AttributeError:
1✔
775
        pass
1✔
776
    try:
1✔
777
        return site.charge
1✔
778
    except AttributeError:
1✔
779
        raise ValueError(
1✔
780
            "Ewald summation can only be performed on structures "
781
            "that are either oxidation state decorated or have "
782
            "site charges."
783
        )
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc