## PeriodicGraphEquilibriumPlacement.jl

Algorithm for barycentric (a.k.a. equilibrium) placement of vertices of a periodic graph
Author Liozou
Popularity
1 Star
Updated Last
1 Year Ago
Started In
June 2022

# PeriodicGraphEquilibriumPlacement

A Julia package for computing the equilibrium, or barycentric, placement of vertices of a periodic graph, as defined by Olaf Delgado-Friedrichs and Michael O'Keeffe. It is accessible through the `equilibrium` exported function, which returns a matrix of rational coordinates that can be fed to the `PeriodicGraphEmbedding` or `SortedPeriodicGraphEmbedding` methods from PeriodicGraphEmbeddings.jl:

```julia> tbo = PeriodicGraph3D("3 1 2 0 0 0 1 3 0 0 0 1 4 0 0 0 2 5 0 0 0 2 6 0 0 0 2 7 0 0 0 3 6 0 0 1 3 8 0 0 0 3 9 0 0 0 4 6 1 0 0 4 10 0 0 0 4 11 0 0 0 5 12 0 0 0 5 13 0 0 0 7 12 1 1 -1 7 13 0 1 0 8 12 0 0 0 8 14 0 0 0 9 12 1 1 0 9 14 0 1 0 10 13 0 0 0 10 14 0 0 0 11 13 1 1 0 11 14 1 1 -1");

julia> equilibrium(tbo)
3×14 Matrix{Rational{Int64}}:
0//1  -1//6  -1//6   1//3  -1//3  -1//3   0//1  -1//3  0//1   0//1   2//3  -2//3  -1//6  -1//6
0//1   0//1   0//1   0//1  -1//3   0//1   1//3  -1//3  1//3  -1//3   1//3  -1//2  -1//2  -1//2
0//1  -1//6   1//3  -1//6   0//1  -1//3  -1//3   1//3  1//3   0//1  -1//3   1//3  -1//6   1//3```

The implementation is optimized through a custom solver specialized for the exact resolution of sparse integer linear system through Dixon's algorithm. The solver is directly accessible through the `dixon_solve` function:

```julia> A = sparse([-3 0 2 0; 0 -5 2 3; 2 2 -2 0; 0 3 0 -3]);

julia> Y = [1 1; 0 2; 1 -1; 0 0];

julia> A * dixon_solve(Val(2), A, Y) == Y
true```

The first argument of `dixon_solve` must be `Val(size(Y)[2])` and the second must be square.

The package also exposes a `rational_solve` function which solves the same systems through a simpler LU decomposition approach. It serves as fallback to `dixon_solve` when Dixon's algorithm fails, but can also be used as-is with the same API. Its performance is in general lower than `dixon_solve`, often significantly so.

• PeriodicGraphs.jl for the underlying library and the API of the `PeriodicGraph` type.