diff options
| author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-03-03 14:41:33 +0000 |
|---|---|---|
| committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-03-03 14:41:33 +0000 |
| commit | efe1965d052815f0534e1baefa5d15b65e67d82b (patch) | |
| tree | e0ba28511109a3beadc1e95fa346a7ecea9dc0f2 | |
| parent | d357b3bf12430d5d1ccd03fed58966155bd8826c (diff) | |
| parent | effc4723dfa2604c8c505b0dfff48b4cab8012ca (diff) | |
Merge last trunk modificatinos
make sphinx depends on cython target
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST_cythonize@2155 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: ebb1709872963ffd30a6d31ab596f2715ca14436
52 files changed, 3320 insertions, 742 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 0cfa5af7..5185391b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -106,6 +106,8 @@ else() add_definitions(-DBOOST_RESULT_OF_USE_DECLTYPE) # BOOST ISSUE with Libraries name resolution under Windows add_definitions(-DBOOST_ALL_NO_LIB) + # problem with Visual Studio link on Boost program_options + add_definitions( -DBOOST_ALL_DYN_LINK ) INCLUDE_DIRECTORIES(${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${Boost_LIBRARY_DIRS}) diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 5eba5d0a..8e202d32 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -971,3 +971,11 @@ author={Wagner, Hubert and Chen, Chao and Vucini, Erald}, pages={91-106}, language={English} } + +@article{de2004topological, + title={Topological estimation using witness complexes}, + author={De Silva, Vin and Carlsson, Gunnar}, + journal={Proc. Sympos. Point-Based Graphics}, + pages={157--166}, + year={2004} +}
\ No newline at end of file diff --git a/scripts/generate_version.sh b/scripts/generate_version.sh index 54bb727f..f999c6c4 100755 --- a/scripts/generate_version.sh +++ b/scripts/generate_version.sh @@ -66,7 +66,7 @@ do if [ -d "$ROOT_DIR/src/$package" ] && [ $package != "Bottleneck" ] then echo $package - if [ "$package" == "cmake" ] || [ "$package" == "debian" ] + if [ "$package" == "cmake" ] then # SPECIFIC FOR CMAKE MODULES cp -R $ROOT_DIR/src/$package $VERSION_DIR diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 441b9fb5..abd4d12c 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -90,6 +90,8 @@ else() add_definitions(-DBOOST_RESULT_OF_USE_DECLTYPE) # BOOST ISSUE with Libraries name resolution under Windows add_definitions(-DBOOST_ALL_NO_LIB) + # problem with Visual Studio link on Boost program_options + add_definitions( -DBOOST_ALL_DYN_LINK ) INCLUDE_DIRECTORIES(${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${Boost_LIBRARY_DIRS}) diff --git a/src/Doxyfile b/src/Doxyfile index 93399848..13c0a6d6 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -784,7 +784,6 @@ EXCLUDE = data/ \ example/ \ GudhUI/ \ cmake/ \ - debian/ \ src/cython/ \ include/gudhi_patches/ diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt index 38d7e9a9..d2a84b1e 100644 --- a/src/Persistent_cohomology/example/CMakeLists.txt +++ b/src/Persistent_cohomology/example/CMakeLists.txt @@ -1,10 +1,6 @@ cmake_minimum_required(VERSION 2.6) project(Persistent_cohomology_examples) -# problem with Visual Studio link on Boost program_options -add_definitions( -DBOOST_ALL_NO_LIB ) -add_definitions( -DBOOST_ALL_DYN_LINK ) - add_executable(plain_homology plain_homology.cpp) target_link_libraries(plain_homology ${Boost_SYSTEM_LIBRARY}) diff --git a/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp b/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp index c8f0921a..b159c62e 100644 --- a/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp +++ b/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp @@ -34,6 +34,13 @@ #include <utility> // for pair #include <map> +// ---------------------------------------------------------------------------- +// rips_persistence_step_by_step is an example of each step that is required to +// build a Rips over a Simplex_tree. Please refer to rips_persistence to see +// how to do the same thing with the Rips_complex wrapper for less detailed +// steps. +// ---------------------------------------------------------------------------- + // Types definition using Simplex_tree = Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_fast_persistence>; using Vertex_handle = Simplex_tree::Vertex_handle; diff --git a/src/Rips_complex/concept/Simplicial_complex_for_rips.h b/src/Rips_complex/concept/Simplicial_complex_for_rips.h index dc871177..7dab0615 100644 --- a/src/Rips_complex/concept/Simplicial_complex_for_rips.h +++ b/src/Rips_complex/concept/Simplicial_complex_for_rips.h @@ -31,11 +31,10 @@ namespace rips_complex { * complex, that can be created from a `Rips_complex`. The only available model for the moment is the `Simplex_tree`. */ struct SimplicialComplexForRips { - /** \brief Handle to specify the simplex filtration value. */ + /** \brief Type used to store the filtration values of the simplicial complex. */ typedef unspecified Filtration_value; - /** \brief Inserts a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial - * complex. */ + /** \brief Inserts a given `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial complex. */ template<class OneSkeletonGraph> void insert_graph(const OneSkeletonGraph& skel_graph); diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 64fd34bc..8e374c09 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -48,8 +48,10 @@ namespace rips_complex { * 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 one skeleton graph, rips inserts the one skeleton graph into the data - * structure, and then expands the simplicial when required. + * When creating a simplicial complex from this one skeleton graph, Rips inserts the one skeleton 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 "rips_complex_representation.png" "Rips-complex one skeleton graph representation" * @@ -57,6 +59,10 @@ namespace rips_complex { * 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 Rips_complex interfaces are not detailed enough for your need, please refer to + * <a href="_persistent_cohomology_2rips_persistence_step_by_step_8cpp-example.html"> + * rips_persistence_step_by_step.cpp</a> example, where the graph construction over the Simplex_tree is more detailed. + * * \section ripspointsdistance Point cloud and distance function * * \subsection ripspointscloudexample Example from a point cloud and a distance function @@ -68,7 +74,7 @@ namespace rips_complex { * * \include Rips_complex/example_one_skeleton_rips_from_points.cpp * - * When launching (rips maximal distance between 2 points is 12.0, is expanded until dimension 1 - one skeleton graph + * When launching (Rips maximal distance between 2 points is 12.0, is expanded until dimension 1 - one skeleton graph * in other words): * * \code $> ./oneskeletonripspoints @@ -85,7 +91,7 @@ namespace rips_complex { * Then it creates a `Simplex_tree` with it. * * - * Then, it is asked to display information about the rips complex. + * Then, it is asked to display information about the Rips complex. * * \include Rips_complex/example_rips_complex_from_off_file.cpp * @@ -111,7 +117,7 @@ namespace rips_complex { * * \include Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp * - * When launching (rips maximal distance between 2 points is 1.0, is expanded until dimension 1 - one skeleton graph + * When launching (Rips maximal distance between 2 points is 1.0, is expanded until dimension 1 - one skeleton graph * with other words): * * \code $> ./oneskeletonripsdistance @@ -127,7 +133,7 @@ namespace rips_complex { * Then it creates a `Simplex_tree` with it. * * - * Then, it is asked to display information about the rips complex. + * Then, it is asked to display information about the Rips complex. * * \include Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp * diff --git a/src/Rips_complex/example/example_one_skeleton_rips_from_distance_matrix.cpp b/src/Rips_complex/example/example_one_skeleton_rips_from_distance_matrix.cpp index 90bd8e38..bbc3c755 100644 --- a/src/Rips_complex/example/example_one_skeleton_rips_from_distance_matrix.cpp +++ b/src/Rips_complex/example/example_one_skeleton_rips_from_distance_matrix.cpp @@ -29,7 +29,7 @@ int main() { distances.push_back({0.11, 0.39, 0.97, 0.30}); // ---------------------------------------------------------------------------- - // Init of a rips complex from points + // Init of a Rips complex from points // ---------------------------------------------------------------------------- double threshold = 1.0; Rips_complex rips_complex_from_points(distances, threshold); @@ -37,13 +37,13 @@ int main() { Simplex_tree stree; rips_complex_from_points.create_complex(stree, 1); // ---------------------------------------------------------------------------- - // Display information about the one skeleton rips complex + // Display information about the one skeleton Rips complex // ---------------------------------------------------------------------------- std::cout << "Rips complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - std::cout << "Iterator on rips complex simplices in the filtration order, with [filtration value]:" << + std::cout << "Iterator on Rips complex simplices in the filtration order, with [filtration value]:" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { std::cout << " ( "; diff --git a/src/Rips_complex/example/example_one_skeleton_rips_from_points.cpp b/src/Rips_complex/example/example_one_skeleton_rips_from_points.cpp index 5d1216a0..3fd69ebc 100644 --- a/src/Rips_complex/example/example_one_skeleton_rips_from_points.cpp +++ b/src/Rips_complex/example/example_one_skeleton_rips_from_points.cpp @@ -24,7 +24,7 @@ int main() { points.push_back({9.0, 17.0}); // ---------------------------------------------------------------------------- - // Init of a rips complex from points + // Init of a Rips complex from points // ---------------------------------------------------------------------------- double threshold = 12.0; Rips_complex rips_complex_from_points(points, threshold, Euclidean_distance()); @@ -32,13 +32,13 @@ int main() { Simplex_tree stree; rips_complex_from_points.create_complex(stree, 1); // ---------------------------------------------------------------------------- - // Display information about the one skeleton rips complex + // Display information about the one skeleton Rips complex // ---------------------------------------------------------------------------- std::cout << "Rips complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - std::cout << "Iterator on rips complex simplices in the filtration order, with [filtration value]:" << + std::cout << "Iterator on Rips complex simplices in the filtration order, with [filtration value]:" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { std::cout << " ( "; diff --git a/src/Rips_complex/example/example_rips_complex_from_csv_distance_matrix_file.cpp b/src/Rips_complex/example/example_rips_complex_from_csv_distance_matrix_file.cpp index cc6c3a33..ef3a9d13 100644 --- a/src/Rips_complex/example/example_rips_complex_from_csv_distance_matrix_file.cpp +++ b/src/Rips_complex/example/example_rips_complex_from_csv_distance_matrix_file.cpp @@ -29,7 +29,7 @@ int main(int argc, char **argv) { using Distance_matrix = std::vector<std::vector<Filtration_value>>; // ---------------------------------------------------------------------------- - // Init of a rips complex from a distance matrix in a csv file + // Init of a Rips complex from a distance matrix in a csv file // Default separator is ';' // ---------------------------------------------------------------------------- Distance_matrix distances = read_lower_triangular_matrix_from_csv_file<Filtration_value>(csv_file_name); @@ -50,13 +50,13 @@ int main(int argc, char **argv) { std::ostream output_stream(streambufffer); // ---------------------------------------------------------------------------- - // Display information about the rips complex + // Display information about the Rips complex // ---------------------------------------------------------------------------- output_stream << "Rips complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - output_stream << "Iterator on rips complex simplices in the filtration order, with [filtration value]:" << + output_stream << "Iterator on Rips complex simplices in the filtration order, with [filtration value]:" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { output_stream << " ( "; diff --git a/src/Rips_complex/example/example_rips_complex_from_off_file.cpp b/src/Rips_complex/example/example_rips_complex_from_off_file.cpp index b6c961d0..a1e4e255 100644 --- a/src/Rips_complex/example/example_rips_complex_from_off_file.cpp +++ b/src/Rips_complex/example/example_rips_complex_from_off_file.cpp @@ -29,7 +29,7 @@ int main(int argc, char **argv) { using Rips_complex = Gudhi::rips_complex::Rips_complex<Filtration_value>; // ---------------------------------------------------------------------------- - // Init of a rips complex from an OFF file + // Init of a Rips complex from an OFF file // ---------------------------------------------------------------------------- Gudhi::Points_off_reader<Point> off_reader(off_file_name); Rips_complex rips_complex_from_file(off_reader.get_point_cloud(), threshold, Euclidean_distance()); @@ -49,13 +49,13 @@ int main(int argc, char **argv) { std::ostream output_stream(streambufffer); // ---------------------------------------------------------------------------- - // Display information about the rips complex + // Display information about the Rips complex // ---------------------------------------------------------------------------- output_stream << "Rips complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - output_stream << "Iterator on rips complex simplices in the filtration order, with [filtration value]:" << + output_stream << "Iterator on Rips complex simplices in the filtration order, with [filtration value]:" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { output_stream << " ( "; diff --git a/src/Rips_complex/example/full_skeleton_rips_for_doc.txt b/src/Rips_complex/example/full_skeleton_rips_for_doc.txt index 319931e0..55de4ab8 100644 --- a/src/Rips_complex/example/full_skeleton_rips_for_doc.txt +++ b/src/Rips_complex/example/full_skeleton_rips_for_doc.txt @@ -1,5 +1,5 @@ Rips complex is of dimension 3 - 24 simplices - 7 vertices. -Iterator on rips complex simplices in the filtration order, with [filtration value]: +Iterator on Rips complex simplices in the filtration order, with [filtration value]: ( 0 ) -> [0] ( 1 ) -> [0] ( 2 ) -> [0] diff --git a/src/Rips_complex/example/one_skeleton_rips_for_doc.txt b/src/Rips_complex/example/one_skeleton_rips_for_doc.txt index b0e25cc5..706512a5 100644 --- a/src/Rips_complex/example/one_skeleton_rips_for_doc.txt +++ b/src/Rips_complex/example/one_skeleton_rips_for_doc.txt @@ -1,5 +1,5 @@ Rips complex is of dimension 1 - 18 simplices - 7 vertices. -Iterator on rips complex simplices in the filtration order, with [filtration value]: +Iterator on Rips complex simplices in the filtration order, with [filtration value]: ( 0 ) -> [0] ( 1 ) -> [0] ( 2 ) -> [0] diff --git a/src/Rips_complex/include/gudhi/Rips_complex.h b/src/Rips_complex/include/gudhi/Rips_complex.h index f0f39db8..1e4b76a7 100644 --- a/src/Rips_complex/include/gudhi/Rips_complex.h +++ b/src/Rips_complex/include/gudhi/Rips_complex.h @@ -51,7 +51,7 @@ namespace rips_complex { * to a given threshold. Edge length is computed from a user given point cloud with a given distance function, or a * distance matrix. * - * \tparam Filtration_value must meet `SimplicialComplexForRips` concept. + * \tparam Filtration_value is the type used to store the filtration values of the simplicial complex. */ template<typename Filtration_value> class Rips_complex { @@ -70,31 +70,31 @@ class Rips_complex { /** \brief Rips_complex constructor from a list of points. * * @param[in] points Range of points. - * @param[in] threshold rips value. + * @param[in] threshold Rips value. * @param[in] distance distance function that returns a `Filtration_value` from 2 given points. * - * \tparam InputPointRange must be a range for which `std::begin` and `std::end` return input iterators on a + * \tparam ForwardPointRange must be a range for which `std::begin` and `std::end` return input iterators on a * point. * * \tparam Distance furnishes `operator()(const Point& p1, const Point& p2)`, where - * `Point` is a point from the `InputPointRange`, and that returns a `Filtration_value`. + * `Point` is a point from the `ForwardPointRange`, and that returns a `Filtration_value`. */ - template<typename InputPointRange, typename Distance > - Rips_complex(const InputPointRange& points, Filtration_value threshold, Distance distance) { - compute_proximity_graph<InputPointRange, Distance >(points, threshold, distance); + template<typename ForwardPointRange, typename Distance > + Rips_complex(const ForwardPointRange& points, Filtration_value threshold, Distance distance) { + compute_proximity_graph(points, threshold, distance); } /** \brief Rips_complex constructor from a distance matrix. * * @param[in] distance_matrix Range of distances. - * @param[in] threshold rips value. + * @param[in] threshold Rips value. * - * \tparam InputDistanceRange must have a `size()` method and on which `distance_matrix[i][j]` returns - * the distance between points \f$i\f$ and \f$j\f$ as long as \f$ 0 \leqslant i \leqslant j \leqslant + * \tparam DistanceMatrix must have a `size()` method and on which `distance_matrix[i][j]` returns + * the distance between points \f$i\f$ and \f$j\f$ as long as \f$ 0 \leqslant i < j \leqslant * distance\_matrix.size().\f$ */ - template<typename InputDistanceRange> - Rips_complex(const InputDistanceRange& distance_matrix, Filtration_value threshold) { + template<typename DistanceMatrix> + Rips_complex(const DistanceMatrix& distance_matrix, Filtration_value threshold) { compute_proximity_graph(boost::irange((size_t)0, distance_matrix.size()), threshold, [&](size_t i, size_t j){return distance_matrix[j][i];}); } @@ -105,7 +105,7 @@ class Rips_complex { * \tparam SimplicialComplexForRips must meet `SimplicialComplexForRips` concept. * * @param[in] complex SimplicialComplexForRips to be created. - * @param[in] dim_max graph expansion for rips until this given maximal dimension. + * @param[in] dim_max graph expansion for Rips until this given maximal dimension. * @exception std::invalid_argument In debug mode, if `complex.num_vertices()` does not return 0. * */ @@ -126,14 +126,14 @@ class Rips_complex { * If points contains n elements, the proximity graph is the graph with n vertices, and an edge [u,v] iff the * distance function between points u and v is smaller than threshold. * - * \tparam InputPointRange furnishes `.begin()` and `.end()` + * \tparam ForwardPointRange furnishes `.begin()` and `.end()` * methods. * * \tparam Distance furnishes `operator()(const Point& p1, const Point& p2)`, where - * `Point` is a point from the `InputPointRange`, and that returns a `Filtration_value`. + * `Point` is a point from the `ForwardPointRange`, and that returns a `Filtration_value`. */ - template< typename InputPointRange, typename Distance > - void compute_proximity_graph(const InputPointRange& points, Filtration_value threshold, + template< typename ForwardPointRange, typename Distance > + void compute_proximity_graph(const ForwardPointRange& points, Filtration_value threshold, Distance distance) { std::vector< std::pair< Vertex_handle, Vertex_handle > > edges; std::vector< Filtration_value > edges_fil; @@ -144,7 +144,7 @@ class Rips_complex { // -------------------------------------------------------------------------------------------- // Creates the vector of edges and its filtration values (returned by distance function) Vertex_handle idx_u = 0; - for (auto it_u = std::begin(points); it_u != std::end(points); ++it_u) { + for (auto it_u = std::begin(points); it_u != std::end(points); ++it_u, ++idx_u) { Vertex_handle idx_v = idx_u + 1; for (auto it_v = it_u + 1; it_v != std::end(points); ++it_v, ++idx_v) { Filtration_value fil = distance(*it_u, *it_v); @@ -153,7 +153,6 @@ class Rips_complex { edges_fil.push_back(fil); } } - ++idx_u; } // -------------------------------------------------------------------------------------------- diff --git a/src/Rips_complex/test/test_rips_complex.cpp b/src/Rips_complex/test/test_rips_complex.cpp index 1bdd0512..ae68ba0d 100644 --- a/src/Rips_complex/test/test_rips_complex.cpp +++ b/src/Rips_complex/test/test_rips_complex.cpp @@ -51,12 +51,12 @@ bool are_almost_the_same(float a, float b) { BOOST_AUTO_TEST_CASE(RIPS_DOC_OFF_file) { // ---------------------------------------------------------------------------- // - // Init of a rips complex from a OFF file + // Init of a Rips complex from a OFF file // // ---------------------------------------------------------------------------- std::string off_file_name("alphacomplexdoc.off"); double rips_threshold = 12.0; - std::cout << "========== OFF FILE NAME = " << off_file_name << " - rips threshold=" << + std::cout << "========== OFF FILE NAME = " << off_file_name << " - Rips threshold=" << rips_threshold << "==========" << std::endl; Gudhi::Points_off_reader<Point> off_reader(off_file_name); @@ -185,7 +185,7 @@ BOOST_AUTO_TEST_CASE(Rips_complex_from_points) { points.push_back(Point(coords.begin(), coords.end())); // ---------------------------------------------------------------------------- - // Init of a rips complex from the list of points + // Init of a Rips complex from the list of points // ---------------------------------------------------------------------------- Rips_complex rips_complex_from_points(points, 2.0, Custom_square_euclidean_distance()); @@ -195,7 +195,7 @@ BOOST_AUTO_TEST_CASE(Rips_complex_from_points) { rips_complex_from_points.create_complex(st, DIMENSION); // Another way to check num_simplices - std::cout << "Iterator on rips complex simplices in the filtration order, with [filtration value]:" << std::endl; + std::cout << "Iterator on Rips complex simplices in the filtration order, with [filtration value]:" << std::endl; int num_simplices = 0; for (auto f_simplex : st.filtration_simplex_range()) { num_simplices++; @@ -236,12 +236,12 @@ BOOST_AUTO_TEST_CASE(Rips_complex_from_points) { BOOST_AUTO_TEST_CASE(Rips_doc_csv_file) { // ---------------------------------------------------------------------------- // - // Init of a rips complex from a OFF file + // Init of a Rips complex from a OFF file // // ---------------------------------------------------------------------------- std::string csv_file_name("full_square_distance_matrix.csv"); double rips_threshold = 12.0; - std::cout << "========== CSV FILE NAME = " << csv_file_name << " - rips threshold=" << + std::cout << "========== CSV FILE NAME = " << csv_file_name << " - Rips threshold=" << rips_threshold << "==========" << std::endl; Distance_matrix distances = read_lower_triangular_matrix_from_csv_file<Filtration_value>(csv_file_name); @@ -332,12 +332,12 @@ BOOST_AUTO_TEST_CASE(Rips_doc_csv_file) { BOOST_AUTO_TEST_CASE(Rips_create_complex_throw) { // ---------------------------------------------------------------------------- // - // Init of a rips complex from a OFF file + // Init of a Rips complex from a OFF file // // ---------------------------------------------------------------------------- std::string off_file_name("alphacomplexdoc.off"); double rips_threshold = 12.0; - std::cout << "========== OFF FILE NAME = " << off_file_name << " - rips threshold=" << + std::cout << "========== OFF FILE NAME = " << off_file_name << " - Rips threshold=" << rips_threshold << "==========" << std::endl; Gudhi::Points_off_reader<Point> off_reader(off_file_name); diff --git a/src/Witness_complex/concept/Simplicial_complex_for_witness.h b/src/Witness_complex/concept/SimplicialComplexForWitness.h index caaf0db6..d78cc83f 100644 --- a/src/Witness_complex/concept/Simplicial_complex_for_witness.h +++ b/src/Witness_complex/concept/SimplicialComplexForWitness.h @@ -27,57 +27,70 @@ namespace Gudhi { namespace witness_complex { -/** \brief The concept Simplicial_Complex describes the requirements +/** \brief The concept SimplicialComplexForWitness describes the requirements * for a type to implement a simplicial complex, - * used for example to build a 'Witness_complex'. + * used for example to build a Witness_complex or Strong_witness_complex. */ struct SimplicialComplexForWitness { /** Handle to specify a simplex. */ typedef unspecified Simplex_handle; - /** Handle to specify a vertex. Must be a non-negative integer. */ - typedef unspecified Vertex_handle; + // /** Handle to specify a vertex. Must be a non-negative integer. */ + // typedef unspecified Vertex_handle; - /** Returns a Simplex_hanlde that is different from all simplex handles + /** \brief Returns a Simplex_hanlde that is different from all simplex handles * of the simplices. */ Simplex_handle null_simplex(); - /** \brief Iterator over the simplices of the complex, - * in an arbitrary order. - * - * 'value_type' must be 'Simplex_handle'.*/ - typedef unspecified Complex_simplex_range; - - /** - * \brief Returns a range over all the simplices of a - * complex. + /** Returns the number of vertices in the simplicial complex */ - Complex_simplex_range complex_simplex_range(); - - /** \brief Iterator over vertices of a simplex. - * - * 'value type' must be 'Vertex_handle'.*/ - typedef unspecified Simplex_vertex_range; - - /** \brief Returns a range over vertices of a given - * simplex. */ - Simplex_vertex_range simplex_vertex_range(Simplex_handle const & simplex); - + std::size_t num_vertices(); + /** \brief Return type of an insertion of a simplex */ typedef unspecified Insertion_result_type; /** \brief Inserts a simplex with vertices from a given range * 'vertex_range' in the simplicial complex. + * The function is only used in Witness_complex class + * and by construction, it is not necessary to check if + * the faces are in the simplicial complex before insertion. + * The simplex is given the filtration value 'filtration'. + * Filtration_value should be convertible from double. + * The return type is not used. * */ template< typedef Input_vertex_range > - Insertion_result_type insert_simplex(Input_vertex_range const & vertex_range); + Insertion_result_type insert_simplex(Input_vertex_range const & vertex_range, Filtration_value filtration); + /** \brief Inserts a simplex and all its faces + * with vertices from a given range + * 'vertex_range' in the simplicial complex. + * The function is only used in Strong_witness_complex class. + * All inserted simplices are given the filtration + * value 'filtration'. + * Filtration_value should be convertible from double. + * The return type is not used. + */ + + template< typedef Input_vertex_range, + typedef Filtration_value> + Insertion_result_type insert_simplex_and_subfaces(Input_vertex_range const & vertex_range, Filtration_value filtration); + /** \brief Finds a simplex with vertices given by a range * * If a simplex exists, its Simplex_handle is returned. * Otherwise null_simplex() is returned. */ template< typedef Input_vertex_range > Simplex_handle find(Input_vertex_range const & vertex_range); + + /** \brief Sets the dimension of the simplicial complex to + * 'dimension'. + */ + void set_dimension(int dimension); + + /** \brief Returns the filtration of the simplex given by + * the simplex handle 'sh'. + */ + double filtration(Simplex_handle sh); }; } // namespace witness_complex diff --git a/src/Witness_complex/doc/Witness_complex_doc.h b/src/Witness_complex/doc/Witness_complex_doc.h index 60dfd27b..171a185f 100644 --- a/src/Witness_complex/doc/Witness_complex_doc.h +++ b/src/Witness_complex/doc/Witness_complex_doc.h @@ -8,31 +8,106 @@ \image html "Witness_complex_representation.png" "Witness complex representation" - \section Definitions + \section witnessdefinitions Definitions - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: + Witness complex is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: \li \f$W\f$ set of **witnesses** and - \li \f$L \subseteq W\f$ set of **landmarks**. + \li \f$L\f$ set of **landmarks**. - The simplices are based on landmarks - and a simplex belongs to the witness complex if and only if it is witnessed, that is: + Even though often the set of landmarks \f$L\f$ is a subset of the set of witnesses \f$ W\f$, it is not a requirement for the current implementation. - \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that - w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. - - The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + Landmarks are the vertices of the simplicial complex + and witnesses help to decide on which simplices are inserted via a predicate "is witnessed". - \section Implementation + De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**: - The principal class of this module is Gudhi::Witness_complex. + - *weak*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l') \f$ + - *strong*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l') \f$ - In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness. - This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module. + where \f$ d(.,.) \f$ is a distance function. - *\image html "bench_Cy8.png" "Running time as function on number of landmarks" width=10cm - *\image html "bench_sphere.png" "Running time as function on number of witnesses for |L|=300" width=10cm + Both definitions can be relaxed by a real value \f$\alpha\f$: + + - *weak*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + - *strong*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + + which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively. + + \image html "swit.svg" "Strongly witnessed simplex" + + In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in \cite de2004topological, whereas 0-relaxed strong witness complex consists of just vertices and is not very interesting. + Hence for small relaxation weak version is preferable. + However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute and offers similar results. + + \section witnessimplementation Implementation + The two complexes described above are implemented in the corresponding classes + - Gudhi::witness_complex::Witness_complex + - Gudhi::witness_complex::Euclidean_witness_complex + - Gudhi::witness_complex::Strong_witness_complex + - Gudhi::witness_complex::Euclidean_strong_witness_complex + + The construction of the Euclidean versions of complexes follow the same scheme: + 1. Construct a search tree on landmarks (for that Gudhi::spatial_searching::Kd_tree_search is used internally). + 2. Construct lists of nearest landmarks for each witness (special structure Gudhi::witness_complex::Active_witness is used internally). + 3. Construct the witness complex for nearest landmark lists. + + In the non-Euclidean classes, the lists of nearest landmarks are supposed to be given as input. + + The constructors take on the steps 1 and 2, while the function 'create_complex' executes the step 3. + + \section witnessexample1 Example 1: Constructing weak relaxed witness complex from an off file + + Let's start with a simple example, which reads an off point file and computes a weak witness complex. + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp} + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Euclidean_witness_complex.h> +#include <gudhi/pick_n_random_points.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> + +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; +typedef typename K::Point_d Point_d; +typedef typename Gudhi::witness_complex::Euclidean_witness_complex<K> Witness_complex; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::vector< Point_d > Point_vector; + +int main(int argc, char * const argv[]) { + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + point_vector = Point_vector(off_reader.get_point_cloud()); + + // Choose landmarks + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); +} + + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + \section witnessexample2 Example2: Computing persistence using strong relaxed witness complex + + Here is an example of constructing a strong witness complex filtration and computing persistence on it: + + \include Witness_complex/example_strong_witness_persistence.cpp \copyright GNU General Public License v3. diff --git a/src/Witness_complex/doc/Witness_complex_representation.ipe b/src/Witness_complex/doc/Witness_complex_representation.ipe new file mode 100644 index 00000000..f9c45d5d --- /dev/null +++ b/src/Witness_complex/doc/Witness_complex_representation.ipe @@ -0,0 +1,280 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70107" creator="Ipe 7.1.10"> +<info created="D:20161010162425" modified="D:20161010162828"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/ptarc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fptarc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="small" value="\small"/> +<textsize name="footnote" value="\footnotesize"/> +<textsize name="tiny" value="\tiny"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<opacity name="10%" value="0.1"/> +<opacity name="30%" value="0.3"/> +<opacity name="50%" value="0.5"/> +<opacity name="75%" value="0.75"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<use layer="alpha" name="mark/fdisk(sfx)" pos="288 672" size="normal" stroke="darkblue" fill="white"/> +<path stroke="darkblue"> +48.8262 0 0 48.8262 288 672 e +</path> +<text transformations="translations" pos="292 676" stroke="darkblue" type="label" width="6.559" height="4.289" depth="0" valign="baseline">$\omega$</text> +<path stroke="black"> +284 720 m +280 624 l +268 648 l +h +</path> +<use name="mark/fdisk(sfx)" pos="284 720" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="268 648" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="280 624" size="normal" stroke="black" fill="white"/> +<text matrix="1 0 0 1 0 8" transformations="translations" pos="268 672" stroke="black" type="label" width="6.05" height="4.289" depth="0" valign="baseline">$\sigma$</text> +<use name="mark/fdisk(sfx)" pos="344 672" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="356 716" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="364 628" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="244 708" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="196 632" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="200 696" size="normal" stroke="black" fill="white"/> +<use name="mark/fdisk(sfx)" pos="168 716" size="normal" stroke="black" fill="white"/> +</page> +</ipe> diff --git a/src/Witness_complex/doc/Witness_complex_representation.png b/src/Witness_complex/doc/Witness_complex_representation.png Binary files differindex 1d31a490..16e0504e 100644 --- a/src/Witness_complex/doc/Witness_complex_representation.png +++ b/src/Witness_complex/doc/Witness_complex_representation.png diff --git a/src/Witness_complex/doc/swit.svg b/src/Witness_complex/doc/swit.svg new file mode 100644 index 00000000..6ffb5fff --- /dev/null +++ b/src/Witness_complex/doc/swit.svg @@ -0,0 +1,1303 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Created with Inkscape (http://www.inkscape.org/) --> + +<svg + xmlns:ns0="http://www.iki.fi/pav/software/textext/" + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:xlink="http://www.w3.org/1999/xlink" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="113.73116mm" + height="84.14254mm" + viewBox="0 0 402.98441 298.14286" + id="svg2" + version="1.1" + inkscape:version="0.91 r13725" + sodipodi:docname="swit.svg"> + <sodipodi:namedview + id="base" + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1.0" + inkscape:pageopacity="0.0" + inkscape:pageshadow="2" + inkscape:zoom="0.98994949" + inkscape:cx="402.72174" + inkscape:cy="258.46971" + inkscape:document-units="px" + inkscape:current-layer="layer1" + showgrid="false" + inkscape:window-width="1366" + inkscape:window-height="704" + inkscape:window-x="0" + inkscape:window-y="27" + inkscape:window-maximized="1" + fit-margin-top="0" + fit-margin-left="0" + fit-margin-right="0" + fit-margin-bottom="0" /> + <defs + id="defs4"> + <marker + inkscape:stockid="Arrow1Lend" + orient="auto" + refY="0" + refX="0" + id="Arrow1Lend" + style="overflow:visible" + inkscape:isstock="true"> + <path + inkscape:connector-curvature="0" + id="path5009" + d="M 0,0 5,-5 -12.5,0 5,5 0,0 Z" + style="fill:#000080;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1pt;stroke-opacity:1" + transform="matrix(-0.8,0,0,-0.8,-10,0)" /> + </marker> + <marker + inkscape:stockid="Arrow1Lend" + orient="auto" + refY="0" + refX="0" + id="Arrow1Lend-8" + style="overflow:visible" + inkscape:isstock="true"> + <path + inkscape:connector-curvature="0" + id="path5009-5" + d="M 0,0 5,-5 -12.5,0 5,5 0,0 Z" + style="fill:#000080;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1pt;stroke-opacity:1" + transform="matrix(-0.8,0,0,-0.8,-10,0)" /> + </marker> + </defs> + <metadata + id="metadata7"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <g + transform="translate(-130.29351,-300.82484)" + id="layer1" + inkscape:groupmode="layer" + inkscape:label="Layer 1"> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="148.57143" + cy="449.89627" + cx="338.71756" + id="path4136" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" + d="m 318.19805,571.02449 0,-94.95433 -64.64976,-92.42896 164.14979,-30.80966 42.4264,120.71323 -141.92643,3.03046 100.0051,-123.23861 z" + id="path4301" + inkscape:connector-curvature="0" /> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" + d="m 318.70313,571.52957 -65.65992,-187.3833 206.5762,88.89343 z" + id="path4303" + inkscape:connector-curvature="0" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="450.05875" + cx="338.13837" + id="path4138" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4147" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,-261.85036,103.80999)" + style="fill:#000080"> + <defs + id="defs4149"> + <g + id="g4151"> + <symbol + id="textext-20f8880a-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4154" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1" + overflow="visible" + style="overflow:visible"> + <path + id="path4157" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2" + style="fill:#000080"> + <g + id="g4160" + style="fill:#000080;fill-opacity:1"> + <use + id="use4162" + y="134.765" + x="223.43201" + xlink:href="#textext-20f8880a-1" + width="100%" + height="100%" + style="fill:#000080" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="383.79077" + cx="252.85715" + id="path4138-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="353.07648" + cx="418.57144" + id="path4138-3-7" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="475.93362" + cx="317.85715" + id="path4138-3-0" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="570.21936" + cx="317.85715" + id="path4138-3-9" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="473.07648" + cx="459.28571" + id="path4138-3-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="478.07648" + cx="133.57143" + id="path4138-3-6" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="320.21936" + cx="155.71428" + id="path4138-3-06" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="340.73929" + cx="490.7774" + id="path4138-3-2" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="559.76758" + cx="490.60406" + id="path4138-3-61" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + id="g4147-8" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,-152.29409,72.785446)" + style="fill:#000000"> + <defs + id="defs4149-7"> + <g + id="g4151-9"> + <symbol + id="textext-20f8880a-0-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4154-0" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4157-3" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2-7" + style="fill:#000000" /> + </g> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4558" + style="fill:#000080" + transform="matrix(2.7020226,0,0,2.7020226,-254.3195,202.59004)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sigma \\subset L$"> + <defs + id="defs4560"> + <g + id="g4562"> + <symbol + id="textext-b73c230a-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4565" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-1" + overflow="visible" + style="overflow:visible"> + <path + id="path4568" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-2" + overflow="visible" + style="overflow:visible"> + <path + id="path4571" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-3" + overflow="visible" + style="overflow:visible"> + <path + id="path4574" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-4" + overflow="visible" + style="overflow:visible"> + <path + id="path4577" + d="m 6.5625,-4.984375 c 0.171875,0 0.359375,0 0.359375,-0.203125 0,-0.203125 -0.1875,-0.203125 -0.359375,-0.203125 l -2.671875,0 c -1.703125,0 -3.0625,1.296875 -3.0625,2.890625 0,1.609375 1.359375,2.90625 3.0625,2.90625 l 2.671875,0 c 0.171875,0 0.359375,0 0.359375,-0.203125 C 6.921875,0 6.734375,0 6.5625,0 L 3.90625,0 c -1.546875,0 -2.6875,-1.15625 -2.6875,-2.5 0,-1.328125 1.140625,-2.484375 2.6875,-2.484375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-b73c230a-5"> + <g + id="g4580" + style="fill:#000000;fill-opacity:1"> + <use + id="use4582" + y="134.765" + x="223.43201" + xlink:href="#textext-b73c230a-1" + width="100%" + height="100%" /> + </g> + <g + id="g4584" + style="fill:#000000;fill-opacity:1"> + <use + id="use4586" + y="134.765" + x="232.25" + xlink:href="#textext-b73c230a-4" + width="100%" + height="100%" /> + </g> + <g + id="g4588" + style="fill:#000000;fill-opacity:1"> + <use + id="use4590" + y="134.765" + x="242.76601" + xlink:href="#textext-b73c230a-2" + width="100%" + height="100%" /> + </g> + </g> + </g> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:#000080;fill-rule:evenodd;stroke:#000080;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Lend)" + d="m 337.85714,449.50504 148.57143,-8.57143" + id="path5000" + inkscape:connector-curvature="0" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + ns0:text="$\\sqrt{d(w,L)^2 + \\alpha^2}$" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + transform="matrix(1.3935573,-0.10159094,0.10159094,1.3935573,55.220877,276.38005)" + style="fill:#000080;stroke:#000080" + id="g5407"> + <defs + id="defs5409"> + <g + id="g5411"> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-0"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5414" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-1"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.234375,11.5625 c 0.296875,0 0.3125,-0.01563 0.40625,-0.203125 l 5.453125,-11.375 c 0.07813,-0.140625 0.07813,-0.15625 0.07813,-0.1875 0,-0.109375 -0.07813,-0.203125 -0.203125,-0.203125 -0.125,0 -0.171875,0.09375 -0.21875,0.203125 L 4.609375,10.53125 2.484375,5.578125 1.09375,6.65625 1.25,6.8125 1.953125,6.265625 Z m 0,0" + id="path5417" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-2"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5420" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-3"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 5.140625,-6.8125 c 0,0 0,-0.109375 -0.125,-0.109375 -0.15625,0 -1.09375,0.09375 -1.265625,0.109375 -0.078125,0.015625 -0.140625,0.0625 -0.140625,0.1875 0,0.125 0.09375,0.125 0.234375,0.125 0.484375,0 0.5,0.0625 0.5,0.171875 L 4.3125,-6.125 3.71875,-3.765625 C 3.53125,-4.140625 3.25,-4.40625 2.796875,-4.40625 c -1.15625,0 -2.390625,1.46875 -2.390625,2.921875 0,0.9375 0.546875,1.59375 1.3125,1.59375 0.203125,0 0.703125,-0.046875 1.296875,-0.75 0.078125,0.421875 0.4375,0.75 0.90625,0.75 0.359375,0 0.578125,-0.234375 0.75,-0.546875 0.15625,-0.359375 0.296875,-0.96875 0.296875,-0.984375 0,-0.109375 -0.09375,-0.109375 -0.125,-0.109375 -0.09375,0 -0.109375,0.046875 -0.140625,0.1875 -0.171875,0.640625 -0.34375,1.234375 -0.75,1.234375 -0.28125,0 -0.296875,-0.265625 -0.296875,-0.453125 0,-0.25 0.015625,-0.3125 0.046875,-0.484375 z m -2.0625,5.625 C 3.015625,-1 3.015625,-0.984375 2.875,-0.8125 2.4375,-0.265625 2.03125,-0.109375 1.75,-0.109375 c -0.5,0 -0.640625,-0.546875 -0.640625,-0.9375 0,-0.5 0.3125,-1.71875 0.546875,-2.1875 0.3125,-0.578125 0.75,-0.953125 1.15625,-0.953125 0.640625,0 0.78125,0.8125 0.78125,0.875 0,0.0625 -0.015625,0.125 -0.03125,0.171875 z m 0,0" + id="path5423" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-4"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + id="path5426" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-5"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 2.03125,-0.015625 c 0,-0.65625 -0.25,-1.046875 -0.640625,-1.046875 -0.328125,0 -0.53125,0.25 -0.53125,0.53125 C 0.859375,-0.265625 1.0625,0 1.390625,0 1.5,0 1.640625,-0.046875 1.734375,-0.125 1.765625,-0.15625 1.78125,-0.15625 1.78125,-0.15625 c 0.015625,0 0.015625,0 0.015625,0.140625 0,0.75 -0.34375,1.34375 -0.671875,1.671875 -0.109375,0.109375 -0.109375,0.125 -0.109375,0.15625 0,0.078125 0.046875,0.109375 0.09375,0.109375 0.109375,0 0.921875,-0.765625 0.921875,-1.9375 z m 0,0" + id="path5429" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-6"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + id="path5432" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-7"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.75,-2.359375 c 0,-1.5625 -0.921875,-2.046875 -1.65625,-2.046875 -1.375,0 -2.6875,1.421875 -2.6875,2.828125 0,0.9375 0.59375,1.6875 1.625,1.6875 0.625,0 1.34375,-0.234375 2.09375,-0.84375 0.125,0.53125 0.453125,0.84375 0.90625,0.84375 0.53125,0 0.84375,-0.546875 0.84375,-0.703125 0,-0.078125 -0.0625,-0.109375 -0.125,-0.109375 -0.0625,0 -0.09375,0.03125 -0.125,0.109375 -0.1875,0.484375 -0.546875,0.484375 -0.5625,0.484375 -0.3125,0 -0.3125,-0.78125 -0.3125,-1.015625 0,-0.203125 0,-0.234375 0.109375,-0.34375 C 5.796875,-2.65625 6,-3.8125 6,-3.8125 6,-3.84375 5.984375,-3.921875 5.875,-3.921875 c -0.09375,0 -0.09375,0.03125 -0.140625,0.21875 -0.1875,0.625 -0.515625,1.375 -0.984375,1.96875 z m -0.65625,1.375 c -0.890625,0.765625 -1.65625,0.875 -2.046875,0.875 -0.59375,0 -0.90625,-0.453125 -0.90625,-1.09375 0,-0.484375 0.265625,-1.5625 0.578125,-2.0625 C 2.1875,-4 2.734375,-4.1875 3.078125,-4.1875 c 0.984375,0 0.984375,1.3125 0.984375,2.078125 0,0.375 0,0.953125 0.03125,1.125 z m 0,0" + id="path5435" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-8"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5438" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-9"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 3.296875,2.390625 c 0,-0.03125 0,-0.046875 -0.171875,-0.21875 C 1.890625,0.921875 1.5625,-0.96875 1.5625,-2.5 c 0,-1.734375 0.375,-3.46875 1.609375,-4.703125 0.125,-0.125 0.125,-0.140625 0.125,-0.171875 0,-0.078125 -0.03125,-0.109375 -0.09375,-0.109375 -0.109375,0 -1,0.6875 -1.59375,1.953125 -0.5,1.09375 -0.625,2.203125 -0.625,3.03125 0,0.78125 0.109375,1.984375 0.65625,3.125 C 2.25,1.84375 3.09375,2.5 3.203125,2.5 c 0.0625,0 0.09375,-0.03125 0.09375,-0.109375 z m 0,0" + id="path5441" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-10"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 2.875,-2.5 c 0,-0.765625 -0.109375,-1.96875 -0.65625,-3.109375 -0.59375,-1.21875 -1.453125,-1.875 -1.546875,-1.875 -0.0625,0 -0.109375,0.046875 -0.109375,0.109375 0,0.03125 0,0.046875 0.1875,0.234375 0.984375,0.984375 1.546875,2.5625 1.546875,4.640625 0,1.71875 -0.359375,3.46875 -1.59375,4.71875 C 0.5625,2.34375 0.5625,2.359375 0.5625,2.390625 0.5625,2.453125 0.609375,2.5 0.671875,2.5 0.765625,2.5 1.671875,1.8125 2.25,0.546875 2.765625,-0.546875 2.875,-1.65625 2.875,-2.5 Z m 0,0" + id="path5444" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-11"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 4.078125,-2.296875 2.78125,0 C 7,-2.296875 7.1875,-2.296875 7.1875,-2.5 7.1875,-2.6875 7,-2.6875 6.859375,-2.6875 l -2.78125,0 0,-2.796875 c 0,-0.140625 0,-0.328125 -0.203125,-0.328125 -0.203125,0 -0.203125,0.1875 -0.203125,0.328125 l 0,2.796875 -2.78125,0 c -0.140625,0 -0.328125,0 -0.328125,0.1875 0,0.203125 0.1875,0.203125 0.328125,0.203125 l 2.78125,0 0,2.796875 c 0,0.140625 0,0.328125 0.203125,0.328125 0.203125,0 0.203125,-0.1875 0.203125,-0.328125 z m 0,0" + id="path5447" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-12"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="" + id="path5450" /> + </symbol> + <symbol + style="overflow:visible" + overflow="visible" + id="textext-da5ef958-13"> + <path + inkscape:connector-curvature="0" + style="stroke:none" + d="m 3.515625,-1.265625 -0.234375,0 c -0.015625,0.15625 -0.09375,0.5625 -0.1875,0.625 -0.046875,0.046875 -0.578125,0.046875 -0.6875,0.046875 l -1.28125,0 c 0.734375,-0.640625 0.984375,-0.84375 1.390625,-1.171875 0.515625,-0.40625 1,-0.84375 1,-1.5 0,-0.84375 -0.734375,-1.359375 -1.625,-1.359375 -0.859375,0 -1.453125,0.609375 -1.453125,1.25 0,0.34375 0.296875,0.390625 0.375,0.390625 0.15625,0 0.359375,-0.125 0.359375,-0.375 0,-0.125 -0.046875,-0.375 -0.40625,-0.375 C 0.984375,-4.21875 1.453125,-4.375 1.78125,-4.375 c 0.703125,0 1.0625,0.546875 1.0625,1.109375 0,0.609375 -0.4375,1.078125 -0.65625,1.328125 L 0.515625,-0.265625 C 0.4375,-0.203125 0.4375,-0.1875 0.4375,0 l 2.875,0 z m 0,0" + id="path5453" /> + </symbol> + </g> + </defs> + <g + style="fill:#000080;stroke:#000080" + id="textext-da5ef958-14"> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5456"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-1" + x="223.43201" + y="126.247" + id="use5458" /> + </g> + <path + inkscape:connector-curvature="0" + style="fill:#000080;stroke:#000080;stroke-width:0.398;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1" + d="m -4.6875e-4,0.001125 59.07031275,0" + transform="matrix(1,0,0,-1,233.395,126.048)" + id="path5460" /> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5462"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-3" + x="233.395" + y="134.765" + id="use5464" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5466"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-9" + x="238.58" + y="134.765" + id="use5468" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5470"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-4" + x="242.455" + y="134.765" + id="use5472" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5474"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-5" + x="249.85622" + y="134.765" + id="use5476" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5478"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-6" + x="254.28758" + y="134.765" + id="use5480" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5482"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-10" + x="261.06299" + y="134.765" + id="use5484" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5486"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-13" + x="264.93701" + y="131.88699" + id="use5488" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5490"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-11" + x="271.621" + y="134.765" + id="use5492" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5494"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-7" + x="281.58301" + y="134.765" + id="use5496" /> + </g> + <g + style="fill:#000080;fill-opacity:1;stroke:#000080" + id="g5498"> + <use + style="fill:#000080;stroke:#000080" + height="100%" + width="100%" + xlink:href="#textext-da5ef958-13" + x="287.99301" + y="131.88699" + id="use5500" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="148.57143" + cy="449.89627" + cx="738.71753" + id="path4136-7" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="450.05875" + cx="738.13837" + id="path4138-8" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4147-5" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$w$" + transform="matrix(2.7020226,0,0,2.7020226,138.14964,103.80999)" + style="fill:#000080"> + <defs + id="defs4149-9"> + <g + id="g4151-7"> + <symbol + id="textext-20f8880a-0-5" + overflow="visible" + style="overflow:visible"> + <path + id="path4154-3" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-20f8880a-1-8" + overflow="visible" + style="overflow:visible"> + <path + id="path4157-8" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-20f8880a-2-3" + style="fill:#000080"> + <g + id="g4160-1" + style="fill:#000080;fill-opacity:1"> + <use + id="use4162-8" + y="134.765" + x="223.43201" + xlink:href="#textext-20f8880a-1-8" + width="100%" + height="100%" + style="fill:#000080" /> + </g> + </g> + </g> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="342.37451" + cx="681.14148" + id="path4138-3-96" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="353.07648" + cx="818.57141" + id="path4138-3-7-4" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="492.09607" + cx="668.35968" + id="path4138-3-0-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="570.21936" + cx="717.85718" + id="path4138-3-9-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="473.07648" + cx="859.28564" + id="path4138-3-3-3" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="478.07648" + cx="533.57141" + id="path4138-3-6-8" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="350.52393" + cx="594.1001" + id="path4138-3-06-6" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="331.64792" + cx="927.14288" + id="path4138-3-2-0" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <circle + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + r="2.7779195" + cy="505.21936" + cx="930" + id="path4138-3-61-4" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:1;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:#ffffff;fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + id="g4558-8" + style="fill:#000080" + transform="matrix(2.7020226,0,0,2.7020226,145.6805,202.59004)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sigma \\subset L$"> + <defs + id="defs4560-8"> + <g + id="g4562-8"> + <symbol + id="textext-b73c230a-0-9" + overflow="visible" + style="overflow:visible"> + <path + id="path4565-7" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-1-7" + overflow="visible" + style="overflow:visible"> + <path + id="path4568-6" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-2-4" + overflow="visible" + style="overflow:visible"> + <path + id="path4571-3" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-3-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4574-3" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-b73c230a-4-0" + overflow="visible" + style="overflow:visible"> + <path + id="path4577-9" + d="m 6.5625,-4.984375 c 0.171875,0 0.359375,0 0.359375,-0.203125 0,-0.203125 -0.1875,-0.203125 -0.359375,-0.203125 l -2.671875,0 c -1.703125,0 -3.0625,1.296875 -3.0625,2.890625 0,1.609375 1.359375,2.90625 3.0625,2.90625 l 2.671875,0 c 0.171875,0 0.359375,0 0.359375,-0.203125 C 6.921875,0 6.734375,0 6.5625,0 L 3.90625,0 c -1.546875,0 -2.6875,-1.15625 -2.6875,-2.5 0,-1.328125 1.140625,-2.484375 2.6875,-2.484375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-b73c230a-5-2"> + <g + id="g4580-5" + style="fill:#000000;fill-opacity:1"> + <use + id="use4582-4" + y="134.765" + x="223.43201" + xlink:href="#textext-b73c230a-1-7" + width="100%" + height="100%" /> + </g> + <g + id="g4584-0" + style="fill:#000000;fill-opacity:1"> + <use + id="use4586-5" + y="134.765" + x="232.25" + xlink:href="#textext-b73c230a-4-0" + width="100%" + height="100%" /> + </g> + <g + id="g4588-9" + style="fill:#000000;fill-opacity:1"> + <use + id="use4590-4" + y="134.765" + x="242.76601" + xlink:href="#textext-b73c230a-2-4" + width="100%" + height="100%" /> + </g> + </g> + </g> + <path + inkscape:export-ydpi="90" + inkscape:export-xdpi="90" + style="fill:#000080;fill-rule:evenodd;stroke:#000080;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Lend-8)" + d="m 737.85714,449.50504 148.57143,-8.57143" + id="path5000-6" + inkscape:connector-curvature="0" /> + <circle + r="80.779091" + cy="449.46512" + cx="737.3952" + id="path6334" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:0.98999999;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1.06622958;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:3.19868871, 3.19868871;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + <g + id="g6495" + style="fill:#000080;stroke:#000080" + transform="matrix(1.3952558,-0.07472613,0.07472613,1.3952558,431.03302,272.05923)" + ns0:preamble="/home/siarzhuk/GitDrive/2015Gudhi/Aid/preamble.ini" + ns0:text="$\\sqrt{d(w,L \\setminus \\sigma)^2 + \\alpha^2}$"> + <defs + id="defs6497"> + <g + id="g6499"> + <symbol + id="textext-c0d6e8dc-0" + overflow="visible" + style="overflow:visible"> + <path + id="path6502" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-1" + overflow="visible" + style="overflow:visible"> + <path + id="path6505" + d="m 4.234375,11.5625 c 0.296875,0 0.3125,-0.01563 0.40625,-0.203125 l 5.453125,-11.375 c 0.07813,-0.140625 0.07813,-0.15625 0.07813,-0.1875 0,-0.109375 -0.07813,-0.203125 -0.203125,-0.203125 -0.125,0 -0.171875,0.09375 -0.21875,0.203125 L 4.609375,10.53125 2.484375,5.578125 1.09375,6.65625 1.25,6.8125 1.953125,6.265625 Z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-2" + overflow="visible" + style="overflow:visible"> + <path + id="path6508" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-3" + overflow="visible" + style="overflow:visible"> + <path + id="path6511" + d="m 5.140625,-6.8125 c 0,0 0,-0.109375 -0.125,-0.109375 -0.15625,0 -1.09375,0.09375 -1.265625,0.109375 -0.078125,0.015625 -0.140625,0.0625 -0.140625,0.1875 0,0.125 0.09375,0.125 0.234375,0.125 0.484375,0 0.5,0.0625 0.5,0.171875 L 4.3125,-6.125 3.71875,-3.765625 C 3.53125,-4.140625 3.25,-4.40625 2.796875,-4.40625 c -1.15625,0 -2.390625,1.46875 -2.390625,2.921875 0,0.9375 0.546875,1.59375 1.3125,1.59375 0.203125,0 0.703125,-0.046875 1.296875,-0.75 0.078125,0.421875 0.4375,0.75 0.90625,0.75 0.359375,0 0.578125,-0.234375 0.75,-0.546875 0.15625,-0.359375 0.296875,-0.96875 0.296875,-0.984375 0,-0.109375 -0.09375,-0.109375 -0.125,-0.109375 -0.09375,0 -0.109375,0.046875 -0.140625,0.1875 -0.171875,0.640625 -0.34375,1.234375 -0.75,1.234375 -0.28125,0 -0.296875,-0.265625 -0.296875,-0.453125 0,-0.25 0.015625,-0.3125 0.046875,-0.484375 z m -2.0625,5.625 C 3.015625,-1 3.015625,-0.984375 2.875,-0.8125 2.4375,-0.265625 2.03125,-0.109375 1.75,-0.109375 c -0.5,0 -0.640625,-0.546875 -0.640625,-0.9375 0,-0.5 0.3125,-1.71875 0.546875,-2.1875 0.3125,-0.578125 0.75,-0.953125 1.15625,-0.953125 0.640625,0 0.78125,0.8125 0.78125,0.875 0,0.0625 -0.015625,0.125 -0.03125,0.171875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-4" + overflow="visible" + style="overflow:visible"> + <path + id="path6514" + d="M 4.609375,-3.375 C 4.65625,-3.59375 4.75,-3.96875 4.75,-4.03125 c 0,-0.171875 -0.140625,-0.265625 -0.28125,-0.265625 -0.125,0 -0.296875,0.078125 -0.375,0.28125 -0.03125,0.0625 -0.5,1.96875 -0.5625,2.234375 C 3.453125,-1.484375 3.4375,-1.3125 3.4375,-1.125 c 0,0.109375 0,0.125 0.015625,0.171875 -0.234375,0.53125 -0.53125,0.84375 -0.921875,0.84375 -0.796875,0 -0.796875,-0.734375 -0.796875,-0.90625 0,-0.3125 0.046875,-0.703125 0.515625,-1.9375 0.109375,-0.296875 0.171875,-0.4375 0.171875,-0.640625 0,-0.4375 -0.328125,-0.8125 -0.8125,-0.8125 -0.953125,0 -1.3125,1.453125 -1.3125,1.53125 0,0.109375 0.09375,0.109375 0.109375,0.109375 0.109375,0 0.109375,-0.03125 0.15625,-0.1875 C 0.84375,-3.875 1.21875,-4.1875 1.578125,-4.1875 c 0.09375,0 0.25,0.015625 0.25,0.328125 0,0.25 -0.109375,0.53125 -0.1875,0.703125 -0.4375,1.171875 -0.546875,1.625 -0.546875,2.015625 0,0.90625 0.65625,1.25 1.40625,1.25 0.171875,0 0.640625,0 1.03125,-0.703125 0.265625,0.640625 0.953125,0.703125 1.25,0.703125 0.75,0 1.1875,-0.625 1.453125,-1.21875 0.328125,-0.78125 0.65625,-2.125 0.65625,-2.59375 0,-0.546875 -0.265625,-0.703125 -0.4375,-0.703125 -0.25,0 -0.5,0.265625 -0.5,0.484375 0,0.125 0.0625,0.1875 0.140625,0.265625 0.109375,0.109375 0.359375,0.359375 0.359375,0.84375 0,0.34375 -0.28125,1.3125 -0.546875,1.828125 -0.25,0.53125 -0.609375,0.875 -1.09375,0.875 -0.46875,0 -0.734375,-0.296875 -0.734375,-0.875 0,-0.265625 0.0625,-0.578125 0.109375,-0.71875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-5" + overflow="visible" + style="overflow:visible"> + <path + id="path6517" + d="m 2.03125,-0.015625 c 0,-0.65625 -0.25,-1.046875 -0.640625,-1.046875 -0.328125,0 -0.53125,0.25 -0.53125,0.53125 C 0.859375,-0.265625 1.0625,0 1.390625,0 1.5,0 1.640625,-0.046875 1.734375,-0.125 1.765625,-0.15625 1.78125,-0.15625 1.78125,-0.15625 c 0.015625,0 0.015625,0 0.015625,0.140625 0,0.75 -0.34375,1.34375 -0.671875,1.671875 -0.109375,0.109375 -0.109375,0.125 -0.109375,0.15625 0,0.078125 0.046875,0.109375 0.09375,0.109375 0.109375,0 0.921875,-0.765625 0.921875,-1.9375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-6" + overflow="visible" + style="overflow:visible"> + <path + id="path6520" + d="M 3.734375,-6.03125 C 3.8125,-6.390625 3.84375,-6.5 4.78125,-6.5 c 0.296875,0 0.375,0 0.375,-0.1875 0,-0.125 -0.109375,-0.125 -0.15625,-0.125 -0.328125,0 -1.140625,0.03125 -1.46875,0.03125 -0.296875,0 -1.03125,-0.03125 -1.328125,-0.03125 -0.0625,0 -0.1875,0 -0.1875,0.203125 0,0.109375 0.09375,0.109375 0.28125,0.109375 0.015625,0 0.203125,0 0.375,0.015625 0.171875,0.03125 0.265625,0.03125 0.265625,0.171875 0,0.03125 0,0.0625 -0.03125,0.1875 L 1.5625,-0.78125 c -0.09375,0.390625 -0.109375,0.46875 -0.90625,0.46875 -0.171875,0 -0.265625,0 -0.265625,0.203125 C 0.390625,0 0.484375,0 0.65625,0 l 4.625,0 C 5.515625,0 5.515625,0 5.578125,-0.171875 L 6.375,-2.328125 c 0.03125,-0.109375 0.03125,-0.125 0.03125,-0.140625 0,-0.03125 -0.03125,-0.109375 -0.109375,-0.109375 -0.09375,0 -0.109375,0.0625 -0.171875,0.21875 -0.34375,0.90625 -0.78125,2.046875 -2.5,2.046875 l -0.9375,0 c -0.140625,0 -0.171875,0 -0.21875,0 -0.109375,-0.015625 -0.140625,-0.03125 -0.140625,-0.109375 0,-0.03125 0,-0.046875 0.046875,-0.21875 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-7" + overflow="visible" + style="overflow:visible"> + <path + id="path6523" + d="m 5.15625,-3.71875 c 0.140625,0 0.5,0 0.5,-0.34375 0,-0.234375 -0.21875,-0.234375 -0.390625,-0.234375 l -2.28125,0 c -1.5,0 -2.609375,1.640625 -2.609375,2.828125 0,0.875 0.59375,1.578125 1.5,1.578125 1.171875,0 2.5,-1.203125 2.5,-2.734375 0,-0.171875 0,-0.65625 -0.3125,-1.09375 z M 1.890625,-0.109375 C 1.390625,-0.109375 1,-0.46875 1,-1.1875 c 0,-0.296875 0.109375,-1.109375 0.46875,-1.703125 0.421875,-0.6875 1.015625,-0.828125 1.359375,-0.828125 0.828125,0 0.90625,0.65625 0.90625,0.96875 0,0.46875 -0.203125,1.28125 -0.53125,1.796875 -0.390625,0.578125 -0.9375,0.84375 -1.3125,0.84375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-8" + overflow="visible" + style="overflow:visible"> + <path + id="path6526" + d="m 4.75,-2.359375 c 0,-1.5625 -0.921875,-2.046875 -1.65625,-2.046875 -1.375,0 -2.6875,1.421875 -2.6875,2.828125 0,0.9375 0.59375,1.6875 1.625,1.6875 0.625,0 1.34375,-0.234375 2.09375,-0.84375 0.125,0.53125 0.453125,0.84375 0.90625,0.84375 0.53125,0 0.84375,-0.546875 0.84375,-0.703125 0,-0.078125 -0.0625,-0.109375 -0.125,-0.109375 -0.0625,0 -0.09375,0.03125 -0.125,0.109375 -0.1875,0.484375 -0.546875,0.484375 -0.5625,0.484375 -0.3125,0 -0.3125,-0.78125 -0.3125,-1.015625 0,-0.203125 0,-0.234375 0.109375,-0.34375 C 5.796875,-2.65625 6,-3.8125 6,-3.8125 6,-3.84375 5.984375,-3.921875 5.875,-3.921875 c -0.09375,0 -0.09375,0.03125 -0.140625,0.21875 -0.1875,0.625 -0.515625,1.375 -0.984375,1.96875 z m -0.65625,1.375 c -0.890625,0.765625 -1.65625,0.875 -2.046875,0.875 -0.59375,0 -0.90625,-0.453125 -0.90625,-1.09375 0,-0.484375 0.265625,-1.5625 0.578125,-2.0625 C 2.1875,-4 2.734375,-4.1875 3.078125,-4.1875 c 0.984375,0 0.984375,1.3125 0.984375,2.078125 0,0.375 0,0.953125 0.03125,1.125 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-9" + overflow="visible" + style="overflow:visible"> + <path + id="path6529" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-10" + overflow="visible" + style="overflow:visible"> + <path + id="path6532" + d="m 3.296875,2.390625 c 0,-0.03125 0,-0.046875 -0.171875,-0.21875 C 1.890625,0.921875 1.5625,-0.96875 1.5625,-2.5 c 0,-1.734375 0.375,-3.46875 1.609375,-4.703125 0.125,-0.125 0.125,-0.140625 0.125,-0.171875 0,-0.078125 -0.03125,-0.109375 -0.09375,-0.109375 -0.109375,0 -1,0.6875 -1.59375,1.953125 -0.5,1.09375 -0.625,2.203125 -0.625,3.03125 0,0.78125 0.109375,1.984375 0.65625,3.125 C 2.25,1.84375 3.09375,2.5 3.203125,2.5 c 0.0625,0 0.09375,-0.03125 0.09375,-0.109375 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-11" + overflow="visible" + style="overflow:visible"> + <path + id="path6535" + d="m 2.875,-2.5 c 0,-0.765625 -0.109375,-1.96875 -0.65625,-3.109375 -0.59375,-1.21875 -1.453125,-1.875 -1.546875,-1.875 -0.0625,0 -0.109375,0.046875 -0.109375,0.109375 0,0.03125 0,0.046875 0.1875,0.234375 0.984375,0.984375 1.546875,2.5625 1.546875,4.640625 0,1.71875 -0.359375,3.46875 -1.59375,4.71875 C 0.5625,2.34375 0.5625,2.359375 0.5625,2.390625 0.5625,2.453125 0.609375,2.5 0.671875,2.5 0.765625,2.5 1.671875,1.8125 2.25,0.546875 2.765625,-0.546875 2.875,-1.65625 2.875,-2.5 Z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-12" + overflow="visible" + style="overflow:visible"> + <path + id="path6538" + d="m 4.078125,-2.296875 2.78125,0 C 7,-2.296875 7.1875,-2.296875 7.1875,-2.5 7.1875,-2.6875 7,-2.6875 6.859375,-2.6875 l -2.78125,0 0,-2.796875 c 0,-0.140625 0,-0.328125 -0.203125,-0.328125 -0.203125,0 -0.203125,0.1875 -0.203125,0.328125 l 0,2.796875 -2.78125,0 c -0.140625,0 -0.328125,0 -0.328125,0.1875 0,0.203125 0.1875,0.203125 0.328125,0.203125 l 2.78125,0 0,2.796875 c 0,0.140625 0,0.328125 0.203125,0.328125 0.203125,0 0.203125,-0.1875 0.203125,-0.328125 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-13" + overflow="visible" + style="overflow:visible"> + <path + id="path6541" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-14" + overflow="visible" + style="overflow:visible"> + <path + id="path6544" + d="m 4,2.25 c 0.046875,0.140625 0.09375,0.25 0.234375,0.25 0.109375,0 0.1875,-0.09375 0.1875,-0.203125 0,-0.03125 0,-0.046875 -0.046875,-0.15625 l -3.40625,-9.375 c -0.0625,-0.171875 -0.09375,-0.25 -0.21875,-0.25 -0.109375,0 -0.203125,0.09375 -0.203125,0.203125 0,0.03125 0,0.046875 0.046875,0.15625 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-15" + overflow="visible" + style="overflow:visible"> + <path + id="path6547" + d="" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + <symbol + id="textext-c0d6e8dc-16" + overflow="visible" + style="overflow:visible"> + <path + id="path6550" + d="m 3.515625,-1.265625 -0.234375,0 c -0.015625,0.15625 -0.09375,0.5625 -0.1875,0.625 -0.046875,0.046875 -0.578125,0.046875 -0.6875,0.046875 l -1.28125,0 c 0.734375,-0.640625 0.984375,-0.84375 1.390625,-1.171875 0.515625,-0.40625 1,-0.84375 1,-1.5 0,-0.84375 -0.734375,-1.359375 -1.625,-1.359375 -0.859375,0 -1.453125,0.609375 -1.453125,1.25 0,0.34375 0.296875,0.390625 0.375,0.390625 0.15625,0 0.359375,-0.125 0.359375,-0.375 0,-0.125 -0.046875,-0.375 -0.40625,-0.375 C 0.984375,-4.21875 1.453125,-4.375 1.78125,-4.375 c 0.703125,0 1.0625,0.546875 1.0625,1.109375 0,0.609375 -0.4375,1.078125 -0.65625,1.328125 L 0.515625,-0.265625 C 0.4375,-0.203125 0.4375,-0.1875 0.4375,0 l 2.875,0 z m 0,0" + style="stroke:none" + inkscape:connector-curvature="0" /> + </symbol> + </g> + </defs> + <g + id="textext-c0d6e8dc-17" + style="fill:#000080;stroke:#000080"> + <g + id="g6553" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6555" + y="126.247" + x="223.43201" + xlink:href="#textext-c0d6e8dc-1" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <path + id="path6557" + transform="matrix(1,0,0,-1,233.395,126.048)" + d="m -4.6875e-4,0.001125 74.52734375,0" + style="fill:#000080;stroke:#000080;stroke-width:0.398;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-opacity:1" + inkscape:connector-curvature="0" /> + <g + id="g6559" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6561" + y="134.765" + x="233.395" + xlink:href="#textext-c0d6e8dc-3" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6563" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6565" + y="134.765" + x="238.58" + xlink:href="#textext-c0d6e8dc-10" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6567" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6569" + y="134.765" + x="242.455" + xlink:href="#textext-c0d6e8dc-4" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6571" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6573" + y="134.765" + x="249.85622" + xlink:href="#textext-c0d6e8dc-5" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6575" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6577" + y="134.765" + x="254.28758" + xlink:href="#textext-c0d6e8dc-6" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6579" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6581" + y="134.765" + x="263.27701" + xlink:href="#textext-c0d6e8dc-14" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6583" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6585" + y="134.765" + x="270.47198" + xlink:href="#textext-c0d6e8dc-7" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6587" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6589" + y="134.765" + x="276.522" + xlink:href="#textext-c0d6e8dc-11" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6591" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6593" + y="131.88699" + x="280.397" + xlink:href="#textext-c0d6e8dc-16" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6595" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6597" + y="134.765" + x="287.07999" + xlink:href="#textext-c0d6e8dc-12" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6599" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6601" + y="134.765" + x="297.043" + xlink:href="#textext-c0d6e8dc-8" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + <g + id="g6603" + style="fill:#000080;fill-opacity:1;stroke:#000080"> + <use + id="use6605" + y="131.88699" + x="303.453" + xlink:href="#textext-c0d6e8dc-16" + width="100%" + height="100%" + style="fill:#000080;stroke:#000080" /> + </g> + </g> + </g> + </g> + <g + transform="translate(-130.29351,-300.82484)" + style="display:none" + inkscape:label="Layer 2" + id="layer2" + inkscape:groupmode="layer"> + <circle + r="32.857143" + cy="448.79074" + cx="337.85715" + id="path5639" + style="color:#000000;clip-rule:nonzero;display:inline;overflow:visible;visibility:visible;opacity:0.98999999;isolation:auto;mix-blend-mode:normal;color-interpolation:sRGB;color-interpolation-filters:linearRGB;solid-color:#000000;solid-opacity:1;fill:none;fill-opacity:1;fill-rule:evenodd;stroke:#000080;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:3, 3;stroke-dashoffset:0;stroke-opacity:1;marker:none;color-rendering:auto;image-rendering:auto;shape-rendering:auto;text-rendering:auto;enable-background:accumulate" /> + </g> +</svg> diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index 857ec819..9990c541 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -1,17 +1,48 @@ cmake_minimum_required(VERSION 2.6) project(Witness_complex_examples) -# A simple example - add_executable( witness_complex_from_file witness_complex_from_file.cpp ) - add_test( witness_complex_from_bunny ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file - ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off 100) +add_executable ( Witness_complex_example_nearest_landmark_table example_nearest_landmark_table.cpp ) +target_link_libraries(Witness_complex_example_nearest_landmark_table ${Boost_SYSTEM_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(Witness_complex_example_nearest_landmark_table ${TBB_LIBRARIES}) +endif() +add_test(Witness_complex_test_nearest_landmark_table Witness_complex_example_nearest_landmark_table) +# CGAL and Eigen3 are required for Euclidean version of Witness if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.6.0) if (EIGEN3_FOUND) - add_executable ( witness_complex_sphere witness_complex_sphere.cpp ) - target_link_libraries(witness_complex_sphere ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test( witness_complex_sphere_10 ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_sphere 10) + add_executable( Witness_complex_example_off example_witness_complex_off.cpp ) + target_link_libraries(Witness_complex_example_off ${Boost_SYSTEM_LIBRARY}) + add_executable( Witness_complex_example_strong_off example_strong_witness_complex_off.cpp ) + target_link_libraries(Witness_complex_example_strong_off ${Boost_SYSTEM_LIBRARY}) + add_executable ( Witness_complex_example_sphere example_witness_complex_sphere.cpp ) + target_link_libraries(Witness_complex_example_sphere ${Boost_SYSTEM_LIBRARY}) + + add_executable ( Witness_complex_example_witness_persistence example_witness_complex_persistence.cpp ) + target_link_libraries(Witness_complex_example_witness_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + + add_executable ( Witness_complex_example_strong_witness_persistence example_strong_witness_persistence.cpp ) + target_link_libraries(Witness_complex_example_strong_witness_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + + if (TBB_FOUND) + target_link_libraries(Witness_complex_example_witness_persistence ${TBB_LIBRARIES}) + target_link_libraries(Witness_complex_example_strong_witness_persistence ${TBB_LIBRARIES}) + endif() + + add_test(Witness_complex_off_test_torus + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_off + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off 20 1.0 3) + add_test(Witness_complex_strong_off_test_torus + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_strong_off + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off 20 1.0 3) + add_test(Witness_complex_test_sphere_10 Witness_complex_example_sphere 10) + add_test(Witness_complex_test_torus_persistence + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_witness_persistence + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off -l 20 -a 0.5) + add_test(Witness_complex_strong_test_torus_persistence + ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_example_strong_witness_persistence + ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off -l 20 -a 0.5) endif(EIGEN3_FOUND) endif (NOT CGAL_VERSION VERSION_LESS 4.6.0) endif() diff --git a/src/Witness_complex/example/example_nearest_landmark_table.cpp b/src/Witness_complex/example/example_nearest_landmark_table.cpp new file mode 100644 index 00000000..b8594212 --- /dev/null +++ b/src/Witness_complex/example/example_nearest_landmark_table.cpp @@ -0,0 +1,69 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (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/>. + */ + +#define BOOST_PARAMETER_MAX_ARITY 12 + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> +#include <fstream> +#include <utility> +#include <string> +#include <vector> + +int main(int argc, char * const argv[]) { + using Nearest_landmark_range = std::vector<std::pair<std::size_t, double>>; + using Nearest_landmark_table = std::vector<Nearest_landmark_range>; + using Witness_complex = Gudhi::witness_complex::Witness_complex<Nearest_landmark_table>; + using Simplex_tree = Gudhi::Simplex_tree<>; + using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; + using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology<Simplex_tree, Field_Zp>; + + Simplex_tree simplex_tree; + Nearest_landmark_table nlt; + + // Example contains 5 witnesses and 5 landmarks + Nearest_landmark_range w0 = {std::make_pair(0, 0), std::make_pair(1, 1), std::make_pair(2, 2), + std::make_pair(3, 3), std::make_pair(4, 4)}; nlt.push_back(w0); + Nearest_landmark_range w1 = {std::make_pair(1, 0), std::make_pair(2, 1), std::make_pair(3, 2), + std::make_pair(4, 3), std::make_pair(0, 4)}; nlt.push_back(w1); + Nearest_landmark_range w2 = {std::make_pair(2, 0), std::make_pair(3, 1), std::make_pair(4, 2), + std::make_pair(0, 3), std::make_pair(1, 4)}; nlt.push_back(w2); + Nearest_landmark_range w3 = {std::make_pair(3, 0), std::make_pair(4, 1), std::make_pair(0, 2), + std::make_pair(1, 3), std::make_pair(2, 4)}; nlt.push_back(w3); + Nearest_landmark_range w4 = {std::make_pair(4, 0), std::make_pair(0, 1), std::make_pair(1, 2), + std::make_pair(2, 3), std::make_pair(3, 4)}; nlt.push_back(w4); + + Witness_complex witness_complex(nlt); + witness_complex.create_complex(simplex_tree, 4.1); + + std::cout << "Number of simplices: " << simplex_tree.num_simplices() << std::endl; + + Persistent_cohomology pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(11); + + pcoh.compute_persistent_cohomology(-0.1); + pcoh.output_diagram(); +} diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/example_strong_witness_complex_off.cpp index 5dd18d0a..0ee9ee90 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/example_strong_witness_complex_off.cpp @@ -4,7 +4,7 @@ * * Author(s): Siargey Kachanovich * - * Copyright (C) 2015 INRIA + * Copyright (C) 2016 INRIA (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 @@ -20,15 +20,12 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <sys/types.h> -#include <sys/stat.h> - -#include <gudhi/Points_off_io.h> #include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> +#include <gudhi/Euclidean_strong_witness_complex.h> #include <gudhi/pick_n_random_points.h> -#include <gudhi/reader_utils.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> #include <iostream> #include <fstream> @@ -36,49 +33,47 @@ #include <string> #include <vector> -typedef Gudhi::Simplex_tree<> Simplex_tree; -typedef std::vector< Simplex_tree::Vertex_handle > typeVectorVertex; -typedef std::vector< std::vector <double> > Point_Vector; +using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; +using Point_d = typename K::Point_d; +using Witness_complex = Gudhi::witness_complex::Euclidean_strong_witness_complex<K>; +using Point_vector = std::vector<Point_d>; int main(int argc, char * const argv[]) { - if (argc != 3) { + if (argc != 5) { std::cerr << "Usage: " << argv[0] - << " path_to_point_file.off nbL \n"; + << " path_to_point_file number_of_landmarks max_squared_alpha limit_dimension\n"; return 0; } - std::string off_file_name = argv[1]; - int nbL = atoi(argv[2]); + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); clock_t start, end; + Gudhi::Simplex_tree<> simplex_tree; - // Construct the Simplex Tree - Simplex_tree simplex_tree; - - // Read the OFF file (input file name given as parameter) and triangulate points - Gudhi::Points_off_reader<std::vector <double>> off_reader(off_file_name); - // Check the read operation was correct - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_name << std::endl; - } // Read the point file - Point_Vector point_vector = off_reader.get_point_cloud(); + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Strong witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + point_vector = Point_vector(off_reader.get_point_cloud()); + std::cout << "Successfully read " << point_vector.size() << " points.\n"; - std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; + std::cout << "Ambient dimension is " << point_vector[0].dimension() << ".\n"; // Choose landmarks - start = clock(); - std::vector<std::vector< int > > knn; - Point_Vector landmarks; - Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(point_vector, landmarks, knn); - end = clock(); - std::cout << "Landmark choice for " << nbL << " landmarks took " - << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); // Compute witness complex start = clock(); - Gudhi::witness_complex::witness_complex(knn, nbL, point_vector[0].size(), simplex_tree); + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); end = clock(); - std::cout << "Witness complex took " + std::cout << "Strong witness complex took " << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\n"; } diff --git a/src/Witness_complex/example/example_strong_witness_persistence.cpp b/src/Witness_complex/example/example_strong_witness_persistence.cpp new file mode 100644 index 00000000..f786fe7b --- /dev/null +++ b/src/Witness_complex/example/example_strong_witness_persistence.cpp @@ -0,0 +1,171 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (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/>. + */ + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Euclidean_strong_witness_complex.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_off_io.h> +#include <gudhi/pick_n_random_points.h> + +#include <boost/program_options.hpp> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> +#include <limits> // infinity + +using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; +using Point_d = K::Point_d; + +using Point_vector = std::vector<Point_d>; +using Strong_witness_complex = Gudhi::witness_complex::Euclidean_strong_witness_complex<K>; +using SimplexTree = Gudhi::Simplex_tree<>; + +using Filtration_value = SimplexTree::Filtration_value; + +using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology<SimplexTree, Field_Zp>; + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string file_name; + std::string filediag; + Filtration_value max_squared_alpha; + int p, nbL, lim_d; + Filtration_value min_persistence; + SimplexTree simplex_tree; + + program_options(argc, argv, nbL, file_name, filediag, max_squared_alpha, p, lim_d, min_persistence); + + // Extract the points from the file file_name + Point_vector witnesses, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + witnesses = Point_vector(off_reader.get_point_cloud()); + std::cout << "Successfully read " << witnesses.size() << " points.\n"; + std::cout << "Ambient dimension is " << witnesses[0].dimension() << ".\n"; + + // Choose landmarks from witnesses + Gudhi::subsampling::pick_n_random_points(witnesses, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Strong_witness_complex strong_witness_complex(landmarks, + witnesses); + + strong_witness_complex.create_complex(simplex_tree, max_squared_alpha, lim_d); + + std::cout << "The complex contains " << simplex_tree.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << simplex_tree.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&file_name), + "Name of file containing a point set in off format."); + + po::options_description visible("Allowed options", 100); + Filtration_value default_alpha = std::numeric_limits<Filtration_value>::infinity(); + visible.add_options() + ("help,h", "produce help message") + ("landmarks,l", po::value<int>(&nbL), + "Number of landmarks to choose from the point cloud.") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-sq-alpha,a", po::value<Filtration_value>(&max_squared_alpha)->default_value(default_alpha), + "Maximal squared relaxation parameter.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence)->default_value(0), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(std::numeric_limits<int>::max()), + "Maximal dimension of the strong witness complex we want to compute."); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + po::variables_map vm; + + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Strong witness complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} + diff --git a/src/Witness_complex/example/example_witness_complex_off.cpp b/src/Witness_complex/example/example_witness_complex_off.cpp new file mode 100644 index 00000000..b36dac0d --- /dev/null +++ b/src/Witness_complex/example/example_witness_complex_off.cpp @@ -0,0 +1,60 @@ +#include <sys/types.h> +#include <sys/stat.h> + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Euclidean_witness_complex.h> +#include <gudhi/pick_n_random_points.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> + +#include <iostream> +#include <fstream> +#include <ctime> +#include <string> +#include <vector> + +using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; +using Point_d = K::Point_d; +using Witness_complex = Gudhi::witness_complex::Euclidean_witness_complex<K>; +using Point_vector = std::vector< Point_d >; + +int main(int argc, char * const argv[]) { + if (argc != 5) { + std::cerr << "Usage: " << argv[0] + << " path_to_point_file number_of_landmarks max_squared_alpha limit_dimension\n"; + return 0; + } + + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); + clock_t start, end; + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + point_vector = Point_vector(off_reader.get_point_cloud()); + + std::cout << "Successfully read " << point_vector.size() << " points.\n"; + std::cout << "Ambient dimension is " << point_vector[0].dimension() << ".\n"; + + // Choose landmarks + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + start = clock(); + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); + end = clock(); + std::cout << "Witness complex took " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\n"; +} diff --git a/src/Witness_complex/example/example_witness_complex_persistence.cpp b/src/Witness_complex/example/example_witness_complex_persistence.cpp new file mode 100644 index 00000000..a1146922 --- /dev/null +++ b/src/Witness_complex/example/example_witness_complex_persistence.cpp @@ -0,0 +1,171 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (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/>. + */ + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Euclidean_witness_complex.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_off_io.h> +#include <gudhi/pick_n_random_points.h> + +#include <boost/program_options.hpp> + +#include <CGAL/Epick_d.h> + +#include <string> +#include <vector> +#include <limits> // infinity + +using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; +using Point_d = K::Point_d; + +using Point_vector = std::vector<Point_d>; +using Witness_complex = Gudhi::witness_complex::Euclidean_witness_complex<K>; +using SimplexTree = Gudhi::Simplex_tree<>; + +using Filtration_value = SimplexTree::Filtration_value; + +using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology<SimplexTree, Field_Zp>; + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string file_name; + std::string filediag; + Filtration_value max_squared_alpha; + int p, nbL, lim_d; + Filtration_value min_persistence; + SimplexTree simplex_tree; + + program_options(argc, argv, nbL, file_name, filediag, max_squared_alpha, p, lim_d, min_persistence); + + // Extract the points from the file file_name + Point_vector witnesses, landmarks; + Gudhi::Points_off_reader<Point_d> off_reader(file_name); + if (!off_reader.is_valid()) { + std::cerr << "Witness complex - Unable to read file " << file_name << "\n"; + exit(-1); // ----- >> + } + witnesses = Point_vector(off_reader.get_point_cloud()); + std::cout << "Successfully read " << witnesses.size() << " points.\n"; + std::cout << "Ambient dimension is " << witnesses[0].dimension() << ".\n"; + + // Choose landmarks from witnesses + Gudhi::subsampling::pick_n_random_points(witnesses, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Witness_complex witness_complex(landmarks, + witnesses); + + witness_complex.create_complex(simplex_tree, max_squared_alpha, lim_d); + + std::cout << "The complex contains " << simplex_tree.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << simplex_tree.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + + +void program_options(int argc, char * argv[] + , int & nbL + , std::string & file_name + , std::string & filediag + , Filtration_value & max_squared_alpha + , int & p + , int & dim_max + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&file_name), + "Name of file containing a point set in off format."); + + Filtration_value default_alpha = std::numeric_limits<Filtration_value>::infinity(); + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("landmarks,l", po::value<int>(&nbL), + "Number of landmarks to choose from the point cloud.") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-sq-alpha,a", po::value<Filtration_value>(&max_squared_alpha)->default_value(default_alpha), + "Maximal squared relaxation parameter.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence)->default_value(0), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(std::numeric_limits<int>::max()), + "Maximal dimension of the weak witness complex we want to compute."); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + po::variables_map vm; + + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Weak witness complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/src/Witness_complex/example/witness_complex_sphere.cpp b/src/Witness_complex/example/example_witness_complex_sphere.cpp index 60e02225..06fe3889 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/example_witness_complex_sphere.cpp @@ -4,7 +4,7 @@ * * Author(s): Siargey Kachanovich * - * Copyright (C) 2015 INRIA + * Copyright (C) 2016 INRIA (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 @@ -19,18 +19,16 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#define BOOST_PARAMETER_MAX_ARITY 12 - -#include <sys/types.h> -#include <sys/stat.h> +#define BOOST_PARAMETER_MAX_ARITY 12 #include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> +#include <gudhi/Euclidean_witness_complex.h> #include <gudhi/pick_n_random_points.h> #include <gudhi/reader_utils.h> +#include <CGAL/Epick_d.h> + #include <iostream> #include <fstream> #include <ctime> @@ -40,8 +38,6 @@ #include "generators.h" -typedef Gudhi::Simplex_tree<> Simplex_tree; - /** Write a gnuplot readable file. * Data range is a random access range of pairs (arg, value) */ @@ -54,6 +50,9 @@ void write_data(Data_range & data, std::string filename) { } int main(int argc, char * const argv[]) { + using Kernel = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; + using Witness_complex = Gudhi::witness_complex::Euclidean_witness_complex<Kernel>; + if (argc != 2) { std::cerr << "Usage: " << argv[0] << " number_of_landmarks \n"; @@ -63,13 +62,12 @@ int main(int argc, char * const argv[]) { int number_of_landmarks = atoi(argv[1]); clock_t start, end; - // Construct the Simplex Tree - Simplex_tree simplex_tree; - std::vector< std::pair<int, double> > l_time; - // Read the point file + // Generate points for (int nbP = 500; nbP < 10000; nbP += 500) { + // Construct the Simplex Tree + Gudhi::Simplex_tree<> simplex_tree; Point_Vector point_vector, landmarks; generate_points_sphere(point_vector, nbP, 4); std::cout << "Successfully generated " << point_vector.size() << " points.\n"; @@ -77,12 +75,12 @@ int main(int argc, char * const argv[]) { // Choose landmarks start = clock(); - std::vector<std::vector< int > > knn; - Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(point_vector, landmarks, knn); + Gudhi::subsampling::pick_n_random_points(point_vector, number_of_landmarks, std::back_inserter(landmarks)); // Compute witness complex - Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree); + Witness_complex witness_complex(landmarks, + point_vector); + witness_complex.create_complex(simplex_tree, 0); end = clock(); double time = static_cast<double>(end - start) / CLOCKS_PER_SEC; std::cout << "Witness complex for " << number_of_landmarks << " landmarks took " diff --git a/src/Witness_complex/example/generators.h b/src/Witness_complex/example/generators.h index ac445261..7df43db5 100644 --- a/src/Witness_complex/example/generators.h +++ b/src/Witness_complex/example/generators.h @@ -25,17 +25,19 @@ #include <CGAL/Epick_d.h> #include <CGAL/point_generators_d.h> +#include <CGAL/Random.h> #include <fstream> #include <string> #include <vector> +#include <cmath> -typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; -typedef K::FT FT; -typedef K::Point_d Point_d; -typedef std::vector<Point_d> Point_Vector; -typedef CGAL::Random_points_in_cube_d<Point_d> Random_cube_iterator; -typedef CGAL::Random_points_in_ball_d<Point_d> Random_point_iterator; +using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>; +using FT = K::FT; +using Point_d = K::Point_d; +using Point_Vector = std::vector<Point_d>; +using Random_cube_iterator = CGAL::Random_points_in_cube_d<Point_d>; +using Random_point_iterator = CGAL::Random_points_in_ball_d<Point_d>; /** * \brief Rock age method of reading off file @@ -144,4 +146,21 @@ void generate_points_sphere(Point_Vector& W, int nbP, int dim) { W.push_back(*rp++); } +/** \brief Generate nbP points on a (flat) d-torus embedded in R^{2d} + * + */ +void generate_points_torus(Point_Vector& W, int nbP, int dim) { + CGAL::Random rand; + const double pi = std::acos(-1); + for (int i = 0; i < nbP; i++) { + std::vector<FT> point; + for (int j = 0; j < dim; j++) { + double alpha = rand.uniform_real(static_cast<double>(0), 2*pi); + point.push_back(sin(alpha)); + point.push_back(cos(alpha)); + } + W.push_back(Point_d(point)); + } +} + #endif // EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h new file mode 100644 index 00000000..d41a6811 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h @@ -0,0 +1,67 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (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 ACTIVE_WITNESS_ACTIVE_WITNESS_H_ +#define ACTIVE_WITNESS_ACTIVE_WITNESS_H_ + +#include <gudhi/Active_witness/Active_witness_iterator.h> +#include <list> + +namespace Gudhi { + +namespace witness_complex { + + /* \class Active_witness + * \brief Class representing a list of nearest neighbors to a given witness. + * \details Every element is a pair of a landmark identifier and the squared distance to it. + */ +template< typename Id_distance_pair, + typename INS_range > +class Active_witness { + public: + typedef Active_witness<Id_distance_pair, INS_range> ActiveWitness; + typedef typename INS_range::iterator INS_iterator; + typedef Active_witness_iterator< ActiveWitness, Id_distance_pair, INS_iterator > iterator; + typedef typename std::list<Id_distance_pair> Table; + + Table nearest_landmark_table_; + INS_range search_range_; + INS_iterator iterator_next_; + INS_iterator iterator_end_; + + Active_witness(const INS_range& search_range) + : search_range_(search_range), iterator_next_(search_range_.begin()), iterator_end_(search_range_.end()) { + } + + iterator begin() { + return iterator(this, nearest_landmark_table_.begin()); + } + + iterator end() { + return iterator(this); + } +}; + +} // namespace witness_complex +} // namespace Gudhi + +#endif // ACTIVE_WITNESS_ACTIVE_WITNESS_H_ diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h new file mode 100644 index 00000000..0a05173a --- /dev/null +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h @@ -0,0 +1,108 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA (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 ACTIVE_WITNESS_ACTIVE_WITNESS_ITERATOR_H_ +#define ACTIVE_WITNESS_ACTIVE_WITNESS_ITERATOR_H_ + +#include <boost/iterator/iterator_facade.hpp> +#include <list> + +namespace Gudhi { + +namespace witness_complex { + +/* \brief Iterator in the nearest landmark list. + * \details After the iterator reaches the end of the list, + * the list is augmented by a (nearest landmark, distance) pair if possible. + * If all the landmarks are present in the list, iterator returns the specific end value + * of the corresponding 'Active_witness' object. + */ +template< typename Active_witness, + typename Id_distance_pair, + typename INS_iterator > +class Active_witness_iterator + : public boost::iterator_facade< Active_witness_iterator <Active_witness, Id_distance_pair, INS_iterator>, + Id_distance_pair const, + boost::forward_traversal_tag, + Id_distance_pair const> { + friend class boost::iterator_core_access; + + typedef typename std::list<Id_distance_pair>::iterator Pair_iterator; + typedef typename Gudhi::witness_complex::Active_witness_iterator<Active_witness, + Id_distance_pair, + INS_iterator> Iterator; + + Active_witness *aw_; + Pair_iterator lh_; // landmark handle + bool is_end_; // true only if the pointer is end and there are no more neighbors to add + + public: + Active_witness_iterator(Active_witness* aw) + : aw_(aw), lh_(aw_->nearest_landmark_table_.end()), is_end_(true) { + } + + Active_witness_iterator(Active_witness* aw, const Pair_iterator& lh) + : aw_(aw), lh_(lh) { + is_end_ = false; + if (lh_ == aw_->nearest_landmark_table_.end()) { + if (aw_->iterator_next_ == aw_->iterator_end_) { + is_end_ = true; + } else { + aw_->nearest_landmark_table_.push_back(*aw_->iterator_next_); + lh_ = --aw_->nearest_landmark_table_.end(); + ++(aw_->iterator_next_); + } + } + } + + private : + Id_distance_pair& dereference() const { + return *lh_; + } + + bool equal(const Iterator& other) const { + return (is_end_ == other.is_end_) || (lh_ == other.lh_); + } + + void increment() { + // the neighbor search can't be at the end iterator of a list + GUDHI_CHECK(!is_end_ && lh_ != aw_->nearest_landmark_table_.end(), + std::logic_error("Wrong active witness increment.")); + // if the id of the current landmark is the same as the last one + + lh_++; + if (lh_ == aw_->nearest_landmark_table_.end()) { + if (aw_->iterator_next_ == aw_->iterator_end_) { + is_end_ = true; + } else { + aw_->nearest_landmark_table_.push_back(*aw_->iterator_next_); + lh_ = std::prev(aw_->nearest_landmark_table_.end()); + ++(aw_->iterator_next_); + } + } + } +}; + +} // namespace witness_complex +} // namespace Gudhi + +#endif // ACTIVE_WITNESS_ACTIVE_WITNESS_ITERATOR_H_ diff --git a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h deleted file mode 100644 index a8cdd096..00000000 --- a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h +++ /dev/null @@ -1,92 +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): Siargey Kachanovich - * - * 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 <http://www.gnu.org/licenses/>. - */ - -#ifndef CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ -#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ - -#include <boost/range/size.hpp> - -#include <queue> // for priority_queue<> -#include <utility> // for pair<> -#include <iterator> -#include <vector> -#include <set> - -namespace Gudhi { - -namespace witness_complex { - - /** - * \ingroup witness_complex - * \brief Construct the closest landmark tables for all witnesses. - * \details Output a table 'knn', each line of which represents a witness and - * consists of landmarks sorted by - * euclidean distance from the corresponding witness. - * - * The type WitnessContainer is a random access range and - * the type LandmarkContainer is a range. - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges and - * Vertex_handle is the label type of a vertex in a simplicial complex. - * Closest_landmark_range needs to have push_back operation. - */ - - template <typename FiltrationValue, - typename WitnessContainer, - typename LandmarkContainer, - typename KNearestNeighbours> - void construct_closest_landmark_table(WitnessContainer const &points, - LandmarkContainer const &landmarks, - KNearestNeighbours &knn) { - int nbP = boost::size(points); - assert(nbP >= boost::size(landmarks)); - - int dim = boost::size(*std::begin(points)); - typedef std::pair<double, int> dist_i; - typedef bool (*comp)(dist_i, dist_i); - knn = KNearestNeighbours(nbP); - for (int points_i = 0; points_i < nbP; points_i++) { - std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) { - return j1.first > j2.first; - }); - typename LandmarkContainer::const_iterator landmarks_it; - int landmarks_i = 0; - for (landmarks_it = landmarks.begin(), landmarks_i = 0; landmarks_it != landmarks.end(); - ++landmarks_it, landmarks_i++) { - dist_i dist = std::make_pair(Euclidean_distance()(points[points_i], *landmarks_it), - landmarks_i); - l_heap.push(dist); - } - for (int i = 0; i < dim + 1; i++) { - dist_i dist = l_heap.top(); - knn[points_i].push_back(dist.second); - l_heap.pop(); - } - } - } - -} // namespace witness_complex - -} // namespace Gudhi - -#endif // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ diff --git a/src/Witness_complex/include/gudhi/Euclidean_strong_witness_complex.h b/src/Witness_complex/include/gudhi/Euclidean_strong_witness_complex.h new file mode 100644 index 00000000..fb669ef8 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Euclidean_strong_witness_complex.h @@ -0,0 +1,104 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA (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 EUCLIDEAN_STRONG_WITNESS_COMPLEX_H_ +#define EUCLIDEAN_STRONG_WITNESS_COMPLEX_H_ + +#include <gudhi/Strong_witness_complex.h> +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> + +#include <utility> +#include <vector> + +namespace Gudhi { + +namespace witness_complex { + +/** + * \private + * \class Euclidean_strong_witness_complex + * \brief Constructs strong witness complex for given sets of witnesses and landmarks in Euclidean space. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class. + */ +template< class Kernel_ > +class Euclidean_strong_witness_complex + : public Strong_witness_complex<std::vector<typename Gudhi::spatial_searching::Kd_tree_search<Kernel_, + std::vector<typename Kernel_::Point_d>>::INS_range>> { + private: + typedef Kernel_ K; + typedef typename K::Point_d Point_d; + typedef std::vector<Point_d> Point_range; + typedef Gudhi::spatial_searching::Kd_tree_search<Kernel_, Point_range> Kd_tree; + typedef typename Kd_tree::INS_range Nearest_landmark_range; + typedef typename std::vector<Nearest_landmark_range> Nearest_landmark_table; + + typedef typename Nearest_landmark_range::Point_with_transformed_distance Id_distance_pair; + typedef typename Id_distance_pair::first_type Landmark_id; + typedef Landmark_id Vertex_handle; + + private: + Point_range landmarks_; + Kd_tree landmark_tree_; + using Strong_witness_complex<Nearest_landmark_table>::nearest_landmark_table_; + + public: + ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /* @name Constructor + */ + + //@{ + + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records landmarks from the range 'landmarks' into a + * table internally, as well as witnesses from the range 'witnesses'. + * Both ranges should have value_type Kernel_::Point_d. + */ + template< typename LandmarkRange, + typename WitnessRange > + Euclidean_strong_witness_complex(const LandmarkRange & landmarks, + const WitnessRange & witnesses) + : landmarks_(std::begin(landmarks), std::end(landmarks)), landmark_tree_(landmarks_) { + nearest_landmark_table_.reserve(boost::size(witnesses)); + for (auto w : witnesses) + nearest_landmark_table_.push_back(landmark_tree_.query_incremental_nearest_neighbors(w)); + } + + /** \brief Returns the point corresponding to the given vertex. + */ + template <typename Vertex_handle> + Point_d get_point(Vertex_handle vertex) const { + return landmarks_[vertex]; + } + + //@} +}; + +} // namespace witness_complex + +} // namespace Gudhi + +#endif // EUCLIDEAN_STRONG_WITNESS_COMPLEX_H_ diff --git a/src/Witness_complex/include/gudhi/Euclidean_witness_complex.h b/src/Witness_complex/include/gudhi/Euclidean_witness_complex.h new file mode 100644 index 00000000..6afe9a5d --- /dev/null +++ b/src/Witness_complex/include/gudhi/Euclidean_witness_complex.h @@ -0,0 +1,106 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA (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 EUCLIDEAN_WITNESS_COMPLEX_H_ +#define EUCLIDEAN_WITNESS_COMPLEX_H_ + +#include <gudhi/Witness_complex.h> +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> + +#include <utility> +#include <vector> +#include <list> +#include <limits> + +namespace Gudhi { + +namespace witness_complex { + +/** + * \private + * \class Euclidean_witness_complex + * \brief Constructs (weak) witness complex for given sets of witnesses and landmarks in Euclidean space. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class. + */ +template< class Kernel_ > +class Euclidean_witness_complex + : public Witness_complex<std::vector<typename Gudhi::spatial_searching::Kd_tree_search<Kernel_, + std::vector<typename Kernel_::Point_d>>::INS_range>> { + private: + typedef Kernel_ K; + typedef typename K::Point_d Point_d; + typedef std::vector<Point_d> Point_range; + typedef Gudhi::spatial_searching::Kd_tree_search<Kernel_, Point_range> Kd_tree; + typedef typename Kd_tree::INS_range Nearest_landmark_range; + typedef typename std::vector<Nearest_landmark_range> Nearest_landmark_table; + + typedef typename Nearest_landmark_range::Point_with_transformed_distance Id_distance_pair; + typedef typename Id_distance_pair::first_type Landmark_id; + typedef Landmark_id Vertex_handle; + + private: + Point_range landmarks_; + Kd_tree landmark_tree_; + using Witness_complex<Nearest_landmark_table>::nearest_landmark_table_; + + public: + ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /* @name Constructor + */ + + //@{ + + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records landmarks from the range 'landmarks' into a + * table internally, as well as witnesses from the range 'witnesses'. + * Both ranges should have value_type Kernel_::Point_d. + */ + template< typename LandmarkRange, + typename WitnessRange > + Euclidean_witness_complex(const LandmarkRange & landmarks, + const WitnessRange & witnesses) + : landmarks_(std::begin(landmarks), std::end(landmarks)), landmark_tree_(landmarks) { + nearest_landmark_table_.reserve(boost::size(witnesses)); + for (auto w : witnesses) + nearest_landmark_table_.push_back(landmark_tree_.query_incremental_nearest_neighbors(w)); + } + + /** \brief Returns the point corresponding to the given vertex. + * @param[in] vertex Vertex handle of the point to retrieve. + */ + Point_d get_point(Vertex_handle vertex) const { + return landmarks_[vertex]; + } + + //@} +}; + +} // namespace witness_complex + +} // namespace Gudhi + +#endif // EUCLIDEAN_WITNESS_COMPLEX_H_ diff --git a/src/Witness_complex/include/gudhi/Strong_witness_complex.h b/src/Witness_complex/include/gudhi/Strong_witness_complex.h new file mode 100644 index 00000000..6708ac29 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Strong_witness_complex.h @@ -0,0 +1,186 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA (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 STRONG_WITNESS_COMPLEX_H_ +#define STRONG_WITNESS_COMPLEX_H_ + +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> + +#include <utility> +#include <vector> +#include <list> +#include <limits> + +namespace Gudhi { + +namespace witness_complex { + +/* \private + * \class Strong_witness_complex + * \brief Constructs strong witness complex for a given table of nearest landmarks with respect to witnesses. + * \ingroup witness_complex + * + * \tparam Nearest_landmark_table_ needs to be a range of a range of pairs of nearest landmarks and distances. + * The class Nearest_landmark_table_::value_type must be a copiable range. + * The range of pairs must admit a member type 'iterator'. The dereference type + * of the pair range iterator needs to be 'std::pair<std::size_t, double>'. + */ +template< class Nearest_landmark_table_ > +class Strong_witness_complex { + private: + typedef typename Nearest_landmark_table_::value_type Nearest_landmark_range; + typedef std::size_t Witness_id; + typedef std::size_t Landmark_id; + typedef std::pair<Landmark_id, double> Id_distance_pair; + typedef Active_witness<Id_distance_pair, Nearest_landmark_range> ActiveWitness; + typedef std::list< ActiveWitness > ActiveWitnessList; + typedef std::vector< Landmark_id > typeVectorVertex; + typedef std::vector<Nearest_landmark_range> Nearest_landmark_table_internal; + typedef Landmark_id Vertex_handle; + + protected: + Nearest_landmark_table_internal nearest_landmark_table_; + + public: + ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /* @name Constructor + */ + + //@{ + + Strong_witness_complex() { + } + + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records nearest landmark table. + * @param[in] nearest_landmark_table needs to be a range of a range of pairs of nearest landmarks and distances. + * The class Nearest_landmark_table_::value_type must be a copiable range. + * The range of pairs must admit a member type 'iterator'. The dereference type + * of the pair range iterator needs to be 'std::pair<std::size_t, double>'. + */ + Strong_witness_complex(Nearest_landmark_table_ const & nearest_landmark_table) + : nearest_landmark_table_(std::begin(nearest_landmark_table), std::end(nearest_landmark_table)) { + } + + /** \brief Outputs the strong witness complex of relaxation 'max_alpha_square' + * in a simplicial complex data structure. + * \details The function returns true if the construction is successful and false otherwise. + * @param[out] complex Simplicial complex data structure, which is a model of + * SimplicialComplexForWitness concept. + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex + * (default value = no limit). + */ + template < typename SimplicialComplexForWitness > + bool create_complex(SimplicialComplexForWitness& complex, + double max_alpha_square, + Landmark_id limit_dimension = std::numeric_limits<Landmark_id>::max()) const { + Landmark_id complex_dim = 0; + if (complex.num_vertices() > 0) { + std::cerr << "Strong witness complex cannot create complex - complex is not empty.\n"; + return false; + } + if (max_alpha_square < 0) { + std::cerr << "Strong witness complex cannot create complex - squared relaxation parameter must be " + << "non-negative.\n"; + return false; + } + if (limit_dimension < 0) { + std::cerr << "Strong witness complex cannot create complex - limit dimension must be non-negative.\n"; + return false; + } + for (auto w : nearest_landmark_table_) { + ActiveWitness aw(w); + typeVectorVertex simplex; + typename ActiveWitness::iterator aw_it = aw.begin(); + float lim_dist2 = aw.begin()->second + max_alpha_square; + while ((Landmark_id)simplex.size() <= limit_dimension && aw_it != aw.end() && aw_it->second < lim_dist2) { + simplex.push_back(aw_it->first); + complex.insert_simplex_and_subfaces(simplex, aw_it->second - aw.begin()->second); + aw_it++; + } + // continue inserting limD-faces of the following simplices + typeVectorVertex& vertices = simplex; // 'simplex' now will be called vertices + while (aw_it != aw.end() && aw_it->second < lim_dist2) { + typeVectorVertex facet = {}; + add_all_faces_of_dimension(limit_dimension, vertices, vertices.begin(), aw_it, + aw_it->second - aw.begin()->second, facet, complex); + vertices.push_back(aw_it->first); + aw_it++; + } + if ((Landmark_id)simplex.size() - 1 > complex_dim) + complex_dim = simplex.size() - 1; + } + complex.set_dimension(complex_dim); + return true; + } + + private: + /* \brief Adds recursively all the faces of a certain dimension dim-1 witnessed by the same witness. + * Iterator is needed to know until how far we can take landmarks to form simplexes. + * simplex is the prefix of the simplexes to insert. + * The landmark pointed by aw_it is added to all formed simplices. + */ + template < typename SimplicialComplexForWitness > + void add_all_faces_of_dimension(Landmark_id dim, + typeVectorVertex& vertices, + typename typeVectorVertex::iterator curr_it, + typename ActiveWitness::iterator aw_it, + double filtration_value, + typeVectorVertex& simplex, + SimplicialComplexForWitness& sc) const { + if (dim > 0) { + while (curr_it != vertices.end()) { + simplex.push_back(*curr_it); + ++curr_it; + add_all_faces_of_dimension(dim-1, + vertices, + curr_it, + aw_it, + filtration_value, + simplex, + sc); + simplex.pop_back(); + add_all_faces_of_dimension(dim, + vertices, + curr_it, + aw_it, + filtration_value, + simplex, + sc); + } + } else if (dim == 0) { + simplex.push_back(aw_it->first); + sc.insert_simplex_and_subfaces(simplex, filtration_value); + simplex.pop_back(); + } + } + //@} +}; + +} // namespace witness_complex + +} // namespace Gudhi + +#endif // STRONG_WITNESS_COMPLEX_H_ diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 1eb126f1..e7adf80f 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -4,7 +4,7 @@ * * Author(s): Siargey Kachanovich * - * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2015 INRIA (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 @@ -23,64 +23,45 @@ #ifndef WITNESS_COMPLEX_H_ #define WITNESS_COMPLEX_H_ -// Needed for the adjacency graph in bad link search -#include <boost/graph/graph_traits.hpp> -#include <boost/graph/adjacency_list.hpp> -#include <boost/graph/connected_components.hpp> +#include <gudhi/Active_witness/Active_witness.h> +#include <gudhi/Kd_tree_search.h> +#include <gudhi/Witness_complex/all_faces_in.h> -#include <boost/range/size.hpp> - -#include <gudhi/distance_functions.h> - -#include <algorithm> #include <utility> #include <vector> #include <list> -#include <set> -#include <queue> #include <limits> -#include <ctime> -#include <iostream> namespace Gudhi { namespace witness_complex { -// /* -// * \private -// \class Witness_complex -// \brief Constructs the witness complex for the given set of witnesses and landmarks. -// \ingroup witness_complex -// */ -template< class SimplicialComplex> +/** + * \private + * \class Witness_complex + * \brief Constructs (weak) witness complex for a given table of nearest landmarks with respect to witnesses. + * \ingroup witness_complex + * + * \tparam Nearest_landmark_table_ needs to be a range of a range of pairs of nearest landmarks and distances. + * The class Nearest_landmark_table_::value_type must be a copiable range. + * The range of pairs must admit a member type 'iterator'. The dereference type + * of the pair range iterator needs to be 'std::pair<std::size_t, double>'. +*/ +template< class Nearest_landmark_table_ > class Witness_complex { private: - struct Active_witness { - int witness_id; - int landmark_id; - - Active_witness(int witness_id_, int landmark_id_) - : witness_id(witness_id_), - landmark_id(landmark_id_) { } - }; - - private: - typedef typename SimplicialComplex::Simplex_handle Simplex_handle; - typedef typename SimplicialComplex::Vertex_handle Vertex_handle; - - typedef std::vector< double > Point_t; - typedef std::vector< Point_t > Point_Vector; - - typedef std::vector< Vertex_handle > typeVectorVertex; - typedef std::pair< Simplex_handle, bool > typePairSimplexBool; - - typedef int Witness_id; - typedef int Landmark_id; - typedef std::list< Vertex_handle > ActiveWitnessList; - - private: - int nbL_; // Number of landmarks - SimplicialComplex& sc_; // Simplicial complex + typedef typename Nearest_landmark_table_::value_type Nearest_landmark_range; + typedef std::size_t Witness_id; + typedef std::size_t Landmark_id; + typedef std::pair<Landmark_id, double> Id_distance_pair; + typedef Active_witness<Id_distance_pair, Nearest_landmark_range> ActiveWitness; + typedef std::list< ActiveWitness > ActiveWitnessList; + typedef std::vector< Landmark_id > typeVectorVertex; + typedef std::vector<Nearest_landmark_range> Nearest_landmark_table_internal; + typedef Landmark_id Vertex_handle; + + protected: + Nearest_landmark_table_internal nearest_landmark_table_; public: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// @@ -89,174 +70,136 @@ class Witness_complex { //@{ - // Witness_range<Closest_landmark_range<Vertex_handle>> + Witness_complex() { + } - /* - * \brief Iterative construction of the witness complex. - * \details The witness complex is written in sc_ basing on a matrix knn of - * nearest neighbours of the form {witnesses}x{landmarks}. - * - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges. - * - * Constructor takes into account at most (dim+1) - * first landmarks from each landmark range to construct simplices. - * - * Landmarks are supposed to be in [0,nbL_-1] + /** + * \brief Initializes member variables before constructing simplicial complex. + * \details Records nearest landmark table. + * @param[in] nearest_landmark_table needs to be a range of a range of pairs of nearest landmarks and distances. + * The class Nearest_landmark_table_::value_type must be a copiable range. + * The range of pairs must admit a member type 'iterator'. The dereference type + * of the pair range iterator needs to be 'std::pair<std::size_t, double>'. */ - template< typename KNearestNeighbors > - Witness_complex(KNearestNeighbors const & knn, - int nbL, - int dim, - SimplicialComplex & sc) : nbL_(nbL), sc_(sc) { - // Construction of the active witness list - int nbW = boost::size(knn); - typeVectorVertex vv; - int counter = 0; - /* The list of still useful witnesses - * it will diminuish in the course of iterations - */ - ActiveWitnessList active_w; // = new ActiveWitnessList(); - for (Vertex_handle i = 0; i != nbL_; ++i) { - // initial fill of 0-dimensional simplices - // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore - counter++; - vv = {i}; - sc_.insert_simplex(vv); - // TODO(SK) Error if not inserted : normally no need here though + + Witness_complex(Nearest_landmark_table_ const & nearest_landmark_table) + : nearest_landmark_table_(std::begin(nearest_landmark_table), std::end(nearest_landmark_table)) { + } + + /** \brief Outputs the (weak) witness complex of relaxation 'max_alpha_square' + * in a simplicial complex data structure. + * \details The function returns true if the construction is successful and false otherwise. + * @param[out] complex Simplicial complex data structure compatible which is a model of + * SimplicialComplexForWitness concept. + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex + * (default value = no limit). + */ + template < typename SimplicialComplexForWitness > + bool create_complex(SimplicialComplexForWitness& complex, + double max_alpha_square, + std::size_t limit_dimension = std::numeric_limits<std::size_t>::max()) const { + if (complex.num_vertices() > 0) { + std::cerr << "Witness complex cannot create complex - complex is not empty.\n"; + return false; } - int k = 1; /* current dimension in iterative construction */ - for (int i = 0; i != nbW; ++i) - active_w.push_back(i); - while (!active_w.empty() && k < dim) { - typename ActiveWitnessList::iterator it = active_w.begin(); - while (it != active_w.end()) { - typeVectorVertex simplex_vector; - /* THE INSERTION: Checking if all the subfaces are in the simplex tree*/ - bool ok = all_faces_in(knn, *it, k); - if (ok) { - for (int i = 0; i != k + 1; ++i) - simplex_vector.push_back(knn[*it][i]); - sc_.insert_simplex(simplex_vector); - // TODO(SK) Error if not inserted : normally no need here though - ++it; - } else { - active_w.erase(it++); // First increase the iterator and then erase the previous element - } + if (max_alpha_square < 0) { + std::cerr << "Witness complex cannot create complex - squared relaxation parameter must be non-negative.\n"; + return false; + } + if (limit_dimension < 0) { + std::cerr << "Witness complex cannot create complex - limit dimension must be non-negative.\n"; + return false; + } + ActiveWitnessList active_witnesses; + Landmark_id k = 0; /* current dimension in iterative construction */ + for (auto w : nearest_landmark_table_) + active_witnesses.push_back(ActiveWitness(w)); + while (!active_witnesses.empty() && k <= limit_dimension) { + typename ActiveWitnessList::iterator aw_it = active_witnesses.begin(); + std::vector<Landmark_id> simplex; + simplex.reserve(k+1); + while (aw_it != active_witnesses.end()) { + bool ok = add_all_faces_of_dimension(k, + max_alpha_square, + std::numeric_limits<double>::infinity(), + aw_it->begin(), + simplex, + complex, + aw_it->end()); + assert(simplex.empty()); + if (!ok) + active_witnesses.erase(aw_it++); // First increase the iterator and then erase the previous element + else + aw_it++; } k++; } + complex.set_dimension(k-1); + return true; } //@} private: - /* \brief Check if the facets of the k-dimensional simplex witnessed - * by witness witness_id are already in the complex. - * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id + /* \brief Adds recursively all the faces of a certain dimension dim witnessed by the same witness. + * Iterator is needed to know until how far we can take landmarks to form simplexes. + * simplex is the prefix of the simplexes to insert. + * The output value indicates if the witness rests active or not. */ - template <typename KNearestNeighbors> - bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) { - std::vector< Vertex_handle > facet; - // CHECK ALL THE FACETS - for (int i = 0; i != k + 1; ++i) { - facet = {}; - for (int j = 0; j != k + 1; ++j) { - if (j != i) { - facet.push_back(knn[witness_id][j]); + template < typename SimplicialComplexForWitness > + bool add_all_faces_of_dimension(int dim, + double alpha2, + double norelax_dist2, + typename ActiveWitness::iterator curr_l, + std::vector<Landmark_id>& simplex, + SimplicialComplexForWitness& sc, + typename ActiveWitness::iterator end) const { + if (curr_l == end) + return false; + bool will_be_active = false; + typename ActiveWitness::iterator l_it = curr_l; + if (dim > 0) { + for (; l_it != end && l_it->second - alpha2 <= norelax_dist2; ++l_it) { + simplex.push_back(l_it->first); + if (sc.find(simplex) != sc.null_simplex()) { + typename ActiveWitness::iterator next_it = l_it; + will_be_active = add_all_faces_of_dimension(dim-1, + alpha2, + norelax_dist2, + ++next_it, + simplex, + sc, + end) || will_be_active; } - } // endfor - if (sc_.find(facet) == sc_.null_simplex()) - return false; - } // endfor - return true; - } - - template <typename T> - static void print_vector(const std::vector<T>& v) { - std::cout << "["; - if (!v.empty()) { - std::cout << *(v.begin()); - for (auto it = v.begin() + 1; it != v.end(); ++it) { - std::cout << ","; - std::cout << *it; + assert(!simplex.empty()); + simplex.pop_back(); + // If norelax_dist is infinity, change to first omitted distance + if (l_it->second <= norelax_dist2) + norelax_dist2 = l_it->second; } - } - std::cout << "]"; - } - - public: - // /* - // * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. - // * \param print_output =true will print the witnesses for each simplex - // * \remark Added for debugging purposes. - // */ - template< class KNearestNeighbors > - bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) { - for (Simplex_handle sh : sc_.complex_simplex_range()) { - bool is_witnessed = false; - typeVectorVertex simplex; - int nbV = 0; // number of verticed in the simplex - for (Vertex_handle v : sc_.simplex_vertex_range(sh)) - simplex.push_back(v); - nbV = simplex.size(); - for (typeVectorVertex w : knn) { - bool has_vertices = true; - for (Vertex_handle v : simplex) - if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) { - has_vertices = false; - } - if (has_vertices) { - is_witnessed = true; - if (print_output) { - std::cout << "The simplex "; - print_vector(simplex); - std::cout << " is witnessed by the witness "; - print_vector(w); - std::cout << std::endl; - } - break; - } - } - if (!is_witnessed) { - if (print_output) { - std::cout << "The following simplex is not witnessed "; - print_vector(simplex); - std::cout << std::endl; + } else if (dim == 0) { + for (;l_it != end && l_it->second - alpha2 <= norelax_dist2; ++l_it) { + simplex.push_back(l_it->first); + double filtration_value = 0; + // if norelax_dist is infinite, relaxation is 0. + if (l_it->second > norelax_dist2) + filtration_value = l_it->second - norelax_dist2; + if (all_faces_in(simplex, &filtration_value, sc)) { + will_be_active = true; + sc.insert_simplex(simplex, filtration_value); } - assert(is_witnessed); - return false; + assert(!simplex.empty()); + simplex.pop_back(); + // If norelax_dist is infinity, change to first omitted distance + if (l_it->second < norelax_dist2) + norelax_dist2 = l_it->second; } } - return true; + return will_be_active; } }; - /** - * \ingroup witness_complex - * \brief Iterative construction of the witness complex. - * \details The witness complex is written in simplicial complex sc_ - * basing on a matrix knn of - * nearest neighbours of the form {witnesses}x{landmarks}. - * - * The type KNearestNeighbors can be seen as - * Witness_range<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges. - * - * Procedure takes into account at most (dim+1) - * first landmarks from each landmark range to construct simplices. - * - * Landmarks are supposed to be in [0,nbL_-1] - */ - template <class KNearestNeighbors, class SimplicialComplexForWitness> - void witness_complex(KNearestNeighbors const & knn, - int nbL, - int dim, - SimplicialComplexForWitness & sc) { - Witness_complex<SimplicialComplexForWitness>(knn, nbL, dim, sc); - } - } // namespace witness_complex } // namespace Gudhi diff --git a/src/Witness_complex/include/gudhi/Witness_complex/all_faces_in.h b/src/Witness_complex/include/gudhi/Witness_complex/all_faces_in.h new file mode 100644 index 00000000..b68d75a1 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Witness_complex/all_faces_in.h @@ -0,0 +1,55 @@ +/* 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): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA (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 WITNESS_COMPLEX_ALL_FACES_IN_H_ +#define WITNESS_COMPLEX_ALL_FACES_IN_H_ + +/* \brief Check if the facets of the k-dimensional simplex witnessed + * by witness witness_id are already in the complex. + * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id + */ +template < typename SimplicialComplexForWitness, + typename Simplex > + bool all_faces_in(Simplex& simplex, + double* filtration_value, + SimplicialComplexForWitness& sc) { + typedef typename SimplicialComplexForWitness::Simplex_handle Simplex_handle; + + if (simplex.size() == 1) + return true; /* Add vertices unconditionally */ + + Simplex facet; + for (typename Simplex::iterator not_it = simplex.begin(); not_it != simplex.end(); ++not_it) { + facet.clear(); + for (typename Simplex::iterator it = simplex.begin(); it != simplex.end(); ++it) + if (it != not_it) + facet.push_back(*it); + Simplex_handle facet_sh = sc.find(facet); + if (facet_sh == sc.null_simplex()) + return false; + else if (sc.filtration(facet_sh) > *filtration_value) + *filtration_value = sc.filtration(facet_sh); + } + return true; + } + +#endif // WITNESS_COMPLEX_ALL_FACES_IN_H_ diff --git a/src/Witness_complex/test/CMakeLists.txt b/src/Witness_complex/test/CMakeLists.txt index bb55b0f1..084761e2 100644 --- a/src/Witness_complex/test/CMakeLists.txt +++ b/src/Witness_complex/test/CMakeLists.txt @@ -10,21 +10,12 @@ if (GPROF_PATH) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") endif() -add_executable ( simple_witness_complexUT simple_witness_complex.cpp ) -target_link_libraries(simple_witness_complexUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +add_executable ( Witness_complex_test_simple_witness_complex test_simple_witness_complex.cpp ) +target_link_libraries(Witness_complex_test_simple_witness_complex ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +target_link_libraries(Witness_complex_test_simple_witness_complex ${TBB_LIBRARIES}) # Unitary tests definition and xml result file generation -add_test(NAME simple_witness_complexUT - COMMAND ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complexUT +add_test(NAME simple_witness_complex + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/Witness_complex_test_simple_witness_complex # XML format for Jenkins xUnit plugin - --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/simple_witness_complexUT.xml --log_level=test_suite --report_level=no) - -add_executable ( witness_complex_pointsUT witness_complex_points.cpp ) -target_link_libraries(witness_complex_pointsUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) - -# Unitary tests definition and xml result file generation -add_test(NAME witness_complex_pointsUT - COMMAND ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_pointsUT - # XML format for Jenkins xUnit plugin - --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/witness_complex_pointsUT.xml --log_level=test_suite --report_level=no) - + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Witness_complex_test_simple_witness_complexUT.xml --log_level=test_suite --report_level=no) diff --git a/src/Witness_complex/test/simple_witness_complex.cpp b/src/Witness_complex/test/simple_witness_complex.cpp deleted file mode 100644 index 6be39f58..00000000 --- a/src/Witness_complex/test/simple_witness_complex.cpp +++ /dev/null @@ -1,59 +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): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA Sophia Antipolis-Méditerranée (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/>. - */ - -#define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "simple_witness_complex" -#include <boost/test/unit_test.hpp> -#include <boost/mpl/list.hpp> - -#include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> - -#include <iostream> -#include <ctime> -#include <vector> - -typedef Gudhi::Simplex_tree<> Simplex_tree; -typedef std::vector< Simplex_tree::Vertex_handle > typeVectorVertex; -typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; - -BOOST_AUTO_TEST_CASE(simple_witness_complex) { - Simplex_tree complex; - std::vector< typeVectorVertex > knn; - - knn.push_back({1, 0, 5, 2, 6, 3, 4}); - knn.push_back({2, 6, 4, 5, 0, 1, 3}); - knn.push_back({3, 4, 2, 1, 5, 6, 0}); - knn.push_back({4, 2, 1, 3, 5, 6, 0}); - knn.push_back({5, 1, 6, 0, 2, 3, 4}); - knn.push_back({6, 0, 5, 2, 1, 3, 4}); - knn.push_back({0, 5, 6, 1, 2, 3, 4}); - knn.push_back({2, 6, 4, 5, 3, 1, 0}); - knn.push_back({1, 2, 5, 4, 3, 6, 0}); - knn.push_back({3, 4, 0, 6, 5, 1, 2}); - knn.push_back({5, 0, 1, 3, 6, 2, 4}); - knn.push_back({5, 6, 1, 0, 2, 3, 4}); - knn.push_back({1, 6, 0, 5, 2, 3, 4}); - WitnessComplex witnessComplex(knn, 7, 7, complex); - - BOOST_CHECK(witnessComplex.is_witness_complex(knn, false)); -} diff --git a/src/Witness_complex/test/test_simple_witness_complex.cpp b/src/Witness_complex/test/test_simple_witness_complex.cpp new file mode 100644 index 00000000..bb1df72d --- /dev/null +++ b/src/Witness_complex/test/test_simple_witness_complex.cpp @@ -0,0 +1,135 @@ +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simple_witness_complex" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +#include <CGAL/Epick_d.h> + +#include <gudhi/Simplex_tree.h> + +#include <gudhi/Witness_complex.h> +#include <gudhi/Euclidean_witness_complex.h> +#include <gudhi/Strong_witness_complex.h> +#include <gudhi/Euclidean_strong_witness_complex.h> + +#include <gudhi/Kd_tree_search.h> + +#include <iostream> +#include <ctime> +#include <vector> + +typedef Gudhi::Simplex_tree<> Simplex_tree; +typedef typename Simplex_tree::Vertex_handle Vertex_handle; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> Kernel; +typedef typename Kernel::FT FT; +typedef typename Kernel::Point_d Point_d; +typedef Gudhi::witness_complex::Euclidean_witness_complex<Kernel> EuclideanWitnessComplex; +typedef Gudhi::witness_complex::Euclidean_strong_witness_complex<Kernel> EuclideanStrongWitnessComplex; + +typedef std::vector<Point_d> Point_range; +typedef Gudhi::spatial_searching::Kd_tree_search<Kernel, Point_range> Kd_tree; +typedef Kd_tree::INS_range Nearest_landmark_range; +typedef std::vector<Nearest_landmark_range> Nearest_landmark_table; +typedef Gudhi::witness_complex::Witness_complex<Nearest_landmark_table> WitnessComplex; +typedef Gudhi::witness_complex::Strong_witness_complex<Nearest_landmark_table> StrongWitnessComplex; + + +/* All landmarks and witnesses are taken on the grid in the following manner. + LWLWL + WW.WW + L...L + WW.WW + LWLWL + + Witness complex consists of 8 vertices, 12 edges and 4 triangles + */ + +BOOST_AUTO_TEST_CASE(simple_witness_complex) { + Simplex_tree complex, relaxed_complex, strong_relaxed_complex, strong_relaxed_complex2; + Simplex_tree complex_ne, relaxed_complex_ne, strong_relaxed_complex_ne, strong_relaxed_complex2_ne; + + Point_range witnesses, landmarks; + + landmarks.push_back(Point_d(std::vector<FT>{-2,-2})); + landmarks.push_back(Point_d(std::vector<FT>{-2, 0})); + landmarks.push_back(Point_d(std::vector<FT>{-2, 2})); + landmarks.push_back(Point_d(std::vector<FT>{ 0,-2})); + landmarks.push_back(Point_d(std::vector<FT>{ 0, 2})); + landmarks.push_back(Point_d(std::vector<FT>{ 2,-2})); + landmarks.push_back(Point_d(std::vector<FT>{ 2, 0})); + landmarks.push_back(Point_d(std::vector<FT>{ 2, 2})); + witnesses.push_back(Point_d(std::vector<FT>{-2,-1})); + witnesses.push_back(Point_d(std::vector<FT>{-2, 1})); + witnesses.push_back(Point_d(std::vector<FT>{-1,-2})); + witnesses.push_back(Point_d(std::vector<FT>{-1,-1})); + witnesses.push_back(Point_d(std::vector<FT>{-1, 1})); + witnesses.push_back(Point_d(std::vector<FT>{-1, 2})); + witnesses.push_back(Point_d(std::vector<FT>{ 1,-2})); + witnesses.push_back(Point_d(std::vector<FT>{ 1,-1})); + witnesses.push_back(Point_d(std::vector<FT>{ 1, 1})); + witnesses.push_back(Point_d(std::vector<FT>{ 1, 2})); + witnesses.push_back(Point_d(std::vector<FT>{ 2,-1})); + witnesses.push_back(Point_d(std::vector<FT>{ 2, 1})); + + Kd_tree landmark_tree(landmarks); + Nearest_landmark_table nearest_landmark_table; + for (auto w: witnesses) + nearest_landmark_table.push_back(landmark_tree.query_incremental_nearest_neighbors(w)); + + // Weak witness complex: Euclidean version + EuclideanWitnessComplex eucl_witness_complex(landmarks, + witnesses); + eucl_witness_complex.create_complex(complex, 0); + + std::cout << "complex.num_simplices() = " << complex.num_simplices() << std::endl; + BOOST_CHECK(complex.num_simplices() == 24); + + eucl_witness_complex.create_complex(relaxed_complex, 8.01); + + std::cout << "relaxed_complex.num_simplices() = " << relaxed_complex.num_simplices() << std::endl; + BOOST_CHECK(relaxed_complex.num_simplices() == 239); + // The corner simplex {0,2,5,7} and its cofaces are missing. + + // Weak witness complex: non-Euclidean version + WitnessComplex witness_complex(nearest_landmark_table); + witness_complex.create_complex(complex_ne, 0); + + std::cout << "complex.num_simplices() = " << complex_ne.num_simplices() << std::endl; + BOOST_CHECK(complex_ne.num_simplices() == 24); + + witness_complex.create_complex(relaxed_complex_ne, 8.01); + + std::cout << "relaxed_complex.num_simplices() = " << relaxed_complex_ne.num_simplices() << std::endl; + BOOST_CHECK(relaxed_complex_ne.num_simplices() == 239); + + + // Strong complex : Euclidean version + EuclideanStrongWitnessComplex eucl_strong_witness_complex(landmarks, + witnesses); + + eucl_strong_witness_complex.create_complex(strong_relaxed_complex, 9.1); + eucl_strong_witness_complex.create_complex(strong_relaxed_complex2, 9.1, 2); + + std::cout << "strong_relaxed_complex.num_simplices() = " << strong_relaxed_complex.num_simplices() << std::endl; + BOOST_CHECK(strong_relaxed_complex.num_simplices() == 239); + + std::cout << "strong_relaxed_complex2.num_simplices() = " << strong_relaxed_complex2.num_simplices() << std::endl; + BOOST_CHECK(strong_relaxed_complex2.num_simplices() == 92); + + + // Strong complex : non-Euclidean version + StrongWitnessComplex strong_witness_complex(nearest_landmark_table); + + strong_witness_complex.create_complex(strong_relaxed_complex_ne, 9.1); + strong_witness_complex.create_complex(strong_relaxed_complex2_ne, 9.1, 2); + + std::cout << "strong_relaxed_complex.num_simplices() = " << strong_relaxed_complex_ne.num_simplices() << std::endl; + BOOST_CHECK(strong_relaxed_complex_ne.num_simplices() == 239); + + std::cout << "strong_relaxed_complex2.num_simplices() = " << strong_relaxed_complex2_ne.num_simplices() << std::endl; + BOOST_CHECK(strong_relaxed_complex2_ne.num_simplices() == 92); + + + // 8 vertices, 28 edges, 56 triangles +} diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp deleted file mode 100644 index 92f53417..00000000 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ /dev/null @@ -1,58 +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): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA Sophia Antipolis-Méditerranée (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/>. - */ - -#define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "witness_complex_points" -#include <boost/test/unit_test.hpp> -#include <boost/mpl/list.hpp> - -#include <gudhi/Simplex_tree.h> -#include <gudhi/Witness_complex.h> -#include <gudhi/Construct_closest_landmark_table.h> -#include <gudhi/pick_n_random_points.h> - -#include <iostream> -#include <vector> - -typedef std::vector<double> Point; -typedef Gudhi::Simplex_tree<> Simplex_tree; -typedef std::vector< Simplex_tree::Vertex_handle > typeVectorVertex; -typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; - -BOOST_AUTO_TEST_CASE(witness_complex_points) { - std::vector< typeVectorVertex > knn; - std::vector< Point > points, landmarks; - // Add grid points as witnesses - for (double i = 0; i < 10; i += 1.0) - for (double j = 0; j < 10; j += 1.0) - for (double k = 0; k < 10; k += 1.0) - points.push_back(Point({i, j, k})); - - bool b_print_output = false; - // First test: random choice - Simplex_tree complex1; - Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(landmarks)); - Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(points, landmarks, knn); - assert(!knn.empty()); - WitnessComplex witnessComplex1(knn, 100, 3, complex1); - BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output)); -} diff --git a/src/cmake/modules/GUDHI_user_version_target.txt b/src/cmake/modules/GUDHI_user_version_target.txt index 742cbe8c..13fccd32 100644 --- a/src/cmake/modules/GUDHI_user_version_target.txt +++ b/src/cmake/modules/GUDHI_user_version_target.txt @@ -1,8 +1,6 @@ # Some functionnalities requires CMake 2.8.11 minimum if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) - string(TIMESTAMP DATE_AND_TIME "%Y-%m-%d-%H-%M-%S") - # Definition of the custom target user_version add_custom_target(user_version) @@ -11,6 +9,7 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) set(GUDHI_USER_VERSION_DIR ${CMAKE_CURRENT_BINARY_DIR}/${USER_VERSION_DIR}) else() # set the GUDHI_USER_VERSION_DIR with timestamp and Gudhi version number + string(TIMESTAMP DATE_AND_TIME "%Y-%m-%d-%H-%M-%S") set(GUDHI_USER_VERSION_DIR ${CMAKE_CURRENT_BINARY_DIR}/${DATE_AND_TIME}_GUDHI_${GUDHI_VERSION}) endif() @@ -21,6 +20,8 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) COMMENT "user_version creation in ${GUDHI_USER_VERSION_DIR}") add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E + copy ${CMAKE_SOURCE_DIR}/Conventions.txt ${GUDHI_USER_VERSION_DIR}/Conventions.txt) + add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy ${CMAKE_SOURCE_DIR}/README ${GUDHI_USER_VERSION_DIR}/README) add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy ${CMAKE_SOURCE_DIR}/COPYING ${GUDHI_USER_VERSION_DIR}/COPYING) @@ -46,75 +47,47 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy_directory ${CMAKE_SOURCE_DIR}/src/cmake ${GUDHI_USER_VERSION_DIR}/cmake) add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${CMAKE_SOURCE_DIR}/src/debian ${GUDHI_USER_VERSION_DIR}/debian) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy_directory ${CMAKE_SOURCE_DIR}/src/GudhUI ${GUDHI_USER_VERSION_DIR}/GudhUI) set(GUDHI_MODULES "common;Alpha_complex;Bitmap_cubical_complex;Bottleneck_distance;Contraction;Hasse_complex;Persistent_cohomology;Rips_complex;Simplex_tree;Skeleton_blocker;Spatial_searching;Subsampling;Tangential_complex;Witness_complex") - + set(GUDHI_DIRECTORIES "doc;example;concept") + set(GUDHI_INCLUDE_DIRECTORIES "include/gudhi;include/gudhi_patches") + foreach(GUDHI_MODULE ${GUDHI_MODULES}) - # doc files - file(GLOB GUDHI_DOC_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/doc/*) - - foreach(GUDHI_DOC_FILE ${GUDHI_DOC_FILES}) - get_filename_component(GUDHI_DOC_FILE_NAME ${GUDHI_DOC_FILE} NAME) - # GUDHI_DOC_FILE can be a file or a directory - if(IS_DIRECTORY ${GUDHI_DOC_FILE}) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${GUDHI_DOC_FILE} ${GUDHI_USER_VERSION_DIR}/doc/${GUDHI_MODULE}/${GUDHI_DOC_FILE_NAME}) - else() - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy ${GUDHI_DOC_FILE} ${GUDHI_USER_VERSION_DIR}/doc/${GUDHI_MODULE}/${GUDHI_DOC_FILE_NAME}) - endif() - endforeach() - - # example files - file(GLOB GUDHI_EXAMPLE_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/example/*) - - foreach(GUDHI_EXAMPLE_FILE ${GUDHI_EXAMPLE_FILES}) - get_filename_component(GUDHI_EXAMPLE_FILE_NAME ${GUDHI_EXAMPLE_FILE} NAME) - # GUDHI_EXAMPLE_FILE can be a file or a directory - if(IS_DIRECTORY ${GUDHI_EXAMPLE_FILE}) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${GUDHI_EXAMPLE_FILE} ${GUDHI_USER_VERSION_DIR}/example/${GUDHI_MODULE}/${GUDHI_EXAMPLE_FILE_NAME}) - else() - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy ${GUDHI_EXAMPLE_FILE} ${GUDHI_USER_VERSION_DIR}/example/${GUDHI_MODULE}/${GUDHI_EXAMPLE_FILE_NAME}) - endif() - endforeach() - - # include files - file(GLOB GUDHI_INCLUDE_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/include/gudhi/*) - - foreach(GUDHI_INCLUDE_FILE ${GUDHI_INCLUDE_FILES}) - get_filename_component(GUDHI_INCLUDE_FILE_NAME ${GUDHI_INCLUDE_FILE} NAME) - # GUDHI_INCLUDE_FILE can be a file or a directory - if(IS_DIRECTORY ${GUDHI_INCLUDE_FILE}) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${GUDHI_INCLUDE_FILE} ${GUDHI_USER_VERSION_DIR}/include/gudhi/${GUDHI_INCLUDE_FILE_NAME}) - else() - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy ${GUDHI_INCLUDE_FILE} ${GUDHI_USER_VERSION_DIR}/include/gudhi/${GUDHI_INCLUDE_FILE_NAME}) - endif() - endforeach() - - # concept files - file(GLOB GUDHI_CONCEPT_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/concept/*.h) - - foreach(GUDHI_CONCEPT_FILE ${GUDHI_CONCEPT_FILES}) - get_filename_component(GUDHI_CONCEPT_FILE_NAME ${GUDHI_CONCEPT_FILE} NAME) - # GUDHI_CONCEPT_FILE can be a file or a directory - if(IS_DIRECTORY ${GUDHI_CONCEPT_FILE}) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${GUDHI_CONCEPT_FILE} ${GUDHI_USER_VERSION_DIR}/concept/${GUDHI_MODULE}/${GUDHI_CONCEPT_FILE_NAME}) - else() - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy ${GUDHI_CONCEPT_FILE} ${GUDHI_USER_VERSION_DIR}/concept/${GUDHI_MODULE}/${GUDHI_CONCEPT_FILE_NAME}) - endif() - endforeach() - endforeach() + foreach(GUDHI_DIRECTORY ${GUDHI_DIRECTORIES}) + # Find files + file(GLOB GUDHI_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/${GUDHI_DIRECTORY}/*) - add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E - copy_directory ${CMAKE_SOURCE_DIR}/src/common/include/gudhi_patches ${GUDHI_USER_VERSION_DIR}/include/gudhi_patches) + foreach(GUDHI_FILE ${GUDHI_FILES}) + get_filename_component(GUDHI_FILE_NAME ${GUDHI_FILE} NAME) + # GUDHI_FILE can be a file or a directory + if(IS_DIRECTORY ${GUDHI_FILE}) + add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E + copy_directory ${GUDHI_FILE} ${GUDHI_USER_VERSION_DIR}/${GUDHI_DIRECTORY}/${GUDHI_MODULE}/${GUDHI_FILE_NAME}) + else() + add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E + copy ${GUDHI_FILE} ${GUDHI_USER_VERSION_DIR}/${GUDHI_DIRECTORY}/${GUDHI_MODULE}/${GUDHI_FILE_NAME}) + endif() + endforeach() + endforeach(GUDHI_DIRECTORY ${GUDHI_DIRECTORIES}) + + foreach(GUDHI_INCLUDE_DIRECTORY ${GUDHI_INCLUDE_DIRECTORIES}) + # include files + file(GLOB GUDHI_INCLUDE_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/${GUDHI_INCLUDE_DIRECTORY}/*) + + foreach(GUDHI_INCLUDE_FILE ${GUDHI_INCLUDE_FILES}) + get_filename_component(GUDHI_INCLUDE_FILE_NAME ${GUDHI_INCLUDE_FILE} NAME) + # GUDHI_INCLUDE_FILE can be a file or a directory + if(IS_DIRECTORY ${GUDHI_INCLUDE_FILE}) + add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E + copy_directory ${GUDHI_INCLUDE_FILE} ${GUDHI_USER_VERSION_DIR}/${GUDHI_INCLUDE_DIRECTORY}/${GUDHI_INCLUDE_FILE_NAME}) + else() + add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E + copy ${GUDHI_INCLUDE_FILE} ${GUDHI_USER_VERSION_DIR}/${GUDHI_INCLUDE_DIRECTORY}/${GUDHI_INCLUDE_FILE_NAME}) + endif() + endforeach() + endforeach(GUDHI_INCLUDE_DIRECTORY ${GUDHI_INCLUDE_DIRECTORIES}) + + endforeach(GUDHI_MODULE ${GUDHI_MODULES}) endif() diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 60c9cd07..5ca0a6bc 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -120,6 +120,7 @@ <b>Author:</b> Clément Jamin<br> <b>Introduced in:</b> GUDHI 1.4.0<br> <b>Copyright:</b> GPL v3<br> + <b>Requires:</b> \ref cgal ≥ 4.8.0 and \ref eigen3 </td> <td width="75%"> A Tangential Delaunay complex is a <a target="_blank" href="https://en.wikipedia.org/wiki/Simplicial_complex">simplicial complex</a> @@ -139,6 +140,7 @@ <b>Author:</b> Siargey Kachanovich<br> <b>Introduced in:</b> GUDHI 1.3.0<br> <b>Copyright:</b> GPL v3<br> + <b>Euclidean version requires:</b> \ref cgal ≥ 4.6.0 and \ref eigen3 </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$. @@ -412,7 +414,11 @@ make \endverbatim * @example Skeleton_blocker/Skeleton_blocker_link.cpp * @example Tangential_complex/example_basic.cpp * @example Tangential_complex/example_with_perturb.cpp - * @example Witness_complex/witness_complex_from_file.cpp - * @example Witness_complex/witness_complex_sphere.cpp + * @example Witness_complex/example_nearest_landmark_table.cpp + * @example Witness_complex/example_strong_witness_complex_off.cpp + * @example Witness_complex/example_strong_witness_persistence.cpp + * @example Witness_complex/example_witness_complex_off.cpp + * @example Witness_complex/example_witness_complex_persistence.cpp + * @example Witness_complex/example_witness_complex_sphere.cpp */ diff --git a/src/cython/CMakeLists.txt b/src/cython/CMakeLists.txt index 9e107500..e1d71c75 100644 --- a/src/cython/CMakeLists.txt +++ b/src/cython/CMakeLists.txt @@ -172,6 +172,7 @@ if(PYTHON_PATH AND CYTHON_PATH) if (UNIX) add_custom_target(sphinx WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/doc + DEPENDS "${CMAKE_CURRENT_BINARY_DIR}/gudhi.so" COMMAND make html doctest) else (UNIX) add_custom_target(sphinx diff --git a/src/debian/changelog b/src/debian/changelog deleted file mode 100644 index 32b3f6f9..00000000 --- a/src/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/src/debian/compat b/src/debian/compat deleted file mode 100644 index ec635144..00000000 --- a/src/debian/compat +++ /dev/null @@ -1 +0,0 @@ -9 diff --git a/src/debian/control b/src/debian/control deleted file mode 100644 index 838234a9..00000000 --- a/src/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/src/debian/copyright b/src/debian/copyright deleted file mode 100644 index 2e1f88cd..00000000 --- a/src/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/src/debian/docs b/src/debian/docs deleted file mode 100644 index 878a2ba1..00000000 --- a/src/debian/docs +++ /dev/null @@ -1,2 +0,0 @@ -Conventions.txt -README diff --git a/src/debian/rules b/src/debian/rules deleted file mode 100755 index c9b049af..00000000 --- a/src/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/src/debian/source/format b/src/debian/source/format deleted file mode 100644 index 163aaf8d..00000000 --- a/src/debian/source/format +++ /dev/null @@ -1 +0,0 @@ -3.0 (quilt) |
