Interfaces

AbstractFiltration{I, T}

A filtration is used to find the edges in filtration and to create simplices. An AbstractFiltration{I, T}'s simplex type is expected to return simplices of type <:AbstractSimplex{_, T, I}.

Interface

• nv(::AbstractFiltration)
• edges(::AbstractFiltration)
• simplex_type(::Type{AbstractFiltration}, dim)
• simplex(::AbstractFiltration, ::Val{dim}, vertices, sign)
• unsafe_simplex(::AbstractFiltration, ::Val{dim}, vertices, sign)
• unsafe_cofacet(::AbstractFiltration, simplex, vertices, vertex, sign[, edges])
• birth(::AbstractFiltration, v)
• birth(::AbstractFiltration)
• threshold(::AbstractFiltration)
• columns_to_reduce(::AbstractFiltration, ::Any)
• emergent_pairs(::AbstractFiltration)
• postprocess_diagram(::AbstractFiltration, ::Any)

nv(::AbstractFiltration)

Return the number of vertices in filtration.

Example

julia> Ripserer.nv(Rips([1 1; 1 1]))
2

edges(::AbstractFiltration)

Get edges (1-simplices) in filtration. Edges should be of type simplex_type(filtration, 1).

Example

julia> Ripserer.edges(Rips([0 2 1; 2 0 1; 1 1 0], threshold=2))
3-element Array{Simplex{1,Int64,Int64},1}:
 +Simplex{1}([2, 1], 2)
 +Simplex{1}([3, 1], 1)
 +Simplex{1}([3, 2], 1)

birth(::AbstractFiltration, v)
birth(::AbstractFiltration)

Get the birth time of vertex v in filtration. Defaults to 0. When v is not given, return births in an array of same size as vertices(::AbstractFiltration).

Examples

julia> flt = Rips([1 1 2; 1 0 1; 2 1 0]);

julia> birth(flt, 1)
1

julia> birth(flt)
3-element Array{Int64,1}:
 1
 0
 0

threshold(::AbstractFiltration)

Get the threshold of filtration. This is the maximum diameter a simplex in the filtration can have. Defaults to Inf.

Examples

julia> threshold(Rips([0 2 1; 2 0 1; 1 1 0]))
1

julia> threshold(Cubical([1 1 2; 3 2 1; 0 0 0]))
3

simplex_type(::Type{<:AbstractFiltration}, D)
simplex_type(::AbstractFiltration, D)

Return the D-dimensional simplex type in the filtration. Only the method for the type needs to be overloaded.

Examples

julia> Ripserer.simplex_type(Rips{Int, Float64}, 1)
Simplex{1,Float64,Int64}

julia> Ripserer.simplex_type(Cubical{2, Float16}, 2)
Cube{2,Float16,2}

 simplex(::AbstractFiltration, ::Val{D}, vertices, sign=1)

Return D-simplex constructed from vertices with sign equal to sign. Return nothing if simplex is not in filtration. This function is safe to call with vertices that are out of order. Default implementation sorts vertices and calls unsafe_simplex.

Example

julia> simplex(Rips([0 2 1; 2 0 1; 1 1 0], threshold=2), Val(1), (1, 2), -1)
1-dimensional Simplex(index=1, birth=2):
  -[2, 1]

unsafe_simplex(::AbstractFiltration, ::Val{D}, vertices, sign=1)

Return D-simplex constructed from vertices with sign equal to sign. Return nothing if simplex is not in filtration. The unsafe in the name implies that it's up to the caller to ensure vertices are sorted and unique.

unsafe_cofacet(filtration, simplex, cofacet_vertices, v, sign[, edges])
unsafe_cofacet(::Type{S}, filtration, simplex, cofacet_vertices, v, sign[, edges])

Return cofacet of simplex with vertices equal to cofacet_vertices. v is the vertex that was added to construct the cofacet. In the case of sparse rips filtrations, an additional argument edges is used. edges is a vector that contains the weights on edges connecting the new vertex to old vertices. S is the simplex type which can be used for dispatch.

The unsafe in the name implies that it's up to the caller to ensure vertices are sorted and unique.

Default implementation uses unsafe_simplex.

columns_to_reduce(::AbstractFilration, prev_column_itr)

List all columns to reduce in next dimension, possibly computing it from previous columns. Default implementation uses coboundary with the all cofacets parameter set to Val(false).

Example

julia> flt = Rips([0 1 1; 1 0 1; 1 1 0]);

julia> Ripserer.columns_to_reduce(flt, Ripserer.edges(flt)) |> collect
1-element Array{Simplex{2,Int64,Int64},1}:
 +Simplex{2}([3, 2, 1], 1)

emergent_pairs(::AbstractFiltration)

Return true if the emergent pairs optimization is to be performed. Default to returning true. Should be set to false for a filtration type that is unable to produce (co)boundary simplices in the correct order.

postprocess_diagram(::AbstractFiltration, diagram)

This function is called on each resulting persistence diagram after all intervals have been computed. Defaults to sort!ing the diagram.

AbstractRipsFiltration{I<:Signed, T} <: AbstractFiltration{I, T}

An abstract Vietoris-Rips filtration. Its subtypes can only overload dist and get default implementations for the rest of the filtration interface.

Example

julia> struct MyRips <: Ripserer.AbstractRipsFiltration{Int, Float16} end

