1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Clément Maria
*
* Copyright (C) 2014 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef DOC_PERSISTENT_COHOMOLOGY_INTRO_PERSISTENT_COHOMOLOGY_H_
#define DOC_PERSISTENT_COHOMOLOGY_INTRO_PERSISTENT_COHOMOLOGY_H_
// needs namespace for Doxygen to link on classes
namespace Gudhi {
// needs namespace for Doxygen to link on classes
namespace persistent_cohomology {
/** \defgroup persistent_cohomology Persistent Cohomology
\author Clément Maria
Computation of persistent cohomology using the algorithm of
\cite DBLP:journals/dcg/SilvaMV11 and \cite DBLP:conf/compgeom/DeyFW14
and the Compressed Annotation Matrix
implementation of \cite DBLP:conf/esa/BoissonnatDM13
The theory of homology consists in attaching to a topological space a sequence of
(homology) groups,
capturing global topological features
like connected components, holes, cavities, etc. Persistent homology studies the evolution
-- birth, life and death -- of
these features when the topological space is changing. Consequently, the theory is essentially
composed of three elements:
topological spaces, their homology groups and an evolution scheme.
\section persistencetopolocalspaces Topological Spaces
Topological spaces are represented by simplicial complexes.
Let \f$V = \{1, \cdots ,|V|\}\f$ be a set of <EM>vertices</EM>.
A <EM>simplex</EM> \f$\sigma\f$ is a subset of vertices
\f$\sigma \subseteq V\f$. A <EM>simplicial complex</EM> \f$\mathbf{K}\f$
on \f$V\f$ is a collection of simplices \f$\{\sigma\}\f$,
\f$\sigma \subseteq V\f$, such that \f$\tau \subseteq \sigma \in \mathbf{K}
\Rightarrow \tau \in \mathbf{K}\f$. The dimension \f$n=|\sigma|-1\f$ of \f$\sigma\f$
is its number of elements minus 1. A <EM>filtration</EM> of a simplicial complex is
a function \f$f:\mathbf{K} \rightarrow \mathbb{R}\f$ satisfying \f$f(\tau)\leq
f(\sigma)\f$ whenever \f$\tau \subseteq \sigma\f$.
We define the concept FilteredComplex which enumerates the requirements for a class
to represent a filtered complex from which persistent homology may be computed.
We use the vocabulary of simplicial complexes, but the concept
is valid for any type of cell complex. The main requirements
are the definition of:
\li type <CODE>Indexing_tag</CODE>, which is a model of the concept
<CODE>IndexingTag</CODE>,
describing the nature of the indexing scheme,
\li type Simplex_handle to manipulate simplices,
\li method <CODE>int dimension(Simplex_handle)</CODE> returning
the dimension of a simplex,
\li type and method <CODE>Boundary_simplex_range
boundary_simplex_range(Simplex_handle)</CODE> that returns
a range giving access to the codimension 1 subsimplices of the
input simplex, as-well-as the coefficients \f$(-1)^i\f$ in the
definition of the operator \f$\partial\f$. The iterators have
value type <CODE>Simplex_handle</CODE>,
\li type and method
<CODE>Filtration_simplex_range filtration_simplex_range ()</CODE>
that returns a range giving
access to all the simplices of the complex read in the order
assigned by the indexing scheme,
\li type and method
<CODE>Filtration_value filtration (Simplex_handle)</CODE> that returns the value of
the filtration on the simplex represented by the handle.
\section persistencehomology Homology
For a ring \f$\mathcal{R}\f$, the group of <EM>n-chains</EM>,
denoted \f$\mathbf{C}_n(\mathbf{K},\mathcal{R})\f$, of \f$\mathbf{K}\f$ is the
group of formal sums of
n-simplices with \f$\mathcal{R}\f$ coefficients. The <EM>boundary operator</EM> is a
linear operator
\f$\partial_n: \mathbf{C}_n(\mathbf{K},\mathcal{R}) \rightarrow \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R})\f$
such that \f$\partial_n \sigma = \partial_n [v_0, \cdots , v_n] =
\sum_{i=0}^n (-1)^{i}[v_0,\cdots ,\widehat{v_i}, \cdots,v_n]\f$,
where \f$\widehat{v_i}\f$ means \f$v_i\f$ is omitted from the list. The chain
groups form a sequence:
\f[\cdots \ \ \mathbf{C}_n(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_n\ } \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R})
\xrightarrow{\partial_{n-1}} \cdots \xrightarrow{\ \partial_2 \ }
\mathbf{C}_1(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_1 \ } \mathbf{C}_0(\mathbf{K},\mathcal{R}) \f]
of finitely many groups \f$\mathbf{C}_n(\mathbf{K},\mathcal{R})\f$ and homomorphisms
\f$\partial_n\f$, indexed by the dimension \f$n \geq 0\f$.
The boundary operators satisfy the property \f$\partial_n \circ \partial_{n+1}=0\f$
for every \f$n > 0\f$
and we define the homology groups:
\f[\mathbf{H}_n(\mathbf{K},\mathcal{R}) = \ker \partial_n / \mathrm{im} \ \partial_{n+1}\f]
We refer to \cite Munkres-elementsalgtop1984 for an introduction to homology
theory and to \cite DBLP:books/daglib/0025666 for an introduction to persistent homology.
\section persistenceindexingscheme Indexing Scheme
"Changing" a simplicial complex consists in applying a simplicial map.
An <EM>indexing scheme</EM> is a directed graph together with a traversal
order, such that two
consecutive nodes in the graph are connected by an arrow (either forward or backward).
The nodes represent simplicial complexes and the directed edges simplicial maps.
From the computational point of view, there are two types of indexing schemes of
interest
in persistent homology: <EM>linear</EM> ones
\f$\bullet \longrightarrow \bullet \longrightarrow \cdots \longrightarrow \bullet
\longrightarrow \bullet\f$
in persistent homology \cite DBLP:journals/dcg/ZomorodianC05 ,
and <EM>zigzag</EM> ones
\f$\bullet \longrightarrow \bullet \longleftarrow \cdots
\longrightarrow \bullet
\longleftarrow \bullet \f$ in zigzag persistent
homology \cite DBLP:journals/focm/CarlssonS10.
These indexing schemes have a natural left-to-right traversal order, and we
describe them with ranges and iterators.
In the current release of the Gudhi library, only the linear case is implemented.
In the following, we consider the case where the indexing scheme is induced
by a filtration.
Ordering the simplices
by increasing filtration values (breaking ties so as a simplex appears after
its subsimplices of same filtration value) provides an indexing scheme.
\section pcohexamples Examples
We provide several example files: run these examples with -h for details on their use, and read the README file.
\li <a href="_rips_complex_2rips_persistence_8cpp-example.html">
Rips_complex/rips_persistence.cpp</a> computes the Rips complex of a point cloud and outputs its persistence
diagram.
\code $> ./rips_persistence ../../data/points/tore3D_1307.off -r 0.25 -m 0.5 -d 3 -p 3 \endcode
\code The complex contains 177838 simplices
and has dimension 3
3 0 0 inf
3 1 0.0983494 inf
3 1 0.104347 inf
3 2 0.138335 inf \endcode
More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page.
\li <a href="_persistent_cohomology_2rips_multifield_persistence_8cpp-example.html">
Persistent_cohomology/rips_multifield_persistence.cpp</a> computes the Rips complex of a point cloud and outputs its
persistence diagram with a family of field coefficients.
\li <a href="_rips_complex_2rips_distance_matrix_persistence_8cpp-example.html">
Rips_complex/rips_distance_matrix_persistence.cpp</a> computes the Rips complex of a distance matrix and
outputs its persistence diagram.
The file should contain square or lower triangular distance matrix with semicolons as separators.
The code do not check if it is dealing with a distance matrix. It is the user responsibility to provide a valid input.
Please refer to data/distance_matrix/lower_triangular_distance_matrix.csv for an example of a file.
More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page.
\li <a href="_rips_complex_2rips_correlation_matrix_persistence_8cpp-example.html">
Rips_complex/rips_correlation_matrix_persistence.cpp</a>
computes the Rips complex of a correlation matrix and outputs its persistence diagram.
Note that no check is performed if the matrix given as the input is a correlation matrix.
It is the user responsibility to ensure that this is the case. The input is to be given either as a square or a lower
triangular matrix.
Please refer to data/correlation_matrix/lower_triangular_correlation_matrix.csv for an example of a file.
More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page.
\li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html">
Alpha_complex/alpha_complex_3d_persistence.cpp</a> computes the persistent homology with
\f$\mathbb{Z}/2\mathbb{Z}\f$ coefficients of the alpha complex on points sampling from an OFF file.
\code $> ./alpha_complex_3d_persistence ../../data/points/tore3D_300.off -p 2 -m 0.45 \endcode
\code Simplex_tree dim: 3
2 0 0 inf
2 1 0.0682162 1.0001
2 1 0.0934117 1.00003
2 2 0.56444 1.03938 \endcode
More details on the <a href="../../alphacomplex/">Alpha complex utilities</a> dedicated page.
CGAL can be forced to compute the exact values, it is slower, but it is necessary when points are on a grid
for instance (the fast version `--fast` would give incorrect values).
\code $> ./alpha_complex_3d_persistence ../../data/points/sphere3D_pts_on_grid.off --exact -p 2 -m 0.1 \endcode
\code Simplex_tree dim: 3
2 0 0 inf
2 2 0.0002 0.2028 \endcode
It can also compute the persistent homology with
\f$\mathbb{Z}/2\mathbb{Z}\f$ coefficients of the weighted alpha complex on points sampling from an OFF file
and a weights file.
\code $> ./alpha_complex_3d_persistence ../../data/points/tore3D_300.off
--weight-file ../../data/points/tore3D_300.weights -p 2 -m 0.45 \endcode
\code Simplex_tree dim: 3
2 0 -1 inf
2 1 -0.931784 0.000103311
2 1 -0.906588 2.60165e-05
2 2 -0.43556 0.0393798 \endcode
One can also compute the persistent homology with
\f$\mathbb{Z}/2\mathbb{Z}\f$ coefficients of the periodic alpha complex on points sampling from an OFF file.
The second parameter is a \ref FileFormatsIsoCuboid file with coordinates of the periodic cuboid.
Note that the lengths of the sides of the periodic cuboid have to be the same.
\code $> ./alpha_complex_3d_persistence ../../data/points/grid_10_10_10_in_0_1.off
--cuboid-file ../../data/points/iso_cuboid_3_in_0_1.txt -p 3 -m 1.0 \endcode
\code Simplex_tree dim: 3
3 0 0 inf
3 1 0.0025 inf
3 1 0.0025 inf
3 1 0.0025 inf
3 2 0.005 inf
3 2 0.005 inf
3 2 0.005 inf
3 3 0.0075 inf \endcode
In order to compute the persistent homology with
\f$\mathbb{Z}/2\mathbb{Z}\f$ coefficients of the periodic alpha complex on weighted points from an OFF file. The
additional parameters of this program are:<br>
(a) The file with the weights of points. The file consist of a sequence of numbers (as many as points).
Note that the weight of each single point have to be bounded by 1/64 times the square of the cuboid edge length.<br>
(b) A \ref FileFormatsIsoCuboid file with coordinates of the periodic cuboid.
Note that the lengths of the sides of the periodic cuboid have to be the same.<br>
\code $> ./alpha_complex_3d_persistence ../../data/points/shifted_sphere.off
--weight-file ../../data/points/shifted_sphere.weights
--cuboid-file ../../data/points/iso_cuboid_3_in_0_10.txt -p 3 -m 1.0 \endcode
\code Simplex_tree dim: 3
3 0 -0.0001 inf
3 1 16.0264 inf
3 1 16.0273 inf
3 1 16.0303 inf
3 2 36.8635 inf
3 2 36.8704 inf
3 2 36.8838 inf
3 3 58.6783 inf \endcode
\li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html">
Alpha_complex/alpha_complex_persistence.cpp</a> computes the persistent homology with
\f$\mathbb{Z}/p\mathbb{Z}\f$ coefficients of the alpha complex on points sampling from an OFF file.
\code $> ./alpha_complex_persistence -r 32 -p 2 -m 0.45 ../../data/points/tore3D_300.off \endcode
\code Alpha complex is of dimension 3 - 9273 simplices - 300 vertices.
Simplex_tree dim: 3
2 0 0 inf
2 1 0.0682162 1.0001
2 1 0.0934117 1.00003
2 2 0.56444 1.03938 \endcode
More details on the <a href="../../alphacomplex/">Alpha complex utilities</a> dedicated page.
\li <a href="_persistent_cohomology_2plain_homology_8cpp-example.html">
Persistent_cohomology/plain_homology.cpp</a> computes the plain homology of a simple simplicial complex without
filtration values.
*/
} // namespace persistent_cohomology
} // namespace Gudhi
#endif // DOC_PERSISTENT_COHOMOLOGY_INTRO_PERSISTENT_COHOMOLOGY_H_
|
