From b3a64294af818c977804c4b67a317782d872e2b5 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 5 Mar 2018 13:38:57 +0000 Subject: Fix doc and tests git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/cechcomplex_vincent@3262 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c76eb981f5960938221aa2498cb87b0707391733 --- .../benchmark/cech_complex_benchmark.cpp | 10 +- src/Cech_complex/doc/Intro_cech_complex.h | 52 ++++--- .../doc/cech_complex_representation.ipe | 160 +++++++++++---------- .../doc/cech_complex_representation.png | Bin 15677 -> 54399 bytes src/Cech_complex/doc/cech_one_skeleton.ipe | 154 +++++++++----------- src/Cech_complex/doc/cech_one_skeleton.png | Bin 12070 -> 29354 bytes .../example/cech_complex_example_from_points.cpp | 22 +-- .../cech_complex_example_from_points_for_doc.txt | 45 ++++-- src/Cech_complex/include/gudhi/Cech_complex.h | 4 +- .../include/gudhi/Cech_complex_blocker.h | 11 +- src/Cech_complex/test/test_cech_complex.cpp | 12 +- src/Doxyfile | 3 +- src/common/include/gudhi/distance_functions.h | 8 +- 13 files changed, 255 insertions(+), 226 deletions(-) (limited to 'src') diff --git a/src/Cech_complex/benchmark/cech_complex_benchmark.cpp b/src/Cech_complex/benchmark/cech_complex_benchmark.cpp index 71c88982..83ef9dca 100644 --- a/src/Cech_complex/benchmark/cech_complex_benchmark.cpp +++ b/src/Cech_complex/benchmark/cech_complex_benchmark.cpp @@ -93,12 +93,12 @@ int main(int argc, char * argv[]) { Radius_distance()); std::cout << radius_clock << std::endl; - Gudhi::Clock squared_radius_clock("Gudhi::Radius_distance()"); + Gudhi::Clock common_radius_clock("Gudhi::Radius_distance()"); // Compute the proximity graph of the points Proximity_graph sq_radius_prox_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), threshold, Gudhi::Radius_distance()); - std::cout << squared_radius_clock << std::endl; + std::cout << common_radius_clock << std::endl; boost::filesystem::path full_path(boost::filesystem::current_path()); @@ -116,6 +116,7 @@ int main(int argc, char * argv[]) { if ( itr->path().extension() == ".off" ) // see below { Points_off_reader off_reader(itr->path().string()); + Point p0 = off_reader.get_point_cloud()[0]; for (Filtration_value radius = 0.1; radius < 0.4; radius += 0.1) { std::cout << itr->path().stem() << ";"; @@ -123,7 +124,7 @@ int main(int argc, char * argv[]) { Gudhi::Clock rips_clock("Rips computation"); Rips_complex rips_complex_from_points(off_reader.get_point_cloud(), radius, Gudhi::Radius_distance()); Simplex_tree rips_stree; - rips_complex_from_points.create_complex(rips_stree, 2); + rips_complex_from_points.create_complex(rips_stree, p0.size() - 1); // ------------------------------------------ // Display information about the Rips complex // ------------------------------------------ @@ -133,7 +134,7 @@ int main(int argc, char * argv[]) { Gudhi::Clock cech_clock("Cech computation"); Cech_complex cech_complex_from_points(off_reader.get_point_cloud(), radius); Simplex_tree cech_stree; - cech_complex_from_points.create_complex(cech_stree, 2); + cech_complex_from_points.create_complex(cech_stree, p0.size() - 1); // ------------------------------------------ // Display information about the Cech complex // ------------------------------------------ @@ -141,6 +142,7 @@ int main(int argc, char * argv[]) { std::cout << cech_sec << ";"; std::cout << cech_sec / rips_sec << ";"; + assert(rips_stree.num_simplices() >= cech_stree.num_simplices()); std::cout << rips_stree.num_simplices() << ";"; std::cout << cech_stree.num_simplices() << ";" << std::endl; } diff --git a/src/Cech_complex/doc/Intro_cech_complex.h b/src/Cech_complex/doc/Intro_cech_complex.h index f2052763..8b6c7851 100644 --- a/src/Cech_complex/doc/Intro_cech_complex.h +++ b/src/Cech_complex/doc/Intro_cech_complex.h @@ -29,7 +29,7 @@ namespace cech_complex { /** \defgroup cech_complex Cech complex * - * \author Clément Maria, Pawel Dlotko, Vincent Rouvreau + * \author Vincent Rouvreau * * @{ * @@ -40,40 +40,54 @@ namespace cech_complex { * proximity graph that allows to construct a * simplicial complex * from it. - * The input can be a point cloud with a given distance function. + * The input shall be a point cloud in an Euclidean space. * - * The filtration value of each edge is computed from a user-given distance function. + * The filtration value of each edge of the `Gudhi::Proximity_graph` is computed from `Gudhi::Radius_distance` function. * - * All edges that have a filtration value strictly greater than a given threshold value are not inserted into - * the complex. + * All edges that have a filtration value strictly greater than a user given maximal radius value, \f$max\_radius\f$, + * 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). + * \image html "cech_one_skeleton.png" "Cech complex proximity graph representation" * + * When creating a simplicial complex from this proximity graph, Cech inserts the proximity graph into the simplicial + * complex data structure, and then expands the simplicial complex when required. + * + * On this example, as edges \f$(x,y)\f$, \f$(y,z)\f$ and \f$(z,y)\f$ are in the complex, the minimal ball radius + * containing the points \f$(x,y,z)\f$ is computed. + * + * \f$(x,y,z)\f$ is inserted to the simplicial complex with the filtration value set with + * \f$mini\_ball\_radius(x,y,z))\f$ iff \f$mini\_ball\_radius(x,y,z)) \leq max\_radius\f$. + * + * And so on for higher dimensions. + * + * \image html "cech_complex_representation.png" "Cech complex expansion" + * + * The minimal ball radius computation is insured by + * + * the miniball software (V3.0) - Smallest Enclosing Balls of Points - and distributed with GUDHI. + * + * Please refer to + * + * the miniball software design description for more information about this computation. + * * 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. + * + * cech_complex_step_by_step.cpp example, where the graph construction over the Simplex_tree is more detailed. * - * \section cechpointsdistance Point cloud and distance function + * \section cechpointsdistance Point cloud * - * \subsection cechpointscloudexample Example from a point cloud and a distance function + * \subsection cechpointscloudexample Example from a point cloud * - * This example builds the proximity graph from the given points, threshold value, and distance function. + * This example builds the proximity graph from the given points, and maximal radius values. * 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): + * When launching (Cech maximal distance between 2 points is 1., is expanded until dimension 2): * * \code $> ./Cech_complex_example_from_points * \endcode diff --git a/src/Cech_complex/doc/cech_complex_representation.ipe b/src/Cech_complex/doc/cech_complex_representation.ipe index 7f6028f4..c64d7596 100644 --- a/src/Cech_complex/doc/cech_complex_representation.ipe +++ b/src/Cech_complex/doc/cech_complex_representation.ipe @@ -1,7 +1,7 @@ - + @@ -232,95 +232,99 @@ h - -109.771 601.912 m -159.595 601.797 l -140.058 541.915 l + +48 640 m +80 672 l +48 672 l h - -79.8776 552.169 m -109.756 601.699 l -139.812 542.209 l +Cech complex +0 +1 +2 +3 +4 +5 +6 + + + + + + + + + + + + + +32 0 0 32 304 672 e + + +304 672 m +336 672 l + +Maximal radius +7 +8 +9 + +112 576 m +144 608 l + + +144 672 m +144 608 l +200 640 l h - -69.8453 682.419 m -159.925 712.208 l -90.12 732.039 l + +48 576 m +112 576 l +80 544 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 + + +80 672 m +144 672 l +112 728 l +h - -50 530 m -80 580 l + + + + +48 576 m +48 640 l +32 608 l +h - -130 580 m -130 690 l + + + + + + + +32 0 0 32 80 576 e - - - - - - -150.038 609.9 m -179.929 549.727 l + +22.6274 0 0 22.6274 64 656 e - - - -158.7 593.269 m -81.4925 544.805 l + +37.1429 0 0 37.1429 112 690.857 e - -256.324 639.958 m -370.055 639.958 l + +37.1429 0 0 37.1429 162.857 640 e - -56.8567 0 0 56.8567 313.217 639.756 e + +10 + +32 0 0 32 48 608 e - - -Rips threshold + + diff --git a/src/Cech_complex/doc/cech_complex_representation.png b/src/Cech_complex/doc/cech_complex_representation.png index e901d92e..4d103a56 100644 Binary files a/src/Cech_complex/doc/cech_complex_representation.png 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 index 3a35970c..345e6d7b 100644 --- a/src/Cech_complex/doc/cech_one_skeleton.ipe +++ b/src/Cech_complex/doc/cech_one_skeleton.ipe @@ -1,7 +1,7 @@ - + @@ -232,95 +232,83 @@ h - -109.771 601.912 m -159.595 601.797 l -140.058 541.915 l +Proximity graph +0 +1 + +304 672 m +336 672 l + +2 +3 +4 +5 +6 + + + + + + + + + + + +32 0 0 32 304 672 e + +Maximal radius +7 +8 +9 + +112 576 m +144 608 l + + +144 672 m +144 608 l +200 640 l h - -79.8776 552.169 m -109.756 601.699 l -139.812 542.209 l + +48 640 m +80 672 l +48 672 l h - -69.8453 682.419 m -159.925 712.208 l -90.12 732.039 l + +48 576 m +112 576 l +80 544 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 + + +80 672 m +144 672 l +112 728 l +h - -56.8567 0 0 56.8567 313.217 639.756 e + + +48 576 m +48 640 l +32 608 l +h - - -Rips threshold + + + + + + + + + + +10 + + diff --git a/src/Cech_complex/doc/cech_one_skeleton.png b/src/Cech_complex/doc/cech_one_skeleton.png index ffa9c329..807e0936 100644 Binary files a/src/Cech_complex/doc/cech_one_skeleton.png and b/src/Cech_complex/doc/cech_one_skeleton.png differ diff --git a/src/Cech_complex/example/cech_complex_example_from_points.cpp b/src/Cech_complex/example/cech_complex_example_from_points.cpp index 97327e69..3b889d56 100644 --- a/src/Cech_complex/example/cech_complex_example_from_points.cpp +++ b/src/Cech_complex/example/cech_complex_example_from_points.cpp @@ -15,22 +15,26 @@ int main() { using Cech_complex = Gudhi::cech_complex::Cech_complex; Point_cloud points; - points.push_back({0., 0.}); - points.push_back({0., 2.}); - points.push_back({std::sqrt(3.), 1.}); - points.push_back({1., 0.}); - points.push_back({1., 2.}); - points.push_back({1. - std::sqrt(3.), 1.}); + points.push_back({1., 0.}); // 0 + points.push_back({0., 1.}); // 1 + points.push_back({2., 1.}); // 2 + points.push_back({3., 2.}); // 3 + points.push_back({0., 3.}); // 4 + points.push_back({3. + std::sqrt(3.), 3.}); // 5 + points.push_back({1., 4.}); // 6 + points.push_back({3., 4.}); // 7 + points.push_back({2., 4. + std::sqrt(3.)}); // 8 + points.push_back({0., 4.}); // 9 + points.push_back({-0.5, 2.}); // 10 // ---------------------------------------------------------------------------- // Init of a Cech complex from points // ---------------------------------------------------------------------------- - // 5. is a magic number to force one blocker, and one non-blocker - Filtration_value max_radius = 12.; + Filtration_value max_radius = 1.; Cech_complex cech_complex_from_points(points, max_radius); Simplex_tree stree; - cech_complex_from_points.create_complex(stree, -1); + cech_complex_from_points.create_complex(stree, 2); // ---------------------------------------------------------------------------- // Display information about the one skeleton Cech complex // ---------------------------------------------------------------------------- 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 index 684e120b..be0afc76 100644 --- 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 @@ -1,16 +1,31 @@ -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] + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 7 ) -> [0] + ( 8 ) -> [0] + ( 9 ) -> [0] + ( 10 ) -> [0] + ( 9 4 ) -> [0.5] + ( 9 6 ) -> [0.5] + ( 10 1 ) -> [0.559017] + ( 10 4 ) -> [0.559017] + ( 1 0 ) -> [0.707107] + ( 2 0 ) -> [0.707107] + ( 3 2 ) -> [0.707107] + ( 6 4 ) -> [0.707107] + ( 9 6 4 ) -> [0.707107] + ( 2 1 ) -> [1] + ( 2 1 0 ) -> [1] + ( 4 1 ) -> [1] + ( 5 3 ) -> [1] + ( 7 3 ) -> [1] + ( 7 5 ) -> [1] + ( 7 6 ) -> [1] + ( 8 6 ) -> [1] + ( 8 7 ) -> [1] + ( 10 4 1 ) -> [1] diff --git a/src/Cech_complex/include/gudhi/Cech_complex.h b/src/Cech_complex/include/gudhi/Cech_complex.h index a50ed9fa..612c73c3 100644 --- a/src/Cech_complex/include/gudhi/Cech_complex.h +++ b/src/Cech_complex/include/gudhi/Cech_complex.h @@ -23,7 +23,7 @@ #ifndef CECH_COMPLEX_H_ #define CECH_COMPLEX_H_ -#include // for Gudhi::Squared_radius +#include // for Gudhi::Radius_distance #include // for Gudhi::Proximity_graph #include // for GUDHI_CHECK #include // for Gudhi::cech_complex::Cech_blocker @@ -43,7 +43,7 @@ namespace cech_complex { * * \details * The data structure is a proximity graph, containing edges when the edge length is less or equal - * to a given max_radius. Edge length is computed from `Gudhi::Squared_radius` distance function. + * to a given max_radius. Edge length is computed from `Gudhi::Radius_distance` distance function. * * \tparam SimplicialComplexForProximityGraph furnishes `Vertex_handle` and `Filtration_value` type definition required * by `Gudhi::Proximity_graph`. diff --git a/src/Cech_complex/include/gudhi/Cech_complex_blocker.h b/src/Cech_complex/include/gudhi/Cech_complex_blocker.h index d718b56e..5ba17c51 100644 --- a/src/Cech_complex/include/gudhi/Cech_complex_blocker.h +++ b/src/Cech_complex/include/gudhi/Cech_complex_blocker.h @@ -24,7 +24,7 @@ #define CECH_COMPLEX_BLOCKER_H_ #include // Cech_blocker is using a pointer on Gudhi::cech_complex::Cech_complex -#include // for Gudhi::Squared_radius +#include // for Gudhi::Radius_distance #include #include @@ -75,12 +75,13 @@ class Cech_blocker { std::cout << "#(" << vertex << ")#"; #endif // DEBUG_TRACES } - Filtration_value squared_radius = Gudhi::Radius_distance()(points); + Filtration_value radius = Gudhi::Radius_distance()(points); #ifdef DEBUG_TRACES - std::cout << "squared_radius = " << squared_radius << " - " << (squared_radius > cc_ptr_->max_radius()) << std::endl; + if (radius > cc_ptr_->max_radius()) + std::cout << "radius > max_radius => expansion is blocked\n"; #endif // DEBUG_TRACES - simplicial_complex_.assign_filtration(sh, squared_radius); - return (squared_radius > cc_ptr_->max_radius()); + simplicial_complex_.assign_filtration(sh, radius); + return (radius > cc_ptr_->max_radius()); } /** \internal \brief Cech complex blocker constructor. */ diff --git a/src/Cech_complex/test/test_cech_complex.cpp b/src/Cech_complex/test/test_cech_complex.cpp index 626f1d82..eae8778c 100644 --- a/src/Cech_complex/test/test_cech_complex.cpp +++ b/src/Cech_complex/test/test_cech_complex.cpp @@ -86,7 +86,7 @@ BOOST_AUTO_TEST_CASE(Cech_complex_from_file) { BOOST_CHECK(st.num_vertices() == NUMBER_OF_VERTICES); std::cout << "st.num_simplices()=" << st.num_simplices() << std::endl; - BOOST_CHECK(st.num_simplices() == 18); + BOOST_CHECK(st.num_simplices() == 28); // Check filtration values of vertices is 0.0 for (auto f_simplex : st.skeleton_simplex_range(0)) { @@ -119,7 +119,7 @@ BOOST_AUTO_TEST_CASE(Cech_complex_from_file) { BOOST_CHECK(st2.num_vertices() == NUMBER_OF_VERTICES); std::cout << "st2.num_simplices()=" << st2.num_simplices() << std::endl; - BOOST_CHECK(st2.num_simplices() == 23); + BOOST_CHECK(st2.num_simplices() == 63); Point_cloud points012; for (std::size_t vertex = 0; vertex <= 2; vertex++) { @@ -156,7 +156,7 @@ BOOST_AUTO_TEST_CASE(Cech_complex_from_file) { BOOST_CHECK(st3.num_vertices() == NUMBER_OF_VERTICES); std::cout << "st3.num_simplices()=" << st3.num_simplices() << std::endl; - BOOST_CHECK(st3.num_simplices() == 24); + BOOST_CHECK(st3.num_simplices() == 98); Point_cloud points0123; for (std::size_t vertex = 0; vertex <= 3; vertex++) { @@ -236,13 +236,13 @@ BOOST_AUTO_TEST_CASE(Cech_complex_from_points) { GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.0); break; case 1: - GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.5); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.707107, .00001); break; case 2: - GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.666667, .00001); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.816497, .00001); break; case 3: - GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.75); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(st.filtration(f_simplex), 0.866025, .00001); break; default: BOOST_CHECK(false); // Shall not happen diff --git a/src/Doxyfile b/src/Doxyfile index f1981e2e..52de65b0 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -843,7 +843,8 @@ EXAMPLE_RECURSIVE = NO IMAGE_PATH = doc/Skeleton_blocker/ \ doc/Alpha_complex/ \ doc/common/ \ - doc/Contraction/ \ + doc/Cech_complex/ \ + doc/Contraction/ \ doc/Simplex_tree/ \ doc/Persistent_cohomology/ \ doc/Witness_complex/ \ diff --git a/src/common/include/gudhi/distance_functions.h b/src/common/include/gudhi/distance_functions.h index 3ce51ad1..7749b98e 100644 --- a/src/common/include/gudhi/distance_functions.h +++ b/src/common/include/gudhi/distance_functions.h @@ -90,11 +90,11 @@ class Radius_distance { operator()(const Point_cloud& point_cloud) const { using Min_sphere = Miniball::Miniball>; - //Min_sphere ms(point_cloud.begin()->end() - point_cloud.begin()->begin(), point_cloud.begin(),point_cloud.end()); - Min_sphere ms(point_cloud.end() - point_cloud.begin(), point_cloud.begin(),point_cloud.end()); + Min_sphere ms(point_cloud.begin()->end() - point_cloud.begin()->begin(), point_cloud.begin(),point_cloud.end()); #ifdef DEBUG_TRACES - std::cout << "Radius on " << point_cloud.end() - point_cloud.begin() << " points = " - << std::sqrt(ms.squared_radius()) << std::endl; + std::cout << "Radius_distance = " << std::sqrt(ms.squared_radius()) << " | nb points = " + << point_cloud.end() - point_cloud.begin() << " | dimension = " + << point_cloud.begin()->end() - point_cloud.begin()->begin() << std::endl; #endif // DEBUG_TRACES return std::sqrt(ms.squared_radius()); -- cgit v1.2.3