julia> Ripserer.dist(::MyRips) = [0 1 1; 1 0 1; 1 1 0]

julia> ripserer(MyRips())
2-element Array{PersistenceDiagrams.PersistenceDiagram,1}:
 3-element 0-dimensional PersistenceDiagram
 0-element 1-dimensional PersistenceDiagram

dist(::AbstractRipsFiltration, u, v)
dist(::AbstractRipsFiltration)

Return the distance between vertices u and v. If the distance is somehow invalid, it may return missing instead. If u and v are not given, return the distance matrix.

Examples

julia> flt = Rips([1 1 2; 1 0 1; 2 1 0]);

julia> Ripserer.dist(flt, 1, 3)
2

julia> Ripserer.dist(flt)
3×3 Array{Int64,2}:
 1  1  2
 1  0  1
 2  1  0

abstract type AbstractCustomFiltration{I, T} <: AbstractFiltration{I, T}

This abstract type is for filtrations that have all simplices stored in Dicts. The dicts should be accessible by the function simplex_dicts and should be a vector of Dict{I, T}. A custom filtration should also have adjacency_matrix defined. This matrix is only used as an adjacency matrix. Its values are ignored.

simplex_dicts(::AbstractCustomFiltration)

Get the dictionaries used to get simplex birth times. Should return a Vector of Dict{I, T} that maps a simplex index to its birth time. The first element of this Vector corresponds to vertices, second to 1-simplices etc.

adjacency_matrix(::AbstractFiltration)

Return the adjacency matrix. For sparse filtrations, this should return a SparseMatrixCSC.

Examples

julia> Ripserer.adjacency_matrix(Rips([0 2 1; 2 0 1; 1 1 0]))
3×3 Array{Int64,2}:
 0  2  1
 2  0  1
 1  1  0

julia> Ripserer.adjacency_matrix(SparseRips([0 0 1; 0 0 1; 1 1 0]))
3×3 SparseArrays.SparseMatrixCSC{Int64,Int64} with 4 stored entries:
  [3, 1]  =  1
  [3, 2]  =  1
  [1, 3]  =  1
  [2, 3]  =  1

julia> Ripserer.adjacency_matrix(Custom([(2, 1) => 1, (5, 1) => 2, (3, 4) => 3]))
5×5 SparseArrays.SparseMatrixCSC{Bool,Int64} with 6 stored entries:
  [2, 1]  =  1
  [5, 1]  =  1
  [1, 2]  =  1
  [4, 3]  =  1
  [3, 4]  =  1
  [1, 5]  =  1

AbstractSimplex{D, T, I} <: AbstractVector{I}

An abstract type for representing simplices. A simplex must have a diameter of type T, which is its birth time. The dimension must be encoded in the type as D and can be accessed by dim.

The simplex is expected to act like an array of indices of type I, but this is not actually needed for the main algorithm.

Interface

• AbstractSimplex{D}(::SVector{<:Any, <:Integer}, ::T)
• birth(::AbstractSimplex)
• index(::AbstractSimplex)
• sign(::AbstractSimplex)
• coboundary(::Any, ::AbstractSimplex)
• boundary(::Any, ::AbstractSimplex)
• vertices(::AbstractSimplex)
• Base.:-(::AbstractSimplex)

index(simplex::AbstractSimplex)

Get the combinatorial index of the simplex. The index can be any type, but should uniquely identify a simplex. It is also used to break ties when comparing simplices with the same birth time.

julia> index(Simplex{2}((3, 2, 1), 3.2))
1

sign(simplex::AbstractSimplex)

Get the orientation of simplex. Should return -1 or 1.

Examples

julia> sign(Simplex{2}((3, 2, 1), 3.2))
1

julia> sign(-Simplex{2}((3, 2, 1), 3.2))
-1

-(simplex::AbstractSimplex)

Reverse the simplex orientation.

Example

julia> -Simplex{2}((3, 2, 1), 3.2)
2-dimensional Simplex(index=1, birth=3.2):
  -[3, 2, 1]

coboundary(filtration, simplex[, Val{all_cofacets}])

Iterate over the coboundary of simplex by decreasing index. Use the filtration to determine the diameters and validity of cofacets.

If all_cofacets is false, only return cofaces with vertices added to the beginning of vertex list. The method with all_cofacets only has to be implemented if the filtration does not overload columns_to_reduce.

Comes with a default implementation.

Examples

filtration = Rips([0 1 1 1; 1 0 1 1; 1 1 0 1; 1 1 1 0])

for c in Ripserer.coboundary(filtration, Simplex{1}(2, 1))
    println(c)
end

# output

+Simplex{2}([4, 3, 1], 1)
-Simplex{2}([3, 2, 1], 1)

for c in Ripserer.coboundary(filtration, Simplex{1}(2, 1), Val(false))
    println(c)
end

# output

+Simplex{2}([4, 3, 1], 1)

boundary(filtration, simplex[, Val{all_cofacets}])

Iterate over the boundary of simplex by increasing index. Use the filtration to determine the diameters and validity of cofacets.

Comes with a default implementation.

Example

filtration = Rips([0 1 1 1; 1 0 1 1; 1 1 0 1; 1 1 1 0])

for f in Ripserer.boundary(filtration, Simplex{2}(2, 1))
    println(f)
end

# output

+Simplex{1}([2, 1], 1)
-Simplex{1}([4, 1], 1)
+Simplex{1}([4, 2], 1)