WorksPhysics and Astronomy
A path-finding algorithm for computing minimal-weight-matching centrosymmetry parameter
Abstract
In 2020, Peter Larsen reported flaws in the methods for centrosymmetry parameter computation in the existing molecular dynamics and analysis packages. He proposed an intuitive an mathematically rigorous formulation for centrosymmetry parameter in terms of minimal-weight matching (MWM) on a fully-connected graph of atomic neighbors. He proposed using Edmonds' blossom algorithm for computing such a matching. In this paper, we investigate an alternative algorithm for MWM CSP computation using path finding approach and A* algorithm.
Centrosymmetry parameter
The centrosymmetry parameter has been defined as
where is the number of nearest neighbors considered for CSP computation (an even number), and are the vectors corresponding to the pairs of opposite neighbors in the lattice.
The choice of specific pairs has not been described. Larsen [4] reports of two variants of the choice, greedy edge selection and greedy vertex matching, prevailing in the software by 2020, each of which has serious drawbacks. The reader is invited to read Larsen’s paper for further details on those two methods.
Larsen proposed reformulation of the edge selection problem for CSP as a constrained discrete optimization problem:
Each atom must participate in exactly one edge, and
The sum of edge weights must be minimal.
Those two conditions constitute a minimal-weight maximum matching problem on a fully-connected graph of atoms where weight of the edge connecting atoms and equals to .
An alternative formulation
Let us consider a graph where nodes are all possible matchings on the atom graph, edges connect each -pair matching with all -pair matchings formed by adding another pair of atoms to and the weight of the edge equals to the weight of the added atom pair. Then, finding the minimal-weight maximum matching is finding the shortest path from a 0-pair matching to a -pair matching in that graph. As a concrete example, A* algorithm finds a minimum path and has optimal time complexity of all heuristic path search algorithms Although the time complexity for the blossom algorithm is and the worst-case runtime of A* algorithm is where is the branching factor which can be conservatively estimated as , there are a few reasons to consider a path search reformulation for the specific problem:
CSP calculations are done for a small number of neighbors, typically 8 for BCC first shell, 12 for FCC first shell or 14 for BCC second shell
The A* algorithm is more straightforward than blossom algorithm, so that the smaller constant factors may outweigh the larger big-O complexity
With a suitable heuristic and early pruning, effective branching factor can be much smaller than the worst-case estimate.
Algorithm
The general A* search algorithm is defined as follows [2].
Algorithm 1 A* Path Search
1: function Astar(G, W, v_start, v_goal, h)
2: input: graph G = {vertices{v_k}, edges{e_l}}, edge weight matrix W, starting vertex v_start, goal vertex v_goal, heuristic h(v)
3: output: A path S = {e_path} from v_start to v_goal
4: Q ← min heap() ▷ Min-heap ordered by tentative f-score
5: enqueue(Q, [v_start])
6: while Q ≠ ∅ do
7: s ← dequeue(Q)
8: v_current ← last vertex(s)
9: if v_current = v_goal then
10: return s ▷ Goal reached
11: end if
12: for v_next ∈ neighbors(G, v_current) do
13: s′ ← append(s, v_next)
14: s′.f score ← path cost(s) + W[v_current, v_next] + h(v_next)
15: enqueue(Q, s′)
16: end for
17: end while
18: ERROR() ▷ No more vertices to explore but path has not been found
19: end function
If the heuristic is admissible, i.e. does not overestimate true path cost from to , then the A* algorithm finds the shortest path, i.e. it provides a valid solution for our specific problem. However, Algorithm 1 as written is not competitive for the CSP computation due to large work needed for new path exploration. In the rest of the paper, we explore possible optimizations tailor-fitted for the specific problem.
Path representation
Each node in our graph represents a partial matching – a set of disjoint atom pairs. If each of the atom pairs has a unique numeric identifier (ID), then each partial matching has a unique representation in which all pairs are sorted in the ascending order by the ID. Therefore, a path from an emty matching to the matching is represented by the list sorted by ID. Then, to form the next matching, we can consider only adding pairs with ID from onwards. Furthermore, for CSP calculation we are not interested in the set of pairs itself, only in its total weight. In that case, the state representation is further reduced. In the proposed approach, a state is characterized by:
The set of atoms already matched, represented as a bitmask . The number of atoms for CSP calculation does not exceed 16, so that standard 16-, 32- or 64-bit integers are suitable for that purpose,
The largest pair identifier in the matching, ,
The accumulated weight of the matching so far,
The expected total weight, which includes a lower bound on the cost to complete the matching.
The search begins from the empty matching (0-pair state) and terminates upon reaching a complete matching (-pair state where all atoms are covered). Edges in the state space graph correspond to adding one atom pair to the current partial matching. The weight of a transition equals the weight of the added pair, . If the pairs are represented as bitmasks of connected atoms, then the next possible pair to add can be found efficiently by linear scan over the list of pairs and the check of bitwise & .
Path queue representation
The set of next nodes to consider in A* is implemented as a priority queue ordered by expected path weight , implemented as a standard binary heap.
Pair ordering
For the efficient implementation, the weights of all atom pairs are computed in advance and sorted in the ascending order. Firstly, it allows us to use the greedy edge selection estimate. Secondly, it allows further optimizations as described below. The weights are stored in an array which has a length .
Path length heuristic
The A* algorithm requires a heuristic function estimating the cost to complete a partial matching . We define this heuristic as the sum of the shortest edges with IDs larger than of the matching, where is the number of additional pairs needed.
The advantage of this heuristic is that it only depends on the last matched pair, and the values can be statically precomputed prior to A* execution. It is computed in the form of matrix where row number represents and column number represents the remaining number of pairs .
where denotes the weight of the -th pair in the sorted list. If , then the corresponding element of the matrix is set to infinity or to a large enough value.
For a state with last-added edge at index and remaining pairs to add, the heuristic value is . The expected total weight is then , where is the actual cost so far.
Properties of the heuristic. Admissibility
A heuristic is admissible if it never overestimates the true cost to reach the goal. Our heuristic is admissible because:
The sum considers the minimum-weight atom pairs starting from index , ignoring any conflicts between them.
Any valid completion of the partial matching must select pairs, starting from index , which do not overlap with the pairs already present in the matching.
Therefore, all pairs on the true path completing a matching have weights larger or equal than the pairs used to compute , and , where is the true minimum cost to complete matching .
The admissibility is guaranteed by sorting atom pairs in the ascending-weight order prior to A* execution.
Monotonicity
Each column of is sorted in the ascending order:
Therefore, if , then for all .
A* algorithm optimized for CSP
Assuming that the set of covered atoms is stored as 32-bit integer and popcnt is a function returning the number of nonzero bits in the binary number representation, the algorithm can be written as follows.
Algorithm 2 assumes 1-based indexing for arrays and tuples, | and & are used for bitwise “or” and “and”, respectively, << is used for bitwise shift. generate_h_matrix is a function filling the heuristic matrix as explained in § 3.4.
Early-pruning strategies
Although Algorithm 2 correctly finds the minimum-weight path, further optimizations are possible. Profiling shows that the majority of time is spend in priority queue operations, so that additional optimizations are aimed to optimize them by pruning the branches that are guaranteed to not yield the optimal solution before they are enqueued.
Initial upper bound: A greedy vertex matching (selecting the shortest non-conflicting edges) provides an initial upper bound on the optimal MWM weight. Any path with cannot improve the solution.
Dynamic upper bound: During search, when a complete matching is discovered, is updated to the minimum of its current value and the new matching’s weight. This tightens pruning criteria as the search progresses.
Branch pruning: Due to heuristic monotonicity property (3), once an pair satisfies , all subsequent pairs also satisfy this condition. Therefore, the inner loop in Algorithm 2 can be terminated once it is met, because no other next pair can improve the MWM weight estimate.
Queue compaction: As upper bound is updated, the queue is resized to the index of the last item for which . That procedure further restricts the size of the queue.
Algorithm 2 A* algorithm optimized for CSP: No early pruning
1: function MWM_CSP_Astar(R)
2: input: array of particle positions R
3: output: minimum-weight matching CSP C_m
4: N ← length(R)
5: N_pairs ← N(N − 1)/2
6: P_p ← sort([(‖R_i + R_j‖², 1 << i | 1 << j) for i ∈ {0, . . . , N − 1}, j ∈ {i + 1, . . . , N − 1}])
7: H ← generate_H_matrix(P_p, N)
8: w_est ← P_p[1][1] + H[1, N/2 − 1] ▷ greedy path weight estimate
9: Q ← min_heap() ▷ Min-heap ordered by tentative f-score
10: enqueue(Q, (w_est, 0.0, 0, 0))
11: while Q ≠ ∅ do
12: w_est, g, M, ID_max ← dequeue(Q)
13: r ← (N − popcnt(M))/2
14: if r = 0 then
15: return w_est ▷ Goal reached
16: end if
17: for ID ∈ ID_max + 1, . . . , N_pairs do
18: (w, ij) ← P_p[ID]
19: if (M & ij) = 0 then ▷ Next selected edge is not in M
20: w_est ← g + w + H[ID, r]
21: enqueue(Q, (w_est, g + w, M | ij, ID))
22: end if
23: end for
24: end while
25: ERROR() ▷ No more vertices to explore but path has not been found
26: end function
(5) If the number of remaining pairs with ID ID is insufficient to complete the matching, the state is not expanded.
These strategies are included in Algorithms 3 and 4.
The early return in Line 8 of MWM_CSP_Astar when greedy edge selection finds a true solution is not strictly necessary because the initial path would still cause an early termination of the A* loop in that case. However, checking it early still saves some runtime in easy cases by avoiding the matrix generation.
Implementation
Algorithm 2 has been implemented in Julia language within the MDProcessing.jl package. It has been translated to C++ and benchmarked against the reference blossom algorithm implementation by P. Larsen and D. Pereira available in OVITO package [3].
Benchmarks
The C++ source code for the reference MWM CSP implementation and the proposed one have been isolated to be called from MDProcessing.jl package using the precomputed neighbor distance buffers. As such, the differences in runtime of two C++ implementations are only due to algorithmic differences as the Julia runtime overhead includes the same operations in both cases. The Julia
Algorithm 3 A* algorithm optimized for CSP with pruning strategies
1: function MWM_CSP_ASTAR(R)
2: input: array of particle positions R
3: output: minimum-weight matching CSP C_m
4: N ← LENGTH(R)
5: N_pairs ← N(N − 1)/2
6: P_p ← SORT([(||R_i + R_j||², 1 << i | 1 << j) for i ∈ {0, …, N − 1}, j ∈ {i + 1, …, N − 1}])
7: (w_greedy, w_U) ← INITIAL_WEIGHT_GUESSES(P_p)
8: if w_greedy = w_U then ▷ Greedy search gives the needed matching
9: return w_est
10: end if
11: H ← GENERATE_H_MATRIX(P_p, N)
12: Q ← MIN_HEAP() ▷ Min-heap ordered by tentative f-score
13: ENQUEUE(Q, (w_greedy, 0.0, 0, 0))
14: while Q ≠ ∅ do
15: w_est, g, M, ID_max ← DEQUEUE(Q)
16: r ← (N − POPCNT(M))/2
17: if r = 0 then
18: return w_greedy ▷ Goal reached
19: end if
20: w′_U ← g ▷ Initialize values for upper bound guess
21: M′ ← M
22: for ID ∈ ID_max + 1, …, N_pairs do
23: (w, ij) ← P_p[ID]
24: w_est ← g + w + H[ID, r]
25: if w_est < w_U then
26: if (M & ij) = 0 then ▷ Next selected edge is not in M
27: ENQUEUE(Q, (w_est, g + w, M | ij, ID))
28: end if
29: if (M′ & ij) = 0 then
30: M′ ← (M′ | ij)
31: w′_U ← w′_U + w
32: end if
33: else
34: break
35: end if
36: end for
37: if POPCNT(M′) = N and w′_U < w_U then ▷ Found a complete matching with better weight estimate
38: w_U ← w′_U
39: COMPACT_QUEUE(Q, w_U)
40: end if
41: end while
42: return w_U ▷ No more vertices to explore, upper estimate is the best
43: end function
Algorithm 4 Initial guesses for lower and upper bounds
1: function INITIAL_WEIGHT_GUESSES($P p$)
2: input: sorted array of pairs $P p$
3: output: lower bound $w_{\mathrm{greedy}}$, upper bound $w_U$
4: $M \leftarrow 0$
5: $w_U = 0.0$
6: $w_{\mathrm{greedy}} \leftarrow 0.0$ ▷ greedy path weight estimate
7: $n_{\mathrm{greedy}} \leftarrow 0$ ▷ Upper-bound weight estimate
8: for $(w, ij) \in P p$ do
9: if $n_{\mathrm{greedy}} < N/2$ then
10: $w_{\mathrm{greedy}} \leftarrow w_{\mathrm{greedy}} + w$
11: $n_{\mathrm{greedy}} \leftarrow n_{\mathrm{greedy}} + 1$
12: end if
13: if $(M \mathbin{\&} ij) = 0$ then
14: $w_U \leftarrow w_U + w$
15: $M \leftarrow (M \mathbin{|} ij)$
16: if $\operatorname{popcnt}(M) = N$ then
17: break
18: end if
19: end if
20: end for
21: return $(w_{\mathrm{greedy}}, w_U)$
22: end function
implementation is also called from MDProcessing.jl, the only difference is that it uses preallocated buffers for atom pairs, path queue and matrix.
The single-thread runtimes are presented for all MWM CSP implementations on a desktop and a laptop computers under openSUSE operating system with Linux 7.0 kernel. The C++ implementations are called from shared libraries compiled with -Ofast flag using GCC 15.2 compiler. Julia implementation uses Julia 1.11 version of the runtime. The averaged runtimes and standard uncertainties are evaluated using BenchmarkTools.jl [1].
The first benchmark is a system of 1000 Lennard-Jones particles at reduced density and reduced temperature , corresponding to the liquid phase. It corresponds to the case when greedy edge selection fails and full MWM computation is used for most of the particles.
The table shows that, although A* algorithm scales worse than the blossom algorithm for computing the minimum-weight matching, with additional optimization the latter is faster for small graph sizes typical for CSP calculation. The break-even point is between 14 and 16 atoms. Given that the CSP computation is usually done for 8-14 atoms, the A* search is worth considering as the default MWM implementation.
The Julia implementation is competitive against the C++ version, being only a few percent slower.
The second benchmark analyzes runtime for a crystalline system of 8000 Cu atoms. In that case, 12-atom matching must proceed faster due to high rate of greedy edge selection success. Table 2 shows the results. As expected, the original implementation with GES first and blossom algorithm as fallback performs the best. with 12 atoms. For other numbers of neighbors, the fallback method is activated, and the runtimes are larger. For the neighbor counts different than 12, the A* algorithm is faster in all cases. For 12 neighbors, A* is 20% slower on the desktop system, likely due to extra overhead of initial sorting of the edges array. A potential further optimization is to keep greedy edge selection as implemented by Larsen and use the algorithm described here only as fallback.
| Run parameters | Time (ms), Laptop (Ryzen 5 3500U, DDR4-2400) | Time (ms), Desktop (Ryzen 7 7700, DDR5-3400) |
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* |
Table 2. Runtime comparison for different implementations and hardware: Cu crystal
| Run parameters | Time (ms), Laptop (Ryzen 5 3500U, DDR4-2400) | Time (ms), Desktop (Ryzen 7 7700, DDR5-3400) |
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* | ||
| , C++ blossom | ||
| , C++ A* | ||
| , Julia A* |
Table 1. Runtime comparison for different implementations and hardware: LJ liquid
Conclusions
An alternative implementation of minimal-weight matching for centrosymmetry parameter is proposed. It is based on direct graph search using algorithm with extra pruning and early-termination conditions to avoid exploration of dead-ends. The proposed algorithm is competitive with the standard blossom algorithm proposed earlier for this problem if the number of atoms is 16 or less. As such, the method is worth considering as the default for centrosymmetry calculations in atomistic simulations.
HSE University Tikhonov MIEM, Moscow, Russia
Email address: [email protected]
References
- [1]Jiahao Chen and Jarrett Revels. “Robust benchmarking in noisy environments”. In: arXiv e-prints, arXiv:1608.04295 (Aug. 2016). arXiv: 1608.04295 [cs.PF].arxiv.org/abs/1608.04295
- [2]Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. In: IEEE Transactions on Systems Science and Cybernetics 4.2 (1968), pp. 100–107.DOI
- [3]P.M. Larsen and D.L. Pereira. URL: https://gitlab.com/stuko/ovito/-/blob/6c9b8e00a73783770ec8fb056e9527658b10004f/src/3rdparty/mwm_csp/matching.cpp (visited on 05/17/2026).
- [4]Peter M Larsen. “Revisiting the Common Neighbour Analysis and the Centrosymmetry Parameter”. In: arXiv e-prints, arXiv:2003.08879 (2020). DOI: 10.48550/arXiv.2003.08879. arXiv: 2003.08879.DOI