diff options
Diffstat (limited to 'src/Simplex_tree')
24 files changed, 1144 insertions, 499 deletions
diff --git a/src/Simplex_tree/concept/FiltrationValue.h b/src/Simplex_tree/concept/FiltrationValue.h index 79ca06cc..f4dcf985 100644 --- a/src/Simplex_tree/concept/FiltrationValue.h +++ b/src/Simplex_tree/concept/FiltrationValue.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/concept/IndexingTag.h b/src/Simplex_tree/concept/IndexingTag.h index 1dcdd756..37e7e294 100644 --- a/src/Simplex_tree/concept/IndexingTag.h +++ b/src/Simplex_tree/concept/IndexingTag.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/concept/SimplexKey.h b/src/Simplex_tree/concept/SimplexKey.h index 9fbed401..c03f7da1 100644 --- a/src/Simplex_tree/concept/SimplexKey.h +++ b/src/Simplex_tree/concept/SimplexKey.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h index 89acdc18..6638da26 100644 --- a/src/Simplex_tree/concept/SimplexTreeOptions.h +++ b/src/Simplex_tree/concept/SimplexTreeOptions.h @@ -4,7 +4,7 @@ * * Author(s): Marc Glisse * - * Copyright (C) 2015 INRIA Saclay - Ile-de-France (France) + * 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 diff --git a/src/Simplex_tree/concept/VertexHandle.h b/src/Simplex_tree/concept/VertexHandle.h index 3efbba61..9d0642c3 100644 --- a/src/Simplex_tree/concept/VertexHandle.h +++ b/src/Simplex_tree/concept/VertexHandle.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/doc/COPYRIGHT b/src/Simplex_tree/doc/COPYRIGHT index 34345bef..6cde9520 100644 --- a/src/Simplex_tree/doc/COPYRIGHT +++ b/src/Simplex_tree/doc/COPYRIGHT @@ -4,7 +4,7 @@ computational topology. Author(s): Clément Maria -Copyright (C) 2015 INRIA +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 diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h index 769491d9..db399489 100644 --- a/src/Simplex_tree/doc/Intro_simplex_tree.h +++ b/src/Simplex_tree/doc/Intro_simplex_tree.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 @@ -79,7 +79,6 @@ Number of vertices = 10 Number of simplices = 98 \endcode * 1 incidence relations in a complex. It is consequently faster when accessing the boundary of a simplex, but is less * compact and harder to construct from scratch. * - * \copyright GNU General Public License v3. * @} */ diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt index 8bc4ad53..857e8518 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -1,4 +1,3 @@ -cmake_minimum_required(VERSION 2.6) project(Simplex_tree_examples) add_executable ( Simplex_tree_example_from_cliques_of_graph simplex_tree_from_cliques_of_graph.cpp ) @@ -34,6 +33,16 @@ if(GMP_FOUND AND CGAL_FOUND) "${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off") install(TARGETS Simplex_tree_example_alpha_shapes_3_from_off DESTINATION bin) + + add_executable ( Simplex_tree_example_cech_complex_cgal_mini_sphere_3d cech_complex_cgal_mini_sphere_3d.cpp ) + target_link_libraries(Simplex_tree_example_cech_complex_cgal_mini_sphere_3d ${Boost_PROGRAM_OPTIONS_LIBRARY} ${CGAL_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(Simplex_tree_example_cech_complex_cgal_mini_sphere_3d ${TBB_LIBRARIES}) + endif() + add_test(NAME Simplex_tree_example_cech_complex_cgal_mini_sphere_3d COMMAND $<TARGET_FILE:Simplex_tree_example_cech_complex_cgal_mini_sphere_3d> + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" -r 0.3 -d 3) + + install(TARGETS Simplex_tree_example_alpha_shapes_3_from_off DESTINATION bin) endif() add_executable ( Simplex_tree_example_graph_expansion_with_blocker graph_expansion_with_blocker.cpp ) diff --git a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp new file mode 100644 index 00000000..34092ef6 --- /dev/null +++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp @@ -0,0 +1,221 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2017 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/>. + */ + +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Points_off_io.h> + +#include <CGAL/Epick_d.h> +#include <CGAL/Min_sphere_of_spheres_d.h> +#include <CGAL/Min_sphere_of_points_d_traits_d.h> + +#include <boost/program_options.hpp> + +#include <string> +#include <vector> +#include <limits> // infinity +#include <utility> // for pair +#include <map> + +// ------------------------------------------------------------------------------- +// cech_complex_cgal_mini_sphere_3d is an example of each step that is required to +// build a Cech over a Simplex_tree. Please refer to cech_persistence to see +// how to do the same thing with the Cech_complex wrapper for less detailed +// steps. +// ------------------------------------------------------------------------------- + +// Types definition +using Simplex_tree = Gudhi::Simplex_tree<>; +using Vertex_handle = Simplex_tree::Vertex_handle; +using Simplex_handle = Simplex_tree::Simplex_handle; +using Filtration_value = Simplex_tree::Filtration_value; +using Siblings = Simplex_tree::Siblings; +using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, + boost::property<Gudhi::vertex_filtration_t, Filtration_value>, + boost::property<Gudhi::edge_filtration_t, Filtration_value> >; +using Edge_t = std::pair<Vertex_handle, Vertex_handle>; + +using Kernel = CGAL::Epick_d<CGAL::Dimension_tag<3> >; +using Point = Kernel::Point_d; +using Traits = CGAL::Min_sphere_of_points_d_traits_d<Kernel, Filtration_value, 3>; +using Min_sphere = CGAL::Min_sphere_of_spheres_d<Traits>; + +using Points_off_reader = Gudhi::Points_off_reader<Point>; + +class Cech_blocker { + public: + bool operator()(Simplex_handle sh) { + std::vector<Point> points; +#if DEBUG_TRACES + std::cout << "Cech_blocker on ["; +#endif // DEBUG_TRACES + for (auto vertex : simplex_tree_.simplex_vertex_range(sh)) { + points.push_back(point_cloud_[vertex]); +#if DEBUG_TRACES + std::cout << vertex << ", "; +#endif // DEBUG_TRACES + } + Min_sphere ms(points.begin(), points.end()); + Filtration_value radius = ms.radius(); +#if DEBUG_TRACES + std::cout << "] - radius = " << radius << " - returns " << (radius > threshold_) << std::endl; +#endif // DEBUG_TRACES + simplex_tree_.assign_filtration(sh, radius); + return (radius > threshold_); + } + Cech_blocker(Simplex_tree& simplex_tree, Filtration_value threshold, const std::vector<Point>& point_cloud) + : simplex_tree_(simplex_tree), threshold_(threshold), point_cloud_(point_cloud) {} + + private: + Simplex_tree simplex_tree_; + Filtration_value threshold_; + std::vector<Point> point_cloud_; +}; + +template <typename InputPointRange> +Graph_t compute_proximity_graph(InputPointRange& points, Filtration_value threshold); + +void program_options(int argc, char* argv[], std::string& off_file_points, Filtration_value& threshold, int& dim_max); + +int main(int argc, char* argv[]) { + std::string off_file_points; + Filtration_value threshold; + int dim_max; + + program_options(argc, argv, off_file_points, threshold, dim_max); + + // Extract the points from the file filepoints + Points_off_reader off_reader(off_file_points); + + // Compute the proximity graph of the points + Graph_t prox_graph = compute_proximity_graph(off_reader.get_point_cloud(), threshold); + + // Min_sphere sph1(off_reader.get_point_cloud()[0], off_reader.get_point_cloud()[1], off_reader.get_point_cloud()[2]); + // Construct the Rips complex in a Simplex Tree + Simplex_tree st; + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion_with_blockers(dim_max, Cech_blocker(st, threshold, off_reader.get_point_cloud())); + + std::cout << "The complex contains " << st.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << st.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + +#if DEBUG_TRACES + std::cout << "********************************************************************\n"; + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "* The complex contains " << st.num_simplices() << " simplices - dimension=" << st.dimension() << "\n"; + std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " + << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << static_cast<int>(vertex) << " "; + } + std::cout << std::endl; + } +#endif // DEBUG_TRACES + return 0; +} + +void program_options(int argc, char* argv[], std::string& off_file_points, Filtration_value& threshold, int& dim_max) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options()("input-file", po::value<std::string>(&off_file_points), + "Name of an OFF file containing a 3d point set.\n"); + + po::options_description visible("Allowed options", 100); + visible.add_options()("help,h", "produce help message")( + "max-edge-length,r", + po::value<Filtration_value>(&threshold)->default_value(std::numeric_limits<Filtration_value>::infinity()), + "Maximal length of an edge for the Cech complex construction.")( + "cpx-dimension,d", po::value<int>(&dim_max)->default_value(1), + "Maximal dimension of the Cech 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 << "Construct a Cech complex defined on a set of input points.\n \n"; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + exit(-1); + } +} + +/** Output the proximity graph of the points. + * + * 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. + * + * The type PointCloud furnishes .begin() and .end() methods, that return + * iterators with value_type Point. + */ +template <typename InputPointRange> +Graph_t compute_proximity_graph(InputPointRange& points, Filtration_value threshold) { + std::vector<Edge_t> edges; + std::vector<Filtration_value> edges_fil; + + Kernel k; + Vertex_handle idx_u, idx_v; + Filtration_value fil; + idx_u = 0; + for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { + idx_v = idx_u + 1; + for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { + fil = k.squared_distance_d_object()(*it_u, *it_v); + // For Cech Complex, threshold is a radius (distance /2) + fil = std::sqrt(fil) / 2.; + if (fil <= threshold) { + edges.emplace_back(idx_u, idx_v); + edges_fil.push_back(fil); + } + } + ++idx_u; + } + + Graph_t skel_graph(edges.begin(), edges.end(), edges_fil.begin(), + idx_u); // number of points labeled from 0 to idx_u-1 + + auto vertex_prop = boost::get(Gudhi::vertex_filtration_t(), skel_graph); + + boost::graph_traits<Graph_t>::vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); vi != vi_end; ++vi) { + boost::put(vertex_prop, *vi, 0.); + } + + return skel_graph; +} diff --git a/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp index ff2eebcb..290a9d9b 100644 --- a/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp +++ b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2014 INRIA Saclay (France) + * Copyright (C) 2014 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 @@ -28,6 +28,8 @@ #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_3.h> #include <CGAL/Alpha_shape_3.h> +#include <CGAL/Alpha_shape_vertex_base_3.h> +#include <CGAL/Alpha_shape_cell_base_3.h> #include <CGAL/iterator.h> #include <fstream> diff --git a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp index 86bfb8cb..f39de31f 100644 --- a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp +++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2014 + * Copyright (C) 2014 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 @@ -27,51 +27,49 @@ using Simplex_tree = Gudhi::Simplex_tree<>; using Simplex_handle = Simplex_tree::Simplex_handle; -int main(int argc, char * const argv[]) { - +int main(int argc, char* const argv[]) { // Construct the Simplex Tree with a 1-skeleton graph example - Simplex_tree simplexTree; + Simplex_tree stree; - simplexTree.insert_simplex({0, 1}, 0.); - simplexTree.insert_simplex({0, 2}, 1.); - simplexTree.insert_simplex({0, 3}, 2.); - simplexTree.insert_simplex({1, 2}, 3.); - simplexTree.insert_simplex({1, 3}, 4.); - simplexTree.insert_simplex({2, 3}, 5.); - simplexTree.insert_simplex({2, 4}, 6.); - simplexTree.insert_simplex({3, 6}, 7.); - simplexTree.insert_simplex({4, 5}, 8.); - simplexTree.insert_simplex({4, 6}, 9.); - simplexTree.insert_simplex({5, 6}, 10.); - simplexTree.insert_simplex({6}, 10.); + stree.insert_simplex({0, 1}, 0.); + stree.insert_simplex({0, 2}, 1.); + stree.insert_simplex({0, 3}, 2.); + stree.insert_simplex({1, 2}, 3.); + stree.insert_simplex({1, 3}, 4.); + stree.insert_simplex({2, 3}, 5.); + stree.insert_simplex({2, 4}, 6.); + stree.insert_simplex({3, 6}, 7.); + stree.insert_simplex({4, 5}, 8.); + stree.insert_simplex({4, 6}, 9.); + stree.insert_simplex({5, 6}, 10.); + stree.insert_simplex({6}, 10.); - simplexTree.expansion_with_blockers(3, [&](Simplex_handle sh){ - bool result = false; - std::cout << "Blocker on ["; - // User can loop on the vertices from the given simplex_handle i.e. - for (auto vertex : simplexTree.simplex_vertex_range(sh)) { - // We block the expansion, if the vertex '6' is in the given list of vertices - if (vertex == 6) - result = true; - std::cout << vertex << ", "; - } - std::cout << "] ( " << simplexTree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) - simplexTree.assign_filtration(sh, simplexTree.filtration(sh) + 1.); + stree.expansion_with_blockers(3, [&](Simplex_handle sh) { + bool result = false; + std::cout << "Blocker on ["; + // User can loop on the vertices from the given simplex_handle i.e. + for (auto vertex : stree.simplex_vertex_range(sh)) { + // We block the expansion, if the vertex '6' is in the given list of vertices + if (vertex == 6) result = true; + std::cout << vertex << ", "; + } + std::cout << "] ( " << stree.filtration(sh); + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + stree.assign_filtration(sh, stree.filtration(sh) + 1.); - std::cout << " + 1. ) = " << result << std::endl; + std::cout << " + 1. ) = " << result << std::endl; - return result; - }); + return result; + }); std::cout << "********************************************************************\n"; - std::cout << "* The complex contains " << simplexTree.num_simplices() << " simplices"; - std::cout << " - dimension " << simplexTree.dimension() << "\n"; + std::cout << "* The complex contains " << stree.num_simplices() << " simplices"; + std::cout << " - dimension " << stree.dimension() << "\n"; std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; - for (auto f_simplex : simplexTree.filtration_simplex_range()) { - std::cout << " " << "[" << simplexTree.filtration(f_simplex) << "] "; - for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; + for (auto f_simplex : stree.filtration_simplex_range()) { + std::cout << " " + << "[" << stree.filtration(f_simplex) << "] "; + for (auto vertex : stree.simplex_vertex_range(f_simplex)) std::cout << "(" << vertex << ")"; std::cout << std::endl; } diff --git a/src/Simplex_tree/example/mini_simplex_tree.cpp b/src/Simplex_tree/example/mini_simplex_tree.cpp index ad99df23..e7c7177f 100644 --- a/src/Simplex_tree/example/mini_simplex_tree.cpp +++ b/src/Simplex_tree/example/mini_simplex_tree.cpp @@ -4,7 +4,7 @@ * * Author(s): Marc Glisse * - * Copyright (C) 2015 INRIA Saclay - Ile-de-France (France) + * 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 @@ -52,8 +52,6 @@ int main() { auto edge03 = {0, 3}; st.insert_simplex_and_subfaces(triangle012); st.insert_simplex_and_subfaces(edge03); - // FIXME: Remove this line - st.set_dimension(2); auto edge02 = {0, 2}; ST::Simplex_handle e = st.find(edge02); diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp index 09cda526..d71b5608 100644 --- a/src/Simplex_tree/example/simple_simplex_tree.cpp +++ b/src/Simplex_tree/example/simple_simplex_tree.cpp @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2014 + * Copyright (C) 2014 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 @@ -30,10 +30,10 @@ using Simplex_tree = Gudhi::Simplex_tree<>; using Vertex_handle = Simplex_tree::Vertex_handle; using Filtration_value = Simplex_tree::Filtration_value; -using typeVectorVertex = std::vector< Vertex_handle >; -using typePairSimplexBool = std::pair< Simplex_tree::Simplex_handle, bool >; +using typeVectorVertex = std::vector<Vertex_handle>; +using typePairSimplexBool = std::pair<Simplex_tree::Simplex_handle, bool>; -int main(int argc, char * const argv[]) { +int main(int argc, char* const argv[]) { const Filtration_value FIRST_FILTRATION_VALUE = 0.1; const Filtration_value SECOND_FILTRATION_VALUE = 0.2; const Filtration_value THIRD_FILTRATION_VALUE = 0.3; @@ -54,7 +54,7 @@ int main(int argc, char * const argv[]) { // ++ FIRST std::cout << " * INSERT 0" << std::endl; - typeVectorVertex firstSimplexVector = { 0 }; + typeVectorVertex firstSimplexVector = {0}; typePairSimplexBool returnValue = simplexTree.insert_simplex(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); @@ -66,9 +66,8 @@ int main(int argc, char * const argv[]) { // ++ SECOND std::cout << " * INSERT 1" << std::endl; - typeVectorVertex secondSimplexVector = { 1 }; - returnValue = - simplexTree.insert_simplex(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + typeVectorVertex secondSimplexVector = {1}; + returnValue = simplexTree.insert_simplex(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + 1 INSERTED" << std::endl; @@ -78,9 +77,8 @@ int main(int argc, char * const argv[]) { // ++ THIRD std::cout << " * INSERT (0,1)" << std::endl; - typeVectorVertex thirdSimplexVector = { 0, 1 }; - returnValue = - simplexTree.insert_simplex(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + typeVectorVertex thirdSimplexVector = {0, 1}; + returnValue = simplexTree.insert_simplex(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (0,1) INSERTED" << std::endl; @@ -90,9 +88,8 @@ int main(int argc, char * const argv[]) { // ++ FOURTH std::cout << " * INSERT 2" << std::endl; - typeVectorVertex fourthSimplexVector = { 2 }; - returnValue = - simplexTree.insert_simplex(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + typeVectorVertex fourthSimplexVector = {2}; + returnValue = simplexTree.insert_simplex(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + 2 INSERTED" << std::endl; @@ -102,9 +99,8 @@ int main(int argc, char * const argv[]) { // ++ FIFTH std::cout << " * INSERT (2,0)" << std::endl; - typeVectorVertex fifthSimplexVector = { 2, 0 }; - returnValue = - simplexTree.insert_simplex(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + typeVectorVertex fifthSimplexVector = {2, 0}; + returnValue = simplexTree.insert_simplex(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (2,0) INSERTED" << std::endl; @@ -114,9 +110,8 @@ int main(int argc, char * const argv[]) { // ++ SIXTH std::cout << " * INSERT (2,1)" << std::endl; - typeVectorVertex sixthSimplexVector = { 2, 1 }; - returnValue = - simplexTree.insert_simplex(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + typeVectorVertex sixthSimplexVector = {2, 1}; + returnValue = simplexTree.insert_simplex(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (2,1) INSERTED" << std::endl; @@ -126,9 +121,8 @@ int main(int argc, char * const argv[]) { // ++ SEVENTH std::cout << " * INSERT (2,1,0)" << std::endl; - typeVectorVertex seventhSimplexVector = { 2, 1, 0 }; - returnValue = - simplexTree.insert_simplex(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); + typeVectorVertex seventhSimplexVector = {2, 1, 0}; + returnValue = simplexTree.insert_simplex(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (2,1,0) INSERTED" << std::endl; @@ -138,9 +132,8 @@ int main(int argc, char * const argv[]) { // ++ EIGHTH std::cout << " * INSERT 3" << std::endl; - typeVectorVertex eighthSimplexVector = { 3 }; - returnValue = - simplexTree.insert_simplex(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + typeVectorVertex eighthSimplexVector = {3}; + returnValue = simplexTree.insert_simplex(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + 3 INSERTED" << std::endl; @@ -150,9 +143,8 @@ int main(int argc, char * const argv[]) { // ++ NINETH std::cout << " * INSERT (3,0)" << std::endl; - typeVectorVertex ninethSimplexVector = { 3, 0 }; - returnValue = - simplexTree.insert_simplex(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + typeVectorVertex ninethSimplexVector = {3, 0}; + returnValue = simplexTree.insert_simplex(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (3,0) INSERTED" << std::endl; @@ -162,7 +154,7 @@ int main(int argc, char * const argv[]) { // ++ TENTH std::cout << " * INSERT 0 (already inserted)" << std::endl; - typeVectorVertex tenthSimplexVector = { 0 }; + typeVectorVertex tenthSimplexVector = {0}; // With a different filtration value returnValue = simplexTree.insert_simplex(tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); @@ -174,9 +166,8 @@ int main(int argc, char * const argv[]) { // ++ ELEVENTH std::cout << " * INSERT (2,1,0) (already inserted)" << std::endl; - typeVectorVertex eleventhSimplexVector = { 2, 1, 0 }; - returnValue = - simplexTree.insert_simplex(eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); + typeVectorVertex eleventhSimplexVector = {2, 1, 0}; + returnValue = simplexTree.insert_simplex(eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); if (returnValue.second == true) { std::cout << " + (2,1,0) INSERTED" << std::endl; @@ -185,7 +176,6 @@ int main(int argc, char * const argv[]) { } // ++ GENERAL VARIABLE SET - simplexTree.set_dimension(2); // Max dimension = 2 -> (2,1,0) std::cout << "********************************************************************\n"; // Display the Simplex_tree - Can not be done in the middle of 2 inserts @@ -193,9 +183,9 @@ int main(int argc, char * const argv[]) { std::cout << " - dimension " << simplexTree.dimension() << "\n"; std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplexTree.filtration_simplex_range()) { - std::cout << " " << "[" << simplexTree.filtration(f_simplex) << "] "; - for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; + std::cout << " " + << "[" << simplexTree.filtration(f_simplex) << "] "; + for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) std::cout << "(" << vertex << ")"; std::cout << std::endl; } // [0.1] 0 @@ -218,7 +208,7 @@ int main(int argc, char * const argv[]) { else std::cout << "***- NO IT ISN'T\n"; - typeVectorVertex unknownSimplexVector = { 15 }; + typeVectorVertex unknownSimplexVector = {15}; simplexFound = simplexTree.find(unknownSimplexVector); std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) @@ -233,7 +223,7 @@ int main(int argc, char * const argv[]) { else std::cout << "***- NO IT ISN'T\n"; - typeVectorVertex otherSimplexVector = { 1, 15 }; + typeVectorVertex otherSimplexVector = {1, 15}; simplexFound = simplexTree.find(otherSimplexVector); std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) @@ -241,7 +231,7 @@ int main(int argc, char * const argv[]) { else std::cout << "***- NO IT ISN'T\n"; - typeVectorVertex invSimplexVector = { 1, 2, 0 }; + typeVectorVertex invSimplexVector = {1, 2, 0}; simplexFound = simplexTree.find(invSimplexVector); std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) @@ -249,7 +239,7 @@ int main(int argc, char * const argv[]) { else std::cout << "***- NO IT ISN'T\n"; - simplexFound = simplexTree.find({ 0, 1 }); + simplexFound = simplexTree.find({0, 1}); std::cout << "**************IS THE SIMPLEX {0,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) std::cout << "***+ YES IT IS!\n"; @@ -257,23 +247,20 @@ int main(int argc, char * const argv[]) { std::cout << "***- NO IT ISN'T\n"; std::cout << "**************COFACES OF {0,1} IN CODIMENSION 1 ARE\n"; - for (auto& simplex : simplexTree.cofaces_simplex_range(simplexTree.find({0,1}), 1)) { - for (auto vertex : simplexTree.simplex_vertex_range(simplex)) - std::cout << "(" << vertex << ")"; + for (auto& simplex : simplexTree.cofaces_simplex_range(simplexTree.find({0, 1}), 1)) { + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::cout << "(" << vertex << ")"; std::cout << std::endl; } std::cout << "**************STARS OF {0,1} ARE\n"; - for (auto& simplex : simplexTree.star_simplex_range(simplexTree.find({0,1}))) { - for (auto vertex : simplexTree.simplex_vertex_range(simplex)) - std::cout << "(" << vertex << ")"; + for (auto& simplex : simplexTree.star_simplex_range(simplexTree.find({0, 1}))) { + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::cout << "(" << vertex << ")"; std::cout << std::endl; } std::cout << "**************BOUNDARIES OF {0,1,2} ARE\n"; - for (auto& simplex : simplexTree.boundary_simplex_range(simplexTree.find({0,1,2}))) { - for (auto vertex : simplexTree.simplex_vertex_range(simplex)) - std::cout << "(" << vertex << ")"; + for (auto& simplex : simplexTree.boundary_simplex_range(simplexTree.find({0, 1, 2}))) { + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::cout << "(" << vertex << ")"; std::cout << std::endl; } diff --git a/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp b/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp index d1b8b2de..6d70f3d1 100644 --- a/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp +++ b/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 8ab3da41..3ab23c12 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 @@ -49,6 +49,7 @@ #include <initializer_list> #include <algorithm> // for std::max #include <cstdint> // for std::uint32_t +#include <iterator> // for std::distance namespace Gudhi { @@ -106,8 +107,9 @@ class Simplex_tree { }; struct Key_simplex_base_dummy { Key_simplex_base_dummy() {} - void assign_key(Simplex_key) { } - Simplex_key key() const { assert(false); return -1; } + // Undefined so it will not link + void assign_key(Simplex_key); + Simplex_key key() const; }; typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base; @@ -121,7 +123,7 @@ class Simplex_tree { }; struct Filtration_simplex_base_dummy { Filtration_simplex_base_dummy() {} - void assign_filtration(Filtration_value f) { assert(f == 0); } + void assign_filtration(Filtration_value GUDHI_CHECK_code(f)) { GUDHI_CHECK(f == 0, "filtration value specified for a complex that does not store them"); } Filtration_value filtration() const { return 0; } }; typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real, @@ -391,13 +393,13 @@ class Simplex_tree { return sh->second.key(); } - /** \brief Returns the simplex associated to a key. + /** \brief Returns the simplex that has index idx in the filtration. * * The filtration must be initialized. * \pre SimplexTreeOptions::store_key */ - Simplex_handle simplex(Simplex_key key) const { - return filtration_vect_[key]; + Simplex_handle simplex(Simplex_key idx) const { + return filtration_vect_[idx]; } /** \brief Returns the filtration value of a simplex. @@ -482,7 +484,17 @@ class Simplex_tree { } /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() const { + int upper_bound_dimension() const { + return dimension_; + } + + /** \brief Returns the dimension of the simplicial complex. + \details This function is not constant time because it can recompute dimension if required (can be triggered by + `remove_maximal_simplex()` or `prune_above_filtration()`). + */ + int dimension() { + if (dimension_to_be_lowered_) + lower_upper_bound_dimension(); return dimension_; } @@ -490,6 +502,7 @@ class Simplex_tree { * sh has children.*/ template<class SimplexHandle> bool has_children(SimplexHandle sh) const { + // Here we rely on the root using null_vertex(), which cannot match any real vertex. return (sh->second.children()->parent() == sh->first); } @@ -519,18 +532,30 @@ class Simplex_tree { Simplex_handle find_simplex(const std::vector<Vertex_handle> & simplex) { Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; - Vertex_handle last = simplex.back(); - for (auto v : simplex) { - tmp_dit = tmp_sib->members_.find(v); - if (tmp_dit == tmp_sib->members_.end()) { + auto vi = simplex.begin(); + if (Options::contiguous_vertices) { + // Equivalent to the first iteration of the normal loop + GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices"); + Vertex_handle v = *vi++; + if(v < 0 || v >= static_cast<Vertex_handle>(root_.members_.size())) return null_simplex(); - } - if (!has_children(tmp_dit) && v != last) { + tmp_dit = root_.members_.begin() + v; + if (vi == simplex.end()) + return tmp_dit; + if (!has_children(tmp_dit)) + return null_simplex(); + tmp_sib = tmp_dit->second.children(); + } + for (;;) { + tmp_dit = tmp_sib->members_.find(*vi++); + if (tmp_dit == tmp_sib->members_.end()) + return null_simplex(); + if (vi == simplex.end()) + return tmp_dit; + if (!has_children(tmp_dit)) return null_simplex(); - } tmp_sib = tmp_dit->second.children(); } - return tmp_dit; } /** \brief Returns the Simplex_handle corresponding to the 0-simplex @@ -574,12 +599,14 @@ class Simplex_tree { std::pair<Simplex_handle, bool> res_insert; auto vi = simplex.begin(); for (; vi != simplex.end() - 1; ++vi) { + GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!(has_children(res_insert.first))) { res_insert.first->second.assign_children(new Siblings(curr_sib, *vi)); } curr_sib = res_insert.first->second.children(); } + GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!res_insert.second) { // if already in the complex @@ -591,7 +618,11 @@ class Simplex_tree { // if filtration value unchanged return std::pair<Simplex_handle, bool>(null_simplex(), false); } - // otherwise the insertion has succeeded + // otherwise the insertion has succeeded - size is a size_type + if (static_cast<int>(simplex.size()) - 1 > dimension_) { + // Update dimension if needed + dimension_ = static_cast<int>(simplex.size()) - 1; + } return res_insert; } @@ -650,71 +681,71 @@ class Simplex_tree { */ template<class InputVertexRange = std::initializer_list<Vertex_handle>> std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, - Filtration_value filtration = 0) { + Filtration_value filtration = 0) { auto first = std::begin(Nsimplex); auto last = std::end(Nsimplex); if (first == last) - return std::pair<Simplex_handle, bool>(null_simplex(), true); // ----->> + return { null_simplex(), true }; // ----->> // Copy before sorting - std::vector<Vertex_handle> copy(first, last); + // Thread local is not available on XCode version < V.8 - It will slow down computation +#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL + thread_local +#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL + std::vector<Vertex_handle> copy; + copy.clear(); + copy.insert(copy.end(), first, last); std::sort(std::begin(copy), std::end(copy)); + GUDHI_CHECK_code( + for (Vertex_handle v : copy) + GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); + ) - std::vector<std::vector<Vertex_handle>> to_be_inserted; - std::vector<std::vector<Vertex_handle>> to_be_propagated; - return rec_insert_simplex_and_subfaces(copy, to_be_inserted, to_be_propagated, filtration); + return insert_simplex_and_subfaces_sorted(copy, filtration); } private: - std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces(std::vector<Vertex_handle>& the_simplex, - std::vector<std::vector<Vertex_handle>>& to_be_inserted, - std::vector<std::vector<Vertex_handle>>& to_be_propagated, - Filtration_value filtration = 0.0) { - std::pair<Simplex_handle, bool> insert_result; - if (the_simplex.size() > 1) { - // Get and remove last vertex - Vertex_handle last_vertex = the_simplex.back(); - the_simplex.pop_back(); - // Recursive call after last vertex removal - insert_result = rec_insert_simplex_and_subfaces(the_simplex, to_be_inserted, to_be_propagated, filtration); - - // Concatenation of to_be_inserted and to_be_propagated - to_be_inserted.insert(to_be_inserted.begin(), to_be_propagated.begin(), to_be_propagated.end()); - to_be_propagated = to_be_inserted; - - // to_be_inserted treatment - for (auto& simplex_tbi : to_be_inserted) { - simplex_tbi.push_back(last_vertex); - } - std::vector<Vertex_handle> last_simplex(1, last_vertex); - to_be_inserted.insert(to_be_inserted.begin(), last_simplex); - // i.e. (0,1,2) => - // [to_be_inserted | to_be_propagated] = [(1) (0,1) | (0)] - // [to_be_inserted | to_be_propagated] = [(2) (0,2) (1,2) (0,1,2) | (0) (1) (0,1)] - // N.B. : it is important the last inserted to be the highest in dimension - // in order to return the "last" insert_simplex result - - // insert all to_be_inserted - for (auto& simplex_tbi : to_be_inserted) { - insert_result = insert_vertex_vector(simplex_tbi, filtration); - } - } else if (the_simplex.size() == 1) { - // When reaching the end of recursivity, vector of simplices shall be empty and filled on back recursive - if ((to_be_inserted.size() != 0) || (to_be_propagated.size() != 0)) { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty\n"; - exit(-1); + /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted + template<class ForwardVertexRange = std::initializer_list<Vertex_handle>> + std::pair<Simplex_handle, bool> insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex, Filtration_value filt = 0) { + auto first = std::begin(Nsimplex); + auto last = std::end(Nsimplex); + if (first == last) + return { null_simplex(), true }; // FIXME: false would make more sense to me. + GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order"); + // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain. + dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(first, last)) - 1); + return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt); + } + // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. + template<class ForwardVertexIterator> + std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib, ForwardVertexIterator first, ForwardVertexIterator last, Filtration_value filt) { + // An alternative strategy would be: + // - try to find the complete simplex, if found (and low filtration) exit + // - insert all the vertices at once in sib + // - loop over those (new or not) simplices, with a recursive call(++first, last) + Vertex_handle vertex_one = *first; + auto&& dict = sib->members(); + auto insertion_result = dict.emplace(vertex_one, Node(sib, filt)); + Simplex_handle simplex_one = insertion_result.first; + bool one_is_new = insertion_result.second; + if (!one_is_new) { + if (filtration(simplex_one) > filt) { + assign_filtration(simplex_one, filt); + } else { + // FIXME: this interface makes no sense, and it doesn't seem to be tested. + insertion_result.first = null_simplex(); } - std::vector<Vertex_handle> first_simplex(1, the_simplex.back()); - // i.e. (0,1,2) => [to_be_inserted | to_be_propagated] = [(0) | ] - to_be_inserted.push_back(first_simplex); - - insert_result = insert_vertex_vector(first_simplex, filtration); - } else { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error\n"; - exit(-1); } - return insert_result; + if (++first == last) return insertion_result; + if (!has_children(simplex_one)) + // TODO: have special code here, we know we are building the whole subtree from scratch. + simplex_one->second.assign_children(new Siblings(sib, vertex_one)); + auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt); + // No need to continue if the full simplex was already there with a low enough filtration value. + if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt); + return res; } public: @@ -747,8 +778,12 @@ class Simplex_tree { return &root_; } - /** Set a dimension for the simplicial complex. */ + /** \brief Set a dimension for the simplicial complex. + * \details This function must be used with caution because it disables dimension recomputation when required + * (this recomputation can be triggered by `remove_maximal_simplex()` or `prune_above_filtration()`). + */ void set_dimension(int dimension) { + dimension_to_be_lowered_ = false; dimension_ = dimension; } @@ -923,8 +958,9 @@ class Simplex_tree { * called. * * Inserts all vertices and edges given by a OneSkeletonGraph. - * OneSkeletonGraph must be a model of boost::AdjacencyGraph, - * boost::EdgeListGraph and boost::PropertyGraph. + * OneSkeletonGraph must be a model of + * <a href="http://www.boost.org/doc/libs/1_65_1/libs/graph/doc/EdgeListGraph.html">boost::EdgeListGraph</a> + * and <a href="http://www.boost.org/doc/libs/1_65_1/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>. * * The vertex filtration value is accessible through the property tag * vertex_filtration_t. @@ -934,7 +970,10 @@ class Simplex_tree { * boost::graph_traits<OneSkeletonGraph>::vertex_descriptor * must be Vertex_handle. * boost::graph_traits<OneSkeletonGraph>::directed_category - * must be undirected_tag. */ + * must be undirected_tag. + * + * If an edge appears with multiplicity, the function will arbitrarily pick + * one representative to read the filtration value. */ template<class OneSkeletonGraph> void insert_graph(const OneSkeletonGraph& skel_graph) { // the simplex tree must be empty @@ -965,18 +1004,22 @@ class Simplex_tree { ++e_it) { auto u = source(*e_it, skel_graph); auto v = target(*e_it, skel_graph); - if (u < v) { - // count edges only once { std::swap(u,v); } // u < v - auto sh = find_vertex(u); - if (!has_children(sh)) { - sh->second.assign_children(new Siblings(&root_, sh->first)); - } - - sh->second.children()->members().emplace( - v, - Node(sh->second.children(), - boost::get(edge_filtration_t(), skel_graph, *e_it))); + if (u == v) throw "Self-loops are not simplicial"; + // We cannot skip edges with the wrong orientation and expect them to + // come a second time with the right orientation, that does not always + // happen in practice. emplace() should be a NOP when an element with the + // same key is already there, so seeing the same edge multiple times is + // ok. + // Should we actually forbid multiple edges? That would be consistent + // with rejecting self-loops. + if (v < u) std::swap(u, v); + auto sh = find_vertex(u); + if (!has_children(sh)) { + sh->second.assign_children(new Siblings(&root_, sh->first)); } + + sh->second.children()->members().emplace(v, + Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, *e_it))); } } @@ -1014,7 +1057,10 @@ class Simplex_tree { Dictionary_it next = siblings->members().begin(); ++next; - thread_local std::vector<std::pair<Vertex_handle, Node> > inter; +#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL + thread_local +#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL + std::vector<std::pair<Vertex_handle, Node> > inter; for (Dictionary_it s_h = siblings->members().begin(); s_h != siblings->members().end(); ++s_h, ++next) { Simplex_handle root_sh = find_vertex(s_h->first); @@ -1120,7 +1166,7 @@ class Simplex_tree { to_be_inserted=false; break; } - filt = std::max(filt, filtration(border_child)); + filt = (std::max)(filt, filtration(border_child)); } if (to_be_inserted) { intersection.emplace_back(next->first, Node(nullptr, filt)); @@ -1131,7 +1177,7 @@ class Simplex_tree { Siblings * new_sib = new Siblings(siblings, // oncles simplex->first, // parent boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t - std::vector<Simplex_handle> blocked_new_sib_list; + std::vector<Vertex_handle> blocked_new_sib_vertex_list; // As all intersections are inserted, we can call the blocker function on all new_sib members for (auto new_sib_member = new_sib->members().begin(); new_sib_member != new_sib->members().end(); @@ -1139,17 +1185,19 @@ class Simplex_tree { bool blocker_result = block_simplex(new_sib_member); // new_sib member has been blocked by the blocker function // add it to the list to be removed - do not perform it while looping on it - if (blocker_result) - blocked_new_sib_list.push_back(new_sib_member); - } - bool removed = false; - for (auto& blocked_new_sib_member : blocked_new_sib_list){ - removed = removed || remove_maximal_simplex(blocked_new_sib_member); + if (blocker_result) { + blocked_new_sib_vertex_list.push_back(new_sib_member->first); + } } - if (removed) { + if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) { + // Specific case where all have to be deleted + delete new_sib; // ensure the children property simplex->second.assign_children(siblings); } else { + for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) { + new_sib->members().erase(blocked_new_sib_member); + } // ensure recursive call simplex->second.assign_children(new_sib); siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex); @@ -1197,9 +1245,8 @@ class Simplex_tree { } public: - /** \brief Browse the simplex tree to ensure the filtration is not decreasing. - * The simplex tree is browsed starting from the root until the leaf, and the filtration values are set with their - * parent value (increased), in case the values are decreasing. + /** \brief This function ensures that each simplex has a higher filtration value than its faces by increasing the + * filtration values. * @return The filtration modification information. * \post Some simplex tree functions require the filtration to be valid. `make_filtration_non_decreasing()` * function is not launching `initialize_filtration()` but returns the filtration modification information. If the @@ -1254,6 +1301,9 @@ class Simplex_tree { * \post Some simplex tree functions require the filtration to be valid. `prune_above_filtration()` * function is not launching `initialize_filtration()` but returns the filtration modification information. If the * complex has changed , please call `initialize_filtration()` to recompute it. + * \post Note that the dimension of the simplicial complex may be lower after calling `prune_above_filtration()` + * than it was before. However, `upper_bound_dimension()` will return the old value, which remains a valid upper + * bound. If you care, you can call `dimension()` to recompute the exact dimension. */ bool prune_above_filtration(Filtration_value filtration) { return rec_prune_above_filtration(root(), filtration); @@ -1265,6 +1315,8 @@ class Simplex_tree { auto last = std::remove_if(list.begin(), list.end(), [=](Dit_value_t& simplex) { if (simplex.second.filtration() <= filt) return false; if (has_children(&simplex)) rec_delete(simplex.second.children()); + // dimension may need to be lowered + dimension_to_be_lowered_ = true; return true; }); @@ -1273,6 +1325,8 @@ class Simplex_tree { // Removing the whole siblings, parent becomes a leaf. sib->oncles()->members()[sib->parent()].assign_children(sib->oncles()); delete sib; + // dimension may need to be lowered + dimension_to_be_lowered_ = true; return true; } else { // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones. @@ -1284,16 +1338,47 @@ class Simplex_tree { return modified; } + private: + /** \brief Deep search simplex tree dimension recompute. + * @return True if the dimension was modified, false otherwise. + * \pre Be sure the simplex tree has not a too low dimension value as the deep search stops when the former dimension + * has been reached (cf. `upper_bound_dimension()` and `set_dimension()` methods). + */ + bool lower_upper_bound_dimension() { + // reset automatic detection to recompute + dimension_to_be_lowered_ = false; + int new_dimension = -1; + // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree + for (Simplex_handle sh : complex_simplex_range()) { +#ifdef DEBUG_TRACES + for (auto vertex : simplex_vertex_range(sh)) { + std::cout << " " << vertex; + } + std::cout << std::endl; +#endif // DEBUG_TRACES + + int sh_dimension = dimension(sh); + if (sh_dimension >= dimension_) + // Stop browsing as soon as the dimension is reached, no need to go furter + return false; + new_dimension = (std::max)(new_dimension, sh_dimension); + } + dimension_ = new_dimension; + return true; + } + + public: /** \brief Remove a maximal simplex. * @param[in] sh Simplex handle on the maximal simplex to remove. - * @return a boolean value that is an implementation detail, and that the user is supposed to ignore * \pre Please check the simplex has no coface before removing it. * \exception std::invalid_argument In debug mode, if sh has children. * \post Be aware that removing is shifting data in a flat_map (initialize_filtration to be done). - * \internal @return true if the leaf's branch has no other leaves (branch's children has been re-assigned), false otherwise. + * \post Note that the dimension of the simplicial complex may be lower after calling `remove_maximal_simplex()` + * than it was before. However, `upper_bound_dimension()` will return the old value, which remains a valid upper + * bound. If you care, you can call `dimension()` to recompute the exact dimension. */ - bool remove_maximal_simplex(Simplex_handle sh) { + void remove_maximal_simplex(Simplex_handle sh) { // Guarantee the simplex has no children GUDHI_CHECK(!has_children(sh), std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children")); @@ -1309,9 +1394,9 @@ class Simplex_tree { // Sibling is emptied : must be deleted, and its parent must point on his own Sibling child->oncles()->members().at(child->parent()).assign_children(child->oncles()); delete child; - return true; + // dimension may need to be lowered + dimension_to_be_lowered_ = true; } - return false; } private: @@ -1323,6 +1408,7 @@ class Simplex_tree { std::vector<Simplex_handle> filtration_vect_; /** \brief Upper bound on the dimension of the simplicial complex.*/ int dimension_; + bool dimension_to_be_lowered_ = false; }; // Print a Simplex_tree in os. diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h index 7e0a454d..02c8bb64 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 @@ -23,6 +23,8 @@ #ifndef SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_ #define SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_ +#include <gudhi/Debug_utils.h> + #include <boost/iterator/iterator_facade.hpp> #include <boost/version.hpp> #if BOOST_VERSION >= 105600 @@ -99,7 +101,9 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< // any end() iterator explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st) - : sib_(nullptr), + : last_(st->null_vertex()), + next_(st->null_vertex()), + sib_(nullptr), sh_(st->null_simplex()), st_(st) { } @@ -107,16 +111,23 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< template<class SimplexHandle> Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh) : last_(sh->first), + next_(st->null_vertex()), sib_(nullptr), + sh_(st->null_simplex()), st_(st) { + // Only check once at the beginning instead of for every increment, as this is expensive. + if (SimplexTree::Options::contiguous_vertices) + GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes"); Siblings * sib = st->self_siblings(sh); next_ = sib->parent(); sib_ = sib->oncles(); if (sib_ != nullptr) { - sh_ = sib_->find(next_); - } else { - sh_ = st->null_simplex(); - } // vertex: == end() + if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr) + // Only relevant for edges + sh_ = sib_->members_.begin()+next_; + else + sh_ = sib_->find(next_); + } } private: @@ -140,14 +151,19 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< Siblings * for_sib = sib_; Siblings * new_sib = sib_->oncles(); auto rit = suffix_.rbegin(); - if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr && rit != suffix_.rend()) { - // We reached the root, use a short-cut to find a vertex. We could also - // optimize finding the second vertex of a segment, but people are - // expected to call endpoints(). - assert(st_->contiguous_vertices()); - sh_ = for_sib->members_.begin()+*rit; - for_sib = sh_->second.children(); - ++rit; + if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) { + // We reached the root, use a short-cut to find a vertex. + if (rit == suffix_.rend()) { + // Segment, this vertex is the last boundary simplex + sh_ = for_sib->members_.begin()+last_; + sib_ = nullptr; + return; + } else { + // Dim >= 2, initial step of the descent + sh_ = for_sib->members_.begin()+*rit; + for_sib = sh_->second.children(); + ++rit; + } } for (; rit != suffix_.rend(); ++rit) { sh_ = for_sib->find(*rit); diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index 25d4888a..3a75ec72 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index 1eca7f6f..ab2ca707 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h index 0adeb46d..ec4461f3 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h @@ -4,7 +4,7 @@ * * Author(s): Clément Maria * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 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 diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt index fc34e6aa..c63d8532 100644 --- a/src/Simplex_tree/test/CMakeLists.txt +++ b/src/Simplex_tree/test/CMakeLists.txt @@ -1,23 +1,30 @@ -cmake_minimum_required(VERSION 2.6) project(Simplex_tree_tests) include(GUDHI_test_coverage) +# Do not forget to copy test files in current binary dir +file(COPY "simplex_tree_for_unit_test.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + add_executable ( Simplex_tree_test_unit simplex_tree_unit_test.cpp ) target_link_libraries(Simplex_tree_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) if (TBB_FOUND) target_link_libraries(Simplex_tree_test_unit ${TBB_LIBRARIES}) endif() -# Do not forget to copy test files in current binary dir -file(COPY "simplex_tree_for_unit_test.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) - gudhi_add_coverage_test(Simplex_tree_test_unit) -add_executable ( Simplex_tree_test_unit_graph_expansion simplex_tree_graph_expansion_unit_test.cpp ) -target_link_libraries(Simplex_tree_test_unit_graph_expansion ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +add_executable ( Simplex_tree_remove_test_unit simplex_tree_remove_unit_test.cpp ) +target_link_libraries(Simplex_tree_remove_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(Simplex_tree_remove_test_unit ${TBB_LIBRARIES}) +endif() + +gudhi_add_coverage_test(Simplex_tree_remove_test_unit) + +add_executable ( Simplex_tree_iostream_operator_test_unit simplex_tree_iostream_operator_unit_test.cpp ) +target_link_libraries(Simplex_tree_iostream_operator_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) if (TBB_FOUND) - target_link_libraries(Simplex_tree_test_unit_graph_expansion ${TBB_LIBRARIES}) + target_link_libraries(Simplex_tree_iostream_operator_test_unit ${TBB_LIBRARIES}) endif() -gudhi_add_coverage_test(Simplex_tree_test_unit_graph_expansion) +gudhi_add_coverage_test(Simplex_tree_iostream_operator_test_unit) diff --git a/src/Simplex_tree/test/README b/src/Simplex_tree/test/README index 21c3d871..df2ab89a 100644 --- a/src/Simplex_tree/test/README +++ b/src/Simplex_tree/test/README @@ -9,6 +9,6 @@ make To launch with details: *********************** -./SimplexTreeUT --report_level=detailed --log_level=all +./Simplex_tree_test_unit --report_level=detailed --log_level=all ==> echo $? returns 0 in case of success (non-zero otherwise) diff --git a/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp new file mode 100644 index 00000000..ecb9f025 --- /dev/null +++ b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp @@ -0,0 +1,136 @@ +#include <iostream> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simplex_tree_iostream_operator" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +// ^ +// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. +#include "gudhi/Simplex_tree.h" + +using namespace Gudhi; + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; + +typedef boost::mpl::list<Simplex_tree<>, + Simplex_tree<Simplex_tree_options_fast_persistence> + > list_of_tested_variants; + +BOOST_AUTO_TEST_CASE_TEMPLATE(iostream_operator, Stree_type, list_of_tested_variants) { + std::cout << "********************************************************************" << std::endl; + std::cout << "SIMPLEX TREE IOSTREAM OPERATOR" << std::endl; + + Stree_type st; + + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 3.0); + st.insert_simplex_and_subfaces({3, 0}, 2.0); + st.insert_simplex_and_subfaces({2, 1, 0}, 3.0); + + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = " + << st.dimension() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + // st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + std::string iostream_file("simplex_tree_for_iostream_operator_unit_test.txt"); + std::ofstream simplex_tree_ostream(iostream_file.c_str()); + simplex_tree_ostream << st; + simplex_tree_ostream.close(); + + Stree_type read_st; + std::ifstream simplex_tree_istream(iostream_file.c_str()); + simplex_tree_istream >> read_st; + + // Display the Simplex_tree + std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = " + << read_st.dimension() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : read_st.filtration_simplex_range()) { + std::cout << " " << "[" << read_st.filtration(f_simplex) << "] "; + for (auto vertex : read_st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + BOOST_CHECK(st == read_st); +} + + +BOOST_AUTO_TEST_CASE(mini_iostream_operator) { + std::cout << "********************************************************************" << std::endl; + std::cout << "MINI SIMPLEX TREE IOSTREAM OPERATOR" << std::endl; + + Simplex_tree<MyOptions> st; + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = " + << st.dimension() << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + // st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + std::string iostream_file("simplex_tree_for_iostream_operator_unit_test.txt"); + std::ofstream simplex_tree_ostream(iostream_file.c_str()); + simplex_tree_ostream << st; + simplex_tree_ostream.close(); + + Simplex_tree<MyOptions> read_st; + std::ifstream simplex_tree_istream(iostream_file.c_str()); + simplex_tree_istream >> read_st; + + // Display the Simplex_tree + std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = " + << read_st.dimension() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : read_st.filtration_simplex_range()) { + std::cout << " " << "[" << read_st.filtration(f_simplex) << "] "; + for (auto vertex : read_st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + BOOST_CHECK(st == read_st); +} diff --git a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp new file mode 100644 index 00000000..dc37375c --- /dev/null +++ b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp @@ -0,0 +1,427 @@ +#include <iostream> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simplex_tree_remove" +#include <boost/test/unit_test.hpp> + +// ^ +// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. +#include "gudhi/Simplex_tree.h" + +using namespace Gudhi; + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; + +using Mini_stree = Simplex_tree<MyOptions>; +using Stree = Simplex_tree<>; + +BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { + std::cout << "********************************************************************" << std::endl; + std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; + + Mini_stree st; + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + + // Constructs a copy at this state for further test purpose + Mini_stree st_pruned = st; + + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + // Constructs a copy at this state for further test purpose + Mini_stree st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + +#ifdef GUDHI_DEBUG + std::cout << "Check exception throw in debug mode" << std::endl; + // throw excpt because sh has children + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument); + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument); + BOOST_CHECK(st == st_complete); +#endif + std::cout << "st.remove_maximal_simplex({0, 2})" << std::endl; + st.remove_maximal_simplex(st.find({0, 2})); + std::cout << "st.remove_maximal_simplex({0, 1, 2})" << std::endl; + st.remove_maximal_simplex(st.find({0, 1, 2})); + std::cout << "st.remove_maximal_simplex({1, 2})" << std::endl; + st.remove_maximal_simplex(st.find({1, 2})); + std::cout << "st.remove_maximal_simplex({2})" << std::endl; + st.remove_maximal_simplex(st.find({2})); + std::cout << "st.remove_maximal_simplex({3})" << std::endl; + st.remove_maximal_simplex(st.find({0, 3})); + + BOOST_CHECK(st == st_pruned); + // Remove all, but as the simplex tree is not storing filtration, there is no modification + st.prune_above_filtration(0.0); + BOOST_CHECK(st == st_pruned); + + Mini_stree st_wo_seven; + + st_wo_seven.insert_simplex_and_subfaces({0, 1, 6}); + st_wo_seven.insert_simplex_and_subfaces({3, 4, 5}); + // st_wo_seven: + // 1 6 + // o---o + // \X/ + // o o---o + // 0 3\X/4 + // o + // 5 + + // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not) + std::cout << "st.remove_maximal_simplex({0, 1, 6, 7})" << std::endl; + st.remove_maximal_simplex(st.find({0, 1, 6, 7})); + std::cout << "st.remove_maximal_simplex({0, 1, 7})" << std::endl; + st.remove_maximal_simplex(st.find({0, 1, 7})); + std::cout << "st.remove_maximal_simplex({0, 6, 7})" << std::endl; + st.remove_maximal_simplex(st.find({0, 6, 7})); + std::cout << "st.remove_maximal_simplex({0, 7})" << std::endl; + st.remove_maximal_simplex(st.find({0, 7})); + std::cout << "st.remove_maximal_simplex({1, 6, 7})" << std::endl; + st.remove_maximal_simplex(st.find({1, 6, 7})); + std::cout << "st.remove_maximal_simplex({1, 7})" << std::endl; + st.remove_maximal_simplex(st.find({1, 7})); + std::cout << "st.remove_maximal_simplex({6, 7})" << std::endl; + st.remove_maximal_simplex(st.find({6, 7})); + std::cout << "st.remove_maximal_simplex({7})" << std::endl; + st.remove_maximal_simplex(st.find({7})); + + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + + // Check dimension calls lower_upper_bound_dimension to recompute dimension + BOOST_CHECK(st.dimension() == 2); + BOOST_CHECK(st.upper_bound_dimension() == 2); + + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() + << " | st_wo_seven.upper_bound_dimension()=" << st_wo_seven.upper_bound_dimension() << std::endl; + std::cout << "st.dimension()=" << st.dimension() << " | st_wo_seven.dimension()=" << st_wo_seven.dimension() << std::endl; + BOOST_CHECK(st == st_wo_seven); +} + +BOOST_AUTO_TEST_CASE(auto_dimension_set) { + std::cout << "********************************************************************" << std::endl; + std::cout << "DIMENSION ON REMOVE MAXIMAL SIMPLEX" << std::endl; + + Mini_stree st; + + st.insert_simplex_and_subfaces({0, 1, 2}); + st.insert_simplex_and_subfaces({0, 1, 3}); + st.insert_simplex_and_subfaces({1, 2, 3, 4}); + st.insert_simplex_and_subfaces({1, 2, 3, 5}); + st.insert_simplex_and_subfaces({6, 7, 8, 9}); + st.insert_simplex_and_subfaces({6, 7, 8, 10}); + + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.remove_maximal_simplex({6, 7, 8, 10})" << std::endl; + st.remove_maximal_simplex(st.find({6, 7, 8, 10})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.remove_maximal_simplex({6, 7, 8, 9})" << std::endl; + st.remove_maximal_simplex(st.find({6, 7, 8, 9})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.remove_maximal_simplex({1, 2, 3, 4})" << std::endl; + st.remove_maximal_simplex(st.find({1, 2, 3, 4})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.remove_maximal_simplex({1, 2, 3, 5})" << std::endl; + st.remove_maximal_simplex(st.find({1, 2, 3, 5})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; + + std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; + st.insert_simplex_and_subfaces({1, 2, 3, 5}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 4})" << std::endl; + st.insert_simplex_and_subfaces({1, 2, 3, 4}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + + std::cout << "st.remove_maximal_simplex({1, 2, 3, 5})" << std::endl; + st.remove_maximal_simplex(st.find({1, 2, 3, 5})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + + std::cout << "st.remove_maximal_simplex({1, 2, 3, 4})" << std::endl; + st.remove_maximal_simplex(st.find({1, 2, 3, 4})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; + + std::cout << "st.insert_simplex_and_subfaces({0, 1, 3, 4})" << std::endl; + st.insert_simplex_and_subfaces({0, 1, 3, 4}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.remove_maximal_simplex({0, 1, 3, 4})" << std::endl; + st.remove_maximal_simplex(st.find({0, 1, 3, 4})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; + + std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; + st.insert_simplex_and_subfaces({1, 2, 3, 5}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 4})" << std::endl; + st.insert_simplex_and_subfaces({1, 2, 3, 4}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + + // Check you can override the dimension + // This is a limit test case - shall not happen + st.set_dimension(1); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 1); + // check dimension() and lower_upper_bound_dimension() is not giving the right answer because dimension is too low + BOOST_CHECK(st.dimension() == 1); + + + // Check you can override the dimension + // This is a limit test case - shall not happen + st.set_dimension(6); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); + // check dimension() do not launch lower_upper_bound_dimension() + BOOST_CHECK(st.dimension() == 6); + + + // Reset with the correct value + st.set_dimension(3); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + BOOST_CHECK(st.dimension() == 3); + + std::cout << "st.insert_simplex_and_subfaces({0, 1, 2, 3, 4, 5, 6})" << std::endl; + st.insert_simplex_and_subfaces({0, 1, 2, 3, 4, 5, 6}); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); + BOOST_CHECK(st.dimension() == 6); + + std::cout << "st.remove_maximal_simplex({0, 1, 2, 3, 4, 5, 6})" << std::endl; + st.remove_maximal_simplex(st.find({0, 1, 2, 3, 4, 5, 6})); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); + BOOST_CHECK(st.dimension() == 5); + +} + +BOOST_AUTO_TEST_CASE(prune_above_filtration) { + std::cout << "********************************************************************" << std::endl; + std::cout << "PRUNE ABOVE FILTRATION" << std::endl; + + Stree st; + + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + + // Constructs a copy at this state for further test purpose + Stree st_pruned = st; + st_pruned.initialize_filtration(); // reset + + st.insert_simplex_and_subfaces({3, 0}, 3.0); + st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); + + // Constructs a copy at this state for further test purpose + Stree st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + + bool simplex_is_changed = false; + // Check the no action cases + // greater than initial filtration value + simplex_is_changed = st.prune_above_filtration(10.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + // equal to initial filtration value + simplex_is_changed = st.prune_above_filtration(6.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + // lower than initial filtration value, but still greater than the maximum filtration value + simplex_is_changed = st.prune_above_filtration(5.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + // Check the pruned cases + simplex_is_changed = st.prune_above_filtration(2.5); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_pruned); + BOOST_CHECK(simplex_is_changed); + + // Display the Simplex_tree + std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + + simplex_is_changed = st.prune_above_filtration(2.0); + if (simplex_is_changed) + st.initialize_filtration(); + + std::cout << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + + BOOST_CHECK(st == st_pruned); + BOOST_CHECK(!simplex_is_changed); + + Stree st_empty; + simplex_is_changed = st.prune_above_filtration(0.0); + BOOST_CHECK(simplex_is_changed == true); + if (simplex_is_changed) + st.initialize_filtration(); + + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices"; + std::cout << " - upper_bound_dimension " << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); + + BOOST_CHECK(st.dimension() == -1); + std::cout << "upper_bound_dimension=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == -1); + + BOOST_CHECK(st == st_empty); + BOOST_CHECK(simplex_is_changed); + + // Test case to the limit + simplex_is_changed = st.prune_above_filtration(-1.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_empty); + BOOST_CHECK(!simplex_is_changed); +} + +BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { + std::cout << "********************************************************************" << std::endl; + std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl; + + Mini_stree st; + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + // st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + st.initialize_filtration(); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(st.num_simplices() == 27); + + // Test case to the limit - With these options, there is no filtration, which means filtration is 0 + bool simplex_is_changed = st.prune_above_filtration(1.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(!simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 27); + + simplex_is_changed = st.prune_above_filtration(0.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(!simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 27); + + // Test case to the limit + simplex_is_changed = st.prune_above_filtration(-1.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at -1.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 0); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + +} diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 17ddc605..f63ea080 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -297,6 +297,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var // Simplex_handle = boost::container::flat_map< typeST::Vertex_handle, Node >::iterator typename typeST::Simplex_handle shReturned = returnValue.first; BOOST_CHECK(shReturned == typename typeST::Simplex_handle(nullptr)); + std::cout << "st.num_vertices()=" << st.num_vertices() << std::endl; BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! BOOST_CHECK(st.dimension() == dim_max); @@ -617,9 +618,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var /* o */ /* 5 */ - // FIXME - st.set_dimension(3); - std::vector<typename typeST::Vertex_handle> simplex_result; std::vector<typename typeST::Simplex_handle> result; std::cout << "First test - Star of (3):" << std::endl; @@ -716,9 +714,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_ /* o */ /* 5 */ - // FIXME - st.set_dimension(3); - std::cout << "Printing st - address = " << &st << std::endl; // Copy constructor @@ -869,270 +864,34 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { } -struct MyOptions : Simplex_tree_options_full_featured { - // Not doing persistence, so we don't need those - static const bool store_key = false; - static const bool store_filtration = false; - // I have few vertices - typedef short Vertex_handle; -}; - -BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { +BOOST_AUTO_TEST_CASE(insert_graph) { std::cout << "********************************************************************" << std::endl; - std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; - - - typedef Simplex_tree<MyOptions> miniST; - miniST st; - - // FIXME - st.set_dimension(3); - - st.insert_simplex_and_subfaces({0, 1, 6, 7}); - st.insert_simplex_and_subfaces({3, 4, 5}); + std::cout << "INSERT GRAPH" << std::endl; + typedef typename boost::adjacency_list<boost::vecS, boost::vecS, + boost::undirectedS, + boost::property<vertex_filtration_t, double>, + boost::property<edge_filtration_t, double>> Graph; + Graph g(3); + // filtration value 0 everywhere + put(Gudhi::vertex_filtration_t(), g, 0, 0); + put(Gudhi::vertex_filtration_t(), g, 1, 0); + put(Gudhi::vertex_filtration_t(), g, 2, 0); + // vertices don't always occur in sorted order + add_edge(0, 1, 0, g); + add_edge(2, 1, 0, g); + add_edge(2, 0, 0, g); - // Constructs a copy at this state for further test purpose - miniST st_pruned = st; - - st.insert_simplex_and_subfaces({3, 0}); - st.insert_simplex_and_subfaces({2, 1, 0}); - - // Constructs a copy at this state for further test purpose - miniST st_complete = st; - // st_complete and st: - // 1 6 - // o---o - // /X\7/ - // o---o---o---o - // 2 0 3\X/4 - // o - // 5 - // st_pruned: - // 1 6 - // o---o - // \7/ - // o o---o - // 0 3\X/4 - // o - // 5 - -#ifdef GUDHI_DEBUG - std::cout << "Check exception throw in debug mode" << std::endl; - // throw excpt because sh has children - BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument); - BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument); - BOOST_CHECK(st == st_complete); -#endif - - st.remove_maximal_simplex(st.find({0, 2})); - st.remove_maximal_simplex(st.find({0, 1, 2})); - st.remove_maximal_simplex(st.find({1, 2})); - st.remove_maximal_simplex(st.find({2})); - st.remove_maximal_simplex(st.find({0, 3})); - - BOOST_CHECK(st == st_pruned); - // Remove all, but as the simplex tree is not storing filtration, there is no modification - st.prune_above_filtration(0.0); - BOOST_CHECK(st == st_pruned); - - miniST st_wo_seven; - // FIXME - st_wo_seven.set_dimension(3); - - st_wo_seven.insert_simplex_and_subfaces({0, 1, 6}); - st_wo_seven.insert_simplex_and_subfaces({3, 4, 5}); - // st_wo_seven: - // 1 6 - // o---o - // \X/ - // o o---o - // 0 3\X/4 - // o - // 5 - - // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not) - st.remove_maximal_simplex(st.find({0, 1, 6, 7})); - st.remove_maximal_simplex(st.find({0, 1, 7})); - st.remove_maximal_simplex(st.find({0, 6, 7})); - st.remove_maximal_simplex(st.find({0, 7})); - st.remove_maximal_simplex(st.find({1, 6, 7})); - st.remove_maximal_simplex(st.find({1, 7})); - st.remove_maximal_simplex(st.find({6, 7})); - st.remove_maximal_simplex(st.find({7})); - - BOOST_CHECK(st == st_wo_seven); -} - -BOOST_AUTO_TEST_CASE(prune_above_filtration) { - std::cout << "********************************************************************" << std::endl; - std::cout << "PRUNE ABOVE FILTRATION" << std::endl; typedef Simplex_tree<> typeST; - typeST st; - - // FIXME - st.set_dimension(3); - - st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); - st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - - // Constructs a copy at this state for further test purpose - typeST st_pruned = st; - st_pruned.initialize_filtration(); // reset - - st.insert_simplex_and_subfaces({3, 0}, 3.0); - st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); - - // Constructs a copy at this state for further test purpose - typeST st_complete = st; - // st_complete and st: - // 1 6 - // o---o - // /X\7/ - // o---o---o---o - // 2 0 3\X/4 - // o - // 5 - // st_pruned: - // 1 6 - // o---o - // \7/ - // o o---o - // 0 3\X/4 - // o - // 5 - - bool simplex_is_changed = false; - // Check the no action cases - // greater than initial filtration value - simplex_is_changed = st.prune_above_filtration(10.0); - if (simplex_is_changed) - st.initialize_filtration(); - BOOST_CHECK(st == st_complete); - BOOST_CHECK(!simplex_is_changed); - // equal to initial filtration value - simplex_is_changed = st.prune_above_filtration(6.0); - if (simplex_is_changed) - st.initialize_filtration(); - BOOST_CHECK(st == st_complete); - BOOST_CHECK(!simplex_is_changed); - // lower than initial filtration value, but still greater than the maximum filtration value - simplex_is_changed = st.prune_above_filtration(5.0); - if (simplex_is_changed) - st.initialize_filtration(); - BOOST_CHECK(st == st_complete); - BOOST_CHECK(!simplex_is_changed); - - // Display the Simplex_tree - std::cout << "The complex contains " << st.num_simplices() << " simplices"; - std::cout << " - dimension " << st.dimension() << std::endl; - std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for (auto f_simplex : st.filtration_simplex_range()) { - std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; - } - std::cout << std::endl; - } - - // Check the pruned cases - simplex_is_changed = st.prune_above_filtration(2.5); - if (simplex_is_changed) - st.initialize_filtration(); - BOOST_CHECK(st == st_pruned); - BOOST_CHECK(simplex_is_changed); - - // Display the Simplex_tree - std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices"; - std::cout << " - dimension " << st.dimension() << std::endl; - - simplex_is_changed = st.prune_above_filtration(2.0); - if (simplex_is_changed) - st.initialize_filtration(); - - std::cout << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices"; - std::cout << " - dimension " << st.dimension() << std::endl; - - BOOST_CHECK(st == st_pruned); - BOOST_CHECK(!simplex_is_changed); - - typeST st_empty; - // FIXME - st_empty.set_dimension(3); - simplex_is_changed = st.prune_above_filtration(0.0); - if (simplex_is_changed) - st.initialize_filtration(); - - // Display the Simplex_tree - std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices"; - std::cout << " - dimension " << st.dimension() << std::endl; - - BOOST_CHECK(st == st_empty); - BOOST_CHECK(simplex_is_changed); - - // Test case to the limit - simplex_is_changed = st.prune_above_filtration(-1.0); - if (simplex_is_changed) - st.initialize_filtration(); - BOOST_CHECK(st == st_empty); - BOOST_CHECK(!simplex_is_changed); -} - -BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { - std::cout << "********************************************************************" << std::endl; - std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl; - typedef Simplex_tree<MyOptions> typeST; - typeST st; - - // FIXME - st.set_dimension(3); - - st.insert_simplex_and_subfaces({0, 1, 6, 7}); - st.insert_simplex_and_subfaces({3, 4, 5}); - st.insert_simplex_and_subfaces({3, 0}); - st.insert_simplex_and_subfaces({2, 1, 0}); - - // st: - // 1 6 - // o---o - // /X\7/ - // o---o---o---o - // 2 0 3\X/4 - // o - // 5 - - st.initialize_filtration(); - - // Display the Simplex_tree - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - BOOST_CHECK(st.num_simplices() == 27); - - // Test case to the limit - With these options, there is no filtration, which means filtration is 0 - bool simplex_is_changed = st.prune_above_filtration(1.0); - if (simplex_is_changed) - st.initialize_filtration(); - // Display the Simplex_tree - std::cout << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl; - BOOST_CHECK(!simplex_is_changed); - BOOST_CHECK(st.num_simplices() == 27); - - simplex_is_changed = st.prune_above_filtration(0.0); - if (simplex_is_changed) - st.initialize_filtration(); - // Display the Simplex_tree - std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; - BOOST_CHECK(!simplex_is_changed); - BOOST_CHECK(st.num_simplices() == 27); - - // Test case to the limit - simplex_is_changed = st.prune_above_filtration(-1.0); - if (simplex_is_changed) - st.initialize_filtration(); - // Display the Simplex_tree - std::cout << "The complex pruned at -1.0 contains " << st.num_simplices() << " simplices" << std::endl; - BOOST_CHECK(simplex_is_changed); - BOOST_CHECK(st.num_simplices() == 0); - - // Display the Simplex_tree - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - + typeST st1; + st1.insert_graph(g); + BOOST_CHECK(st1.num_simplices() == 6); + + // edges can have multiplicity in the graph unless we replace the first vecS with (hash_)setS + add_edge(1, 0, 0, g); + add_edge(1, 2, 0, g); + add_edge(0, 2, 0, g); + add_edge(0, 2, 0, g); + typeST st2; + st2.insert_graph(g); + BOOST_CHECK(st2.num_simplices() == 6); } |