Edit on GitHub

Ring statistics

Definitions

In this section, we use the terminology recommended by Blatov, O’Keeffe and Proserpio. In particular:

  • a cycle is a sequence of vertices v₁, v₂, ..., vₙ such that for all i between 2 and n, vᵢ₋₁ and vᵢ are neighbors, as well as v₁ and vₙ, and no vᵢ occurs more than once in the sequence. It can be equivalently represented by the sequence of edges between two consecutive vertices and between v₁ and vₙ.
  • the sum of two or more cycles is the set of edges occurring only an odd number of times in the set of input cycles. The sum of two cycles is thus the symmetric difference of their edges. Note that the sum of cycles may be empty, or may be the juxtaposition of several edge-disjoint cycles.
  • the length of a cycle is its number of edges. It is also equal to its number of vertices since no vertex is repeated in the sequence. A cycle a is strictly smaller than another b when the length of a is strictly lower than that of b.
  • a ring is a cycle which is not the sum of two strictly smaller cycles. An equivalent definition is that a ring is a cycle which does not admit a short-circuit: between two vertices of the ring, there is no path of the graph strictly smaller than both branches of the ring linking the two vertices.
  • a strong ring is a cycle which is not the sum of any number of strictly smaller cycles.

Manual

PeriodicGraphs.jl provides an algorithm for the determination of all rings and strong rings up to a given size in a PeriodicGraph. It can also be used on finite graphs by converting them to PeriodicGraph{0}, although the code is not optimized for this case.

The rings (respectively strong_rings) function returns the list of all rings (respectively strong rings) in the graph up to a given size:

PeriodicGraphs.rings — Function
rings(g::PeriodicGraph{D}, [depth::Integer=15,] symmetries::AbstractSymmetryGroup=NoSymmetryGroup(g), dist::DistanceRecord=DistanceRecord(g,depth)) where D

Compute the list of rings in g, up to length 2*depth+3. Return the list of Vector{Int} where each sublist is a ring whose vertices are the reverse_hash_positions of the sublist elements. Also return an AbstractSymmetryGroup acting on the returned rings.

A ring is a cycle of the graph for which there is no shortcut, i.e. no path in the graph between two vertices of the cycle that is shorter than either path connecting the vertices in the cycle.

If provided, symmetries should represent the symmetries of the graph as a AbstractSymmetryGroup object respecting its documented interface.

A PeriodicGraphs.DistanceRecord dist can be optionally provided to track the distances between pairs of vertices in the graph.

source
PeriodicGraphs.strong_rings — Function
strong_rings([rs::Vector{Vector{Int}},] g::PeriodicGraph{D}, [depth::Integer=15,] symmetries::AbstractSymmetryGroup=NoSymmetryGroup(g), dist::DistanceRecord=DistanceRecord(g,depth)) where D

Compute the list of strong rings in g, up to length 2*depth+3. Return them with their symmetry group. Each ring is represented by the list of hash_position of its vertices.

The optional first argument rs is the list of rings which can be provided if previously computed.

See rings for the meaning of the other arguments.

A strong ring is a cycle of the graph which cannot be decomposed into a sum of any number of smaller cycles. By comparison, a ring is a cycle which cannot be decomposed into a sum of two smaller cycles. In particular, all strong rings are rings.

See also strong_erings to obtain the rings as a list of integers representing the edges of the ring, instead of a list of integers representing its vertices.

source

A few notes on the output:

  • The output is a pair (rs, symm) where rs is the list of rings (respectively strong rings) and symm is an AbstractSymmetryGroup which contains symmetries of rs. symm is always a NoSymmetryGroup if the optional argument symmetries is not provided.
  • The returned list of rings rs is generally unsorted.
  • All translations of the same ring are represented by a unique ring, which means that a ring crossing through different unit cells will only appear once in the list, even though it may appear several times in a single unit cell.
  • The symmetries optional argument reduces the computational cost of the algorithm. The output lists rs with and without the optional argument are identical except for the order of their elements.

The optional argument depth defaults to 15, which means that rings containing up to 33 edges will be considered. This default value is chosen to accomodate the vast majority of periodic nets encountered as crystal nets, for which the ring size rarely exceeds 20.

Let's take as example an aperiodic graph representing a small house, made of a cube with a pyramid on top:

julia> house = PeriodicGraph{0}("0 "*
                    "1 2  2 3  3 4  4 1 "* # square base of the house
                    "1 5  2 6  3 7  4 8 "* # 4 vertical pillars
                    "5 6  6 7  7 8  8 5 "* # square ceiling
                    "5 9  6 9  7 9  8 9 "  # pyramidal roof
       );

