Metadata-Version: 2.4
Name: messthaler-wulff
Version: 2026.5.2
Author-email: Guenthner <guenthner.jonathan@gmail.com>
License-File: LICENSE.txt
Keywords: Wulff,Wulff Crystals
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.8
Requires-Dist: argcomplete
Requires-Dist: colorama
Requires-Dist: matplotlib
Requires-Dist: mydefaults==2.*
Requires-Dist: networkx
Requires-Dist: open3d
Requires-Dist: prettytable
Requires-Dist: psutil
Requires-Dist: pydantic
Requires-Dist: scipy
Description-Content-Type: text/markdown

---
title: The Meßthaler-Wulff Project
author: Julia Meßthaler
---

Blazingly fast code for finding all crystals
(subsets of a graph) that can be constructed
using only transformations that locally minimize
surface energy.

## The Problem

Let $(G, E)$ be some graph and $N{}: G → \wp(G)$ denote the neighbors
of a given node, defined as
$$
  N{}(n) := \{ n_0 \in G \mid \{n_0, n\} \in E \}
$$

Now we can define a crystal as $c \subset G$ with $c$ finite.
This allows us to define the set of all crystals
$C := \{ c \subset G \mid c \text{ finite} \}$.

Now we can define the surface energy of the crystal $c$
(or arbitrary subsets of $G$) as
$$
  E_c := \sum_{n \in c} f_{G \setminus c}(n)
$$
where $f_M(n)$ denotes the "friendliness" of the node $n$ or 
how many friends it has defined as
$$
  f_M(n) := \# \{ n_0 \in N{}(n) \mid n_0 \in M \}
$$

The idea now is to find crystals $c$ such that $\frac{E_{c}}{\#c}$
is optimal.

    Note:
$$
    E_c = \sum_{n} χ_c(n) · (\#N{}(n) - f_c(n))
$$

$$
    = \sum_n χ_c(n) · \#N{}(n) - \sum_{a,b \in N{}(a)} χ_c(a) · χ_c(b)
$$

$$
    N{}' := (\#N{}(n_i))_{1 ≤ i ≤ B}
$$

$$
    E_c = (N{}'^\top · χ_c) - (χ_c^\top · A_G · χ_c)
$$

## The Crystal Graph

We can impose a graph structure on $C$ with the edges
$$
  T := \{ \{ c, c \setminus \{n\} \} \mid c \in C \text{ and } n \in c \}
$$
we call these the transformations and $(C,T)$ the transformation graph.

If we want to discover optimal crystals, then we must efficiently walk this
graph. Since this graph is very dense and very large, we must first
discuss some optimizations:

- [$O(1)$ transformations](#efficient-transformations)

## Efficient Transformations

In the code this is achieved using the stateful class `AdditiveSimulation` that walks
along the transformation graph. This class keeps track of two
important properties, namely $f_c(n)$ and $χ_c(n)$ for (almost) all
$n \in G$, we do not need to store the (possibly) infinite number of values, as
we can let $f_c(n)$ default to $0$ and $χ_c(n)$ to $0$.
$χ_c(n) \in \{0,1\}$ is the characteristic function of the set $c$
and is equal to $1$ exactly iff the node is in $c$.

To the characteristic function we can associate a sign using
$s: \{0,1\} → \{-1, 1\}$, defined as $s(x) = 2x - 1$.

Now let us take a look at what happens, if we walk along an edge $t \in T$.
Let $n$ be the single node that is affected by this transformation.

Let $φ$ be any specific integer quantity we are tracking, then let
$Δφ := φ' - φ$ be the difference between the old and the new value
of the quantity.

$χ_c$ is updated using $Δχ_c(n) = -s∘χ_c(n)$.

The friendliness $f_c(n)$ does not change. Instead, the friendliness of
each neighbor must be updated. So for each $n_0 \in N{}(n)$:
$Δ f_c(n_0) = -s∘χ_c(n)$.

For updating the Energy $E_c$ will first require some work. We already know
the update rule for neighbors $n_0$ of $n$. For nodes $n_0$ that are not $n$
or neighbors of $n$ the differential is $Δ f_c(n_0) = 0$, in essence this is
also not problematic.

However for $n$ the differential is more involved, as the transition makes
the node become part of or be excluded from the sum that defines $E_c$.
So its contribution is
$$
    -s∘χ_c(n) · f_{G \setminus c}(n) = -s∘χ_c(n) · [\#N{}(n) - f_c(n)]
$$

Now for the calculation:
$$
    Δ E_c   = \sum_{n_0 \in c} f_{G \setminus c}(n_0)
$$

$$
            = \left[ \sum_{n_0 \in N{}(n) ∩ c} Δ f_{G \setminus c}(n_0)\right] -s∘χ_c(n) · [\#N{}(n) - f_c(n)]
$$

$$
            = \left[ \sum_{n_0 \in N{}(n) ∩ c} s∘χ_c(n) \right] -s∘χ_c(n) · [\#N{}(n) - f_c(n)]
$$

$$
            = s∘χ_c(n) · f_c(n) -s∘χ_c(n) · [\#N{}(n) - f_c(n)]
$$

$$
            = s∘χ_c(n) · (2f_c(n) - \#N{}(n))
$$

## Min-Calculus

$$
    Q: ℤ^n → ℤ
$$

$$
    r_k: ℤ^{n-k} → ℤ
$$

$$
    \min(Q) = r_n
$$

$$
    r_0 = Q
$$

$$
    r_k = \min(r_{k-1}(0),r_{k-1}(1))
$$

### Solvers

---