Debian Codegraph @

src/common/doc/main_page.md

raw
1 [TOC]
2
3 # The C++ library {#main_page}
4 \image html "Gudhi_banner.png"
5 <br><br><br><br>
6
7 ## Data structures for cell complexes {#Complexes}
8 ### Cubical complexes
9
10 <table>
11 <tr>
12 <td width="35%" rowspan=2>
13 \image html "Cubical_complex_representation.png"
14 </td>
15 <td width="50%">
16 The cubical complex is an example of a structured complex useful in computational mathematics (specially
17 rigorous numerics) and image analysis.<br>
18 </td>
19 <td width="15%">
20 <b>Author:</b> Pawel Dlotko<br>
21 <b>Introduced in:</b> GUDHI 1.3.0<br>
22 <b>License:</b> MIT<br>
23 </td>
24 </tr>
25 <tr>
26 <td colspan=2 height="25">
27 <b>User manual:</b> \ref cubical_complex
28 </td>
29 </tr>
30 </table>
31
32 ### Simplicial complexes
33
34 #### Simplex tree
35 <table>
36 <tr>
37 <td width="35%" rowspan=2>
38 \image html "Simplex_tree_representation.png"
39 </td>
40 <td width="50%">
41 The simplex tree is an efficient and flexible
42 data structure for representing general (filtered) simplicial complexes. The data structure
43 is described in \cite boissonnatmariasimplextreealgorithmica .
44 </td>
45 <td width="15%">
46 <b>Author:</b> Cl&eacute;ment Maria<br>
47 <b>Introduced in:</b> GUDHI 1.0.0<br>
48 <b>License:</b> MIT<br>
49 </td>
50 </tr>
51 <tr>
52 <td colspan=2 height="25">
53 <b>User manual:</b> \ref simplex_tree
54 </td>
55 </tr>
56 </table>
57
58 #### Toplex Map
59
60 <table>
61 <tr>
62 <td width="35%" rowspan=2>
63 \image html "map.png"
64 </td>
65 <td width="50%">
66 The Toplex map data structure is composed firstly of a raw storage of toplices (the maximal simplices)
67 and secondly of a map which associate any vertex to a set of pointers toward all toplices
68 containing this vertex.
69 </td>
70 <td width="15%">
71 <b>Author:</b> Fran&ccedil;ois Godi<br>
72 <b>Introduced in:</b> GUDHI 2.1.0<br>
73 <b>License:</b> MIT<br>
74 </td>
75 </tr>
76 <tr>
77 <td colspan=2 height="25">
78 <b>User manual:</b> \ref toplex_map
79 </td>
80 </tr>
81 </table>
82
83 #### Skeleton blocker
84
85 <table>
86 <tr>
87 <td width="35%" rowspan=2>
88 \image html "ds_representation.png"
89 </td>
90 <td width="50%">
91 The Skeleton-Blocker data-structure proposes a light encoding for simplicial complexes by storing only an *implicit*
92 representation of its simplices \cite socg_blockers_2011,\cite blockers2012. Intuitively, it just stores the
93 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that is very small in practice.
94 This data-structure handles all simplicial complexes operations such as simplex enumeration or simplex removal but
95 operations that are particularly efficient are operations that do not require simplex enumeration such as edge
96 iteration, link computation or simplex contraction.
97 </td>
98 <td width="15%">
99 <b>Author:</b> David Salinas<br>
100 <b>Introduced in:</b> GUDHI 1.1.0<br>
101 <b>License:</b> MIT<br>
102 </td>
103 </tr>
104 <tr>
105 <td colspan=2 height="25">
106 <b>User manual:</b> \ref skbl
107 </td>
108 </tr>
109 </table>
110
111 #### Basic operation: contraction
112
113 <table>
114 <tr>
115 <td width="35%" rowspan=2>
116 \image html "sphere_contraction_representation.png"
117 </td>
118 <td width="50%">
119 The purpose of this package is to offer a user-friendly interface for edge contraction simplification of huge
120 simplicial complexes. It uses the \ref skbl data-structure whose size remains small during simplification of most
121 used geometrical complexes of topological data analysis such as the Rips or the Delaunay complexes. In practice,
122 the size of this data-structure is even much lower than the total number of simplices.
123 </td>
124 <td width="15%">
125 <b>Author:</b> David Salinas<br>
126 <b>Introduced in:</b> GUDHI 1.1.0<br>
127 <b>License:</b> MIT [(LGPL v3)](../../licensing/)<br>
128 <b>Requires:</b> \ref cgal
129 </td>
130 </tr>
131 <tr>
132 <td colspan=2 height="25">
133 <b>User manual:</b> \ref contr
134 </td>
135 </tr>
136 </table>
137
138 ## Filtrations
139 ### Alpha complex and Delaunay
140
141 <table>
142 <tr>
143 <td width="35%" rowspan=2>
144 \image html "alpha_complex_representation.png"
145 </td>
146 <td width="50%">
147 The alpha-complex is a filtration of the finite cells of a Delaunay Triangulation which is topologically
148 equivalent to the Čech.
149 The filtration value of each simplex is computed as the squared radius of the smallest Delaunay ball
150 of this simplex.<br>
151 Also provided are the (unfiltered) Delaunay triangulation, and the *incremental* Delaunay triangulation.
152 </td>
153 <td width="15%">
154 <b>Authors:</b> Vincent Rouvreau, Michael Kerber, Marc Glisse<br>
155 <b>Introduced in:</b> GUDHI 1.3.0<br>
156 <b>License:</b> MIT [(GPL v3)](../../licensing/), GPL v3 (only for incremental Delaunay)<br>
157 <b>Requires:</b> \ref eigen and \ref cgal
158 </td>
159 </tr>
160 <tr>
161 <td colspan=2 height="25">
162 <b>User manual:</b> \ref alpha_complex
163 </td>
164 </tr>
165 </table>
166
167 ### Čech complex
168
169 <table>
170 <tr>
171 <td width="35%" rowspan=2>
172 \image html "cech_complex_representation.png"
173 </td>
174 <td width="50%">
175 The Čech complex is a filtered simplicial complex defined as the nerve of a union of balls.
176 The set of all simplices is filtered by the radius of their minimal enclosing ball.
177 </td>
178 <td width="15%">
179 <b>Author:</b> Vincent Rouvreau, Hind Montassif<br>
180 <b>Introduced in:</b> GUDHI 2.2.0<br>
181 <b>License:</b> MIT [(LGPL v3)](../../licensing/)<br>
182 <b>Requires:</b> \ref cgal
183 </td>
184 </tr>
185 <tr>
186 <td colspan=2 height="25">
187 <b>User manual:</b> \ref cech_complex
188 </td>
189 </tr>
190 </table>
191
192 ### Rips complex
193
194 <table>
195 <tr>
196 <td width="35%" rowspan=2>
197 \image html "rips_complex_representation.png"
198 </td>
199 <td width="50%">
200 The (Vietoris-)Rips complex is a filtered simplicial complex where every tuple of points appears with its diameter
201 as filtration value. Alternatively, it is defined by the cliques of a graph, usually representing a metric.<br>
202 This complex can be built from a point cloud and a distance function, or from a distance matrix.
203 </td>
204 <td width="15%">
205 <b>Author:</b> Cl&eacute;ment Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse<br>
206 <b>Introduced in:</b> GUDHI 2.0.0<br>
207 <b>License:</b> MIT<br>
208 </td>
209 </tr>
210 <tr>
211 <td colspan=2 height="25">
212 <b>User manual:</b> \ref rips_complex
213 </td>
214 </tr>
215 </table>
216
217 ### Edge collapse
218
219 <table>
220 <tr>
221 <td width="35%" rowspan=2>
222 \image html "dominated_edge.png"
223 </td>
224 <td width="50%">
225 Edge collapse is able to reduce any flag filtration to a smaller flag filtration with the same persistence, using
226 only the 1-skeletons of a simplicial complex.
227 The reduction is exact and the persistence homology of the reduced sequence is identical to the persistence
228 homology of the input sequence. The resulting method is simple and extremely efficient.
229
230 Computation of edge collapse and persistent homology of a filtered flag complex via edge collapse as described in
231 \cite edgecollapsearxiv.
232 </td>
233 <td width="15%">
234 <b>Author:</b> Siddharth Pritam, Marc Glisse<br>
235 <b>Introduced in:</b> GUDHI 3.3.0<br>
236 <b>License:</b> MIT
237 </td>
238 </tr>
239 <tr>
240 <td colspan=2 height="25">
241 <b>User manual:</b> \ref edge_collapse
242 </td>
243 </tr>
244 </table>
245
246 ### Witness complex
247
248 <table>
249 <tr>
250 <td width="35%" rowspan=2>
251 \image html "Witness_complex_representation.png"
252 </td>
253 <td width="50%">
254 Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$.
255 The data structure is described in \cite boissonnatmariasimplextreealgorithmica .
256 </td>
257 <td width="15%">
258 <b>Author:</b> Siargey Kachanovich<br>
259 <b>Introduced in:</b> GUDHI 1.3.0<br>
260 <b>License:</b> MIT ([GPL v3](../../licensing/) for Euclidean version)<br>
261 <b>Euclidean version requires:</b> \ref eigen and \ref cgal
262 </td>
263 </tr>
264 <tr>
265 <td colspan=2 height="25">
266 <b>User manual:</b> \ref witness_complex
267 </td>
268 </tr>
269 </table>
270
271 ### Cover Complexes
272 <table>
273 <tr>
274 <td width="35%" rowspan=2>
275 \image html "gicvisu.jpg"
276 </td>
277 <td width="50%">
278 Nerves and Graph Induced Complexes are cover complexes, i.e. simplicial complexes that provably contain
279 topological information about the input data. They can be computed with a cover of the
280 data, that comes i.e. from the preimage of a family of intervals covering the image
281 of a scalar-valued function defined on the data. <br>
282 </td>
283 <td width="15%">
284 <b>Author:</b> Mathieu Carri&egrave;re<br>
285 <b>Introduced in:</b> GUDHI 2.1.0<br>
286 <b>License:</b> MIT [(GPL v3)](../../licensing/)<br>
287 <b>Requires:</b> \ref cgal
288 </td>
289 </tr>
290 <tr>
291 <td colspan=2 height="25">
292 <b>User manual:</b> \ref cover_complex
293 </td>
294 </tr>
295 </table>
296
297 ## Manifold reconstructions
298 ### Coxeter triangulation
299
300 <table>
301 <tr>
302 <td width="35%" rowspan=2>
303 \image html "manifold_tracing_on_custom_function_example.png"
304 </td>
305 <td width="50%">
306 Coxeter triangulation module is designed to provide tools for constructing a piecewise-linear approximation of an
307 \f$m\f$-dimensional smooth manifold embedded in \f$ \mathbb{R}^d \f$ using an ambient triangulation.
308 </td>
309 <td width="15%">
310 <b>Author:</b> Siargey Kachanovich<br>
311 <b>Introduced in:</b> GUDHI 3.4.0<br>
312 <b>License:</b> MIT [(LGPL v3)](../../licensing/)<br>
313 <b>Requires:</b> \ref eigen
314 </td>
315 </tr>
316 <tr>
317 <td colspan=2 height="25">
318 <b>User manual:</b> \ref coxeter_triangulation
319 </td>
320 </tr>
321 </table>
322
323 ### Tangential complex
324
325 <table>
326 <tr>
327 <td width="35%" rowspan=2>
328 \image html "tc_examples.png"
329 </td>
330 <td width="50%">
331 A Tangential Delaunay complex is a <a target="_blank" href="https://en.wikipedia.org/wiki/Simplicial_complex">simplicial complex</a>
332 designed to reconstruct a \f$ k \f$-dimensional manifold embedded in \f$ d \f$-dimensional Euclidean space.
333 The input is a point sample coming from an unknown manifold.
334 The running time depends only linearly on the extrinsic dimension \f$ d \f$
335 and exponentially on the intrinsic dimension \f$ k \f$.
336 </td>
337 <td width="15%">
338 <b>Author:</b> Cl&eacute;ment Jamin<br>
339 <b>Introduced in:</b> GUDHI 2.0.0<br>
340 <b>License:</b> MIT [(GPL v3)](../../licensing/)<br>
341 <b>Requires:</b> \ref eigen and \ref cgal
342 </td>
343 </tr>
344 <tr>
345 <td colspan=2 height="25">
346 <b>User manual:</b> \ref tangential_complex
347 </td>
348 </tr>
349 </table>
350
351 ## Topological descriptors computation {#TopologicalDescriptorsComputation}
352
353 ### Persistent Cohomology
354
355 <table>
356 <tr>
357 <td width="35%" rowspan=2>
358 \image html "plain_homology.png"
359 </td>
360 <td width="50%">
361 The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing
362 global topological features like connected components, holes, cavities, etc. Persistent homology studies the
363 evolution -- birth, life and death -- of these features when the topological space is changing. Consequently, the
364 theory is essentially composed of three elements: topological spaces, their homology groups and an evolution
365 scheme.
366 Computation of persistent cohomology using the algorithm of \cite DBLP:journals/dcg/SilvaMV11 and
367 \cite DBLP:conf/compgeom/DeyFW14 and the Compressed Annotation Matrix implementation of
368 \cite DBLP:conf/esa/BoissonnatDM13 .
369 </td>
370 <td width="15%">
371 <b>Author:</b> Cl&eacute;ment Maria<br>
372 <b>Introduced in:</b> GUDHI 1.0.0<br>
373 <b>License:</b> MIT<br>
374 </td>
375 </tr>
376 <tr>
377 <td colspan=2 height="25">
378 <b>User manual:</b> \ref persistent_cohomology
379 </td>
380 </tr>
381 </table>
382
383 ### Persistence Matrix
384
385 <table>
386 <tr>
387 <td width="35%" rowspan=2>
388 \image html "persistence_matrix.png"
389 </td>
390 <td width="50%">
391 Matrix structure for filtered complexes with multiple functionnalities related to persistence homology,
392 such as representative cycles computation or vineyards.
393 <dl class="section note">
394 <dt>Note</dt>
395 <dd>Matrix API is in a beta version and may change in incompatible ways in the near future.</dd>
396 </dl>
397
398 </td>
399 <td width="15%">
400 <b>Author:</b> Hannah Schreiber<br>
401 <b>Introduced in:</b> GUDHI 3.10.0<br>
402 <b>Copyright:</b> MIT<br>
403 </td>
404 </tr>
405 <tr>
406 <td colspan=2 height="25">
407 <b>User manual:</b> \ref persistence_matrix and \ref persistence_fields
408 </td>
409 </tr>
410 </table>
411
412 ### Zigzag Persistent Homology
413
414 <table>
415 <tr>
416 <td width="35%" rowspan=2>
417 \image html "zigzag_ex.png"
418 </td>
419 <td width="50%">
420 Zigzag filtrations are a generalization of (standard) filtrations: the inclusion maps can not only go forward,
421 but also backward. In other words, simplices can also be removed from the complex which is build.
422 The implemented algorithm is from \cite zigzag.
423 </td>
424 <td width="15%">
425 <b>Author:</b> Cl&eacute;ment Maria, Hannah Schreiber<br>
426 <b>Introduced in:</b> GUDHI 3.11.0<br>
427 <b>Copyright:</b> MIT<br>
428 </td>
429 </tr>
430 <tr>
431 <td colspan=2 height="25">
432 <b>User manual:</b> \ref zigzag_persistence
433 </td>
434 </tr>
435 </table>
436
437 ## Topological descriptors tools {#TopologicalDescriptorsTools}
438
439 ### Bottleneck distance
440
441 <table>
442 <tr>
443 <td width="35%" rowspan=2>
444 \image html "perturb_pd.png"
445 </td>
446 <td width="50%">
447 Bottleneck distance measures the similarity between two persistence diagrams.
448 It's the shortest distance b for which there exists a perfect matching between
449 the points of the two diagrams (+ all the diagonal points) such that
450 any couple of matched points are at distance at most b,
451 where the distance between points is the sup norm in \f$\mathbb{R}^2\f$
452 (not the Euclidean distance).
453 </td>
454 <td width="15%">
455 <b>Author:</b> Fran&ccedil;ois Godi<br>
456 <b>Introduced in:</b> GUDHI 2.0.0<br>
457 <b>License:</b> MIT [(GPL v3)](../../licensing/)<br>
458 <b>Requires:</b> \ref cgal
459 </td>
460 </tr>
461 <tr>
462 <td colspan=2 height="25">
463 <b>User manual:</b> \ref bottleneck_distance
464 </td>
465 </tr>
466 </table>
467
468 ### Persistence representations
469
470 <table>
471 <tr>
472 <td width="35%" rowspan=2>
473 \image html "average_landscape.png"
474 </td>
475 <td width="50%">
476 It contains implementation of various representations of persistence diagrams; diagrams themselves, persistence
477 landscapes (rigorous and grid version), persistence heat maps, vectors and others. It implements basic
478 functionalities which are necessary to use persistence in statistics and machine learning.
479 </td>
480 <td width="15%">
481 <b>Author:</b> Pawel Dlotko<br>
482 <b>Introduced in:</b> GUDHI 2.1.0<br>
483 <b>License:</b> MIT<br>
484 </td>
485 </tr>
486 <tr>
487 <td colspan=2 height="25">
488 <b>User manual:</b> \ref Persistence_representations
489 </td>
490 </tr>
491 </table>
492
493 ## Point cloud utilities {#PointCloudUtils}
494
495 <table>
496 <tr>
497 <td width="35%" rowspan=2>
498 \f$(x_1,\ldots,x_d)\f$
499 </td>
500 <td width="50%">
501 This contains various tools to handle point clouds: spatial searching, subsampling, etc.
502 </td>
503 <td width="15%">
504 <b>Author:</b>Clément Jamin, Siargey Kachanovich, Marc Glisse<br>
505 <b>Introduced in:</b> GUDHI 1.3.0<br>
506 <b>License:</b> MIT [(GPL v3)](../../licensing/)<br>
507 </td>
508 </tr>
509 <tr>
510 <td colspan=2 height="25">
511 <b>Manuals:</b> \ref spatial_searching, \ref subsampling
512 </td>
513 </tr>
514 </table>