8545078607

Committed 03 Apr 2024 08:26PM UTC coverage: 96.51% (+0.09%) from 96.417%

Build # 8545078607

Build Type

Pull #166

github

Committed by

web-flow

Commit Message

Merge ed46e50d4 into 3f2d63fae

Pull Request Pull Request #166: Better homology

Run Details

245 of 250 new or added lines in 5 files covered. (98.0%)

3 existing lines in 3 files now uncovered.

1770 of 1834 relevant lines covered (96.51%)

3302629.22 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.41

/src/computation/homology.jl

"""
Write a blurb here.
"""
struct Homology
    implicit::Bool

    Homology(; implicit=true) = new(implicit)
end

"""
    BoundaryMatrix{I}

This `struct` is used to compute homology. The `I` parameter sets whether the implicit
algoritm is used or not.
"""
struct BoundaryMatrix{
    I,T<:Number,F,S1<:AbstractCell,S2<:AbstractCell,R<:ReducedMatrix,B<:Chain{T},C<:Chain{T}
}
    filtration::F
    reduced::R
    buffer::B
    chain::C
    birth_candidates::Vector{S1} # used to find infinite intervals
    columns_to_reduce::Vector{S2}
    zeroed::Set{S2}
    infinite_intervals::Bool
end

function BoundaryMatrix{I}(
    ::Type{T}, filtration, birth_candidates, columns_to_reduce; infinite_intervals=true
) where {I,T}
    S2 = eltype(columns_to_reduce)
    S1 = simplex_type(filtration, dim(S2) - 1)

    if !I
        reduced = ReducedMatrix{S1,T,S1}()
        buffer = Chain{T,S1}()
    else
        reduced = ReducedMatrix{S1,T,S2}()
        buffer = Chain{T,S2}()
    end
    sizehint!(reduced, length(columns_to_reduce))
    chain = Chain{T,S1}()

    return BoundaryMatrix{
        I,T,typeof(filtration),S1,S2,typeof(reduced),typeof(buffer),typeof(chain)
    }(
        filtration,
        reduced,
        buffer,
        chain,
        birth_candidates,
        columns_to_reduce,
        Set{S1}(),
        infinite_intervals,
    )
end

field_type(::BoundaryMatrix{<:Any,T}) where {T} = T
dim(::BoundaryMatrix{<:Any,<:Any,<:Any,S}) where {S} = dim(S)
ordering(::BoundaryMatrix) = Base.Order.Reverse

is_implicit(::BoundaryMatrix{I}) where {I} = I
is_cohomology(::BoundaryMatrix) = false

function attempt_early_stop!(matrix::BoundaryMatrix, i, columns)
    if length(matrix.reduced.column_index) ≥ length(matrix.birth_candidates)
        # At this point, all potential births have been found. The rest of the columns
        # should be marked as zeroed.
        for j in i:length(columns)
            push!(matrix.zeroed, columns[j])
        end
        return true
    else
        return false
    end
end

# The naming here is not ideal...
function coboundary(matrix::BoundaryMatrix, simplex::AbstractCell)
    return boundary(matrix.filtration, simplex)
end

function mark_zero_column!(matrix::BoundaryMatrix, column_index)
    if matrix.infinite_intervals
        push!(matrix.zeroed, column_index)
    end
    return nothing
end

function append_infinite_intervals!(intervals, matrix::BoundaryMatrix)
    if matrix.infinite_intervals && length(matrix.birth_candidates) ≠ length(intervals)
        for simplex in matrix.birth_candidates
            if !haskey(matrix.reduced, simplex)
                push!(
                    intervals,
                    PersistenceInterval(
                        birth(simplex),
                        Inf,
                        (; birth_simplex=simplex, death_simplex=nothing),
                    ),
                )
            end
        end
    end
    return intervals
end

function next_matrix(matrix::BoundaryMatrix{I}) where {I}
    birth_candidates = filter(matrix.columns_to_reduce) do sx
        sx in matrix.zeroed
    end
    columns = simplex_type(matrix.filtration, dim(matrix) + 2)[]
    for col in columns_to_reduce(matrix.filtration, matrix.columns_to_reduce)
        push!(columns, abs(col))
    end

    return BoundaryMatrix{I}(
        field_type(matrix), matrix.filtration, birth_candidates, columns
    )
end

function _ripserer(
    ::Val{:homology}, filtration, cutoff, verbose, field, dim_max, reps, implicit
)
    result = PersistenceDiagram[]
    zeroth, to_reduce, to_skip = zeroth_intervals(
        filtration, cutoff, verbose, field, _reps(reps, 0)
    )
    push!(result, zeroth)
    if dim_max > 0
        birth_candidates = to_reduce
        columns = simplex_type(filtration, 2)[]
        for col in columns_to_reduce(filtration, Iterators.flatten((to_reduce, to_skip)))
            push!(columns, abs(col))
        end
        matrix = BoundaryMatrix{implicit}(field, filtration, birth_candidates, columns)
        for dim in 1:dim_max
            push!(result, compute_intervals!(matrix, cutoff, verbose, _reps(reps, dim)))

            if dim < dim_max
                matrix = next_matrix(matrix)
            end
        end
    end
    return result
end

