Utilities
Hashing
It is sometimes convenient to be able to associate to each vertex of periodic graph g an integer hash, such that the hashes of vertices in the reference unit cell are between 1 and nv(g), the hashes of the vertices in the unit cells around the reference are next, then the vertices of the unit cells around those, etc. To do so, PeriodicGraphs.jl export the hash_position function as follows:
PeriodicGraphs.hash_position — Functionhash_position(x::PeriodicVertex{N}, n::Integer) where NGiven x, a PeriodicVertex{N}, and the number n of vertex identifiers in a graph, compute a unique positive integer hash for the given vertex.
This hash function is a bijection between the set of all the vertices of the periodic graph and the set of positive integers. Its value is an integer between 1+n*(2d-1)^N (or 1 if d == 0) and n*(2d+1)^N, where d = maximum(abs.(x.ofs)).
In particular, this means that when one unit cell B is further than another A from the origin (for the Manhattan distance), all vertices in B have a larger hash than all vertices in A.
The reciproque function is also exported:
PeriodicGraphs.reverse_hash_position — Functionreverse_hash_position(hash::Integer, n::Integer, ::Val{N}) where NGiven a hash obtained from hash_position(x, n) where x is a PeriodicVertex{N}, return the corresponding x.
If the offset of the returned PeriodicVertex is not needed, simply doing mod1(x, n) yields the identifier of the vertex and is faster.
Both functions are optimized for dimensions 1, 2 and 3, especially for unit cells not too far from the reference.
Isomorphic transformations
Several functions transform a periodic graph into another isomorphic to the input, by renumbering the vertices (vertex_permutation) or the axes (swap_axes!), or by offsetting the chosen representatives for each vertex (offset_representatives!). It is also possible to make an isomorphic graph with more vertices per unit cell by using a supercell (make_supercell).
PeriodicGraphs.vertex_permutation — Functionvertex_permutation(g::PeriodicGraph, vlist)Return the PeriodicGraph corresponding to g with its vertices identifiers permuted according to vlist. isperm(vlist) must hold and will not be checked.
See also Graphs.induced_subgraph for the more general case where vlist is not a permutation.
The resulting graph is isomorphic to the initial one, only the representation has changed.
PeriodicGraphs.swap_axes! — Functionswap_axes!(g::PeriodicGraph, t)In-place modifies graph g so that the new initial cell corresponds to the previous one with its axes swapped according to the permutation t.
The resulting graph is isomorphic to the initial one, only the representation has changed.
PeriodicGraphs.offset_representatives! — Functionoffset_representatives!(g::PeriodicGraph, offsets)In-place modifies graph g so that the i-th vertex of the new initial cell corresponds to the i-th vertex in cell offsets[i] compared to the previous initial cell.
The resulting graph is isomorphic to the initial one, only the representation has changed.
PeriodicGraphs.make_supercell — Functionmake_supercell(g::PeriodicGraph, t)Return a graph isomorphic to the input g whose its unit cell is a repetition of that of g, each dimension i being repeated t[i] times. It follows that the number of vertices of make_supercell(g, t) is prod(t)*nv(g)
t must be an interator over positive integers.
Dimension reduction
Any PeriodicGraph can be naturally reduced to an aperiodic graph by removing all offsets from the edges and either keeping (quotient_graph) or removing (truncated_graph) edges crossing from one unit cell to another.
PeriodicGraphs.quotient_graph — Functionquotient_graph(g::PeriodicGraph)Extract a simple graph from g by removing all indications of offset in the edges. This means that edges that used to cross the boundaries of the initial cell now bind the source vertex to the representative of the destination vertex that is in the initial cell.
Note that these modified edges may turn into loops.
See also truncated_graph to remove all of these edges and slice_graph to keep only some of these edges.
PeriodicGraphs.truncated_graph — Functiontruncated_graph(g::PeriodicGraph)Extract a simple graph from g by only keeping the edges that are strictly within the initial cell.
See also quotient_graph to keep all of these edges and slice_graph to keep only some of these edges.
It is also possible to reduce the dimension of a graph by removing only some selected offsets with the slice_graph function.
PeriodicGraphs.slice_graph — Functionslice_graph(g::PeriodicGraph{D}, remove::Union{SVector{N},NTuple{N}}) where {D,N}Extract a PeriodicGraph{D-N} from g by removing all edges that have an offset o such that !iszero(o[remove]) and shrinking the resulting offsets. In other words, remove the dimensions in remove.
To only remove the edges while keeping the same number of dimensions, use slice_graph(g, collect(remove))
remove is assumed to be sorted and to contain unique elements.
No verification of the previous assumption will be performed.
slice_graph(g::PeriodicGraph{D}, remove::Vector{<:Integer}) where DExtract a PeriodicGraph{D} from g by removing all edges that have an offset o such that !iszero(o[remove]).
Contrarily to the slice_graph(g::PeriodicGraph{D}, remove::Union{SVector{N},NTuple{N}}) where {D,N} method, the dimensions along which the edges are erased are still kept here.
remove is assumed to be sorted and to contain unique elements.
No verification of the previous assumption will be performed.
Arithmetics
These utilities are internally used for dimensionality computations, but may be useful in other contexts.
PeriodicGraphs.extended_gcd — Functionextended_gcd(s)::Tuple{BigInt, Vector{BigInt}}Given a list of integers, return a tuple (d, coefs) where d is the gcd of these integers and coefs is a list of integers such that dot(s, coefs) == d.
PeriodicGraphs.normal_basis — Functionnormal_basis(l::AbstractVector{<:StaticVector{N,T}}) where {N,T<:Integer}Given a list of integer vectors of dimension N, return a tuple (mat, D) where D is the dimension of the space spanned by the input vectors, and mat is an invertible matrix whose D first columns form a basis of this spanned space, which does not depend on the exact input.
If D ≠ N, the remaining columns are set so that mat be invertible. These additional columns will only contain one coefficient equal to 1, and all others to 0. No other assumption should be made about these columns; in particular, they may depend on the input.
If modifiable, the input list will be modified in-place during this process.
Unclassified other utilities
These other convenience functions may be useful for the manipulation of PeriodicGraphs:
PeriodicGraphs.find_edges — Functionfind_edges(g::PeriodicGraph, s::Int, d::Int)Return the set of PeriodicVertex v of graph g such that there is an edge between a source vertex of identifier s and v, and the identifier of v is d.
PeriodicGraphs.coordination_sequence — Functioncoordination_sequence(g::PeriodicGraph, v::Integer, dmax)Compute the list of numbers of n-th neighbors of vertex v in graph g, for 1 ≤ n ≤ dmax.