julia> sort!(first(rings(house)))
14-element Vector{Vector{Int64}}:
 [1, 2, 3, 4]
 [1, 2, 3, 7, 8, 5]
 [1, 2, 6, 5]
 [1, 2, 6, 7, 8, 4]
 [1, 4, 3, 7, 6, 5]
 [1, 4, 8, 5]
 [2, 3, 4, 8, 5, 6]
 [2, 3, 7, 6]
 [3, 4, 8, 7]
 [5, 6, 7, 8]
 [5, 6, 9]
 [5, 8, 9]
 [6, 7, 9]
 [7, 8, 9]

julia> sort!(first(strong_rings(house)))
9-element Vector{Vector{Int64}}:
 [1, 2, 3, 4]
 [1, 2, 6, 5]
 [1, 4, 8, 5]
 [2, 3, 7, 6]
 [3, 4, 8, 7]
 [5, 6, 9]
 [5, 8, 9]
 [6, 7, 9]
 [7, 8, 9]

We can see that the house has four weak rings of size 6, six rings of size 4 among which five are strong, and four strong rings of size 3.

The strong rings are the faces of the house: there are four triangles that make the roof, four squares that make the walls and one last square for the base of the house. The square corresponding to the ceiling is actually the sum of the four triangles of the roof, which is why it is not a strong ring. The four weak rings of size 6 are those that go through each vertex of the cube except for one of the four opposite pairs.

To explore the ring distributions around individual vertices, the RingAttributions struct factors the ring distribution by vertex. The list of rings including a particular vertex is factored into a RingIncluding struct:

PeriodicGraphs.RingAttributions — Type
RingAttributions{D} <: AbstractVector{RingIncluding{D}}

Represent a set of rings of a PeriodicGraph{D}.

For ra of type RingAttributions{D}, ra[i] is a RingIncluding{D} object representing the set of rings including PeriodicVertex{D}(i).

source
PeriodicGraphs.RingIncluding — Type
RingIncluding{D} <: AbstractVector{OffsetVertexIterator{D}}

The list of rings of a PeriodicGraph{D} including a particular vertex PeriodicVertex{D}(i).

The object is iterable and indexable by an integer: for ri of type RingIncluding{D}, ri[j] is an iterable over the vertices of the j-th ring including vertex i.

source

To avoid useless computations, the lists of rings and the rings themselves are returned as iterables instead of Vector{PeriodicVertex{N}} and such, so they should be collected if required.

Let's look all the rings on our little house:

julia> ras = RingAttributions(house)
RingAttributions{0}(rings per node: [6, 6, 6, 6, 8, 8, 8, 8, 4])

julia> roofpeak = ras[9] # the list of rings including the top of the roof
4-element RingIncluding{0}:
 [5, 8, 9]
 [5, 6, 9]
 [7, 8, 9]
 [6, 7, 9]

julia> roofpeak[2] # the second ring including the top of the roof
3-element PeriodicGraphs.OffsetVertexIterator{0}:
 5
 6
 9

julia> rasstrong = RingAttributions(house, true)
RingAttributions{0}(rings per node: [3, 3, 3, 3, 4, 4, 4, 4, 4])

julia> rasstrong[1] # the base and two walls make the strong rings around vertex 1
3-element RingIncluding{0}:
 [1, 2, 6, 5]
 [1, 4, 8, 5]
 [1, 2, 3, 4]

julia> collect(rasstrong[5]) # two rooftiles and two walls make the strong rings around vertex 5
4-element Vector{PeriodicGraphs.OffsetVertexIterator{0}}:
 [5, 8, 9]
 [5, 6, 9]
 [1, 2, 6, 5]
 [1, 4, 8, 5]

Internal API

Here is a collection of internal utilities used for the algorithms of rings and strong_rings:

PeriodicGraphs.JunctionNode — Type
JunctionNode{T}

Element of the DAG representing the set of arcs linking each vertex x to a fixed vertex i of graph g. Each JunctionNode contains information on the arcs passing through a particular vertex x:

  • num is the length of the shortest path between x and i. Since we only collect rings, only the shortest paths are of interest, as well as the path of length num+1 which may form an odd-length ring when combined with a shortest path.
  • heads is a list of neighbors of x such that the lastshort first are at distance num - 1 from i, and the rest are at distance num and have a lower value than x.
  • shortroots is the set of roots reachable on a shortest path from x to i. A root is the neighbor of i on that path, a.k.a. the second-to-last vertex on that path.
  • longroots is the set of roots reachable on a path of length num+1 from x to i.