1	"""
2	Write a blurb here.
3	"""
4	struct Homology
5	implicit::Bool
6
NEW 7	Homology(; implicit=true) = new(implicit)	×
8	end
9
10	"""
11	BoundaryMatrix{I}
12
13	This `struct` is used to compute homology. The `I` parameter sets whether the implicit
14	algoritm is used or not.
15	"""
16	struct BoundaryMatrix{
17	I,T<:Number,F,S1<:AbstractCell,S2<:AbstractCell,R<:ReducedMatrix,B<:Chain{T},C<:Chain{T}
18	}
19	filtration::F	40✔
20	reduced::R
21	buffer::B
22	chain::C
23	birth_candidates::Vector{S1} # used to find infinite intervals
24	columns_to_reduce::Vector{S2}
25	zeroed::Set{S2}
26	infinite_intervals::Bool
27	end
28
29	function BoundaryMatrix{I}(	80✔
30	::Type{T}, filtration, birth_candidates, columns_to_reduce; infinite_intervals=true
31	) where {I,T}
32	S2 = eltype(columns_to_reduce)	40✔
33	S1 = simplex_type(filtration, dim(S2) - 1)	40✔
34
35	if !I	40✔
36	reduced = ReducedMatrix{S1,T,S1}()	17✔
37	buffer = Chain{T,S1}()	17✔
38	else
39	reduced = ReducedMatrix{S1,T,S2}()	23✔
40	buffer = Chain{T,S2}()	23✔
41	end
42	sizehint!(reduced, length(columns_to_reduce))	40✔
43	chain = Chain{T,S1}()	40✔
44
45	return BoundaryMatrix{	40✔
46	I,T,typeof(filtration),S1,S2,typeof(reduced),typeof(buffer),typeof(chain)
47	}(
48	filtration,
49	reduced,
50	buffer,
51	chain,
52	birth_candidates,
53	columns_to_reduce,
54	Set{S1}(),
55	infinite_intervals,
56	)
57	end
58
59	field_type(::BoundaryMatrix{<:Any,T}) where {T} = T	4,158✔
60	dim(::BoundaryMatrix{<:Any,<:Any,<:Any,S}) where {S} = dim(S)	50✔
61	ordering(::BoundaryMatrix) = Base.Order.Reverse	585,064✔
62
63	is_implicit(::BoundaryMatrix{I}) where {I} = I	149,276✔
64	is_cohomology(::BoundaryMatrix) = false	18,797✔
65
66	function attempt_early_stop!(matrix::BoundaryMatrix, i, columns)	18,285✔
67	if length(matrix.reduced.column_index) ≥ length(matrix.birth_candidates)	18,285✔
68	# At this point, all potential births have been found. The rest of the columns
69	# should be marked as zeroed.
70	for j in i:length(columns)	17✔
71	push!(matrix.zeroed, columns[j])	7,096✔
72	end	14,175✔
73	return true	17✔
74	else
75	return false	18,268✔
76	end
77	end
78
79	# The naming here is not ideal...
80	function coboundary(matrix::BoundaryMatrix, simplex::AbstractCell)	49,027✔
81	return boundary(matrix.filtration, simplex)	49,027✔
82	end
83
84	function mark_zero_column!(matrix::BoundaryMatrix, column_index)	9,315✔
85	if matrix.infinite_intervals	9,315✔
86	push!(matrix.zeroed, column_index)	9,315✔
87	end
88	return nothing	9,315✔
89	end
90
91	function append_infinite_intervals!(intervals, matrix::BoundaryMatrix)	40✔
92	if matrix.infinite_intervals && length(matrix.birth_candidates) ≠ length(intervals)	40✔
93	for simplex in matrix.birth_candidates	27✔
94	if !haskey(matrix.reduced, simplex)	5,743✔
95	push!(	4✔
96	intervals,
97	PersistenceInterval(
98	birth(simplex),
99	Inf,
100	(; birth_simplex=simplex, death_simplex=nothing),
101	),
102	)
103	end
104	end	5,743✔
105	end
106	return intervals	40✔
107	end
108
109	function next_matrix(matrix::BoundaryMatrix{I}) where {I}	10✔
110	birth_candidates = filter(matrix.columns_to_reduce) do sx	10✔
111	sx in matrix.zeroed	6,020✔
112	end
113	columns = simplex_type(matrix.filtration, dim(matrix) + 2)[]	10✔
114	for col in columns_to_reduce(matrix.filtration, matrix.columns_to_reduce)	15✔
115	push!(columns, abs(col))	27,058✔
116	end	22,298✔
117
118	return BoundaryMatrix{I}(	10✔
119	field_type(matrix), matrix.filtration, birth_candidates, columns
120	)
121	end
122
123	function _ripserer(	18✔
124	::Val{:homology}, filtration, cutoff, verbose, field, dim_max, reps, implicit
125	)
126	result = PersistenceDiagram[]	18✔
127	zeroth, to_reduce, to_skip = zeroth_intervals(	18✔
128	filtration, cutoff, verbose, field, _reps(reps, 0)
129	)
130	push!(result, zeroth)	18✔
131	if dim_max > 0	18✔
132	birth_candidates = to_reduce	18✔
133	columns = simplex_type(filtration, 2)[]	18✔
134	for col in columns_to_reduce(filtration, Iterators.flatten((to_reduce, to_skip)))	30✔
135	push!(columns, abs(col))	4,272✔
136	end	5,054✔
137	matrix = BoundaryMatrix{implicit}(field, filtration, birth_candidates, columns)	18✔
138	for dim in 1:dim_max	18✔
139	push!(result, compute_intervals!(matrix, cutoff, verbose, _reps(reps, dim)))	28✔
140
141	if dim < dim_max	28✔
142	matrix = next_matrix(matrix)	10✔
143	end
144	end	38✔
145	end
146	return result	18✔
147	end

mtsch / Ripserer.jl / 8545078607

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous