Neighbor Finding¶
This guide explains how neighbors are identified in the CNF representation. Every crystal has a well-defined set of neighbors: structures that differ by small geometric perturbations. These neighbors form a graph connecting all possible crystals of a given composition, enabling pathfinding algorithms to discover transformation pathways between phases.
from pymatgen.core import Structure, Lattice
from cnf import CNFConstructor
from cnf.navigation import NeighborFinder, find_neighbors
import numpy as np
# Create rutile TiO2
a, c = 4.594, 2.959
lattice = Lattice.tetragonal(a, c)
species = ["Ti", "Ti", "O", "O", "O", "O"]
coords = [[0, 0, 0], [0.5, 0.5, 0.5], [0.305, 0.305, 0], [0.695, 0.695, 0], [0.805, 0.195, 0.5], [0.195, 0.805, 0.5]]
rutile = Structure(lattice, species, coords)
constructor = CNFConstructor(xi=1.0, delta=100)
result = constructor.from_pymatgen_structure(rutile)
cnf = result.cnf
print(f"Rutile TiO2 CNF: {cnf.coords}")
Rutile TiO2 CNF: (9, 21, 21, 51, 30, 30, 42, 50, 50, 50, 0, 30, 30, 0, 70, 70, 50, 20, 80, 50, 80, 20)
Two Types of Neighbors¶
The CNF tuple consists of two parts: the lattice (first 7 integers) and the motif (remaining coordinates). Correspondingly, there are two types of neighbors.
Lattice neighbors differ in the vonorm coordinates and represent small strain transformations of the unit cell. Motif neighbors differ in the atomic position coordinates and represent small displacements of atoms within a fixed lattice. Together, these neighbors capture all possible small perturbations of a crystal structure.
finder = NeighborFinder.from_cnf(cnf)
lattice_neighbors = finder.find_lattice_neighbor_cnfs(cnf)
motif_neighbors = finder.find_motif_neighbor_cnfs(cnf)
print(f"Lattice neighbors: {len(lattice_neighbors)}")
print(f"Motif neighbors: {len(motif_neighbors)}")
print(f"Total neighbors: {len(lattice_neighbors) + len(motif_neighbors)}")
Lattice neighbors: 11 Motif neighbors: 11 Total neighbors: 22
Lattice Neighbors: The 42 Steps¶
A lattice can have up to 42 neighboring lattices connected by small strains. These arise from the structure of the vonorm representation.
Recall that the 7 vonorms are not independent—they satisfy a constraint relating the primary vonorms (indices 0-3, the squared lengths of superbasis vectors) to the secondary vonorms (indices 4-6, the squared lengths of pairwise sums). Valid lattice perturbations must preserve this constraint.
The 42 possible steps come from considering all pairs of vonorm indices. For each pair, we adjust one index by +1 and the other by ±1, with the sign determined by whether the indices are primary or secondary. Each such adjustment, along with its negation, gives 2 steps per pair. With 21 pairs from 7 indices, we get 42 total steps.
from cnf.navigation.lattice_step import LatticeStep
all_steps = LatticeStep.all_step_vecs()
print(f"Total lattice step vectors: {len(all_steps)}")
print("\nExample step vectors:")
for i, step in enumerate(all_steps[:6]):
print(f" {step}")
print(f" ... and {len(all_steps) - 6} more")
Total lattice step vectors: 42 Example step vectors: [1, -1, 0, 0, 0, 0, 0] [-1, 1, 0, 0, 0, 0, 0] [1, 0, -1, 0, 0, 0, 0] [-1, 0, 1, 0, 0, 0, 0] [1, 0, 0, -1, 0, 0, 0] [-1, 0, 0, 1, 0, 0, 0] ... and 36 more
# Show the pattern: pairs of indices with specific sign rules
print("Step vector structure:")
print(" Primary indices (0-3): squared lengths of superbasis vectors")
print(" Secondary indices (4-6): squared lengths of pairwise sums")
print()
print("Sign rules for (i, j) pairs:")
print(" Primary-Primary: (+1, -1)")
print(" Primary-Secondary: (+1, +1)")
print(" Secondary-Secondary: (+1, -1)")
Step vector structure: Primary indices (0-3): squared lengths of superbasis vectors Secondary indices (4-6): squared lengths of pairwise sums Sign rules for (i, j) pairs: Primary-Primary: (+1, -1) Primary-Secondary: (+1, +1) Secondary-Secondary: (+1, -1)
Validating Lattice Steps¶
Not all 42 steps produce valid neighbors from a given lattice. A step is valid only if the resulting superbasis remains obtuse, meaning all conorms (dot products between superbasis vectors) are non-positive.
The validation process applies each step vector to the current vonorms, checks that the resulting conorms satisfy the obtuseness constraint, and then canonicalizes the result to ensure it is in normal form.
# Show which steps are valid for this lattice
current_vonorms = np.array(cnf.coords[:7])
print(f"Current vonorms: {tuple(current_vonorms)}")
print()
print(f"Valid lattice neighbors: {len(lattice_neighbors)}")
print(f"Invalid steps (rejected): {42 - len(lattice_neighbors)}")
Current vonorms: (9, 21, 21, 51, 30, 30, 42) Valid lattice neighbors: 11 Invalid steps (rejected): 31
# Show how lattice neighbors differ from the original
print("First 5 lattice neighbors (showing vonorm changes):")
orig_vonorms = np.array(cnf.coords[:7])
for i, neighbor in enumerate(lattice_neighbors[:5]):
neighbor_vonorms = np.array(neighbor.coords[:7])
diff = neighbor_vonorms - orig_vonorms
changes = [f"v{j}: {int(diff[j]):+d}" for j in np.where(diff != 0)[0]]
print(f" {i+1}. {', '.join(changes)}")
First 5 lattice neighbors (showing vonorm changes): 1. v2: +1, v3: -1 2. v1: +1, v2: +9, v3: -9, v5: -8, v6: +9 3. v2: +9, v3: -9, v4: -1, v5: -8, v6: +9 4. v0: +1, v2: +9, v3: -10, v5: -9, v6: +9 5. v3: -1, v6: -1
Motif Neighbors: Atomic Displacements¶
Motif neighbors keep the lattice fixed and perturb the atomic positions. For a structure with N atoms, there are up to 8(N-1) motif neighbors. The factor of N-1 arises because one atom is fixed at the origin.
For each non-origin atom, we consider two types of perturbations. First, we vary each of the three fractional coordinates individually by ±1 (in units of 1/δ), giving 6 neighbors per atom. Second, we vary all three coordinates simultaneously by ±1, giving 2 more neighbors per atom. This corresponds to a diagonal displacement in fractional coordinate space.
n_atoms = len(cnf.elements)
n_non_origin = n_atoms - 1
print(f"Number of atoms: {n_atoms}")
print(f"Non-origin atoms: {n_non_origin}")
print()
print(f"Individual coordinate variations: {n_non_origin} atoms × 3 coords × 2 directions = {n_non_origin * 6}")
print(f"Diagonal variations: {n_non_origin} atoms × 2 directions = {n_non_origin * 2}")
print(f"Maximum motif neighbors: {n_non_origin * 8}")
print()
print(f"Actual motif neighbors found: {len(motif_neighbors)}")
Number of atoms: 6 Non-origin atoms: 5 Individual coordinate variations: 5 atoms × 3 coords × 2 directions = 30 Diagonal variations: 5 atoms × 2 directions = 10 Maximum motif neighbors: 40 Actual motif neighbors found: 11
# Show how motif neighbors differ from the original
print("First 5 motif neighbors (showing coordinate changes):")
orig_coords = np.array(cnf.coords)
for i, neighbor in enumerate(motif_neighbors[:5]):
neighbor_coords = np.array(neighbor.coords)
diff = neighbor_coords - orig_coords
# Only show motif differences (indices 7+)
changes = [f"[{j}]: {int(diff[j]):+d}" for j in np.where(diff != 0)[0] if j >= 7]
if changes:
print(f" {i+1}. {', '.join(changes)}")
else:
# The neighbor might have permuted coordinates
print(f" {i+1}. (coordinates reordered by canonicalization)")
First 5 motif neighbors (showing coordinate changes): 1. [8]: -1, [11]: -1, [14]: -1, [17]: -1, [20]: -1 2. [16]: -1, [17]: +1, [18]: -1 3. [16]: -1, [17]: -1, [18]: +1 4. [16]: -1 5. [7]: -1
The Role of Stabilizers¶
High-symmetry lattices have stabilizers: permutations that leave the canonical vonorms unchanged. When finding motif neighbors, we must account for these symmetries.
The algorithm applies each stabilizer transformation to the motif before generating coordinate perturbations. This ensures that equivalent perturbations related by lattice symmetry are discovered. After generating all candidates, each is canonicalized (via the MNF algorithm) and duplicates are removed.
from cnf.lattice.voronoi import VonormList
vonorms = VonormList(cnf.coords[:7], conorm_tol=0)
stabilizers = vonorms.stabilizer_matrices_fast()
print(f"Number of stabilizer matrices: {len(stabilizers)}")
print()
print("Each stabilizer represents a symmetry operation that preserves the lattice.")
print("Motif perturbations are tried from each stabilizer-transformed starting point.")
Number of stabilizer matrices: 8 Each stabilizer represents a symmetry operation that preserves the lattice. Motif perturbations are tried from each stabilizer-transformed starting point.
Canonicalization and Deduplication¶
After generating candidate neighbors, each must be converted to canonical form. For lattice neighbors, this means recomputing the LNF (applying permissible permutations and selecting the lexicographically smallest vonorms). For motif neighbors, this means recomputing the MNF (trying all stabilizers and origin shifts, then selecting the lexicographically smallest coordinates).
Canonicalization serves two purposes. First, it ensures that neighbors are directly comparable—two structures are identical if and only if their canonical forms match. Second, it eliminates duplicates: different perturbations that produce the same physical structure will canonicalize to the same tuple.
# The combined neighbor set is deduplicated
all_neighbors = find_neighbors(cnf)
print(f"Lattice neighbors: {len(lattice_neighbors)}")
print(f"Motif neighbors: {len(motif_neighbors)}")
print(f"Combined (deduplicated): {len(all_neighbors)}")
print()
print("The combined count equals the sum because lattice and motif neighbors")
print("are disjoint—they change different parts of the CNF tuple.")
Lattice neighbors: 11 Motif neighbors: 11 Combined (deduplicated): 22 The combined count equals the sum because lattice and motif neighbors are disjoint—they change different parts of the CNF tuple.
Self-Loop Filtering¶
On high-symmetry lattices, a perturbation can sometimes map back to the original structure after canonicalization. These self-loops must be filtered out to avoid infinite loops in pathfinding algorithms.
The implementation explicitly checks for and removes the original point from the neighbor set.
# Verify no self-loops
original_tuple = cnf.coords
self_loops = [n for n in all_neighbors if n.coords == original_tuple]
print(f"Self-loops found: {len(self_loops)}")
print("(Self-loops are automatically filtered out)")
Self-loops found: 0 (Self-loops are automatically filtered out)
The Neighbor Graph¶
The neighbor relation defines a graph over all possible crystals of a given composition. Each crystal is a node, and edges connect crystals that are neighbors. This graph is symmetric: if B is a neighbor of A, then A is a neighbor of B.
Pathfinding algorithms like A* can traverse this graph to find transformation pathways between any two structures. The path length gives a measure of structural distance, and by evaluating energies along the path, one can identify minimum-energy barriers between phases.
# Verify symmetry: pick a neighbor and check that the original is in its neighbor set
if all_neighbors:
test_neighbor = all_neighbors[0]
neighbor_of_neighbor = find_neighbors(test_neighbor)
# Check if original is a neighbor of the neighbor
original_in_neighbors = any(n.coords == original_tuple for n in neighbor_of_neighbor)
print(f"Testing symmetry with neighbor: {test_neighbor.coords[:7]}...")
print(f"Original is neighbor of neighbor: {original_in_neighbors}")
Testing symmetry with neighbor: (9, 21, 21, 51, 30, 30, 42)... Original is neighbor of neighbor: True
Summary¶
Neighbor finding in the CNF representation works as follows:
Lattice neighbors are generated by applying up to 42 step vectors to the vonorms, validating that the result has an obtuse superbasis, and canonicalizing via the LNF algorithm.
Motif neighbors are generated by perturbing each non-origin atom's coordinates by ±1 (individually and diagonally), applying all stabilizer transformations, and canonicalizing via the MNF algorithm.
Both types of neighbors are deduplicated and self-loops are removed.
The result is a well-defined neighbor graph connecting all crystals of a given composition, suitable for systematic exploration and pathfinding.