source
PeriodicGraphs.PhantomJunctionNode — Type
PhantomJunctionNode{D}

Element of the phantom DAG.

Similarly to the DAG of JunctionNode, the phantom DAG tracks arcs linking vertices x to a fixed vertex i, except that the vertices x are those that should be ignored in the returned list of rings. Thus, only the shortest distance between x and i needs to be recorded, since the arcs themselves will be discarded eventually.

source
PeriodicGraphs.arcs_list — Function
arcs_list(g::PeriodicGraph{D}, i, depth::T, ringavoid=nothing, cycleavoid=nothing) where {D,T}

Compute the list of shortest arcs starting from vertex i up to length depth+1. Vertices in ringavoid are not included in the returned arcs, but considered still part of the graph for distance computations. Vertices in cycleavoid are considered removed from the graph completely.

Return (dag, vertexnums) where dag is a Vector{JunctionNode{T}} representing, for each visited node, the DAG of all arcs from that node back to i, in a compact representation. vertexnums is a Vector{PeriodicVertex{D}} whose k-th value is the vertex represented by number k in dag.

If ringavoid !== nothing, dag will also not include arcs that pass through nodes of the form PeriodicVertex{D}(j, ofs) with j == i and ofs < zero(SVector{Int,D}): this allows eagerly pruning cycles that are translations of others. Note that this can result in missing cycles if those pass through at least three nodes with j == i, but that situation should be exceptionally rare.

Note

The type T of depth is used as type parameter to the JunctionNode, just to avoid having a dedicated argument (since depth should be at most 62 for the rest of the algorithm to work). This size controls the maximal degree a vertex of g should have : for example, T == UInt32 indicates that all vertices must have degree at most 31.

source
PeriodicGraphs.RingsEndingAt — Type
RingsEndingAt(dag, midnode, record)

Iterable over the rings of graph g around node i with midnode as vertex furthest from i. If there are two such vertices (odd ring), midnode is the higher of the two.

record should be set to (dist, vertexnums) where dist == DistanceRecord(g, depth) and dag, vertexnums == first(arcs_list(g, i, depth, ...)), otherwise the iterator will return many more cycles that may not be rings.

Warning

In order to efficiently cycle through the rings, the iterator reuses a buffer on which the rings are written. This means that performing an iteration will change the value of the previously returned result: for example, collect(RingsEndingAt(...)) will yield a list containing the same sublist (unlikely to be an actual ring) repeated over. To actually obtain the list of rings, copy the result as they arrive by doing map(copy, RingsEndingAt(...)) or [copy(x) for x in RingsEndingAt(...)] for example.

This also means that the list returned at each iteration should never be modified directly: copy it before.

source
PeriodicGraphs.normalize_cycle! — Function
normalize_cycle!(cycle::Vector{Int}, n, v::Val{D}) where D

In-place rotate and possibly reverse cycle, a Vector{Int} whose elements are the hash_position of vertices of g so that the result is the same for all such vectors that represent the same cycle, possibly translated to a different unit cell or rotated.

The graph g::PeriodicGraph{D} is represented as n = nv(g) and v = Val(D)

source
PeriodicGraphs.symdiff_cycles — Function
symdiff_cycles(a, b)

Symmetric difference between two sorted lists a and b. Return the sorted list of elements belonging to a or to b but not to both.

Use PeriodicGraphs.symdiff_cycles! to provide a pre-allocated destination.

Example

julia> PeriodicGraphs.symdiff_cycles([3,4,5], [4,5,6])
2-element Vector{Int64}:
 3
 6
source
PeriodicGraphs.IterativeGaussianElimination — Type
IterativeGaussianElimination{T}

Struct containing the list of sparse columns of the matrix under gaussian elimination on the 𝔽₂ finite field.

To be used with PeriodicGraphs.gaussian_elimination! as one of the three concrete types:

  • PeriodicGraphs.IterativeGaussianEliminationNone for simple gaussian elimination,
  • PeriodicGraphs.IterativeGaussianEliminationLength to detect when a new column can be expressed as a sum of strictly smaller columns of the matrix.
  • PeriodicGraphs.IterativeGaussianEliminationDecomposition to detect when a new column can be expressed as a sum of other columns of the matrix and keep track of which.
source
PeriodicGraphs.gaussian_elimination! — Function
gaussian_elimination!(gauss::IterativeGaussianElimination, r::Vector{Int})

