From d57e3dfbf15f8aaa3afa097a4e3ed49cd23d26ea Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 20 Feb 2018 16:30:27 +0000 Subject: Add doc, example renamed git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/cechcomplex_vincent@3254 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 666bacd07c711b89167c87155c21fe88688e2e68 --- src/Cech_complex/doc/COPYRIGHT | 19 ++ src/Cech_complex/doc/Intro_cech_complex.h | 92 ++++++ .../doc/cech_complex_representation.ipe | 326 +++++++++++++++++++++ .../doc/cech_complex_representation.png | Bin 0 -> 15677 bytes src/Cech_complex/doc/cech_one_skeleton.ipe | 326 +++++++++++++++++++++ src/Cech_complex/doc/cech_one_skeleton.png | Bin 0 -> 47651 bytes src/Cech_complex/example/CMakeLists.txt | 6 +- .../example/cech_complex_example_from_points.cpp | 75 +++++ .../cech_complex_example_from_points_for_doc.txt | 16 + .../example_one_skeleton_cech_from_points.cpp | 75 ----- .../include/gudhi/Cech_complex_blocker.h | 8 +- 11 files changed, 861 insertions(+), 82 deletions(-) create mode 100644 src/Cech_complex/doc/COPYRIGHT create mode 100644 src/Cech_complex/doc/cech_complex_representation.ipe create mode 100644 src/Cech_complex/doc/cech_complex_representation.png create mode 100644 src/Cech_complex/doc/cech_one_skeleton.ipe create mode 100644 src/Cech_complex/doc/cech_one_skeleton.png create mode 100644 src/Cech_complex/example/cech_complex_example_from_points.cpp create mode 100644 src/Cech_complex/example/cech_complex_example_from_points_for_doc.txt delete mode 100644 src/Cech_complex/example/example_one_skeleton_cech_from_points.cpp (limited to 'src/Cech_complex') diff --git a/src/Cech_complex/doc/COPYRIGHT b/src/Cech_complex/doc/COPYRIGHT new file mode 100644 index 00000000..594b7d03 --- /dev/null +++ b/src/Cech_complex/doc/COPYRIGHT @@ -0,0 +1,19 @@ +The files of this directory are part of the Gudhi Library. The Gudhi library +(Geometric Understanding in Higher Dimensions) is a generic C++ library for +computational topology. + +Author(s): Clément Maria, Pawel Dlotko, Vincent Rouvreau + +Copyright (C) 2015 INRIA + +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 . diff --git a/src/Cech_complex/doc/Intro_cech_complex.h b/src/Cech_complex/doc/Intro_cech_complex.h index e69de29b..f2052763 100644 --- a/src/Cech_complex/doc/Intro_cech_complex.h +++ b/src/Cech_complex/doc/Intro_cech_complex.h @@ -0,0 +1,92 @@ +/* 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) 2018 Inria + * + * 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 . + */ + +#ifndef DOC_CECH_COMPLEX_INTRO_CECH_COMPLEX_H_ +#define DOC_CECH_COMPLEX_INTRO_CECH_COMPLEX_H_ + +namespace Gudhi { + +namespace cech_complex { + +/** \defgroup cech_complex Cech complex + * + * \author Clément Maria, Pawel Dlotko, Vincent Rouvreau + * + * @{ + * + * \section cechdefinition Cech complex definition + * + * Cech_complex + * (Wikipedia) is a + * proximity graph that allows to construct a + * simplicial complex + * from it. + * The input can be a point cloud with a given distance function. + * + * The filtration value of each edge is computed from a user-given distance function. + * + * All edges that have a filtration value strictly greater than a given threshold value are not inserted into + * the complex. + * + * When creating a simplicial complex from this proximity graph, Cech inserts the proximity graph into the data + * structure, and then expands the simplicial complex when required. + * + * Vertex name correspond to the index of the point in the given range (aka. the point cloud). + * + * \image html "cech_complex_representation.png" "Cech complex proximity graph representation" + * + * On this example, as edges (4,5), (4,6) and (5,6) are in the complex, simplex (4,5,6) is added with the filtration + * value set with \f$max(filtration(4,5), filtration(4,6), filtration(5,6))\f$. + * And so on for simplex (0,1,2,3). + * + * If the Cech_complex interfaces are not detailed enough for your need, please refer to + * + * cech_persistence_step_by_step.cpp example, where the graph construction over the Simplex_tree is more detailed. + * + * \section cechpointsdistance Point cloud and distance function + * + * \subsection cechpointscloudexample Example from a point cloud and a distance function + * + * This example builds the proximity graph from the given points, threshold value, and distance function. + * Then it creates a `Simplex_tree` with it. + * + * Then, it is asked to display information about the simplicial complex. + * + * \include Cech_complex/cech_complex_example_from_points.cpp + * + * When launching (Cech maximal distance between 2 points is 7.1, is expanded until dimension 2): + * + * \code $> ./Cech_complex_example_from_points + * \endcode + * + * the program output is: + * + * \include Cech_complex/cech_complex_example_from_points_for_doc.txt + * + */ +/** @} */ // end defgroup cech_complex + +} // namespace cech_complex + +} // namespace Gudhi + +#endif // DOC_CECH_COMPLEX_INTRO_CECH_COMPLEX_H_ diff --git a/src/Cech_complex/doc/cech_complex_representation.ipe b/src/Cech_complex/doc/cech_complex_representation.ipe new file mode 100644 index 00000000..7f6028f4 --- /dev/null +++ b/src/Cech_complex/doc/cech_complex_representation.ipe @@ -0,0 +1,326 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +109.771 601.912 m +159.595 601.797 l +140.058 541.915 l +h + + +79.8776 552.169 m +109.756 601.699 l +139.812 542.209 l +h + + +69.8453 682.419 m +159.925 712.208 l +90.12 732.039 l +h + +Rips complex +0 +1 +2 +3 +4 +5 +6 + +60 710 m +40 660 l + + +40 660 m +130 690 l + + +130 690 m +60 710 l + + +40 660 m +80 580 l + + +80 580 m +130 580 l +130 580 l + + +130 580 m +110 520 l + + +110 520 m +50 530 l +50 530 l +50 530 l + + +50 530 m +80 580 l + + +130 580 m +130 690 l + + + + + + + +150.038 609.9 m +179.929 549.727 l + + + + +158.7 593.269 m +81.4925 544.805 l + + +256.324 639.958 m +370.055 639.958 l + + +56.8567 0 0 56.8567 313.217 639.756 e + + + +Rips threshold + + diff --git a/src/Cech_complex/doc/cech_complex_representation.png b/src/Cech_complex/doc/cech_complex_representation.png new file mode 100644 index 00000000..e901d92e Binary files /dev/null and b/src/Cech_complex/doc/cech_complex_representation.png differ diff --git a/src/Cech_complex/doc/cech_one_skeleton.ipe b/src/Cech_complex/doc/cech_one_skeleton.ipe new file mode 100644 index 00000000..3a35970c --- /dev/null +++ b/src/Cech_complex/doc/cech_one_skeleton.ipe @@ -0,0 +1,326 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +109.771 601.912 m +159.595 601.797 l +140.058 541.915 l +h + + +79.8776 552.169 m +109.756 601.699 l +139.812 542.209 l +h + + +69.8453 682.419 m +159.925 712.208 l +90.12 732.039 l +h + +One skeleton graph +0 +1 +2 +3 +4 +5 +6 + +60 710 m +40 660 l + + +40 660 m +130 690 l + + +130 690 m +60 710 l + + +40 660 m +80 580 l + + +80 580 m +130 580 l +130 580 l + + +130 580 m +110 520 l + + +110 520 m +50 530 l +50 530 l +50 530 l + + +50 530 m +80 580 l + + +130 580 m +130 690 l + + + + + + + +150.038 609.9 m +179.929 549.727 l + + + + +158.7 593.269 m +81.4925 544.805 l + + +256.324 639.958 m +370.055 639.958 l + + +56.8567 0 0 56.8567 313.217 639.756 e + + + +Rips threshold + + diff --git a/src/Cech_complex/doc/cech_one_skeleton.png b/src/Cech_complex/doc/cech_one_skeleton.png new file mode 100644 index 00000000..1028770e Binary files /dev/null and b/src/Cech_complex/doc/cech_one_skeleton.png differ diff --git a/src/Cech_complex/example/CMakeLists.txt b/src/Cech_complex/example/CMakeLists.txt index 8097871f..ac32ff95 100644 --- a/src/Cech_complex/example/CMakeLists.txt +++ b/src/Cech_complex/example/CMakeLists.txt @@ -7,8 +7,8 @@ if (TBB_FOUND) target_link_libraries(Cech_complex_example_step_by_step ${TBB_LIBRARIES}) endif() -add_executable ( Cech_complex_example_one_skeleton_from_points example_one_skeleton_cech_from_points.cpp) +add_executable ( Cech_complex_example_from_points cech_complex_example_from_points.cpp) if (TBB_FOUND) - target_link_libraries(Cech_complex_example_one_skeleton_from_points ${TBB_LIBRARIES}) + target_link_libraries(Cech_complex_example_from_points ${TBB_LIBRARIES}) endif() -add_test(NAME Cech_complex_example_one_skeleton_from_points COMMAND $) +add_test(NAME Cech_complex_example_from_points COMMAND $) diff --git a/src/Cech_complex/example/cech_complex_example_from_points.cpp b/src/Cech_complex/example/cech_complex_example_from_points.cpp new file mode 100644 index 00000000..882849c3 --- /dev/null +++ b/src/Cech_complex/example/cech_complex_example_from_points.cpp @@ -0,0 +1,75 @@ +/* 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) 2018 Inria + * + * 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 . + */ + +#include +#include +#include + +#include +#include +#include +#include + +int main() { + // Type definitions + using Point_cloud = std::vector>; + using Simplex_tree = Gudhi::Simplex_tree; + using Filtration_value = Simplex_tree::Filtration_value; + using Cech_complex = Gudhi::cech_complex::Cech_complex; + + Point_cloud points; + points.push_back({1.0, 1.0}); + points.push_back({7.0, 0.0}); + points.push_back({4.0, 6.0}); + points.push_back({9.0, 6.0}); + points.push_back({0.0, 14.0}); + points.push_back({2.0, 19.0}); + points.push_back({9.0, 17.0}); + + // ---------------------------------------------------------------------------- + // Init of a Cech complex from points + // ---------------------------------------------------------------------------- + // 7.1 is a magic number to force one blocker, and one non-blocker + Filtration_value threshold = 7.1; + Cech_complex cech_complex_from_points(points, threshold, Gudhi::Euclidean_distance()); + + Simplex_tree stree; + cech_complex_from_points.create_complex(stree, 2); + // ---------------------------------------------------------------------------- + // Display information about the one skeleton Cech complex + // ---------------------------------------------------------------------------- + std::cout << "Cech complex is of dimension " << stree.dimension() << + " - " << stree.num_simplices() << " simplices - " << + stree.num_vertices() << " vertices." << std::endl; + + std::cout << "Iterator on Cech complex simplices in the filtration order, with [filtration value]:" << + std::endl; + for (auto f_simplex : stree.filtration_simplex_range()) { + std::cout << " ( "; + for (auto vertex : stree.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << ") -> " << "[" << stree.filtration(f_simplex) << "] "; + std::cout << std::endl; + } + return 0; +} diff --git a/src/Cech_complex/example/cech_complex_example_from_points_for_doc.txt b/src/Cech_complex/example/cech_complex_example_from_points_for_doc.txt new file mode 100644 index 00000000..684e120b --- /dev/null +++ b/src/Cech_complex/example/cech_complex_example_from_points_for_doc.txt @@ -0,0 +1,16 @@ +Cech complex is of dimension 2 - 14 simplices - 7 vertices. +Iterator on Cech complex simplices in the filtration order, with [filtration value]: + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 3 2 ) -> [5] + ( 5 4 ) -> [5.38516] + ( 2 0 ) -> [5.83095] + ( 1 0 ) -> [6.08276] + ( 3 1 ) -> [6.32456] + ( 2 1 ) -> [6.7082] + ( 3 2 1 ) -> [7.07107] diff --git a/src/Cech_complex/example/example_one_skeleton_cech_from_points.cpp b/src/Cech_complex/example/example_one_skeleton_cech_from_points.cpp deleted file mode 100644 index 73679716..00000000 --- a/src/Cech_complex/example/example_one_skeleton_cech_from_points.cpp +++ /dev/null @@ -1,75 +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) 2018 Inria - * - * 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 . - */ - -#include -#include -#include - -#include -#include -#include -#include -#include // for std::numeric_limits - -int main() { - // Type definitions - using Point_cloud = std::vector>; - using Simplex_tree = Gudhi::Simplex_tree; - using Filtration_value = Simplex_tree::Filtration_value; - using Cech_complex = Gudhi::cech_complex::Cech_complex; - - Point_cloud points; - points.push_back({1.0, 1.0}); - points.push_back({7.0, 0.0}); - points.push_back({4.0, 6.0}); - points.push_back({9.0, 6.0}); - points.push_back({0.0, 14.0}); - points.push_back({2.0, 19.0}); - points.push_back({9.0, 17.0}); - - // ---------------------------------------------------------------------------- - // Init of a Rips complex from points - // ---------------------------------------------------------------------------- - Filtration_value threshold = 12.0; - Cech_complex cech_complex_from_points(points, threshold, Gudhi::Euclidean_distance()); - - Simplex_tree stree; - cech_complex_from_points.create_complex(stree, 3); - // ---------------------------------------------------------------------------- - // Display information about the one skeleton Rips complex - // ---------------------------------------------------------------------------- - std::cout << "Cech complex is of dimension " << stree.dimension() << - " - " << stree.num_simplices() << " simplices - " << - stree.num_vertices() << " vertices." << std::endl; - - std::cout << "Iterator on Cech complex simplices in the filtration order, with [filtration value]:" << - std::endl; - for (auto f_simplex : stree.filtration_simplex_range()) { - std::cout << " ( "; - for (auto vertex : stree.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; - } - std::cout << ") -> " << "[" << stree.filtration(f_simplex) << "] "; - std::cout << std::endl; - } - return 0; -} diff --git a/src/Cech_complex/include/gudhi/Cech_complex_blocker.h b/src/Cech_complex/include/gudhi/Cech_complex_blocker.h index f8738be0..fb52f712 100644 --- a/src/Cech_complex/include/gudhi/Cech_complex_blocker.h +++ b/src/Cech_complex/include/gudhi/Cech_complex_blocker.h @@ -80,12 +80,12 @@ class Cech_blocker { #endif // DEBUG_TRACES } Min_sphere ms(cc_ptr_->dimension(), points.begin(),points.end()); - Filtration_value radius = std::sqrt(ms.squared_radius()); + Filtration_value diameter = 2 * std::sqrt(ms.squared_radius()); #ifdef DEBUG_TRACES - std::cout << "radius = " << radius << " - " << (radius > cc_ptr_->threshold()) << std::endl; + std::cout << "diameter = " << diameter << " - " << (diameter > cc_ptr_->threshold()) << std::endl; #endif // DEBUG_TRACES - simplicial_complex_.assign_filtration(sh, radius); - return (radius > cc_ptr_->threshold()); + simplicial_complex_.assign_filtration(sh, diameter); + return (diameter > cc_ptr_->threshold()); } /** \internal \brief Cech complex blocker constructor. */ -- cgit v1.2.3