diff options
-rwxr-xr-x | GudhUI/utils/homsimpl | bin | 118624 -> 0 bytes | |||
-rw-r--r-- | debian/changelog | 5 | ||||
-rw-r--r-- | debian/compat | 1 | ||||
-rw-r--r-- | debian/control | 26 | ||||
-rw-r--r-- | debian/copyright | 28 | ||||
-rw-r--r-- | debian/docs | 2 | ||||
-rwxr-xr-x | debian/rules | 28 | ||||
-rw-r--r-- | debian/source/format | 1 | ||||
-rw-r--r-- | doc/common/main_page.h~ | 341 | ||||
-rw-r--r-- | include/gudhi/Alpha_complex.h~ | 417 |
10 files changed, 0 insertions, 849 deletions
diff --git a/GudhUI/utils/homsimpl b/GudhUI/utils/homsimpl Binary files differdeleted file mode 100755 index 12227502..00000000 --- a/GudhUI/utils/homsimpl +++ /dev/null diff --git a/debian/changelog b/debian/changelog deleted file mode 100644 index 32b3f6f9..00000000 --- a/debian/changelog +++ /dev/null @@ -1,5 +0,0 @@ -gudhi (1.3.0-1) unstable; urgency=low - - * Initial release. - - -- Marc Glisse <marc.glisse@inria.fr> Sat, 26 Mar 2016 10:51:01 +0100 diff --git a/debian/compat b/debian/compat deleted file mode 100644 index ec635144..00000000 --- a/debian/compat +++ /dev/null @@ -1 +0,0 @@ -9 diff --git a/debian/control b/debian/control deleted file mode 100644 index 838234a9..00000000 --- a/debian/control +++ /dev/null @@ -1,26 +0,0 @@ -Source: gudhi -Priority: optional -Maintainer: Marc Glisse <marc.glisse@normalesup.org> -Build-Depends: debhelper (>= 9), cmake, libboost-dev -Standards-Version: 3.9.6 -Section: libs -Homepage: http://gudhi.gforge.inria.fr/ -#Vcs-Git: git://anonscm.debian.org/collab-maint/gudhi.git -#Vcs-Browser: https://anonscm.debian.org/gitweb/?p=collab-maint/gudhi.git;a=summary - -Package: libgudhi-dev -Section: libdevel -Architecture: all -Depends: libboost-dev, ${misc:Depends} -Recommends: libcgal-dev -Description: Gudhi library for topological data analysis - The Gudhi library (Geometric Understanding in Higher Dimensions) is a generic - open source C++ library for Computational Topology and Topological Data - Analysis (TDA). - . - The current release of the GUDHI library includes: - * Data structures to represent, construct and manipulate simplicial and - cubical complexes, including alpha-complex, witness complex, Rips complex. - * Algorithms to compute persistent homology and multi-field persistent - homology. - * Simplication of simplicial complexes by edge contraction. diff --git a/debian/copyright b/debian/copyright deleted file mode 100644 index 2e1f88cd..00000000 --- a/debian/copyright +++ /dev/null @@ -1,28 +0,0 @@ -Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ -Upstream-Name: gudhi -Upstream-Contact: gudhi-users@lists.gforge.inria.fr -Source: <url://http://gudhi.gforge.inria.fr/> - -Files: * -Copyright: 2014-2016 Inria Sophia Antipolis-Méditerranée - 2014-2016 Inria Saclay - Ile de France - 2014-2016 Université Nice Sophia Antipolis -License: GPL-3.0+ - -License: GPL-3.0+ - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - . - This package is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - . - You should have received a copy of the GNU General Public License - along with this program. If not, see <https://www.gnu.org/licenses/>. - . - On Debian systems, the complete text of the GNU General - Public License version 3 can be found in "/usr/share/common-licenses/GPL-3". - diff --git a/debian/docs b/debian/docs deleted file mode 100644 index 878a2ba1..00000000 --- a/debian/docs +++ /dev/null @@ -1,2 +0,0 @@ -Conventions.txt -README diff --git a/debian/rules b/debian/rules deleted file mode 100755 index c9b049af..00000000 --- a/debian/rules +++ /dev/null @@ -1,28 +0,0 @@ -#!/usr/bin/make -f -# See debhelper(7) (uncomment to enable) -# output every command that modifies files on the build system. -#export DH_VERBOSE = 1 - -# see EXAMPLES in dpkg-buildflags(1) and read /usr/share/dpkg/* -DPKG_EXPORT_BUILDFLAGS = 1 -include /usr/share/dpkg/default.mk - -# see FEATURE AREAS in dpkg-buildflags(1) -#export DEB_BUILD_MAINT_OPTIONS = hardening=+all - -# see ENVIRONMENT in dpkg-buildflags(1) -# package maintainers to append CFLAGS -#export DEB_CFLAGS_MAINT_APPEND = -Wall -pedantic -# package maintainers to append LDFLAGS -#export DEB_LDFLAGS_MAINT_APPEND = -Wl,--as-needed - - -# main packaging script based on dh7 syntax -%: - dh $@ - -# dh_make generated override targets -# This is example for Cmake (See https://bugs.debian.org/641051 ) -#override_dh_auto_configure: -# dh_auto_configure -- \ -# -DCMAKE_LIBRARY_PATH=$(DEB_HOST_MULTIARCH) diff --git a/debian/source/format b/debian/source/format deleted file mode 100644 index 163aaf8d..00000000 --- a/debian/source/format +++ /dev/null @@ -1 +0,0 @@ -3.0 (quilt) diff --git a/doc/common/main_page.h~ b/doc/common/main_page.h~ deleted file mode 100644 index abe7398b..00000000 --- a/doc/common/main_page.h~ +++ /dev/null @@ -1,341 +0,0 @@ -/*! \mainpage - * \tableofcontents - * \image html "Gudhi_banner.png" "" width=20cm - * - * \section Introduction Introduction - * The Gudhi library (Geometry Understanding in Higher Dimensions) is a generic open source C++ library for - * Computational Topology and Topological Data Analysis - * (<a class="el" target="_blank" href="https://en.wikipedia.org/wiki/Topological_data_analysis">TDA</a>). - * The GUDHI library intends to help the development of new algorithmic solutions in TDA and their transfer to - * applications. It provides robust, efficient, flexible and easy to use implementations of state-of-the-art - * algorithms and data structures. - * - * The current release of the GUDHI library includes: - * - * \li Data structures to represent, construct and manipulate simplicial complexes. - * \li Algorithms to compute persistent homology and multi-field persistent homology. - * \li Simplication of simplicial complexes by edge contraction. - * - * All data-structures are generic and several of their aspects can be parameterized via template classes. - * We refer to \cite gudhilibrary_ICMS14 for a detailed description of the design of the library. - * - \section DataStructures Data structures - \subsection AlphaComplexDataStructure Alpha complex - \image html "alpha_complex_representation.png" "Alpha complex representation" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> Vincent Rouvreau<br> - <b>Introduced in:</b> GUDHI 1.3.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - Alpha_complex is a simplicial complex constructed from the finite cells of a Delaunay Triangulation.<br> - The filtration value of each simplex is computed as the square of the circumradius of the simplex if the - circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration - values of the codimension 1 cofaces that make it not Gabriel otherwise. - All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into - the complex.<br> - <b>User manual:</b> \ref alpha_complex - <b>Reference manual:</b> Gudhi::alphacomplex::Alpha_complex - </td> - </tr> -</table> - \subsection CubicalComplexDataStructure Cubical complex - \image html "Cubical_complex_representation.png" "Cubical complex representation" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> Pawel Dlotko<br> - <b>Introduced in:</b> GUDHI 1.3.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - The cubical complex is an example of a structured complex useful in computational mathematics (specially - rigorous numerics) and image analysis.<br> - <b>User manual:</b> \ref cubical_complex - <b>Reference manual:</b> Gudhi::Cubical_complex::Bitmap_cubical_complex - </td> - </tr> -</table> - \subsection SimplexTreeDataStructure Simplex tree - \image html "Simplex_tree_representation.png" "Simplex tree representation" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> Clément Maria<br> - <b>Introduced in:</b> GUDHI 1.0.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - The simplex tree is an efficient and flexible - data structure for representing general (filtered) simplicial complexes. The data structure - is described in \cite boissonnatmariasimplextreealgorithmica .<br> - <b>User manual:</b> \ref simplex_tree - <b>Reference manual:</b> Gudhi::Simplex_tree - </td> - </tr> -</table> - \subsection SkeletonBlockerDataStructure Skeleton blocker - \image html "ds_representation.png" "Skeleton blocker representation" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> David Salinas<br> - <b>Introduced in:</b> GUDHI 1.1.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - The Skeleton-Blocker data-structure proposes a light encoding for simplicial complexes by storing only an *implicit* - representation of its simplices \cite socg_blockers_2011,\cite blockers2012. Intuitively, it just stores the - 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that is very small in practice. - This data-structure handles all simplicial complexes operations such as simplex enumeration or simplex removal but - operations that are particularly efficient are operations that do not require simplex enumeration such as edge - iteration, link computation or simplex contraction.<br> - <b>User manual:</b> \ref skbl - <b>Reference manual:</b> Gudhi::skbl::Skeleton_blocker_complex - </td> - </tr> -</table> - \subsection WitnessComplexDataStructure Witness complex - \image html "Witness_complex_representation.png" "Witness complex representation" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> Siargey Kachanovich<br> - <b>Introduced in:</b> GUDHI 1.3.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$. - The data structure is described in \cite boissonnatmariasimplextreealgorithmica .<br> - <b>User manual:</b> \ref witness_complex - <b>Reference manual:</b> Gudhi::witness_complex::SimplicialComplexForWitness - </td> - </tr> -</table> - - \section Toolbox Toolbox - \subsection ContractionToolbox Contraction - \image html "sphere_contraction_representation.png" "Sphere contraction example" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> David Salinas<br> - <b>Introduced in:</b> GUDHI 1.1.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - The purpose of this package is to offer a user-friendly interface for edge contraction simplification of huge - simplicial complexes. It uses the \ref skbl data-structure whose size remains small during simplification of most - used geometrical complexes of topological data analysis such as the Rips or the Delaunay complexes. In practice, - the size of this data-structure is even much lower than the total number of simplices.<br> - <b>User manual:</b> \ref contr - </td> - </tr> -</table> - \subsection PersistentCohomologyToolbox Persistent Cohomology - \image html "3DTorus_poch.png" "Rips Persistent Cohomology on a 3D Torus" -<table border="0"> - <tr> - <td width="25%"> - <b>Author:</b> Clément Maria<br> - <b>Introduced in:</b> GUDHI 1.0.0<br> - <b>Copyright:</b> GPL v3<br> - </td> - <td width="75%"> - 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. - Computation of persistent cohomology using the algorithm of \cite DBLP:journals/dcg/SilvaMV11 and - \cite DBLP:journals/corr/abs-1208-5018 and the Compressed Annotation Matrix implementation of - \cite DBLP:conf/esa/BoissonnatDM13 .<br> - <b>User manual:</b> \ref persistent_cohomology - <b>Reference manual:</b> Gudhi::persistent_cohomology::Persistent_cohomology - </td> - </tr> -</table> -*/ - -/*! \page installation Gudhi installation - * As Gudhi is a header only library, there is no need to install the library. - * - * Examples of Gudhi headers inclusion can be found in \ref demos. - * - * \section compiling Compiling - * The library uses c++11 and requires <a target="_blank" href="http://www.boost.org/">Boost</a> with version 1.48.0 or - * more recent. It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2015. - * - * \subsection gmp GMP: - * The multi-field persistent homology algorithm requires GMP which is a free library for arbitrary-precision - * arithmetic, operating on signed integers, rational numbers, and floating point numbers. - * - * The following example requires the <a target="_blank" href="http://gmplib.org/">GNU Multiple Precision Arithmetic - * Library</a> (GMP) and will not be built if GMP is not installed: - * \li <a href="_persistent_cohomology_2performance_rips_persistence_8cpp-example.html"> - * Persistent_cohomology/performance_rips_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2rips_multifield_persistence_8cpp-example.html"> - * Persistent_cohomology/rips_multifield_persistence.cpp</a> - * - * Having GMP version 4.2 or higher installed is recommended. - * - * \subsection cgal CGAL: - * CGAL is a C++ library which provides easy access to efficient and reliable geometric algorithms. - * - * Having CGAL version 4.4 or higher installed is recommended. The procedure to install this library according to - * your operating system is detailed here http://doc.cgal.org/latest/Manual/installation.html - * - * The following examples require the <a target="_blank" href="http://www.cgal.org/">Computational Geometry Algorithms - * Library</a> (CGAL \cite cgal:eb-15b) and will not be built if CGAL is not installed: - * \li <a href="_persistent_cohomology_2alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_3d_persistence.cpp</a> - * \li <a href="_simplex_tree_2simplex_tree_from_alpha_shapes_3_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp</a> - * \li <a href="_alpha_complex_2_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_2_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * - * The following example requires CGAL version ≥ 4.6: - * \li <a href="_witness_complex_2witness_complex_sphere_8cpp-example.html"> - * Witness_complex/witness_complex_sphere.cpp</a> - * - * The following example requires CGAL version ≥ 4.7: - * \li <a href="_alpha_complex_2_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_2_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * \li <a href="_persistent_cohomology_2alpha_complex_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * - * \subsection eigen3 Eigen3: - * <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen3</a> is a C++ template library for linear algebra: - * matrices, vectors, numerical solvers, and related algorithms. - * - * The following example requires the <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen3</a> and will not be - * built if Eigen3 is not installed: - * \li <a href="_alpha_complex_2_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> (requires also Eigen3) - * \li <a href="_alpha_complex_2_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> (requires also Eigen3) - * \li <a href="_persistent_cohomology_2alpha_complex_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * - * \subsection tbb Threading Building Blocks: - * <a target="_blank" href="https://www.threadingbuildingblocks.org/">Intel® TBB</a> lets you easily write parallel - * C++ programs that take full advantage of multicore performance, that are portable and composable, and that have - * future-proof scalability. - * - * Having Intel® TBB installed is recommended to parallelize and accelerate some GUDHI computations. - * - * The following examples are using Intel® TBB if installed: - * \li <a href="_alpha_complex_2_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_2_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_8cpp-example.html"> - * Bitmap_cubical_complex/Bitmap_cubical_complex.cpp</a> - * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_periodic_boundary_conditions_8cpp-example.html"> - * Bitmap_cubical_complex/Bitmap_cubical_complex_periodic_boundary_conditions.cpp</a> - * \li <a href="_bitmap_cubical_complex_2_random_bitmap_cubical_complex_8cpp-example.html"> - * Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp</a> - * \li <a href="_persistent_cohomology_2alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_3d_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2alpha_complex_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_persistence.cpp</a> - * \li <a href="_simplex_tree_2simple_simplex_tree_8cpp-example.html"> - * Simplex_tree/simple_simplex_tree.cpp</a> - * \li <a href="_simplex_tree_2simplex_tree_from_alpha_shapes_3_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp</a> - * \li <a href="_simplex_tree_2simplex_tree_from_cliques_of_graph_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_cliques_of_graph.cpp</a> - * \li <a href="_persistent_cohomology_2alpha_shapes_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_shapes_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2rips_persistence_via_boundary_matrix_8cpp-example.html"> - * Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp</a> - * \li <a href="_persistent_cohomology_2performance_rips_persistence_8cpp-example.html"> - * Persistent_cohomology/performance_rips_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2persistence_from_file_8cpp-example.html"> - * Persistent_cohomology/persistence_from_file.cpp</a> - * \li <a href="_persistent_cohomology_2persistence_from_simple_simplex_tree_8cpp-example.html"> - * Persistent_cohomology/persistence_from_simple_simplex_tree.cpp</a> - * \li <a href="_persistent_cohomology_2plain_homology_8cpp-example.html"> - * Persistent_cohomology/plain_homology.cpp</a> - * \li <a href="_persistent_cohomology_2rips_multifield_persistence_8cpp-example.html"> - * Persistent_cohomology/rips_multifield_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2rips_persistence_8cpp-example.html"> - * Persistent_cohomology/rips_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * - * \subsection demos Demos and examples - * To build the demos and examples, run the following commands in a terminal: -\verbatim cd /path-to-gudhi/ -mkdir build -cd build/ -cmake .. -make \endverbatim - * A list of examples is available <a href="examples.html">here</a>. - * - * \subsection testsuites Test suites - * To test your build, run the following command in a terminal: - * \verbatim make test \endverbatim - * - * \section Contributions Bug reports and contributions - * Please help us improving the quality of the GUDHI library. You may report bugs or suggestions to: - * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim - * - * Gudhi is open to external contributions. If you want to join our development team, please contact us. - * -*/ - -/*! \page Citation Acknowledging the GUDHI library - * We kindly ask users to cite the GUDHI library as appropriately as possible in their papers, and to mention the use - * of the GUDHI library on the web pages of their projects using GUDHI and provide us with links to these web pages. - * Feel free to contact us in case you have any question or remark on this topic. - * - * We provide \ref GudhiBibtex entries for the modules of the User and Reference Manual, as well as for publications - * directly related to the GUDHI library. - * \section GudhiBibtex GUDHI bibtex - * \verbinclude biblio/how_to_cite_gudhi.bib -*/ - -// List of Gudhi examples - Doxygen needs at least a file tag to analyse comments -/*! @file Examples - * @example Alpha_complex/Alpha_complex_from_off.cpp - * @example Alpha_complex/Alpha_complex_from_points.cpp - * @example Bitmap_cubical_complex/Bitmap_cubical_complex.cpp - * @example Bitmap_cubical_complex/Bitmap_cubical_complex_periodic_boundary_conditions.cpp - * @example Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp - * @example common/CGAL_3D_points_off_reader.cpp - * @example common/CGAL_points_off_reader.cpp - * @example Contraction/Garland_heckbert.cpp - * @example Contraction/Rips_contraction.cpp - * @example Persistent_cohomology/alpha_complex_3d_persistence.cpp - * @example Persistent_cohomology/alpha_complex_persistence.cpp - * @example Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp - * @example Persistent_cohomology/performance_rips_persistence.cpp - * @example Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp - * @example Persistent_cohomology/persistence_from_file.cpp - * @example Persistent_cohomology/persistence_from_simple_simplex_tree.cpp - * @example Persistent_cohomology/plain_homology.cpp - * @example Persistent_cohomology/rips_multifield_persistence.cpp - * @example Persistent_cohomology/rips_persistence.cpp - * @example Persistent_cohomology/custom_persistence_sort.cpp - * @example Simplex_tree/mini_simplex_tree.cpp - * @example Simplex_tree/simple_simplex_tree.cpp - * @example Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp - * @example Simplex_tree/simplex_tree_from_cliques_of_graph.cpp - * @example Skeleton_blocker/Skeleton_blocker_from_simplices.cpp - * @example Skeleton_blocker/Skeleton_blocker_iteration.cpp - * @example Skeleton_blocker/Skeleton_blocker_link.cpp - * @example Witness_complex/witness_complex_from_file.cpp - * @example Witness_complex/witness_complex_sphere.cpp - */ - diff --git a/include/gudhi/Alpha_complex.h~ b/include/gudhi/Alpha_complex.h~ deleted file mode 100644 index a1900cb9..00000000 --- a/include/gudhi/Alpha_complex.h~ +++ /dev/null @@ -1,417 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Vincent Rouvreau - * - * Copyright (C) 2015 INRIA Saclay (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#ifndef ALPHA_COMPLEX_H_ -#define ALPHA_COMPLEX_H_ - -// to construct a simplex_tree from Delaunay_triangulation -#include <gudhi/graph_simplicial_complex.h> -#include <gudhi/Simplex_tree.h> -#include <gudhi/Debug_utils.h> -// to construct Alpha_complex from a OFF file of points -#include <gudhi/Points_off_io.h> - -#include <stdlib.h> -#include <math.h> // isnan, fmax - -#include <CGAL/Delaunay_triangulation.h> -#include <CGAL/Epick_d.h> -#include <CGAL/Spatial_sort_traits_adapter_d.h> - -#include <iostream> -#include <vector> -#include <string> -#include <limits> // NaN -#include <map> -#include <utility> // std::pair -#include <stdexcept> -#include <numeric> // for std::iota - -namespace Gudhi { - -namespace alphacomplex { - -/** - * \class Alpha_complex Alpha_complex.h gudhi/Alpha_complex.h - * \brief Alpha complex data structure. - * - * \ingroup alpha_complex - * - * \details - * The data structure can be constructed from a CGAL Delaunay triangulation (for more informations on CGAL Delaunay - * triangulation, please refer to the corresponding chapter in page http://doc.cgal.org/latest/Triangulation/) or from - * an OFF file (cf. Points_off_reader). - * - * Please refer to \ref alpha_complex for examples. - * - * The complex is a template class requiring an Epick_d <a target="_blank" - * href="http://doc.cgal.org/latest/Kernel_d/index.html#Chapter_dD_Geometry_Kernel">dD Geometry Kernel</a> - * \cite cgal:s-gkd-15b from CGAL as template, default value is <a target="_blank" - * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> - * < <a target="_blank" href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dynamic__dimension__tag.html"> - * CGAL::Dynamic_dimension_tag </a> > - * - * \remark When Alpha_complex is constructed with an infinite value of alpha, the complex is a Delaunay complex. - * - */ -template<class Kernel = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>> -class Alpha_complex : public Simplex_tree<> { - public: - // Add an int in TDS to save point index in the structure - typedef CGAL::Triangulation_data_structure<typename Kernel::Dimension, - CGAL::Triangulation_vertex<Kernel, std::ptrdiff_t>, - CGAL::Triangulation_full_cell<Kernel> > TDS; - /** \brief A Delaunay triangulation of a set of points in \f$ \mathbb{R}^D\f$.*/ - typedef CGAL::Delaunay_triangulation<Kernel, TDS> Delaunay_triangulation; - - /** \brief A point in Euclidean space.*/ - typedef typename Kernel::Point_d Point_d; - /** \brief Geometric traits class that provides the geometric types and predicates needed by Delaunay - * triangulations.*/ - typedef Kernel Geom_traits; - - private: - // From Simplex_tree - // Type required to insert into a simplex_tree (with or without subfaces). - typedef std::vector<Vertex_handle> Vector_vertex; - - // Simplex_result is the type returned from simplex_tree insert function. - typedef typename std::pair<Simplex_handle, bool> Simplex_result; - - typedef typename Kernel::Compute_squared_radius_d Squared_Radius; - typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; - typedef typename Kernel::Point_dimension_d Point_Dimension; - - // Type required to compute squared radius, or side of bounded sphere on a vector of points. - typedef typename std::vector<Point_d> Vector_of_CGAL_points; - - // Vertex_iterator type from CGAL. - typedef typename Delaunay_triangulation::Vertex_iterator CGAL_vertex_iterator; - - // size_type type from CGAL. - typedef typename Delaunay_triangulation::size_type size_type; - - // Map type to switch from simplex tree vertex handle to CGAL vertex iterator. - typedef typename std::map< Vertex_handle, CGAL_vertex_iterator > Vector_vertex_iterator; - - private: - /** \brief Vertex iterator vector to switch from simplex tree vertex handle to CGAL vertex iterator. - * Vertex handles are inserted sequentially, starting at 0.*/ - Vector_vertex_iterator vertex_handle_to_iterator_; - /** \brief Pointer on the CGAL Delaunay triangulation.*/ - Delaunay_triangulation* triangulation_; - /** \brief Kernel for triangulation_ functions access.*/ - Kernel kernel_; - - public: - /** \brief Alpha_complex constructor from an OFF file name. - * Uses the Delaunay_triangulation_off_reader to construct the Delaunay triangulation required to initialize - * the Alpha_complex. - * - * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. - * - * @param[in] off_file_name OFF file [path and] name. - * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. - */ - Alpha_complex(const std::string& off_file_name, - Filtration_value max_alpha_square = std::numeric_limits<Filtration_value>::infinity()) - : triangulation_(nullptr) { - Gudhi::Points_off_reader<Point_d> off_reader(off_file_name); - if (!off_reader.is_valid()) { - std::cerr << "Alpha_complex - Unable to read file " << off_file_name << "\n"; - exit(-1); // ----- >> - } - - init_from_range(off_reader.get_point_cloud(), max_alpha_square); - } - - /** \brief Alpha_complex constructor from a list of points. - * - * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. - * - * @param[in] points Range of points to triangulate. Points must be in Kernel::Point_d - * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. - * - * The type InputPointRange must be a range for which std::begin and - * std::end return input iterators on a Kernel::Point_d. - * - * @post Compare num_simplices with InputPointRange points number (not the same in case of duplicate points). - */ - template<typename InputPointRange > - Alpha_complex(const InputPointRange& points, - Filtration_value max_alpha_square = std::numeric_limits<Filtration_value>::infinity()) - : triangulation_(nullptr) { - init_from_range(points, max_alpha_square); - } - - /** \brief Alpha_complex destructor. - * - * @warning Deletes the Delaunay triangulation. - */ - ~Alpha_complex() { - delete triangulation_; - } - - // Forbid copy/move constructor/assignment operator - Alpha_complex(const Alpha_complex& other) = delete; - Alpha_complex& operator= (const Alpha_complex& other) = delete; - Alpha_complex (Alpha_complex&& other) = delete; - Alpha_complex& operator= (Alpha_complex&& other) = delete; - - /** \brief get_point returns the point corresponding to the vertex given as parameter. - * - * @param[in] vertex Vertex handle of the point to retrieve. - * @return The point found. - * @exception std::out_of_range In case vertex is not found (cf. std::vector::at). - */ - Point_d get_point(Vertex_handle vertex) const { - return vertex_handle_to_iterator_.at(vertex)->point(); - } - - private: - template<typename InputPointRange > - void init_from_range(const InputPointRange& points, Filtration_value max_alpha_square) { - auto first = std::begin(points); - auto last = std::end(points); - if (first != last) { - // point_dimension function initialization - Point_Dimension point_dimension = kernel_.point_dimension_d_object(); - - // Delaunay triangulation is point dimension. - triangulation_ = new Delaunay_triangulation(point_dimension(*first)); - - std::vector<Point_d> points(first, last); - - // Creates a vector {0, 1, ..., N-1} - std::vector<std::ptrdiff_t> indices(boost::counting_iterator<std::ptrdiff_t>(0), - boost::counting_iterator<std::ptrdiff_t>(points.size())); - - // Sort indices considering CGAL spatial sort - typedef CGAL::Spatial_sort_traits_adapter_d<Kernel, Point_d*> Search_traits_d; - spatial_sort(indices.begin(), indices.end(), Search_traits_d(&(points[0]))); - - typename Delaunay_triangulation::Full_cell_handle hint; - for (auto index : indices) { - typename Delaunay_triangulation::Vertex_handle pos = triangulation_->insert(points[index], hint); - // Save index value as data to retrieve it after insertion - pos->data() = index; - hint = pos->full_cell(); - } - init(max_alpha_square); - } - } - - /** \brief Initialize the Alpha_complex from the Delaunay triangulation. - * - * @param[in] max_alpha_square maximum for alpha square value. - * - * @warning Delaunay triangulation must be already constructed with at least one vertex and dimension must be more - * than 0. - * - * Initialization can be launched once. - */ - void init(Filtration_value max_alpha_square) { - if (triangulation_ == nullptr) { - std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation\n"; - return; // ----- >> - } - if (triangulation_->number_of_vertices() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices\n"; - return; // ----- >> - } - if (triangulation_->maximal_dimension() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation\n"; - return; // ----- >> - } - if (num_vertices() > 0) { - std::cerr << "Alpha_complex init - Cannot init twice\n"; - return; // ----- >> - } - - set_dimension(triangulation_->maximal_dimension()); - - // -------------------------------------------------------------------------------------------- - // double map to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa - // Loop on triangulation vertices list - for (CGAL_vertex_iterator vit = triangulation_->vertices_begin(); vit != triangulation_->vertices_end(); ++vit) { - if (!triangulation_->is_infinite(*vit)) { -#ifdef DEBUG_TRACES - std::cout << "Vertex insertion - " << vit->data() << " -> " << vit->point() << std::endl; -#endif // DEBUG_TRACES - vertex_handle_to_iterator_.emplace(vit->data(), vit); - } - } - // -------------------------------------------------------------------------------------------- - - // -------------------------------------------------------------------------------------------- - // Simplex_tree construction from loop on triangulation finite full cells list - for (auto cit = triangulation_->finite_full_cells_begin(); cit != triangulation_->finite_full_cells_end(); ++cit) { - Vector_vertex vertexVector; -#ifdef DEBUG_TRACES - std::cout << "Simplex_tree insertion "; -#endif // DEBUG_TRACES - for (auto vit = cit->vertices_begin(); vit != cit->vertices_end(); ++vit) { - if (*vit != nullptr) { -#ifdef DEBUG_TRACES - std::cout << " " << (*vit)->data(); -#endif // DEBUG_TRACES - // Vector of vertex construction for simplex_tree structure - vertexVector.push_back((*vit)->data()); - } - } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES - // Insert each simplex and its subfaces in the simplex tree - filtration is NaN - insert_simplex_and_subfaces(vertexVector, std::numeric_limits<double>::quiet_NaN()); - } - // -------------------------------------------------------------------------------------------- - - // -------------------------------------------------------------------------------------------- - // Will be re-used many times - Vector_of_CGAL_points pointVector; - // ### For i : d -> 0 - for (int decr_dim = dimension(); decr_dim >= 0; decr_dim--) { - // ### Foreach Sigma of dim i - for (auto f_simplex : skeleton_simplex_range(decr_dim)) { - int f_simplex_dim = dimension(f_simplex); - if (decr_dim == f_simplex_dim) { - pointVector.clear(); -#ifdef DEBUG_TRACES - std::cout << "Sigma of dim " << decr_dim << " is"; -#endif // DEBUG_TRACES - for (auto vertex : simplex_vertex_range(f_simplex)) { - pointVector.push_back(get_point(vertex)); -#ifdef DEBUG_TRACES - std::cout << " " << vertex; -#endif // DEBUG_TRACES - } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES - // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) - if (isnan(filtration(f_simplex))) { - Filtration_value alpha_complex_filtration = 0.0; - // No need to compute squared_radius on a single point - alpha is 0.0 - if (f_simplex_dim > 0) { - // squared_radius function initialization - Squared_Radius squared_radius = kernel_.compute_squared_radius_d_object(); - - alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); - } - assign_filtration(f_simplex, alpha_complex_filtration); -#ifdef DEBUG_TRACES - std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << filtration(f_simplex) << std::endl; -#endif // DEBUG_TRACES - } - propagate_alpha_filtration(f_simplex, decr_dim); - } - } - } - // -------------------------------------------------------------------------------------------- - - // -------------------------------------------------------------------------------------------- - // As Alpha value is an approximation, we have to make filtration non decreasing while increasing the dimension - bool modified_filt = make_filtration_non_decreasing(); - // Remove all simplices that have a filtration value greater than max_alpha_square - // Remark: prune_above_filtration does not require initialize_filtration to be done before. - modified_filt |= prune_above_filtration(max_alpha_square); - if (modified_filt) { - initialize_filtration(); - } - // -------------------------------------------------------------------------------------------- - } - - template<typename Simplex_handle> - void propagate_alpha_filtration(Simplex_handle f_simplex, int decr_dim) { - // ### Foreach Tau face of Sigma - for (auto f_boundary : boundary_simplex_range(f_simplex)) { -#ifdef DEBUG_TRACES - std::cout << " | --------------------------------------------------\n"; - std::cout << " | Tau "; - for (auto vertex : simplex_vertex_range(f_boundary)) { - std::cout << vertex << " "; - } - std::cout << "is a face of Sigma\n"; - std::cout << " | isnan(filtration(Tau)=" << isnan(filtration(f_boundary)) << std::endl; -#endif // DEBUG_TRACES - // ### If filt(Tau) is not NaN - if (!isnan(filtration(f_boundary))) { - // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) - Filtration_value alpha_complex_filtration = fmin(filtration(f_boundary), filtration(f_simplex)); - assign_filtration(f_boundary, alpha_complex_filtration); -#ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << filtration(f_boundary) << std::endl; -#endif // DEBUG_TRACES - // ### Else - } else { - // No need to compute is_gabriel for dimension <= 2 - // i.e. : Sigma = (3,1) => Tau = 1 - if (decr_dim > 1) { - // insert the Tau points in a vector for is_gabriel function - Vector_of_CGAL_points pointVector; -#ifdef DEBUG_TRACES - Vertex_handle vertexForGabriel = Vertex_handle(); -#endif // DEBUG_TRACES - for (auto vertex : simplex_vertex_range(f_boundary)) { - pointVector.push_back(get_point(vertex)); - } - // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function - Point_d point_for_gabriel; - for (auto vertex : simplex_vertex_range(f_simplex)) { - point_for_gabriel = get_point(vertex); - if (std::find(pointVector.begin(), pointVector.end(), point_for_gabriel) == pointVector.end()) { -#ifdef DEBUG_TRACES - // vertex is not found in Tau - vertexForGabriel = vertex; -#endif // DEBUG_TRACES - // No need to continue loop - break; - } - } - // is_gabriel function initialization - Is_Gabriel is_gabriel = kernel_.side_of_bounded_sphere_d_object(); - bool is_gab = is_gabriel(pointVector.begin(), pointVector.end(), point_for_gabriel) - != CGAL::ON_BOUNDED_SIDE; -#ifdef DEBUG_TRACES - std::cout << " | Tau is_gabriel(Sigma)=" << is_gab << " - vertexForGabriel=" << vertexForGabriel << std::endl; -#endif // DEBUG_TRACES - // ### If Tau is not Gabriel of Sigma - if (false == is_gab) { - // ### filt(Tau) = filt(Sigma) - Filtration_value alpha_complex_filtration = filtration(f_simplex); - assign_filtration(f_boundary, alpha_complex_filtration); -#ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = filt(Sigma) = " << filtration(f_boundary) << std::endl; -#endif // DEBUG_TRACES - } - } - } - } - } -}; - -} // namespace alphacomplex - -} // namespace Gudhi - -#endif // ALPHA_COMPLEX_H_ |