Test whether r can be expressed as a sum of vectors stored in gauss, and store r if not. "sum" refers to the symmetric difference of boolean vectors, represented in sparse format as the ordered list of non-zero indices.

If gauss isa IterativeGaussianEliminationLength, return whether r can be expressed as a sum of strictly smaller vectors.

Otherwise, return true when r is a sum of any previously encoutered vectors. If gauss isa IterativeGaussianEliminationDecomposition, query retrieve_track(gauss) to obtain the sorted list of indices of such previously encountered vectors.

See also gaussian_elimination to test r without storing it.

source
PeriodicGraphs.gaussian_elimination — Function
gaussian_elimination(gauss::IterativeGaussianElimination, r::Vector{Int})

Return notindependent, info where notindependent is true if r can be expressed as a sum of vectors stored in gauss.

See PeriodicGraphs.gaussian_elimination! to store r in gauss if not, and for more details dependending on the type of gauss.

Call PeriodicGraphs.gaussian_elimination!(gauss, r, notindependent, info) to obtain the result of PeriodicGraphs.gaussian_elimination!(gauss, r) without duplicating computation.

source
PeriodicGraphs.intersect_cycles — Function
intersect_cycles(a, b)

Intersection between two sorted lists a and b. Return the sorted list of elements belonging to both a and b.

Use PeriodicGraphs.intersect_cycles! to provide a pre-allocated destination.

Example

julia> PeriodicGraphs.intersect_cycles([3,4,5], [4,5,6])
2-element Vector{Int64}:
 4
 5
source
PeriodicGraphs.union_cycles — Function
union_cycles(a, b)

Union between two sorted lists a and b. Return the sorted list of elements belonging to a or b or both.

Use PeriodicGraphs.union_cycles! to provide a pre-allocated destination.

Example

julia> PeriodicGraphs.union_cycles([3,4,5], [4,5,6])
4-element Vector{Int64}:
 3
 4
 5
 6
source
PeriodicGraphs.retrieve_track! — Function
retrieve_track!([ret::Vector{Int32}, buffer::Vector{Int32},] gauss::IterativeGaussianEliminationDecomposition)

To be called consecutive to a call to gaussian_elimination!(gauss, x) that returned true. In that case, x was found to be the sum of previously encountered vectors: return the (reverse-sorted) list of their indices.

Warning

Calling retrieve_track! after a call to gaussian_elimination! that returned false will produce an invalid result. Calling it twice will also produce an invalid result.

source
PeriodicGraphs.rings_around — Function
rings_around(g::PeriodicGraph{D}, i, depth=15, dist::DistanceRecord=DistanceRecord(g,depth), visited=nothing) where D

Return the list of all rings around node i in graph g up to length 2*depth+3.

The returned rings are the list of hash_position of the corresponding vertices. To get back the list of actual PeriodicVertex of a returned ring in the list, do

[reverse_hash_position(x, g) for x in ring]

If the offsets of the corresponding vertices are not needed, simply do

[mod1(x, n) for x in ring]   # n should be nv(g)

visited is interpreted as the ringavoid argument of arcs_list unless dist === nothing, in which case it is interpreted as the cycleavoid argument. In particular, unless dist === nothing, only one ring will appear in the list even if some of its translated images also pass through PeriodicVertex{D}(i).

source
PeriodicGraphs.EdgeDict — Type
EdgeDict{D}

Map from pairs of PeriodicVertex{D} to the identifier of the corresponding edge.

kp::EdgeDict{D} should be queried by either get!(kp, minmax(v1, v2)) where v1 and v2 are PeriodicVertex{D} to obtain the identifier of the edge and store a new identifier if absent, or by kp[i] where i is an Integer to obtain the pair of vertices corresponding to identifier i.

kp is built by calling EdgeDict(g) where g is a PeriodicGraph.

source
PeriodicGraphs.strong_erings — Function
strong_erings([rs::Vector{Vector{Int}},], g::PeriodicGraph{D}, [depth=15,] ringsymms::AbstractSymmetryGroup=NoSymmetryGroup(length(rs))) where D

Compute the list of strong edge rings in g, up to length 2*depth+3. See strong_rings and rings for the meaning of the optional arguments.

Return a quadruplet of values:

  • the two first values are the list of rings and their symmetry group, identical to the result of strong_rings, unless rs is provided (see below).
  • the third is the list of edge rings: each edge of the periodic graph is mapped to an integer and each ring is represented by the sorted list of its edges.
  • the last is the mapping from edges to integers, given as an EdgeDict.

If rs is provided, the first returned value is the list of indices keep of rs such that rs[keep] is the list of strong rings.

source