diff options
Diffstat (limited to 'src/Simplex_tree')
21 files changed, 1406 insertions, 754 deletions
diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h index 800879fe..2d3ecdec 100644 --- a/src/Simplex_tree/doc/Intro_simplex_tree.h +++ b/src/Simplex_tree/doc/Intro_simplex_tree.h @@ -39,11 +39,9 @@ namespace Gudhi { * \subsubsection filteredcomplexessimplextreeexamples Examples * * Here is a list of simplex tree examples : - * \li <a href="_simplex_tree_2simple_simplex_tree_8cpp-example.html"> - * Simplex_tree/simple_simplex_tree.cpp</a> - Simple simplex tree construction and basic function use. + * \li \gudhi_example_link{Simplex_tree,simple_simplex_tree.cpp} - Simple simplex tree construction and basic function use. * - * \li <a href="_simplex_tree_2simplex_tree_from_cliques_of_graph_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_cliques_of_graph.cpp</a> - Simplex tree construction from cliques of graph read in + * \li \gudhi_example_link{Simplex_tree,simplex_tree_from_cliques_of_graph.cpp} - Simplex tree construction from cliques of graph read in * a file. * * Simplex tree construction with \f$\mathbb{Z}/3\mathbb{Z}\f$ coefficients on weighted graph Klein bottle file: @@ -54,12 +52,10 @@ Expand the simplex tree in 3.8e-05 s. Information of the Simplex Tree: Number of vertices = 10 Number of simplices = 98 \endcode * - * \li <a href="_simplex_tree_2example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html"> - * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - Simplex tree is computed and displayed + * \li \gudhi_example_link{Simplex_tree,example_alpha_shapes_3_simplex_tree_from_off_file.cpp} - Simplex tree is computed and displayed * from a 3D alpha complex (Requires CGAL, GMP and GMPXX to be installed). * - * \li <a href="_simplex_tree_2graph_expansion_with_blocker_8cpp-example.html"> - * Simplex_tree/graph_expansion_with_blocker.cpp</a> - Simple simplex tree construction from a one-skeleton graph with + * \li \gudhi_example_link{Simplex_tree,graph_expansion_with_blocker.cpp} - Simple simplex tree construction from a one-skeleton graph with * a simple blocker expansion method. * * \subsection filteredcomplexeshassecomplex Hasse complex diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt index 8a8cac58..81d352fc 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -29,18 +29,20 @@ if(GMP_FOUND AND NOT CGAL_VERSION VERSION_LESS 4.11.0) target_link_libraries(Simplex_tree_example_alpha_shapes_3_from_off ${TBB_LIBRARIES}) endif() add_test(NAME Simplex_tree_example_alpha_shapes_3_from_off COMMAND $<TARGET_FILE:Simplex_tree_example_alpha_shapes_3_from_off> - "${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off") + "${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off") endif() if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) - 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}) + if(TARGET Boost::program_options) + 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 ${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) 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) endif () add_executable ( Simplex_tree_example_graph_expansion_with_blocker graph_expansion_with_blocker.cpp ) diff --git a/src/Simplex_tree/example/README b/src/Simplex_tree/example/README deleted file mode 100644 index a9498173..00000000 --- a/src/Simplex_tree/example/README +++ /dev/null @@ -1,73 +0,0 @@ -To build the example, run in a Terminal: - -cd /path-to-gudhi/ -cmake . -cd /path-to-example/ -make - - -Example of use : - -*** Simple simplex tree construction - -./Simplex_tree_example_simple_simplex_tree - -******************************************************************** -EXAMPLE OF SIMPLE INSERTION - * INSERT 0 - + 0 INSERTED - * INSERT 1 - + 1 INSERTED - * INSERT (0,1) - + (0,1) INSERTED - * INSERT 2 - + 2 INSERTED - * INSERT (2,0) - + (2,0) INSERTED - * INSERT (2,1) - + (2,1) INSERTED - * INSERT (2,1,0) - + (2,1,0) INSERTED - * INSERT 3 - + 3 INSERTED - * INSERT (3,0) - + (3,0) INSERTED - * INSERT 0 (already inserted) - - 0 NOT INSERTED - * INSERT (2,1,0) (already inserted) - - (2,1,0) NOT INSERTED -******************************************************************** -* The complex contains 9 simplices - - dimension 2 - filtration 0.4 -* Iterator on Simplices in the filtration, with [filtration value]: - [0.1] 0 - [0.1] 1 - [0.1] 2 - [0.1] 3 - [0.2] 1 0 - [0.2] 2 0 - [0.2] 2 1 - [0.2] 3 0 - [0.3] 2 1 0 - -*** Simplex tree construction with Z/2Z coefficients on weighted graph Klein bottle file: - -./Simplex_tree_example_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 2 -Insert the 1-skeleton in the simplex tree in 0 s. -Expand the simplex tree in 0 s. -Information of the Simplex Tree: - Number of vertices = 10 Number of simplices = 82 - -with Z/3Z coefficients: - -./Simplex_tree_example_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 3 - -Insert the 1-skeleton in the simplex tree in 0 s. -Expand the simplex tree in 0 s. -Information of the Simplex Tree: - Number of vertices = 10 Number of simplices = 106 - -*** Simplex_tree computed and displayed from a 3D alpha complex: - [ Requires CGAL, GMP and GMPXX to be installed] - -./Simplex_tree_example_alpha_shapes_3_from_off ../../../data/points/bunny_5000 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 index d716fb1f..0e7e382b 100644 --- a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp +++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp @@ -55,18 +55,18 @@ class Cech_blocker { bool operator()(Simplex_handle sh) { std::vector<Point> points; #if DEBUG_TRACES - std::cout << "Cech_blocker on ["; + std::clog << "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 << ", "; + std::clog << 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; + std::clog << "] - radius = " << radius << " - returns " << (radius > threshold_) << std::endl; #endif // DEBUG_TRACES simplex_tree_.assign_filtration(sh, radius); return (radius > threshold_); @@ -106,24 +106,24 @@ int main(int argc, char* argv[]) { // 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"; + std::clog << "The complex contains " << st.num_simplices() << " simplices \n"; + std::clog << " and has dimension " << st.dimension() << " \n"; // Sort the simplices in the order of the filtration st.initialize_filtration(); #if DEBUG_TRACES - std::cout << "********************************************************************\n"; + std::clog << "********************************************************************\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"; + std::clog << "* The complex contains " << st.num_simplices() << " simplices - dimension=" << st.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : st.filtration_simplex_range()) { - std::cout << " " + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << static_cast<int>(vertex) << " "; + std::clog << static_cast<int>(vertex) << " "; } - std::cout << std::endl; + std::clog << std::endl; } #endif // DEBUG_TRACES return 0; @@ -154,11 +154,11 @@ void program_options(int argc, char* argv[], std::string& off_file_points, Filtr 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::clog << std::endl; + std::clog << "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; + std::clog << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::clog << visible << std::endl; exit(-1); } } 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 e455c426..8ee7ab74 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 @@ -63,7 +63,7 @@ Vertex_list from(const Cell_handle& ch) { Vertex_list the_list; for (auto i = 0; i < 4; i++) { #ifdef DEBUG_TRACES - std::cout << "from cell[" << i << "]=" << ch->vertex(i)->point() << std::endl; + std::clog << "from cell[" << i << "]=" << ch->vertex(i)->point() << std::endl; #endif // DEBUG_TRACES the_list.push_back(ch->vertex(i)); } @@ -75,7 +75,7 @@ Vertex_list from(const Facet& fct) { for (auto i = 0; i < 4; i++) { if (fct.second != i) { #ifdef DEBUG_TRACES - std::cout << "from facet=[" << i << "]" << fct.first->vertex(i)->point() << std::endl; + std::clog << "from facet=[" << i << "]" << fct.first->vertex(i)->point() << std::endl; #endif // DEBUG_TRACES the_list.push_back(fct.first->vertex(i)); } @@ -88,7 +88,7 @@ Vertex_list from(const Edge& edg) { for (auto i = 0; i < 4; i++) { if ((edg.second == i) || (edg.third == i)) { #ifdef DEBUG_TRACES - std::cout << "from edge[" << i << "]=" << edg.first->vertex(i)->point() << std::endl; + std::clog << "from edge[" << i << "]=" << edg.first->vertex(i)->point() << std::endl; #endif // DEBUG_TRACES the_list.push_back(edg.first->vertex(i)); } @@ -99,7 +99,7 @@ Vertex_list from(const Edge& edg) { Vertex_list from(const Alpha_shape_3::Vertex_handle& vh) { Vertex_list the_list; #ifdef DEBUG_TRACES - std::cout << "from vertex=" << vh->point() << std::endl; + std::clog << "from vertex=" << vh->point() << std::endl; #endif // DEBUG_TRACES the_list.push_back(vh); return the_list; @@ -128,7 +128,7 @@ int main(int argc, char * const argv[]) { // alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode. Alpha_shape_3 as(lp.begin(), lp.end(), 0, Alpha_shape_3::GENERAL); #ifdef DEBUG_TRACES - std::cout << "Alpha shape computed in GENERAL mode" << std::endl; + std::clog << "Alpha shape computed in GENERAL mode" << std::endl; #endif // DEBUG_TRACES // filtration with alpha values from alpha shape @@ -140,7 +140,7 @@ int main(int argc, char * const argv[]) { as.filtration_with_alpha_values(disp); #ifdef DEBUG_TRACES - std::cout << "filtration_with_alpha_values returns : " << the_objects.size() << " objects" << std::endl; + std::clog << "filtration_with_alpha_values returns : " << the_objects.size() << " objects" << std::endl; #endif // DEBUG_TRACES Alpha_shape_3::size_type count_vertices = 0; @@ -177,7 +177,7 @@ int main(int argc, char * const argv[]) { // alpha shape not found Simplex_tree_vertex vertex = map_cgal_simplex_tree.size(); #ifdef DEBUG_TRACES - std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] not found - insert_simplex " << vertex << "\n"; + std::clog << "vertex [" << the_alpha_shape_vertex->point() << "] not found - insert_simplex " << vertex << "\n"; #endif // DEBUG_TRACES the_simplex_tree.push_back(vertex); map_cgal_simplex_tree.insert(Alpha_shape_simplex_tree_pair(the_alpha_shape_vertex, vertex)); @@ -185,14 +185,14 @@ int main(int argc, char * const argv[]) { // alpha shape found Simplex_tree_vertex vertex = the_map_iterator->second; #ifdef DEBUG_TRACES - std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] found in " << vertex << std::endl; + std::clog << "vertex [" << the_alpha_shape_vertex->point() << "] found in " << vertex << std::endl; #endif // DEBUG_TRACES the_simplex_tree.push_back(vertex); } } // Construction of the simplex_tree #ifdef DEBUG_TRACES - std::cout << "filtration = " << *the_alpha_value_iterator << std::endl; + std::clog << "filtration = " << *the_alpha_value_iterator << std::endl; #endif // DEBUG_TRACES simplex_tree.insert_simplex(the_simplex_tree, std::sqrt(*the_alpha_value_iterator)); if (the_alpha_value_iterator != the_alpha_values.end()) @@ -201,61 +201,61 @@ int main(int argc, char * const argv[]) { std::cerr << "This shall not happen" << std::endl; } #ifdef DEBUG_TRACES - std::cout << "vertices \t\t" << count_vertices << std::endl; - std::cout << "edges \t\t" << count_edges << std::endl; - std::cout << "facets \t\t" << count_facets << std::endl; - std::cout << "cells \t\t" << count_cells << std::endl; + std::clog << "vertices \t\t" << count_vertices << std::endl; + std::clog << "edges \t\t" << count_edges << std::endl; + std::clog << "facets \t\t" << count_facets << std::endl; + std::clog << "cells \t\t" << count_cells << std::endl; - std::cout << "Information of the Simplex Tree:\n"; - std::cout << " Number of vertices = " << simplex_tree.num_vertices() << " "; - std::cout << " Number of simplices = " << simplex_tree.num_simplices() << std::endl << std::endl; + std::clog << "Information of the Simplex Tree:\n"; + std::clog << " Number of vertices = " << simplex_tree.num_vertices() << " "; + std::clog << " Number of simplices = " << simplex_tree.num_simplices() << std::endl << std::endl; #endif // DEBUG_TRACES #ifdef DEBUG_TRACES - std::cout << "Iterator on vertices: \n"; + std::clog << "Iterator on vertices: \n"; for (auto vertex : simplex_tree.complex_vertex_range()) { - std::cout << vertex << " "; + std::clog << vertex << " "; } #endif // DEBUG_TRACES - std::cout << simplex_tree << std::endl; + std::clog << simplex_tree << std::endl; #ifdef DEBUG_TRACES - std::cout << std::endl << std::endl << "Iterator on simplices:\n"; + std::clog << std::endl << std::endl << "Iterator on simplices:\n"; for (auto simplex : simplex_tree.complex_simplex_range()) { - std::cout << " "; + std::clog << " "; for (auto vertex : simplex_tree.simplex_vertex_range(simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } #endif // DEBUG_TRACES #ifdef DEBUG_TRACES - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } #endif // DEBUG_TRACES #ifdef DEBUG_TRACES - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, and their boundary simplices:\n"; + std::clog << std::endl << std::endl << "Iterator on Simplices in the filtration, and their boundary simplices:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; for (auto b_simplex : simplex_tree.boundary_simplex_range(f_simplex)) { - std::cout << " " << "[" << simplex_tree.filtration(b_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(b_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(b_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } } #endif // DEBUG_TRACES diff --git a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp index 494f8b1d..eef8b665 100644 --- a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp +++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp @@ -34,31 +34,31 @@ int main(int argc, char* const argv[]) { stree.expansion_with_blockers(3, [&](Simplex_handle sh) { bool result = false; - std::cout << "Blocker on ["; + std::clog << "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::clog << 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) + std::clog << "] ( " << stree.filtration(sh); + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) stree.assign_filtration(sh, stree.filtration(sh) + 1.); - std::cout << " + 1. ) = " << result << std::endl; + std::clog << " + 1. ) = " << result << std::endl; return result; }); - std::cout << "********************************************************************\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"; + std::clog << "********************************************************************\n"; + std::clog << "* The complex contains " << stree.num_simplices() << " simplices"; + std::clog << " - dimension " << stree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : stree.filtration_simplex_range()) { - std::cout << " " + std::clog << " " << "[" << stree.filtration(f_simplex) << "] "; - for (auto vertex : stree.simplex_vertex_range(f_simplex)) std::cout << "(" << vertex << ")"; - std::cout << std::endl; + for (auto vertex : stree.simplex_vertex_range(f_simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } return 0; diff --git a/src/Simplex_tree/example/mini_simplex_tree.cpp b/src/Simplex_tree/example/mini_simplex_tree.cpp index bbc582c7..4043bffd 100644 --- a/src/Simplex_tree/example/mini_simplex_tree.cpp +++ b/src/Simplex_tree/example/mini_simplex_tree.cpp @@ -48,7 +48,7 @@ int main() { for (ST::Simplex_handle t : st.cofaces_simplex_range(e, 1)) { // Only coface is 012 for (ST::Vertex_handle v : st.simplex_vertex_range(t)) // v in { 0, 1, 2 } - std::cout << v; - std::cout << '\n'; + std::clog << v; + std::clog << '\n'; } } diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp index 4353939f..965711da 100644 --- a/src/Simplex_tree/example/simple_simplex_tree.cpp +++ b/src/Simplex_tree/example/simple_simplex_tree.cpp @@ -28,8 +28,8 @@ int main(int argc, char* const argv[]) { const Filtration_value FOURTH_FILTRATION_VALUE = 0.4; // TEST OF INSERTION - std::cout << "********************************************************************" << std::endl; - std::cout << "EXAMPLE OF SIMPLE INSERTION" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "EXAMPLE OF SIMPLE INSERTION" << std::endl; // Construct the Simplex Tree Simplex_tree simplexTree; @@ -41,140 +41,139 @@ int main(int argc, char* const argv[]) { /* 2 0 3 */ // ++ FIRST - std::cout << " * INSERT 0" << std::endl; + std::clog << " * INSERT 0" << std::endl; typeVectorVertex firstSimplexVector = {0}; typePairSimplexBool returnValue = simplexTree.insert_simplex(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { - std::cout << " + 0 INSERTED" << std::endl; + std::clog << " + 0 INSERTED" << std::endl; } else { - std::cout << " - 0 NOT INSERTED" << std::endl; + std::clog << " - 0 NOT INSERTED" << std::endl; } // ++ SECOND - std::cout << " * INSERT 1" << std::endl; + std::clog << " * INSERT 1" << std::endl; typeVectorVertex secondSimplexVector = {1}; returnValue = simplexTree.insert_simplex(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { - std::cout << " + 1 INSERTED" << std::endl; + std::clog << " + 1 INSERTED" << std::endl; } else { - std::cout << " - 1 NOT INSERTED" << std::endl; + std::clog << " - 1 NOT INSERTED" << std::endl; } // ++ THIRD - std::cout << " * INSERT (0,1)" << std::endl; + std::clog << " * INSERT (0,1)" << std::endl; 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; + std::clog << " + (0,1) INSERTED" << std::endl; } else { - std::cout << " - (0,1) NOT INSERTED" << std::endl; + std::clog << " - (0,1) NOT INSERTED" << std::endl; } // ++ FOURTH - std::cout << " * INSERT 2" << std::endl; + std::clog << " * INSERT 2" << std::endl; typeVectorVertex fourthSimplexVector = {2}; returnValue = simplexTree.insert_simplex(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { - std::cout << " + 2 INSERTED" << std::endl; + std::clog << " + 2 INSERTED" << std::endl; } else { - std::cout << " - 2 NOT INSERTED" << std::endl; + std::clog << " - 2 NOT INSERTED" << std::endl; } // ++ FIFTH - std::cout << " * INSERT (2,0)" << std::endl; + std::clog << " * INSERT (2,0)" << std::endl; 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; + std::clog << " + (2,0) INSERTED" << std::endl; } else { - std::cout << " - (2,0) NOT INSERTED" << std::endl; + std::clog << " - (2,0) NOT INSERTED" << std::endl; } // ++ SIXTH - std::cout << " * INSERT (2,1)" << std::endl; + std::clog << " * INSERT (2,1)" << std::endl; 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; + std::clog << " + (2,1) INSERTED" << std::endl; } else { - std::cout << " - (2,1) NOT INSERTED" << std::endl; + std::clog << " - (2,1) NOT INSERTED" << std::endl; } // ++ SEVENTH - std::cout << " * INSERT (2,1,0)" << std::endl; + std::clog << " * INSERT (2,1,0)" << std::endl; 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; + std::clog << " + (2,1,0) INSERTED" << std::endl; } else { - std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + std::clog << " - (2,1,0) NOT INSERTED" << std::endl; } // ++ EIGHTH - std::cout << " * INSERT 3" << std::endl; + std::clog << " * INSERT 3" << std::endl; typeVectorVertex eighthSimplexVector = {3}; returnValue = simplexTree.insert_simplex(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); if (returnValue.second == true) { - std::cout << " + 3 INSERTED" << std::endl; + std::clog << " + 3 INSERTED" << std::endl; } else { - std::cout << " - 3 NOT INSERTED" << std::endl; + std::clog << " - 3 NOT INSERTED" << std::endl; } - // ++ NINETH - std::cout << " * INSERT (3,0)" << std::endl; + // ++ NINTH + std::clog << " * INSERT (3,0)" << std::endl; 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; + std::clog << " + (3,0) INSERTED" << std::endl; } else { - std::cout << " - (3,0) NOT INSERTED" << std::endl; + std::clog << " - (3,0) NOT INSERTED" << std::endl; } // ++ TENTH - std::cout << " * INSERT 0 (already inserted)" << std::endl; + std::clog << " * INSERT 0 (already inserted)" << std::endl; typeVectorVertex tenthSimplexVector = {0}; // With a different filtration value returnValue = simplexTree.insert_simplex(tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); if (returnValue.second == true) { - std::cout << " + 0 INSERTED" << std::endl; + std::clog << " + 0 INSERTED" << std::endl; } else { - std::cout << " - 0 NOT INSERTED" << std::endl; + std::clog << " - 0 NOT INSERTED" << std::endl; } // ++ ELEVENTH - std::cout << " * INSERT (2,1,0) (already inserted)" << std::endl; + std::clog << " * INSERT (2,1,0) (already inserted)" << std::endl; 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; + std::clog << " + (2,1,0) INSERTED" << std::endl; } else { - std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + std::clog << " - (2,1,0) NOT INSERTED" << std::endl; } // ++ GENERAL VARIABLE SET - std::cout << "********************************************************************\n"; - // Display the Simplex_tree - Can not be done in the middle of 2 inserts - std::cout << "* The complex contains " << simplexTree.num_simplices() << " simplices\n"; - std::cout << " - dimension " << simplexTree.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "********************************************************************\n"; + std::clog << "* The complex contains " << simplexTree.num_simplices() << " simplices\n"; + std::clog << " - dimension " << simplexTree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplexTree.filtration_simplex_range()) { - std::cout << " " + std::clog << " " << "[" << simplexTree.filtration(f_simplex) << "] "; - for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) std::cout << "(" << vertex << ")"; - std::cout << std::endl; + for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } // [0.1] 0 // [0.1] 1 @@ -190,66 +189,66 @@ int main(int argc, char* const argv[]) { // Find in the simplex_tree // ------------------------------------------------------------------------------------------------------------------ Simplex_tree::Simplex_handle simplexFound = simplexTree.find(secondSimplexVector); - std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; typeVectorVertex unknownSimplexVector = {15}; simplexFound = simplexTree.find(unknownSimplexVector); - std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; simplexFound = simplexTree.find(fifthSimplexVector); - std::cout << "**************IS THE SIMPLEX {2,0} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {2,0} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; typeVectorVertex otherSimplexVector = {1, 15}; simplexFound = simplexTree.find(otherSimplexVector); - std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; typeVectorVertex invSimplexVector = {1, 2, 0}; simplexFound = simplexTree.find(invSimplexVector); - std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; simplexFound = simplexTree.find({0, 1}); - std::cout << "**************IS THE SIMPLEX {0,1} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {0,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != simplexTree.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; - std::cout << "**************COFACES OF {0,1} IN CODIMENSION 1 ARE\n"; + std::clog << "**************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 << ")"; - std::cout << std::endl; + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } - std::cout << "**************STARS OF {0,1} ARE\n"; + std::clog << "**************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 << ")"; - std::cout << std::endl; + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } - std::cout << "**************BOUNDARIES OF {0,1,2} ARE\n"; + std::clog << "**************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 << ")"; - std::cout << std::endl; + for (auto vertex : simplexTree.simplex_vertex_range(simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } return 0; 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 f6dfa53c..6278efa7 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 @@ -42,67 +42,67 @@ int main(int argc, char * const argv[]) { // insert the graph in the simplex tree as 1-skeleton st.insert_graph(g); end = clock(); - std::cout << "Insert the 1-skeleton in the simplex tree in " + std::clog << "Insert the 1-skeleton in the simplex tree in " << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; start = clock(); // expand the 1-skeleton until dimension max_dim st.expansion(max_dim); end = clock(); - std::cout << "max_dim = " << max_dim << "\n"; - std::cout << "Expand the simplex tree in " + std::clog << "max_dim = " << max_dim << "\n"; + std::clog << "Expand the simplex tree in " << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; - std::cout << "Information of the Simplex Tree: " << std::endl; - std::cout << " Number of vertices = " << st.num_vertices() << " "; - std::cout << " Number of simplices = " << st.num_simplices() << std::endl; - std::cout << std::endl << std::endl; + std::clog << "Information of the Simplex Tree: " << std::endl; + std::clog << " Number of vertices = " << st.num_vertices() << " "; + std::clog << " Number of simplices = " << st.num_simplices() << std::endl; + std::clog << std::endl << std::endl; - std::cout << "Iterator on vertices: "; + std::clog << "Iterator on vertices: "; for (auto vertex : st.complex_vertex_range()) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; - std::cout << std::endl << std::endl; + std::clog << std::endl << std::endl; - std::cout << "Iterator on simplices: " << std::endl; + std::clog << "Iterator on simplices: " << std::endl; for (auto simplex : st.complex_simplex_range()) { - std::cout << " "; + std::clog << " "; for (auto vertex : st.simplex_vertex_range(simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } - std::cout << std::endl << std::endl; + std::clog << std::endl << std::endl; - std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::clog << "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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } - std::cout << std::endl << std::endl; + std::clog << std::endl << std::endl; - std::cout << "Iterator on Simplices in the filtration, and their boundary simplices:" << std::endl; + std::clog << "Iterator on Simplices in the filtration, and their boundary simplices:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { - std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; for (auto b_simplex : st.boundary_simplex_range(f_simplex)) { - std::cout << " " << "[" << st.filtration(b_simplex) << "] "; + std::clog << " " << "[" << st.filtration(b_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(b_simplex)) { - std::cout << vertex << " "; + std::clog << vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } } return 0; diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 76608008..4177a0b8 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -24,6 +24,9 @@ #include <boost/iterator/transform_iterator.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/range/adaptor/reversed.hpp> +#include <boost/range/adaptor/transformed.hpp> +#include <boost/range/size.hpp> +#include <boost/container/static_vector.hpp> #ifdef GUDHI_USE_TBB #include <tbb/parallel_sort.h> @@ -41,6 +44,24 @@ namespace Gudhi { +/** \addtogroup simplex_tree + * @{ + */ + +/** + * \class Extended_simplex_type Simplex_tree.h gudhi/Simplex_tree.h + * \brief Extended simplex type data structure for representing the type of simplices in an extended filtration. + * + * \details The extended simplex type can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). + * + * Details may be found in \cite Cohen-Steiner2009 and section 2.2 in \cite Carriere16. + * + */ +enum class Extended_simplex_type {UP, DOWN, EXTRA}; + struct Simplex_tree_options_full_featured; /** @@ -82,10 +103,11 @@ class Simplex_tree { // Simplex_key next to each other). typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary; - /* \brief Set of nodes sharing a same parent in the simplex tree. */ - /* \brief Set of nodes sharing a same parent in the simplex tree. */ + /** \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings; + + struct Key_simplex_base_real { Key_simplex_base_real() : key_(-1) {} void assign_key(Simplex_key k) { key_ = k; } @@ -99,6 +121,12 @@ class Simplex_tree { void assign_key(Simplex_key); Simplex_key key() const; }; + struct Extended_filtration_data { + Filtration_value minval; + Filtration_value maxval; + Extended_filtration_data(){} + Extended_filtration_data(Filtration_value vmin, Filtration_value vmax): minval(vmin), maxval(vmax) {} + }; typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base; @@ -119,7 +147,10 @@ class Simplex_tree { public: /** \brief Handle type to a simplex contained in the simplicial complex represented - * by the simplex tree. */ + * by the simplex tree. + * + * They are essentially pointers into internal vectors, and any insertion or removal + * of a simplex may invalidate any other Simplex_handle in the complex. */ typedef typename Dictionary::iterator Simplex_handle; private: @@ -161,6 +192,12 @@ class Simplex_tree { typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator; /** \brief Range over the simplices of the boundary of a simplex. */ typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range; + /** \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices. + * + * 'value_type' is std::pair<Simplex_handle, Vertex_handle>. */ + typedef Simplex_tree_boundary_opposite_vertex_simplex_iterator<Simplex_tree> Boundary_opposite_vertex_simplex_iterator; + /** \brief Range over the simplices of the boundary of a simplex and their opposite vertices. */ + typedef boost::iterator_range<Boundary_opposite_vertex_simplex_iterator> Boundary_opposite_vertex_simplex_range; /** \brief Iterator over the simplices of the simplicial complex. * * 'value_type' is Simplex_handle. */ @@ -232,11 +269,9 @@ class Simplex_tree { * * The filtration must be valid. If the filtration has not been initialized yet, the * method initializes it (i.e. order the simplices). If the complex has changed since the last time the filtration - * was initialized, please call `initialize_filtration()` to recompute it. */ + * was initialized, please call `clear_filtration()` or `initialize_filtration()` to recompute it. */ Filtration_simplex_range const& filtration_simplex_range(Indexing_tag = Indexing_tag()) { - if (filtration_vect_.empty()) { - initialize_filtration(); - } + maybe_initialize_filtration(); return filtration_vect_; } @@ -246,8 +281,8 @@ class Simplex_tree { * which is consequenlty * equal to \f$(-1)^{\text{dim} \sigma}\f$ the canonical orientation on the simplex. */ - Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) { - assert(sh != null_simplex()); // Empty simplex + Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const { + GUDHI_CHECK(sh != null_simplex(), "empty simplex"); return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -272,6 +307,23 @@ class Simplex_tree { Boundary_simplex_iterator(this)); } + /** \brief Given a simplex, returns a range over the simplices of its boundary and their opposite vertices. + * + * The boundary of a simplex is the set of codimension \f$1\f$ subsimplices of the simplex. + * If the simplex is \f$[v_0, \cdots ,v_d]\f$, with canonical orientation induced by \f$ v_0 < \cdots < v_d \f$, the + * iterator enumerates the simplices of the boundary in the order: + * \f$[v_0,\cdots,\widehat{v_i},\cdots,v_d]\f$ for \f$i\f$ from \f$d\f$ to \f$0\f$, where \f$\widehat{v_i}\f$ means + * that the vertex \f$v_i\f$, known as the opposite vertex, is omitted from boundary, but returned as the second + * element of a pair. + * + * @param[in] sh Simplex for which the boundary is computed. + */ + template<class SimplexHandle> + Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh) { + return Boundary_opposite_vertex_simplex_range(Boundary_opposite_vertex_simplex_iterator(this, sh), + Boundary_opposite_vertex_simplex_iterator(this)); + } + /** @} */ // end range and iterator methods /** \name Constructor/Destructor * @{ */ @@ -286,7 +338,7 @@ class Simplex_tree { /** \brief User-defined copy constructor reproduces the whole tree structure. */ Simplex_tree(const Simplex_tree& complex_source) { #ifdef DEBUG_TRACES - std::cout << "Simplex_tree copy constructor" << std::endl; + std::clog << "Simplex_tree copy constructor" << std::endl; #endif // DEBUG_TRACES copy_from(complex_source); } @@ -296,7 +348,7 @@ class Simplex_tree { */ Simplex_tree(Simplex_tree && complex_source) { #ifdef DEBUG_TRACES - std::cout << "Simplex_tree move constructor" << std::endl; + std::clog << "Simplex_tree move constructor" << std::endl; #endif // DEBUG_TRACES move_from(complex_source); @@ -313,7 +365,7 @@ class Simplex_tree { /** \brief User-defined copy assignment reproduces the whole tree structure. */ Simplex_tree& operator= (const Simplex_tree& complex_source) { #ifdef DEBUG_TRACES - std::cout << "Simplex_tree copy assignment" << std::endl; + std::clog << "Simplex_tree copy assignment" << std::endl; #endif // DEBUG_TRACES // Self-assignment detection if (&complex_source != this) { @@ -330,7 +382,7 @@ class Simplex_tree { */ Simplex_tree& operator=(Simplex_tree&& complex_source) { #ifdef DEBUG_TRACES - std::cout << "Simplex_tree move assignment" << std::endl; + std::clog << "Simplex_tree move assignment" << std::endl; #endif // DEBUG_TRACES // Self-assignment detection if (&complex_source != this) { @@ -450,10 +502,19 @@ class Simplex_tree { return true; } + /** \brief Returns the filtration value of a simplex. + * + * Same as `filtration()`, but does not handle `null_simplex()`. + */ + static Filtration_value filtration_(Simplex_handle sh) { + GUDHI_CHECK (sh != null_simplex(), "null simplex"); + return sh->second.filtration(); + } + public: /** \brief Returns the key associated to a simplex. * - * The filtration must be initialized. + * If no key has been assigned, returns `null_key()`. * \pre SimplexTreeOptions::store_key */ static Simplex_key key(Simplex_handle sh) { @@ -463,7 +524,6 @@ class Simplex_tree { /** \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 idx) const { return filtration_vect_[idx]; @@ -499,8 +559,7 @@ class Simplex_tree { return Dictionary_it(nullptr); } - /** \brief Returns a key different for all keys associated to the - * simplices of the simplicial complex. */ + /** \brief Returns a fixed number not in the interval [0, `num_simplices()`). */ static Simplex_key null_key() { return -1; } @@ -645,10 +704,10 @@ class Simplex_tree { return true; } - private: - /** \brief Inserts a simplex represented by a vector of vertex. - * @param[in] simplex vector of Vertex_handles, representing the vertices of the new simplex. The vector must be - * sorted by increasing vertex handle order. + protected: + /** \brief Inserts a simplex represented by a range of vertex. + * @param[in] simplex range of Vertex_handles, representing the vertices of the new simplex. The range must be + * sorted by increasing vertex handle order, and not empty. * @param[in] filtration the filtration value assigned to the new simplex. * @return If the new simplex is inserted successfully (i.e. it was not in the * simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned @@ -660,12 +719,13 @@ class Simplex_tree { * null_simplex. * */ - std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex, + template <class RandomVertexHandleRange = std::initializer_list<Vertex_handle>> + std::pair<Simplex_handle, bool> insert_simplex_raw(const RandomVertexHandleRange& simplex, Filtration_value filtration) { Siblings * curr_sib = &root_; std::pair<Simplex_handle, bool> res_insert; auto vi = simplex.begin(); - for (; vi != simplex.end() - 1; ++vi) { + for (; vi != std::prev(simplex.end()); ++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))) { @@ -686,9 +746,10 @@ class Simplex_tree { return std::pair<Simplex_handle, bool>(null_simplex(), false); } // otherwise the insertion has succeeded - size is a size_type - if (static_cast<int>(simplex.size()) - 1 > dimension_) { + int dim = static_cast<int>(boost::size(simplex)) - 1; + if (dim > dimension_) { // Update dimension if needed - dimension_ = static_cast<int>(simplex.size()) - 1; + dimension_ = dim; } return res_insert; } @@ -729,7 +790,7 @@ class Simplex_tree { // Copy before sorting std::vector<Vertex_handle> copy(first, last); std::sort(std::begin(copy), std::end(copy)); - return insert_vertex_vector(copy, filtration); + return insert_simplex_raw(copy, filtration); } /** \brief Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of @@ -755,12 +816,7 @@ class Simplex_tree { if (first == last) return { null_simplex(), true }; // FIXME: false would make more sense to me. - // Copy before sorting - // 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; + thread_local std::vector<Vertex_handle> copy; copy.clear(); copy.insert(copy.end(), first, last); std::sort(copy.begin(), copy.end()); @@ -827,7 +883,7 @@ class Simplex_tree { /** Returns the Siblings containing a simplex.*/ template<class SimplexHandle> - Siblings* self_siblings(SimplexHandle sh) { + static Siblings* self_siblings(SimplexHandle sh) { if (sh->second.children()->parent() == sh->first) return sh->second.children()->oncles(); else @@ -850,15 +906,13 @@ class Simplex_tree { } public: - /** \brief Initializes the filtrations, i.e. sort the - * simplices according to their order in the filtration and initializes all Simplex_keys. + /** \brief Initializes the filtration cache, i.e. sorts the + * simplices according to their order in the filtration. * - * After calling this method, filtration_simplex_range() becomes valid, and each simplex is - * assigned a Simplex_key corresponding to its order in the filtration (from 0 to m-1 for a - * simplicial complex with m simplices). + * It always recomputes the cache, even if one already exists. * - * Will be automatically called when calling filtration_simplex_range() - * if the filtration has never been initialized yet. */ + * Any insertion, deletion or change of filtration value invalidates this cache, + * which can be cleared with clear_filtration(). */ void initialize_filtration() { filtration_vect_.clear(); filtration_vect_.reserve(num_simplices()); @@ -880,6 +934,21 @@ class Simplex_tree { std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); #endif } + /** \brief Initializes the filtration cache if it isn't initialized yet. + * + * Automatically called by filtration_simplex_range(). */ + void maybe_initialize_filtration() { + if (filtration_vect_.empty()) { + initialize_filtration(); + } + } + /** \brief Clears the filtration cache produced by initialize_filtration(). + * + * Useful when initialize_filtration() has already been called and we perform an operation + * (say an insertion) that invalidates the cache. */ + void clear_filtration() { + filtration_vect_.clear(); + } private: /** Recursive search of cofaces @@ -903,7 +972,7 @@ class Simplex_tree { // If we reached the end of the vertices, and the simplex has more vertices than the given simplex // => we found a coface - // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices + // Add a coface if we want the star or if the number of vertices of the current simplex matches with nbVertices bool addCoface = (star || curr_nbVertices == nbVertices); if (addCoface) cofaces.push_back(simplex); @@ -1021,8 +1090,8 @@ class Simplex_tree { * * Inserts all vertices and edges given by a OneSkeletonGraph. * 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>. + * <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/VertexAndEdgeListGraph.html">boost::VertexAndEdgeListGraph</a> + * and <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>. * * The vertex filtration value is accessible through the property tag * vertex_filtration_t. @@ -1042,7 +1111,10 @@ class Simplex_tree { // the simplex tree must be empty assert(num_simplices() == 0); - if (boost::num_vertices(skel_graph) == 0) { + // is there a better way to let the compiler know that we don't mean Simplex_tree::num_vertices? + using boost::num_vertices; + + if (num_vertices(skel_graph) == 0) { return; } if (num_edges(skel_graph) == 0) { @@ -1051,25 +1123,21 @@ class Simplex_tree { dimension_ = 1; } - root_.members_.reserve(boost::num_vertices(skel_graph)); + root_.members_.reserve(num_vertices(skel_graph)); // probably useless in most cases + auto verts = vertices(skel_graph) | boost::adaptors::transformed([&](auto v){ + return Dit_value_t(v, Node(&root_, get(vertex_filtration_t(), skel_graph, v))); }); + root_.members_.insert(boost::begin(verts), boost::end(verts)); + // This automatically sorts the vertices, the graph concept doesn't guarantee the order in which we iterate. - typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it, - v_it_end; - for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end; - ++v_it) { - root_.members_.emplace_hint( - root_.members_.end(), *v_it, - Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); - } std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator, - typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = boost::edges(skel_graph); + typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = edges(skel_graph); // boost_edges.first is the equivalent to boost_edges.begin() // boost_edges.second is the equivalent to boost_edges.end() for (; boost_edges.first != boost_edges.second; boost_edges.first++) { auto edge = *(boost_edges.first); auto u = source(edge, skel_graph); auto v = target(edge, skel_graph); - if (u == v) throw "Self-loops are not simplicial"; + if (u == v) throw std::invalid_argument("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 @@ -1084,10 +1152,25 @@ class Simplex_tree { } sh->second.children()->members().emplace(v, - Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, edge))); + Node(sh->second.children(), get(edge_filtration_t(), skel_graph, edge))); } } + /** \brief Inserts several vertices. + * @param[in] vertices A range of Vertex_handle + * @param[in] filt filtration value of the new vertices (the same for all) + * + * This may be faster than inserting the vertices one by one, especially in a random order. + * The complex does not need to be empty before calling this function. However, if a vertex is + * already present, its filtration value is not modified, unlike with other insertion functions. */ + template <class VertexRange> + void insert_batch_vertices(VertexRange const& vertices, Filtration_value filt = 0) { + auto verts = vertices | boost::adaptors::transformed([&](auto v){ + return Dit_value_t(v, Node(&root_, filt)); }); + root_.members_.insert(boost::begin(verts), boost::end(verts)); + if (dimension_ < 0 && !root_.members_.empty()) dimension_ = 0; + } + /** \brief Expands the Simplex_tree containing only its one skeleton * until dimension max_dim. * @@ -1101,6 +1184,7 @@ class Simplex_tree { * 1 when calling the method. */ void expansion(int max_dim) { if (max_dim <= 1) return; + clear_filtration(); // Drop the cache. dimension_ = max_dim; for (Dictionary_it root_it = root_.members_.begin(); root_it != root_.members_.end(); ++root_it) { @@ -1123,10 +1207,7 @@ class Simplex_tree { Dictionary_it next = siblings->members().begin(); ++next; -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL - thread_local -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - std::vector<std::pair<Vertex_handle, Node> > inter; + 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); @@ -1243,6 +1324,7 @@ class Simplex_tree { Siblings * new_sib = new Siblings(siblings, // oncles simplex->first, // parent boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t + simplex->second.assign_children(new_sib); 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(); @@ -1265,7 +1347,6 @@ class Simplex_tree { 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); } } else { @@ -1275,7 +1356,7 @@ class Simplex_tree { } } - /* \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given + /** \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given * Vertex_handle if the Vertex_handle is found in the Simplex_handle children list. * Returns null_simplex() if it does not exist */ @@ -1314,9 +1395,8 @@ class Simplex_tree { /** \brief This function ensures that each simplex has a higher filtration value than its faces by increasing the * filtration values. * @return True if any filtration value was modified, false if the filtration was already non-decreasing. - * \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 - * complex has changed , please call `initialize_filtration()` to recompute it. + * + * If a simplex has a `NaN` filtration value, it is considered lower than any other defined filtration value. */ bool make_filtration_non_decreasing() { bool modified = false; @@ -1326,6 +1406,8 @@ class Simplex_tree { modified |= rec_make_filtration_non_decreasing(simplex.second.children()); } } + if(modified) + clear_filtration(); // Drop the cache. return modified; } @@ -1347,7 +1429,9 @@ class Simplex_tree { }); Filtration_value max_filt_border_value = filtration(*max_border); - if (simplex.second.filtration() < max_filt_border_value) { + // Replacing if(f<max) with if(!(f>=max)) would mean that if f is NaN, we replace it with the max of the children. + // That seems more useful than keeping NaN. + if (!(simplex.second.filtration() >= max_filt_border_value)) { // Store the filtration modification information modified = true; simplex.second.assign_filtration(max_filt_border_value); @@ -1363,16 +1447,16 @@ class Simplex_tree { public: /** \brief Prune above filtration value given as parameter. * @param[in] filtration Maximum threshold value. - * @return The filtration modification information. - * \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. + * @return True if any simplex was removed, false if all simplices already had a value below the threshold. * \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); + bool modified = rec_prune_above_filtration(root(), filtration); + if(modified) + clear_filtration(); // Drop the cache. + return modified; } private: @@ -1418,14 +1502,14 @@ class Simplex_tree { for (Simplex_handle sh : complex_simplex_range()) { #ifdef DEBUG_TRACES for (auto vertex : simplex_vertex_range(sh)) { - std::cout << " " << vertex; + std::clog << " " << vertex; } - std::cout << std::endl; + std::clog << 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 + // Stop browsing as soon as the dimension is reached, no need to go further return false; new_dimension = (std::max)(new_dimension, sh_dimension); } @@ -1439,7 +1523,6 @@ class Simplex_tree { * @param[in] sh Simplex handle on the maximal simplex to remove. * \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). * \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. @@ -1465,6 +1548,200 @@ class Simplex_tree { } } + /** \brief Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the + * computation of extended persistence requires modifying the filtration values, this function can be used + * to recover the original values. Moreover, computing extended persistence requires adding new simplices + * in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). See the definition of Extended_simplex_type. Note that if the simplex type is DOWN, the original filtration value + * is set to be the original filtration value of the corresponding (not coned) original simplex. + * \pre This function should be called only if `extend_filtration()` has been called first! + * \post The output filtration value is supposed to be the same, but might be a little different, than the + * original filtration value, due to the internal transformation (scaling to [-2,-1]) that is + * performed on the original filtration values during the computation of extended persistence. + * @param[in] f Filtration value of the simplex in the extended (i.e., modified) filtration. + * @param[in] efd Structure containing the minimum and maximum values of the original filtration. This the output of `extend_filtration()`. + * @return A pair containing the original filtration value of the simplex as well as the simplex type. + */ + std::pair<Filtration_value, Extended_simplex_type> decode_extended_filtration(Filtration_value f, const Extended_filtration_data& efd){ + std::pair<Filtration_value, Extended_simplex_type> p; + Filtration_value minval = efd.minval; + Filtration_value maxval = efd.maxval; + if (f >= -2 && f <= -1){ + p.first = minval + (maxval-minval)*(f + 2); p.second = Extended_simplex_type::UP; + } + else if (f >= 1 && f <= 2){ + p.first = minval - (maxval-minval)*(f - 2); p.second = Extended_simplex_type::DOWN; + } + else{ + p.first = std::numeric_limits<Filtration_value>::quiet_NaN(); p.second = Extended_simplex_type::EXTRA; + } + return p; + }; + + /** \brief Extend filtration for computing extended persistence. + * This function only uses the filtration values at the 0-dimensional simplices, + * and computes the extended persistence diagram induced by the lower-star filtration + * computed with these values. + * \post Note that after calling this function, the filtration + * values are actually modified. The function `decode_extended_filtration()` + * retrieves the original values and outputs the extended simplex type. + * \pre Note that this code creates an extra vertex internally, so you should make sure that + * the Simplex tree does not contain a vertex with the largest Vertex_handle. + * @return A data structure containing the maximum and minimum values of the original filtration. + * It is meant to be provided as input to `decode_extended_filtration()` in order to retrieve + * the original filtration values for each simplex. + */ + Extended_filtration_data extend_filtration() { + clear_filtration(); // Drop the cache. + + // Compute maximum and minimum of filtration values + Vertex_handle maxvert = std::numeric_limits<Vertex_handle>::min(); + Filtration_value minval = std::numeric_limits<Filtration_value>::infinity(); + Filtration_value maxval = -std::numeric_limits<Filtration_value>::infinity(); + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){ + Filtration_value f = this->filtration(sh); + minval = std::min(minval, f); + maxval = std::max(maxval, f); + maxvert = std::max(sh->first, maxvert); + } + + GUDHI_CHECK(maxvert < std::numeric_limits<Vertex_handle>::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle")); + maxvert += 1; + + Simplex_tree st_copy = *this; + + // Add point for coning the simplicial complex + this->insert_simplex_raw({maxvert}, -3); + + // For each simplex + std::vector<Vertex_handle> vr; + for (auto sh_copy : st_copy.complex_simplex_range()){ + + // Locate simplex + vr.clear(); + for (auto vh : st_copy.simplex_vertex_range(sh_copy)){ + vr.push_back(vh); + } + auto sh = this->find(vr); + + // Create cone on simplex + vr.push_back(maxvert); + if (this->dimension(sh) == 0){ + Filtration_value v = this->filtration(sh); + Filtration_value scaled_v = (v-minval)/(maxval-minval); + // Assign ascending value between -2 and -1 to vertex + this->assign_filtration(sh, -2 + scaled_v); + // Assign descending value between 1 and 2 to cone on vertex + this->insert_simplex(vr, 2 - scaled_v); + } + else{ + // Assign value -3 to simplex and cone on simplex + this->assign_filtration(sh, -3); + this->insert_simplex(vr, -3); + } + } + + // Automatically assign good values for simplices + this->make_filtration_non_decreasing(); + + // Return the filtration data + Extended_filtration_data efd(minval, maxval); + return efd; + } + + /** \brief Returns a vertex of `sh` that has the same filtration value as `sh` if it exists, and `null_vertex()` otherwise. + * + * For a lower-star filtration built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which vertex had its filtration value propagated to `sh`. + * If several vertices have the same filtration value, the one it returns is arbitrary. */ + Vertex_handle vertex_with_same_filtration(Simplex_handle sh) { + auto filt = filtration_(sh); + for(auto v : simplex_vertex_range(sh)) + if(filtration_(find_vertex(v)) == filt) + return v; + return null_vertex(); + } + + /** \brief Returns an edge of `sh` that has the same filtration value as `sh` if it exists, and `null_simplex()` otherwise. + * + * For a flag-complex built with `expansion()`, this is a way to invert the process and find out which edge had its filtration value propagated to `sh`. + * If several edges have the same filtration value, the one it returns is arbitrary. + * + * \pre `sh` must have dimension at least 1. */ + Simplex_handle edge_with_same_filtration(Simplex_handle sh) { + // See issue #251 for potential speed improvements. + auto&& vertices = simplex_vertex_range(sh); // vertices in decreasing order + auto end = std::end(vertices); + auto vi = std::begin(vertices); + GUDHI_CHECK(vi != end, "empty simplex"); + auto v0 = *vi; + ++vi; + GUDHI_CHECK(vi != end, "simplex of dimension 0"); + if(std::next(vi) == end) return sh; // shortcut for dimension 1 + boost::container::static_vector<Vertex_handle, 40> suffix; + suffix.push_back(v0); + auto filt = filtration_(sh); + do + { + Vertex_handle v = *vi; + auto&& children1 = find_vertex(v)->second.children()->members_; + for(auto w : suffix){ + // Can we take advantage of the fact that suffix is ordered? + Simplex_handle s = children1.find(w); + if(filtration_(s) == filt) + return s; + } + suffix.push_back(v); + } + while(++vi != end); + return null_simplex(); + } + + /** \brief Returns a minimal face of `sh` that has the same filtration value as `sh`. + * + * For a filtration built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which simplex had its filtration value propagated to `sh`. + * If several minimal (for inclusion) simplices have the same filtration value, the one it returns is arbitrary, and it is not guaranteed to be the one with smallest dimension. */ + Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) { + auto filt = filtration_(sh); + // Naive implementation, it can be sped up. + for(auto b : boundary_simplex_range(sh)) + if(filtration_(b) == filt) + return minimal_simplex_with_same_filtration(b); + return sh; // None of its faces has the same filtration. + } + + public: + /** \brief This function resets the filtration value of all the simplices of dimension at least min_dim. Resets all + * the Simplex_tree when `min_dim = 0`. + * `reset_filtration` may break the filtration property with `min_dim > 0`, and it is the user's responsibility to + * make it a valid filtration (using a large enough `filt_value`, or calling `make_filtration_non_decreasing` + * afterwards for instance). + * @param[in] filt_value The new filtration value. + * @param[in] min_dim The minimal dimension. Default value is 0. + */ + void reset_filtration(Filtration_value filt_value, int min_dim = 0) { + rec_reset_filtration(&root_, filt_value, min_dim); + clear_filtration(); // Drop the cache. + } + + private: + /** \brief Recursively resets filtration value when minimal depth <= 0. + * @param[in] sib Siblings to be parsed. + * @param[in] filt_value The new filtration value. + * @param[in] min_depth The minimal depth. + */ + void rec_reset_filtration(Siblings * sib, Filtration_value filt_value, int min_depth) { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { + if (min_depth <= 0) { + sh->second.assign_filtration(filt_value); + } + if (has_children(sh)) { + rec_reset_filtration(sh->second.children(), filt_value, min_depth - 1); + } + } + } + private: Vertex_handle null_vertex_; /** \brief Total number of simplices in the complex, without the empty simplex.*/ @@ -1542,7 +1819,7 @@ struct Simplex_tree_options_fast_persistence { static const bool contiguous_vertices = true; }; -/** @} */ // end defgroup simplex_tree +/** @}*/ // end addtogroup simplex_tree } // namespace Gudhi 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 efccf2f2..b63a5595 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 @@ -5,6 +5,7 @@ * Copyright (C) 2014 Inria * * Modification(s): + * - 2022/04 Vincent Rouvreau: Add Simplex_tree_boundary_opposite_vertex_simplex_iterator for alpha and cech purpose * - YYYY/MM Author: Description of the modification */ @@ -14,21 +15,19 @@ #include <gudhi/Debug_utils.h> #include <boost/iterator/iterator_facade.hpp> -#include <boost/version.hpp> -#if BOOST_VERSION >= 105600 -# include <boost/container/static_vector.hpp> -#endif +#include <boost/container/static_vector.hpp> #include <vector> +#include <utility> // for std::pair namespace Gudhi { -/* \addtogroup simplex_tree +/** \addtogroup simplex_tree * Iterators and range types for the Simplex_tree. - * @{ + * @{ */ -/* \brief Iterator over the vertices of a simplex +/** \brief Iterator over the vertices of a simplex * in a SimplexTree. * * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/ @@ -42,13 +41,13 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade< typedef typename SimplexTree::Siblings Siblings; typedef typename SimplexTree::Vertex_handle Vertex_handle; - explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st) + explicit Simplex_tree_simplex_vertex_iterator(SimplexTree const* st) : // any end() iterator sib_(nullptr), v_(st->null_vertex()) { } - Simplex_tree_simplex_vertex_iterator(SimplexTree * st, Simplex_handle sh) + Simplex_tree_simplex_vertex_iterator(SimplexTree const* st, Simplex_handle sh) : sib_(st->self_siblings(sh)), v_(sh->first) { } @@ -74,7 +73,7 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade< }; /*---------------------------------------------------------------------------*/ -/* \brief Iterator over the simplices of the boundary of a +/** \brief Iterator over the simplices of the boundary of a * simplex. * * Forward iterator, value_type is SimplexTree::Simplex_handle.*/ @@ -87,6 +86,12 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< typedef typename SimplexTree::Vertex_handle Vertex_handle; typedef typename SimplexTree::Siblings Siblings; + // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is overwritten. + Simplex_tree_boundary_simplex_iterator() + : sib_(nullptr), + st_(nullptr) { + } + // any end() iterator explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st) : last_(st->null_vertex()), @@ -120,7 +125,7 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< private: friend class boost::iterator_core_access; -// valid when iterating along the SAME boundary. + // valid when iterating along the SAME boundary. bool equal(Simplex_tree_boundary_simplex_iterator const& other) const { return sh_ == other.sh_; } @@ -166,21 +171,127 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< // Most of the storage should be moved to the range, iterators should be light. Vertex_handle last_; // last vertex of the simplex Vertex_handle next_; // next vertex to push in suffix_ -#if BOOST_VERSION >= 105600 // 40 seems a conservative bound on the dimension of a Simplex_tree for now, // as it would not fit on the biggest hard-drive. boost::container::static_vector<Vertex_handle, 40> suffix_; // static_vector still has some overhead compared to a trivial hand-made // version using std::aligned_storage, or compared to making suffix_ static. -#else - std::vector<Vertex_handle> suffix_; -#endif Siblings * sib_; // where the next search will start from Simplex_handle sh_; // current Simplex_handle in the boundary SimplexTree * st_; // simplex containing the simplicial complex }; + +/** \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices. + * + * Forward iterator, value_type is std::pair<SimplexTree::Simplex_handle, SimplexTree::Vertex_handle>.*/ +template<class SimplexTree> +class Simplex_tree_boundary_opposite_vertex_simplex_iterator : public boost::iterator_facade< + Simplex_tree_boundary_opposite_vertex_simplex_iterator<SimplexTree>, + std::pair<typename SimplexTree::Simplex_handle, typename SimplexTree::Vertex_handle> const, boost::forward_traversal_tag> { + public: + using Simplex_handle = typename SimplexTree::Simplex_handle; + using Vertex_handle = typename SimplexTree::Vertex_handle; + using Siblings = typename SimplexTree::Siblings; + + // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is + // overwritten. + Simplex_tree_boundary_opposite_vertex_simplex_iterator() + : sib_(nullptr), + st_(nullptr) { + } + + // any end() iterator + explicit Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st) + : last_(st->null_vertex()), + next_(st->null_vertex()), + sib_(nullptr), + baov_(st->null_simplex(), st->null_vertex()), + st_(st) { + } + + template<class SimplexHandle> + Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st, SimplexHandle sh) + : last_(sh->first), + next_(st->null_vertex()), + sib_(nullptr), + baov_(st->null_simplex(), sh->first), + 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) { + if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr) + // Only relevant for edges + baov_.first = sib_->members_.begin()+next_; + else + baov_.first = sib_->find(next_); + } + } + + private: + friend class boost::iterator_core_access; + + // valid when iterating along the SAME boundary. + bool equal(Simplex_tree_boundary_opposite_vertex_simplex_iterator const& other) const { + return (baov_.first == other.baov_.first); + } + + std::pair<Simplex_handle, Vertex_handle> const& dereference() const { + return baov_; + } + + void increment() { + if (sib_ == nullptr) { + baov_.first = st_->null_simplex(); + return; // ------>> + } + Siblings * for_sib = sib_; + Siblings * new_sib = sib_->oncles(); + auto rit = suffix_.rbegin(); + if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) { + // We reached the root, use a short-cut to find a vertex. + if (rit == suffix_.rend()) { + baov_.second = baov_.first->first; + // Segment, this vertex is the last boundary simplex + baov_.first = for_sib->members_.begin()+last_; + sib_ = nullptr; + return; + } else { + // Dim >= 2, initial step of the descent + baov_.first = for_sib->members_.begin()+*rit; + for_sib = baov_.first->second.children(); + ++rit; + } + } + for (; rit != suffix_.rend(); ++rit) { + baov_.first = for_sib->find(*rit); + for_sib = baov_.first->second.children(); + } + baov_.first = for_sib->find(last_); // baov_.first points to the right simplex now + suffix_.push_back(next_); + next_ = sib_->parent(); + sib_ = new_sib; + baov_.second = suffix_.back(); + } + + // Most of the storage should be moved to the range, iterators should be light. + Vertex_handle last_; // last vertex of the simplex + Vertex_handle next_; // next vertex to push in suffix_ + // 40 seems a conservative bound on the dimension of a Simplex_tree for now, + // as it would not fit on the biggest hard-drive. + boost::container::static_vector<Vertex_handle, 40> suffix_; + // static_vector still has some overhead compared to a trivial hand-made + // version using std::aligned_storage, or compared to making suffix_ static. + Siblings * sib_; // where the next search will start from + std::pair<Simplex_handle, Vertex_handle> baov_; // a pair containing the current Simplex_handle in the boundary and its opposite vertex + SimplexTree * st_; // simplex containing the simplicial complex +}; + /*---------------------------------------------------------------------------*/ -/* \brief Iterator over the simplices of a simplicial complex. +/** \brief Iterator over the simplices of a simplicial complex. * * Forward iterator, value_type is SimplexTree::Simplex_handle.*/ template<class SimplexTree> @@ -253,7 +364,7 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade< SimplexTree * st_; }; -/* \brief Iterator over the simplices of the skeleton of a given +/** \brief Iterator over the simplices of the skeleton of a given * dimension of the simplicial complex. * * Forward iterator, value_type is SimplexTree::Simplex_handle.*/ @@ -336,7 +447,8 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade< int curr_dim_; }; -/* @} */ // end addtogroup simplex_tree +/** @}*/ // end addtogroup simplex_tree + } // namespace Gudhi #endif // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_ 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 ae140859..63023daa 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 @@ -15,16 +15,15 @@ namespace Gudhi { -/* \addtogroup simplex_tree +/** \addtogroup simplex_tree * Represents a node of a Simplex_tree. * @{ */ -/* - * \brief Node of a simplex tree with filtration value +/** \brief Node of a simplex tree with filtration value * and simplex key. * - * It stores explicitely its own filtration value and its own Simplex_key. + * It stores explicitly its own filtration value and its own Simplex_key. */ template<class SimplexTree> struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base { @@ -54,7 +53,8 @@ struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base Siblings * children_; }; -/* @} */ // end addtogroup simplex_tree +/** @}*/ // end addtogroup simplex_tree + } // namespace Gudhi #endif // SIMPLEX_TREE_SIMPLEX_TREE_NODE_EXPLICIT_STORAGE_H_ 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 b53bad29..d849eeba 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 @@ -20,12 +20,12 @@ namespace Gudhi { -/* \addtogroup simplex_tree +/** \addtogroup simplex_tree * Represents a set of node of a Simplex_tree that share the same parent. * @{ */ -/* \brief Data structure to store a set of nodes in a SimplexTree sharing +/** \brief Data structure to store a set of nodes in a SimplexTree sharing * the same parent node.*/ template<class SimplexTree, class MapContainer> class Simplex_tree_siblings { @@ -36,6 +36,7 @@ class Simplex_tree_siblings { template<class T> friend class Simplex_tree_boundary_simplex_iterator; template<class T> friend class Simplex_tree_complex_simplex_iterator; template<class T> friend class Simplex_tree_skeleton_simplex_iterator; + template<class T> friend class Simplex_tree_boundary_opposite_vertex_simplex_iterator; typedef typename SimplexTree::Vertex_handle Vertex_handle; typedef typename SimplexTree::Filtration_value Filtration_value; @@ -57,7 +58,7 @@ class Simplex_tree_siblings { members_() { } - /* \brief Constructor with initialized set of members. + /** \brief Constructor with initialized set of members. * * 'members' must be sorted and unique.*/ template<typename RandomAccessVertexRange> @@ -71,8 +72,7 @@ class Simplex_tree_siblings { } } - /* - * \brief Inserts a Node in the set of siblings nodes. + /** \brief Inserts a Node in the set of siblings nodes. * * If already present, assigns the minimal filtration value * between input filtration_value and the value already @@ -113,7 +113,8 @@ class Simplex_tree_siblings { Dictionary members_; }; -/* @} */ // end addtogroup simplex_tree +/** @}*/ // end addtogroup simplex_tree + } // namespace Gudhi #endif // SIMPLEX_TREE_SIMPLEX_TREE_SIBLINGS_H_ 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 3e395ae2..29c76e50 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h @@ -20,7 +20,7 @@ namespace Gudhi { struct linear_indexing_tag { }; -/* \brief Tag for a zigzag ordering of simplices. */ +/** \brief Tag for a zigzag ordering of simplices. */ // struct zigzag_indexing_tag {}; } // namespace Gudhi diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt index 8b9163f5..25b562e0 100644 --- a/src/Simplex_tree/test/CMakeLists.txt +++ b/src/Simplex_tree/test/CMakeLists.txt @@ -28,3 +28,15 @@ if (TBB_FOUND) target_link_libraries(Simplex_tree_ctor_and_move_test_unit ${TBB_LIBRARIES}) endif() gudhi_add_boost_test(Simplex_tree_ctor_and_move_test_unit) + +add_executable ( Simplex_tree_make_filtration_non_decreasing_test_unit simplex_tree_make_filtration_non_decreasing_unit_test.cpp ) +if (TBB_FOUND) + target_link_libraries(Simplex_tree_make_filtration_non_decreasing_test_unit ${TBB_LIBRARIES}) +endif() +gudhi_add_boost_test(Simplex_tree_make_filtration_non_decreasing_test_unit) + +add_executable ( Simplex_tree_graph_expansion_test_unit simplex_tree_graph_expansion_unit_test.cpp ) +if (TBB_FOUND) + target_link_libraries(Simplex_tree_graph_expansion_test_unit ${TBB_LIBRARIES}) +endif() +gudhi_add_boost_test(Simplex_tree_graph_expansion_test_unit) diff --git a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp index c0615b12..f6118fe0 100644 --- a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp @@ -30,16 +30,16 @@ void print_simplex_filtration(Simplex_tree& st, const std::string& msg) { // Required before browsing through filtration values st.initialize_filtration(); - std::cout << "********************************************************************\n"; - std::cout << "* " << msg << "\n"; - std::cout << "* The complex contains " << st.num_simplices() << " simplices"; - std::cout << " - dimension " << st.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "********************************************************************\n"; + std::clog << "* " << msg << "\n"; + std::clog << "* The complex contains " << st.num_simplices() << " simplices"; + std::clog << " - dimension " << st.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : st.filtration_simplex_range()) { - std::cout << " " + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; - for (auto vertex : st.simplex_vertex_range(f_simplex)) std::cout << "(" << vertex << ")"; - std::cout << std::endl; + for (auto vertex : st.simplex_vertex_range(f_simplex)) std::clog << "(" << vertex << ")"; + std::clog << std::endl; } } @@ -70,8 +70,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te print_simplex_filtration(st, "Default Simplex_tree is initialized"); - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF COPY CONSTRUCTOR" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF COPY CONSTRUCTOR" << std::endl; Simplex_tree st1(st); Simplex_tree st2(st); @@ -82,8 +82,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te BOOST_CHECK(st == st2); BOOST_CHECK(st1 == st); - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF COPY ASSIGNMENT" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF COPY ASSIGNMENT" << std::endl; Simplex_tree st3; // To check there is no memory leak st3.insert_simplex_and_subfaces({9, 10, 11}, 200.0); @@ -98,13 +98,21 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te BOOST_CHECK(st == st4); BOOST_CHECK(st3 == st); +#ifdef __clang__ +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wself-assign-overloaded" +#endif st = st; - print_simplex_filtration(st4, "Third self copy assignment from the default Simplex_tree"); +#ifdef __clang__ +#pragma GCC diagnostic pop +#endif + + print_simplex_filtration(st, "Third self copy assignment from the default Simplex_tree"); BOOST_CHECK(st3 == st); - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF MOVE CONSTRUCTOR" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF MOVE CONSTRUCTOR" << std::endl; Simplex_tree st5(std::move(st1)); print_simplex_filtration(st5, "First move constructor from the default Simplex_tree"); print_simplex_filtration(st1, "First moved Simplex_tree shall be empty"); @@ -122,8 +130,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te BOOST_CHECK(empty_st == st2); BOOST_CHECK(st1 == empty_st); - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF MOVE ASSIGNMENT" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF MOVE ASSIGNMENT" << std::endl; Simplex_tree st7; // To check there is no memory leak diff --git a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp index fab25eb8..54e23204 100644 --- a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp @@ -9,33 +9,62 @@ */ #include <iostream> -#include <fstream> -#include <string> -#include <algorithm> -#include <utility> // std::pair, std::make_pair -#include <cmath> // float comparison -#include <limits> -#include <functional> // greater +#include <vector> #define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "simplex_tree" +#define BOOST_TEST_MODULE "simplex_tree_graph_expansion" #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" +#include <gudhi/Unitary_tests_utils.h> using namespace Gudhi; typedef boost::mpl::list<Simplex_tree<>, Simplex_tree<Simplex_tree_options_fast_persistence>> list_of_tested_variants; +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_all_is_blocked, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_all_is_blocked\n"; + std::clog << "********************************************************************\n"; + using Simplex_handle = typename typeST::Simplex_handle; + // Construct the Simplex Tree with a 1-skeleton graph example + typeST simplex_tree; + + simplex_tree.insert_simplex({0, 1}, 0.); + simplex_tree.insert_simplex({0, 2}, 1.); + simplex_tree.insert_simplex({0, 3}, 2.); + simplex_tree.insert_simplex({1, 2}, 3.); + simplex_tree.insert_simplex({1, 3}, 4.); + simplex_tree.insert_simplex({2, 3}, 5.); + simplex_tree.insert_simplex({2, 4}, 6.); + simplex_tree.insert_simplex({3, 6}, 7.); + simplex_tree.insert_simplex({4, 5}, 8.); + simplex_tree.insert_simplex({4, 6}, 9.); + simplex_tree.insert_simplex({5, 6}, 10.); + simplex_tree.insert_simplex({6}, 10.); + + typeST stree_copy = simplex_tree; + + simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){ return true; }); + + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) + std::clog << "(" << vertex << ")"; + std::clog << std::endl; + } -bool AreAlmostTheSame(float a, float b) { - return std::fabs(a - b) < std::numeric_limits<float>::epsilon(); + BOOST_CHECK(stree_copy == simplex_tree); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_blockers_3\n"; + std::clog << "********************************************************************\n"; using Simplex_handle = typename typeST::Simplex_handle; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -55,49 +84,54 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){ bool result = false; - std::cout << "Blocker on ["; + std::clog << "Blocker on ["; // User can loop on the vertices from the given simplex_handle i.e. for (auto vertex : simplex_tree.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::clog << vertex << ", "; } - std::cout << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + std::clog << "] ( " << simplex_tree.filtration(sh); + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.); - std::cout << " + 1. ) = " << result << std::endl; + std::clog << " + 1. ) = " << result << std::endl; return result; }); - std::cout << "********************************************************************\n"; - std::cout << "simplex_tree_expansion_with_blockers_3\n"; - std::cout << "********************************************************************\n"; - std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; - std::cout << " - dimension " << simplex_tree.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; - std::cout << std::endl; + std::clog << "(" << vertex << ")"; + std::clog << std::endl; } BOOST_CHECK(simplex_tree.num_simplices() == 23); BOOST_CHECK(simplex_tree.dimension() == 3); // {4, 5, 6} shall be blocked BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex()); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 7.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast<typename typeST::Filtration_value>(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast<typename typeST::Filtration_value>(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast<typename typeST::Filtration_value>(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast<typename typeST::Filtration_value>(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), + static_cast<typename typeST::Filtration_value>(7.)); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_blockers_2\n"; + std::clog << "********************************************************************\n"; using Simplex_handle = typename typeST::Simplex_handle; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -117,48 +151,112 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li simplex_tree.expansion_with_blockers(2, [&](Simplex_handle sh){ bool result = false; - std::cout << "Blocker on ["; + std::clog << "Blocker on ["; // User can loop on the vertices from the given simplex_handle i.e. for (auto vertex : simplex_tree.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::clog << vertex << ", "; } - std::cout << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + std::clog << "] ( " << simplex_tree.filtration(sh); + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.); - std::cout << " + 1. ) = " << result << std::endl; + std::clog << " + 1. ) = " << result << std::endl; return result; }); - std::cout << "********************************************************************\n"; - std::cout << "simplex_tree_expansion_with_blockers_2\n"; - std::cout << "********************************************************************\n"; - std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; - std::cout << " - dimension " << simplex_tree.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; - std::cout << std::endl; + std::clog << "(" << vertex << ")"; + std::clog << std::endl; } BOOST_CHECK(simplex_tree.num_simplices() == 22); BOOST_CHECK(simplex_tree.dimension() == 2); // {4, 5, 6} shall be blocked BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex()); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast<typename typeST::Filtration_value>(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast<typename typeST::Filtration_value>(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast<typename typeST::Filtration_value>(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast<typename typeST::Filtration_value>(6.)); BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex()); } -BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_variants) { +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_find_simplex_blockers, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_find_simplex_blockers\n"; + std::clog << "********************************************************************\n"; + using Simplex_handle = typename typeST::Simplex_handle; + // Construct the Simplex Tree with a 1-skeleton graph example + typeST simplex_tree; + + simplex_tree.insert_simplex({0, 1}, 0.); + simplex_tree.insert_simplex({0, 2}, 1.); + simplex_tree.insert_simplex({0, 3}, 2.); + simplex_tree.insert_simplex({1, 2}, 3.); + simplex_tree.insert_simplex({1, 3}, 4.); + simplex_tree.insert_simplex({2, 3}, 5.); + simplex_tree.insert_simplex({2, 4}, 6.); + simplex_tree.insert_simplex({3, 6}, 7.); + simplex_tree.insert_simplex({4, 5}, 8.); + simplex_tree.insert_simplex({4, 6}, 9.); + simplex_tree.insert_simplex({5, 6}, 10.); + simplex_tree.insert_simplex({6}, 10.); + + simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){ + bool result = false; + std::clog << "Blocker on ["; + std::vector<typename typeST::Vertex_handle> simplex; + // User can loop on the vertices from the given simplex_handle i.e. + for (auto vertex : simplex_tree.simplex_vertex_range(sh)) { + // We block the expansion, if the vertex '1' is in the given list of vertices + if (vertex == 1) + result = true; + std::clog << vertex << ", "; + simplex.push_back(vertex); + } + std::clog << "] => " << result << std::endl; + // Not efficient but test it works - required by the python interface + BOOST_CHECK(simplex_tree.find(simplex) == sh); + return result; + }); + + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) + std::clog << "(" << vertex << ")"; + std::clog << std::endl; + } + + BOOST_CHECK(simplex_tree.num_simplices() == 20); + BOOST_CHECK(simplex_tree.dimension() == 2); + + // {1, 2, 3}, {0, 1, 2} and {0, 1, 3} shall be blocked as it contains vertex 1 + BOOST_CHECK(simplex_tree.find({4, 5, 6}) != simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({1, 2, 3}) == simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 2, 3}) != simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 1, 2}) == simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 1, 3}) == simplex_tree.null_simplex()); +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_3, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_3\n"; + std::clog << "********************************************************************\n"; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -176,32 +274,38 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_var simplex_tree.insert_simplex({6}, 10.); simplex_tree.expansion(3); - std::cout << "********************************************************************\n"; - std::cout << "simplex_tree_expansion_3\n"; - std::cout << "********************************************************************\n"; - std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; - std::cout << " - dimension " << simplex_tree.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; - std::cout << std::endl; + std::clog << "(" << vertex << ")"; + std::clog << std::endl; } BOOST_CHECK(simplex_tree.num_simplices() == 24); BOOST_CHECK(simplex_tree.dimension() == 3); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({4,5,6})), + static_cast<typename typeST::Filtration_value>(10.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast<typename typeST::Filtration_value>(3.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast<typename typeST::Filtration_value>(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast<typename typeST::Filtration_value>(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast<typename typeST::Filtration_value>(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), + static_cast<typename typeST::Filtration_value>(5.)); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_2\n"; + std::clog << "********************************************************************\n"; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -220,26 +324,28 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_v simplex_tree.expansion(2); - std::cout << "********************************************************************\n"; - std::cout << "simplex_tree_expansion_2\n"; - std::cout << "********************************************************************\n"; - std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; - std::cout << " - dimension " << simplex_tree.dimension() << "\n"; - std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; for (auto f_simplex : simplex_tree.filtration_simplex_range()) { - std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) - std::cout << "(" << vertex << ")"; - std::cout << std::endl; + std::clog << "(" << vertex << ")"; + std::clog << std::endl; } BOOST_CHECK(simplex_tree.num_simplices() == 23); BOOST_CHECK(simplex_tree.dimension() == 2); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({4,5,6})), + static_cast<typename typeST::Filtration_value>(10.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast<typename typeST::Filtration_value>(3.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast<typename typeST::Filtration_value>(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast<typename typeST::Filtration_value>(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast<typename typeST::Filtration_value>(5.)); BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex()); } 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 index 28c29489..20007488 100644 --- a/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp @@ -34,8 +34,8 @@ typedef boost::mpl::list<Simplex_tree<>, > 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; + std::clog << "********************************************************************" << std::endl; + std::clog << "SIMPLEX TREE IOSTREAM OPERATOR" << std::endl; Stree_type st; @@ -46,15 +46,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(iostream_operator, Stree_type, list_of_tested_vari st.initialize_filtration(); // Display the Simplex_tree - std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = " + std::clog << "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; + std::clog << 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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } // st: @@ -75,15 +75,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(iostream_operator, Stree_type, list_of_tested_vari simplex_tree_istream >> read_st; // Display the Simplex_tree - std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = " + std::clog << "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; + std::clog << 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) << "] "; + std::clog << " " << "[" << read_st.filtration(f_simplex) << "] "; for (auto vertex : read_st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } BOOST_CHECK(st == read_st); @@ -91,8 +91,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(iostream_operator, Stree_type, list_of_tested_vari BOOST_AUTO_TEST_CASE(mini_iostream_operator) { - std::cout << "********************************************************************" << std::endl; - std::cout << "MINI SIMPLEX TREE IOSTREAM OPERATOR" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "MINI SIMPLEX TREE IOSTREAM OPERATOR" << std::endl; Simplex_tree<MyOptions> st; @@ -103,14 +103,14 @@ BOOST_AUTO_TEST_CASE(mini_iostream_operator) { st.initialize_filtration(); // Display the Simplex_tree - std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = " + std::clog << "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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } // st: @@ -131,15 +131,15 @@ BOOST_AUTO_TEST_CASE(mini_iostream_operator) { simplex_tree_istream >> read_st; // Display the Simplex_tree - std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = " + std::clog << "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; + std::clog << 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) << "] "; + std::clog << " " << "[" << read_st.filtration(f_simplex) << "] "; for (auto vertex : read_st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } BOOST_CHECK(st == read_st); diff --git a/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp new file mode 100644 index 00000000..e0e7cadf --- /dev/null +++ b/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp @@ -0,0 +1,148 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2020 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#include <iostream> +#include <limits> // for NaN +#include <cmath> // for isNaN + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simplex_tree_make_filtration_non_decreasing" +#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; + +typedef boost::mpl::list<Simplex_tree<>, Simplex_tree<Simplex_tree_options_fast_persistence>> list_of_tested_variants; + +BOOST_AUTO_TEST_CASE_TEMPLATE(make_filtration_non_decreasing, typeST, list_of_tested_variants) { + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + + /* Inserted simplex: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + std::clog << "Check default insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 2.0 + // to 1.0 + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Inserted simplex: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + std::clog << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Copy original simplex tree + typeST st_copy = st; + + // Modify specific values for st to become like st_copy thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({0,1,6,7}), 0.8); + st.assign_filtration(st.find({0,1,6}), 0.9); + st.assign_filtration(st.find({0,6}), 0.6); + st.assign_filtration(st.find({3,4,5}), 1.2); + st.assign_filtration(st.find({3,4}), 1.1); + st.assign_filtration(st.find({4,5}), 1.99); + + std::clog << "Check the simplex_tree is rolled back in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_copy); + + // Other simplex tree + typeST st_other; + st_other.insert_simplex_and_subfaces({2, 1, 0}, 3.0); // This one is different from st + st_other.insert_simplex_and_subfaces({3, 0}, 2.0); + st_other.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + st_other.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Modify specific values for st to become like st_other thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({2}), 3.0); + // By modifying just the simplex {2} + // {0,1,2}, {1,2} and {0,2} will be modified + + std::clog << "Check the simplex_tree is repaired in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other); + + // Modify specific values for st still to be non-decreasing + st.assign_filtration(st.find({0,1,2}), 10.0); + st.assign_filtration(st.find({0,2}), 9.0); + st.assign_filtration(st.find({0,1,6,7}), 50.0); + st.assign_filtration(st.find({0,1,6}), 49.0); + st.assign_filtration(st.find({0,1,7}), 48.0); + // Other copy simplex tree + typeST st_other_copy = st; + + std::clog << "Check the simplex_tree is not modified in case of non-decreasing filtration values" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other_copy); + +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(make_filtration_non_decreasing_on_nan_values, typeST, list_of_tested_variants) { + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, std::numeric_limits<double>::quiet_NaN()); + st.insert_simplex_and_subfaces({3, 0}, std::numeric_limits<double>::quiet_NaN()); + st.insert_simplex_and_subfaces({3, 4, 5}, std::numeric_limits<double>::quiet_NaN()); + + /* Inserted simplex: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + std::clog << "SPECIFIC CASE:" << std::endl; + std::clog << "Insertion with NaN values does not ensure the filtration values are non decreasing" << std::endl; + st.make_filtration_non_decreasing(); + + std::clog << "Check all filtration values are NaN" << std::endl; + for (auto f_simplex : st.complex_simplex_range()) { + BOOST_CHECK(std::isnan(st.filtration(f_simplex))); + } + + st.assign_filtration(st.find({0}), 0.); + st.assign_filtration(st.find({1}), 0.); + st.assign_filtration(st.find({2}), 0.); + st.assign_filtration(st.find({3}), 0.); + st.assign_filtration(st.find({4}), 0.); + st.assign_filtration(st.find({5}), 0.); + + std::clog << "Check make_filtration_non_decreasing is modifying the simplicial complex" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + + std::clog << "Check all filtration values are now defined" << std::endl; + for (auto f_simplex : st.complex_simplex_range()) { + BOOST_CHECK(!std::isnan(st.filtration(f_simplex))); + } +} diff --git a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp index 97347992..36b8b3c6 100644 --- a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp @@ -32,8 +32,8 @@ 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; + std::clog << "********************************************************************" << std::endl; + std::clog << "REMOVE MAXIMAL SIMPLEX" << std::endl; Mini_stree st; @@ -66,21 +66,21 @@ BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { // 5 #ifdef GUDHI_DEBUG - std::cout << "Check exception throw in debug mode" << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "st.remove_maximal_simplex({2})" << std::endl; st.remove_maximal_simplex(st.find({2})); - std::cout << "st.remove_maximal_simplex({3})" << std::endl; + std::clog << "st.remove_maximal_simplex({3})" << std::endl; st.remove_maximal_simplex(st.find({0, 3})); BOOST_CHECK(st == st_pruned); @@ -102,39 +102,39 @@ BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { // 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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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() + std::clog << "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; + std::clog << "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; + std::clog << "********************************************************************" << std::endl; + std::clog << "DIMENSION ON REMOVE MAXIMAL SIMPLEX" << std::endl; Mini_stree st; @@ -148,80 +148,80 @@ BOOST_AUTO_TEST_CASE(auto_dimension_set) { BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); - std::cout << "st.remove_maximal_simplex({6, 7, 8, 10})" << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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::clog << "st.dimension()=" << st.dimension() << std::endl; - std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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::clog << "st.dimension()=" << st.dimension() << std::endl; - std::cout << "st.insert_simplex_and_subfaces({0, 1, 3, 4})" << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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::clog << "st.dimension()=" << st.dimension() << std::endl; - std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); @@ -229,7 +229,7 @@ BOOST_AUTO_TEST_CASE(auto_dimension_set) { // 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; + std::clog << "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); @@ -238,7 +238,7 @@ BOOST_AUTO_TEST_CASE(auto_dimension_set) { // 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; + std::clog << "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); @@ -246,27 +246,27 @@ BOOST_AUTO_TEST_CASE(auto_dimension_set) { // Reset with the correct value st.set_dimension(3); - std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "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; + std::clog << "********************************************************************" << std::endl; + std::clog << "PRUNE ABOVE FILTRATION" << std::endl; Stree st; @@ -321,15 +321,15 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { 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; + std::clog << "The complex contains " << st.num_simplices() << " simplices"; + std::clog << " - dimension " << st.dimension() << std::endl; + std::clog << "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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } // Check the pruned cases @@ -340,15 +340,15 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { 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; + std::clog << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices"; + std::clog << " - 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; + std::clog << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices"; + std::clog << " - dimension " << st.dimension() << std::endl; BOOST_CHECK(st == st_pruned); BOOST_CHECK(!simplex_is_changed); @@ -360,12 +360,12 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { 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; + std::clog << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices"; + std::clog << " - 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; + std::clog << "upper_bound_dimension=" << st.upper_bound_dimension() << std::endl; BOOST_CHECK(st.upper_bound_dimension() == -1); BOOST_CHECK(st == st_empty); @@ -380,8 +380,8 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { } BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { - std::cout << "********************************************************************" << std::endl; - std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "MINI PRUNE ABOVE FILTRATION" << std::endl; Mini_stree st; @@ -402,7 +402,7 @@ BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { st.initialize_filtration(); // Display the Simplex_tree - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::clog << "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 @@ -410,7 +410,7 @@ BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { 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; + std::clog << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl; BOOST_CHECK(!simplex_is_changed); BOOST_CHECK(st.num_simplices() == 27); @@ -418,7 +418,7 @@ BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { 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; + std::clog << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; BOOST_CHECK(!simplex_is_changed); BOOST_CHECK(st.num_simplices() == 27); @@ -427,11 +427,11 @@ BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { 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; + std::clog << "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; + std::clog << "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 58bfa8db..ebcc406c 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -17,6 +17,8 @@ #include <limits> #include <functional> // greater #include <tuple> // std::tie +#include <iterator> // for std::distance +#include <cstddef> // for std::size_t #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "simplex_tree" @@ -48,22 +50,22 @@ void test_empty_simplex_tree(typeST& tst) { template<class typeST> void test_iterators_on_empty_simplex_tree(typeST& tst) { - std::cout << "Iterator on vertices: " << std::endl; + std::clog << "Iterator on vertices: " << std::endl; for (auto vertex : tst.complex_vertex_range()) { - std::cout << "vertice:" << vertex << std::endl; + std::clog << "vertice:" << vertex << std::endl; BOOST_CHECK(false); // shall be empty } - std::cout << "Iterator on simplices: " << std::endl; + std::clog << "Iterator on simplices: " << std::endl; for (auto simplex : tst.complex_simplex_range()) { BOOST_CHECK(simplex != simplex); // shall be empty - to remove warning of non-used simplex } - std::cout + std::clog << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : tst.filtration_simplex_range()) { BOOST_CHECK(false); // shall be empty - std::cout << "test_iterators_on_empty_simplex_tree - filtration=" + std::clog << "test_iterators_on_empty_simplex_tree - filtration=" << tst.filtration(f_simplex) << std::endl; } } @@ -72,15 +74,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_when_empty, typeST, list_of_tested_va typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool; typedef std::vector<typename typeST::Vertex_handle> typeVectorVertex; - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; typeST st; test_empty_simplex_tree(st); test_iterators_on_empty_simplex_tree(st); // TEST OF EMPTY INSERTION - std::cout << "TEST OF EMPTY INSERTION" << std::endl; + std::clog << "TEST OF EMPTY INSERTION" << std::endl; typeVectorVertex simplexVectorEmpty; BOOST_CHECK(simplexVectorEmpty.empty() == true); typePairSimplexBool returnEmptyValue = st.insert_simplex(simplexVectorEmpty, 0.0); @@ -98,8 +100,8 @@ bool AreAlmostTheSame(float a, float b) { BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_from_file, typeST, list_of_tested_variants) { // TEST OF INSERTION - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl; typeST st; std::string inputFile("simplex_tree_for_unit_test.txt"); @@ -107,8 +109,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_from_file, typeST, list_of_tested_var simplex_tree_stream >> st; // Display the Simplex_tree - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - std::cout << " - dimension " << st.dimension() << std::endl; + std::clog << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::clog << " - dimension " << st.dimension() << std::endl; // Check BOOST_CHECK(st.num_simplices() == 143353); @@ -134,13 +136,13 @@ template<class typeST, class typeSimplex> void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int pos) { auto f_simplex = simplexTree.filtration_simplex_range().begin() + pos; - std::cout << "test_simplex_tree_contains - filtration=" << simplexTree.filtration(*f_simplex) << "||" << simplex.second << std::endl; + std::clog << "test_simplex_tree_contains - filtration=" << simplexTree.filtration(*f_simplex) << "||" << simplex.second << std::endl; BOOST_CHECK(AreAlmostTheSame(simplexTree.filtration(*f_simplex), simplex.second)); int simplexIndex = simplex.first.size() - 1; std::sort(simplex.first.begin(), simplex.first.end()); // if the simplex wasn't sorted, the next test could fail for (auto vertex : simplexTree.simplex_vertex_range(*f_simplex)) { - std::cout << "test_simplex_tree_contains - vertex=" << vertex << "||" << simplex.first.at(simplexIndex) << std::endl; + std::clog << "test_simplex_tree_contains - vertex=" << vertex << "||" << simplex.first.at(simplexIndex) << std::endl; BOOST_CHECK(vertex == simplex.first.at(simplexIndex)); BOOST_CHECK(simplexIndex >= 0); simplexIndex--; @@ -163,7 +165,7 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons if (vectorSize > dim_max + 1) { dim_max = vectorSize - 1; simplexTree.set_dimension(dim_max); - std::cout << " set_and_test_simplex_tree_dim_fil - dim_max=" << dim_max + std::clog << " set_and_test_simplex_tree_dim_fil - dim_max=" << dim_max << std::endl; } @@ -193,12 +195,12 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var dim_max = -1; // TEST OF INSERTION - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF INSERTION" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF INSERTION" << std::endl; typeST st; // ++ FIRST - std::cout << " - INSERT 0" << std::endl; + std::clog << " - INSERT 0" << std::endl; typeVectorVertex firstSimplexVector{0}; BOOST_CHECK(firstSimplexVector.size() == 1); typeSimplex firstSimplex = std::make_pair(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); @@ -209,7 +211,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 1); // ++ SECOND - std::cout << " - INSERT 1" << std::endl; + std::clog << " - INSERT 1" << std::endl; typeVectorVertex secondSimplexVector{1}; BOOST_CHECK(secondSimplexVector.size() == 1); typeSimplex secondSimplex = std::make_pair(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); @@ -220,7 +222,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 2); // ++ THIRD - std::cout << " - INSERT (0,1)" << std::endl; + std::clog << " - INSERT (0,1)" << std::endl; typeVectorVertex thirdSimplexVector{0, 1}; BOOST_CHECK(thirdSimplexVector.size() == 2); typeSimplex thirdSimplex = std::make_pair(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); @@ -231,7 +233,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 2); // Not incremented !! // ++ FOURTH - std::cout << " - INSERT 2" << std::endl; + std::clog << " - INSERT 2" << std::endl; typeVectorVertex fourthSimplexVector{2}; BOOST_CHECK(fourthSimplexVector.size() == 1); typeSimplex fourthSimplex = std::make_pair(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); @@ -242,7 +244,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 3); // ++ FIFTH - std::cout << " - INSERT (2,0)" << std::endl; + std::clog << " - INSERT (2,0)" << std::endl; typeVectorVertex fifthSimplexVector{2, 0}; BOOST_CHECK(fifthSimplexVector.size() == 2); typeSimplex fifthSimplex = std::make_pair(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); @@ -253,7 +255,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SIXTH - std::cout << " - INSERT (2,1)" << std::endl; + std::clog << " - INSERT (2,1)" << std::endl; typeVectorVertex sixthSimplexVector{2, 1}; BOOST_CHECK(sixthSimplexVector.size() == 2); typeSimplex sixthSimplex = std::make_pair(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); @@ -264,7 +266,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SEVENTH - std::cout << " - INSERT (2,1,0)" << std::endl; + std::clog << " - INSERT (2,1,0)" << std::endl; typeVectorVertex seventhSimplexVector{2, 1, 0}; BOOST_CHECK(seventhSimplexVector.size() == 3); typeSimplex seventhSimplex = std::make_pair(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); @@ -275,7 +277,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ EIGHTH - std::cout << " - INSERT 3" << std::endl; + std::clog << " - INSERT 3" << std::endl; typeVectorVertex eighthSimplexVector{3}; BOOST_CHECK(eighthSimplexVector.size() == 1); typeSimplex eighthSimplex = std::make_pair(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); @@ -285,8 +287,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 4); - // ++ NINETH - std::cout << " - INSERT (3,0)" << std::endl; + // ++ NINTH + std::clog << " - INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector{3, 0}; BOOST_CHECK(ninethSimplexVector.size() == 2); typeSimplex ninethSimplex = std::make_pair(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); @@ -297,7 +299,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! // ++ TENTH - std::cout << " - INSERT 0 (already inserted)" << std::endl; + std::clog << " - INSERT 0 (already inserted)" << std::endl; typeVectorVertex tenthSimplexVector{0}; BOOST_CHECK(tenthSimplexVector.size() == 1); // With a different filtration value @@ -308,12 +310,12 @@ 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; + std::clog << "st.num_vertices()=" << st.num_vertices() << std::endl; BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! BOOST_CHECK(st.dimension() == dim_max); // ++ ELEVENTH - std::cout << " - INSERT (2,1,0) (already inserted)" << std::endl; + std::clog << " - INSERT (2,1,0) (already inserted)" << std::endl; typeVectorVertex eleventhSimplexVector{2, 1, 0}; BOOST_CHECK(eleventhSimplexVector.size() == 3); typeSimplex eleventhSimplex = std::make_pair(eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); @@ -343,35 +345,35 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var // [0.2] 3 0 // [0.3] 2 1 0 // !! Be careful, simplex are sorted by filtration value on insertion !! - std::cout << "simplex_tree_insertion - first - 0" << std::endl; + std::clog << "simplex_tree_insertion - first - 0" << std::endl; test_simplex_tree_contains(st, firstSimplex, 0); // (0) -> 0 - std::cout << "simplex_tree_insertion - second - 1" << std::endl; + std::clog << "simplex_tree_insertion - second - 1" << std::endl; test_simplex_tree_contains(st, secondSimplex, 1); // (1) -> 1 - std::cout << "simplex_tree_insertion - third - 4" << std::endl; + std::clog << "simplex_tree_insertion - third - 4" << std::endl; test_simplex_tree_contains(st, thirdSimplex, 4); // (0,1) -> 4 - std::cout << "simplex_tree_insertion - fourth - 2" << std::endl; + std::clog << "simplex_tree_insertion - fourth - 2" << std::endl; test_simplex_tree_contains(st, fourthSimplex, 2); // (2) -> 2 - std::cout << "simplex_tree_insertion - fifth - 5" << std::endl; + std::clog << "simplex_tree_insertion - fifth - 5" << std::endl; test_simplex_tree_contains(st, fifthSimplex, 5); // (2,0) -> 5 - std::cout << "simplex_tree_insertion - sixth - 6" << std::endl; + std::clog << "simplex_tree_insertion - sixth - 6" << std::endl; test_simplex_tree_contains(st, sixthSimplex, 6); //(2,1) -> 6 - std::cout << "simplex_tree_insertion - seventh - 8" << std::endl; + std::clog << "simplex_tree_insertion - seventh - 8" << std::endl; test_simplex_tree_contains(st, seventhSimplex, 8); // (2,1,0) -> 8 - std::cout << "simplex_tree_insertion - eighth - 3" << std::endl; + std::clog << "simplex_tree_insertion - eighth - 3" << std::endl; test_simplex_tree_contains(st, eighthSimplex, 3); // (3) -> 3 - std::cout << "simplex_tree_insertion - nineth - 7" << std::endl; + std::clog << "simplex_tree_insertion - ninth - 7" << std::endl; test_simplex_tree_contains(st, ninethSimplex, 7); // (3,0) -> 7 // Display the Simplex_tree - Can not be done in the middle of 2 inserts - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - std::cout << " - dimension " << st.dimension() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::clog << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::clog << " - dimension " << st.dimension() << std::endl; + std::clog << 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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } } @@ -380,14 +382,14 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool; typedef std::vector<typename typeST::Vertex_handle> typeVectorVertex; typedef std::pair<typeVectorVertex, typename typeST::Filtration_value> typeSimplex; - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF RECURSIVE INSERTION" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF RECURSIVE INSERTION" << std::endl; typeST st; typePairSimplexBool returnValue; int position = 0; // ++ FIRST - std::cout << " - INSERT (2,1,0)" << std::endl; + std::clog << " - INSERT (2,1,0)" << std::endl; typeVectorVertex SimplexVector1{2, 1, 0}; BOOST_CHECK(SimplexVector1.size() == 3); returnValue = st.insert_simplex_and_subfaces(SimplexVector1); @@ -400,13 +402,13 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o std::sort(SimplexVector1.begin(), SimplexVector1.end(), std::greater<typename typeST::Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle - std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector1[position] << std::endl; + std::clog << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector1[position] << std::endl; BOOST_CHECK(vertex == SimplexVector1[position]); position++; } // ++ SECOND - std::cout << " - INSERT 3" << std::endl; + std::clog << " - INSERT 3" << std::endl; typeVectorVertex SimplexVector2{3}; BOOST_CHECK(SimplexVector2.size() == 1); returnValue = st.insert_simplex_and_subfaces(SimplexVector2); @@ -419,13 +421,13 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o std::sort(SimplexVector2.begin(), SimplexVector2.end(), std::greater<typename typeST::Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle - std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector2[position] << std::endl; + std::clog << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector2[position] << std::endl; BOOST_CHECK(vertex == SimplexVector2[position]); position++; } // ++ THIRD - std::cout << " - INSERT (0,3)" << std::endl; + std::clog << " - INSERT (0,3)" << std::endl; typeVectorVertex SimplexVector3{3, 0}; BOOST_CHECK(SimplexVector3.size() == 2); returnValue = st.insert_simplex_and_subfaces(SimplexVector3); @@ -438,13 +440,13 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o std::sort(SimplexVector3.begin(), SimplexVector3.end(), std::greater<typename typeST::Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle - std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector3[position] << std::endl; + std::clog << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector3[position] << std::endl; BOOST_CHECK(vertex == SimplexVector3[position]); position++; } // ++ FOURTH - std::cout << " - INSERT (1,0) (already inserted)" << std::endl; + std::clog << " - INSERT (1,0) (already inserted)" << std::endl; typeVectorVertex SimplexVector4{1, 0}; BOOST_CHECK(SimplexVector4.size() == 2); returnValue = st.insert_simplex_and_subfaces(SimplexVector4); @@ -455,7 +457,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o BOOST_CHECK(false == returnValue.second); // ++ FIFTH - std::cout << " - INSERT (3,4,5)" << std::endl; + std::clog << " - INSERT (3,4,5)" << std::endl; typeVectorVertex SimplexVector5{3, 4, 5}; BOOST_CHECK(SimplexVector5.size() == 3); returnValue = st.insert_simplex_and_subfaces(SimplexVector5); @@ -468,13 +470,13 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o std::sort(SimplexVector5.begin(), SimplexVector5.end(), std::greater<typename typeST::Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle - std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector5[position] << std::endl; + std::clog << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector5[position] << std::endl; BOOST_CHECK(vertex == SimplexVector5[position]); position++; } // ++ SIXTH - std::cout << " - INSERT (0,1,6,7)" << std::endl; + std::clog << " - INSERT (0,1,6,7)" << std::endl; typeVectorVertex SimplexVector6{0, 1, 6, 7}; BOOST_CHECK(SimplexVector6.size() == 4); returnValue = st.insert_simplex_and_subfaces(SimplexVector6); @@ -487,7 +489,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o std::sort(SimplexVector6.begin(), SimplexVector6.end(), std::greater<typename typeST::Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle - std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector6[position] << std::endl; + std::clog << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector6[position] << std::endl; BOOST_CHECK(vertex == SimplexVector6[position]); position++; } @@ -525,63 +527,63 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o // ------------------------------------------------------------------------------------------------------------------ typeVectorVertex simpleSimplexVector{1}; typename typeST::Simplex_handle simplexFound = st.find(simpleSimplexVector); - std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); typeVectorVertex unknownSimplexVector{15}; simplexFound = st.find(unknownSimplexVector); - std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; // Check it is NOT found BOOST_CHECK(simplexFound == st.null_simplex()); simplexFound = st.find(SimplexVector6); - std::cout << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); typeVectorVertex otherSimplexVector{1, 15}; simplexFound = st.find(otherSimplexVector); - std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; // Check it is NOT found BOOST_CHECK(simplexFound == st.null_simplex()); typeVectorVertex invSimplexVector{1, 2, 0}; simplexFound = st.find(invSimplexVector); - std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; + std::clog << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; + std::clog << "***+ YES IT IS!\n"; else - std::cout << "***- NO IT ISN'T\n"; + std::clog << "***- NO IT ISN'T\n"; // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); // Display the Simplex_tree - Can not be done in the middle of 2 inserts - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - std::cout << " - dimension " << st.dimension() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::clog << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::clog << " - dimension " << st.dimension() << std::endl; + std::clog << 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) << "] "; + std::clog << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { - std::cout << (int) vertex << " "; + std::clog << (int) vertex << " "; } - std::cout << std::endl; + std::clog << std::endl; } } @@ -595,17 +597,17 @@ void test_cofaces(typeST& st, const std::vector<Vertex_handle>& expected, int di for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) { typename typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { - std::cout << "(" << *vertex << ")"; + std::clog << "(" << *vertex << ")"; } - std::cout << std::endl; + std::clog << std::endl; BOOST_CHECK(std::find(res.begin(), res.end(), *simplex) != res.end()); } } BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_variants) { typedef std::vector<typename typeST::Vertex_handle> typeVectorVertex; - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST COFACE ALGORITHM" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST COFACE ALGORITHM" << std::endl; typeST st; typeVectorVertex SimplexVector{2, 1, 0}; @@ -631,7 +633,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var std::vector<typename typeST::Vertex_handle> simplex_result; std::vector<typename typeST::Simplex_handle> result; - std::cout << "First test - Star of (3):" << std::endl; + std::clog << "First test - Star of (3):" << std::endl; simplex_result = {3}; result.push_back(st.find(simplex_result)); @@ -656,7 +658,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var vertex.push_back(1); vertex.push_back(7); - std::cout << "Second test - Star of (1,7): " << std::endl; + std::clog << "Second test - Star of (1,7): " << std::endl; simplex_result = {7, 1}; result.push_back(st.find(simplex_result)); @@ -673,7 +675,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var test_cofaces(st, vertex, 0, result); result.clear(); - std::cout << "Third test - 2-dimension Cofaces of simplex(1,7) : " << std::endl; + std::clog << "Third test - 2-dimension Cofaces of simplex(1,7) : " << std::endl; simplex_result = {7, 1, 0}; result.push_back(st.find(simplex_result)); @@ -684,15 +686,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var test_cofaces(st, vertex, 1, result); result.clear(); - std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension) :" << std::endl; + std::clog << "Cofaces with a codimension too high (codimension + vetices > tree.dimension) :" << std::endl; test_cofaces(st, vertex, 5, result); - //std::cout << "Cofaces with an empty codimension" << std::endl; + //std::clog << "Cofaces with an empty codimension" << std::endl; //test_cofaces(st, vertex, -1, result); - // std::cout << "Cofaces in an empty simplex tree" << std::endl; + // std::clog << "Cofaces in an empty simplex tree" << std::endl; // typeST empty_tree; // test_cofaces(empty_tree, vertex, 1, result); - //std::cout << "Cofaces of an empty simplex" << std::endl; + //std::clog << "Cofaces of an empty simplex" << std::endl; //vertex.clear(); // test_cofaces(st, vertex, 1, result); @@ -700,8 +702,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_variants) { typedef std::vector<typename typeST::Vertex_handle> typeVectorVertex; - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST COPY MOVE CONSTRUCTORS" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST COPY MOVE CONSTRUCTORS" << std::endl; typeST st; typeVectorVertex SimplexVector{2, 1, 0}; @@ -725,11 +727,11 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_ /* o */ /* 5 */ - std::cout << "Printing st - address = " << &st << std::endl; + std::clog << "Printing st - address = " << &st << std::endl; // Copy constructor typeST st_copy = st; - std::cout << "Printing a copy of st - address = " << &st_copy << std::endl; + std::clog << "Printing a copy of st - address = " << &st_copy << std::endl; // Check the data are the same BOOST_CHECK(st == st_copy); @@ -738,7 +740,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_ // Move constructor typeST st_move = std::move(st); - std::cout << "Printing a move of st - address = " << &st_move << std::endl; + std::clog << "Printing a move of st - address = " << &st_move << std::endl; // Check the data are the same BOOST_CHECK(st_move == st_copy); @@ -753,7 +755,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_ BOOST_CHECK(st.num_simplices() == 0); BOOST_CHECK(st.num_vertices() == (size_t)0); - std::cout << "Printing st once again- address = " << &st << std::endl; + std::clog << "Printing st once again- address = " << &st << std::endl; } template<class typeST> @@ -768,22 +770,22 @@ void test_simplex_is_vertex(typeST& st, typename typeST::Simplex_handle sh, type BOOST_AUTO_TEST_CASE(non_contiguous) { typedef Simplex_tree<> typeST; typedef typeST::Simplex_handle Simplex_handle; - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST NON-CONTIGUOUS VERTICES" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST NON-CONTIGUOUS VERTICES" << std::endl; typeST st; typeST::Vertex_handle e[] = {3,-7}; - std::cout << "Insert" << std::endl; + std::clog << "Insert" << std::endl; st.insert_simplex_and_subfaces(e); BOOST_CHECK(st.num_vertices() == 2); BOOST_CHECK(st.num_simplices() == 3); - std::cout << "Find" << std::endl; + std::clog << "Find" << std::endl; Simplex_handle sh = st.find(e); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "Endpoints" << std::endl; + std::clog << "Endpoints" << std::endl; auto p = st.endpoints(sh); test_simplex_is_vertex(st, p.first, 3); test_simplex_is_vertex(st, p.second, -7); - std::cout << "Boundary" << std::endl; + std::clog << "Boundary" << std::endl; auto&& b = st.boundary_simplex_range(sh); auto i = std::begin(b); test_simplex_is_vertex(st, *i, -7); @@ -791,90 +793,6 @@ BOOST_AUTO_TEST_CASE(non_contiguous) { BOOST_CHECK(++i == std::end(b)); } -BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { - std::cout << "********************************************************************" << std::endl; - std::cout << "MAKE FILTRATION NON DECREASING" << std::endl; - typedef Simplex_tree<> typeST; - typeST st; - - st.insert_simplex_and_subfaces({2, 1, 0}, 2.0); - st.insert_simplex_and_subfaces({3, 0}, 2.0); - st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - - /* Inserted simplex: */ - /* 1 */ - /* o */ - /* /X\ */ - /* o---o---o---o */ - /* 2 0 3\X/4 */ - /* o */ - /* 5 */ - - std::cout << "Check default insertion ensures the filtration values are non decreasing" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - - // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 2.0 - // to 1.0 - st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); - - // Inserted simplex: - // 1 6 - // o---o - // /X\7/ - // o---o---o---o - // 2 0 3\X/4 - // o - // 5 - - std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - - // Copy original simplex tree - typeST st_copy = st; - - // Modify specific values for st to become like st_copy thanks to make_filtration_non_decreasing - st.assign_filtration(st.find({0,1,6,7}), 0.8); - st.assign_filtration(st.find({0,1,6}), 0.9); - st.assign_filtration(st.find({0,6}), 0.6); - st.assign_filtration(st.find({3,4,5}), 1.2); - st.assign_filtration(st.find({3,4}), 1.1); - st.assign_filtration(st.find({4,5}), 1.99); - - std::cout << "Check the simplex_tree is rolled back in case of decreasing filtration values" << std::endl; - BOOST_CHECK(st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_copy); - - // Other simplex tree - typeST st_other; - st_other.insert_simplex_and_subfaces({2, 1, 0}, 3.0); // This one is different from st - st_other.insert_simplex_and_subfaces({3, 0}, 2.0); - st_other.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - st_other.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); - - // Modify specific values for st to become like st_other thanks to make_filtration_non_decreasing - st.assign_filtration(st.find({2}), 3.0); - // By modifying just the simplex {2} - // {0,1,2}, {1,2} and {0,2} will be modified - - std::cout << "Check the simplex_tree is repaired in case of decreasing filtration values" << std::endl; - BOOST_CHECK(st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_other); - - // Modify specific values for st still to be non-decreasing - st.assign_filtration(st.find({0,1,2}), 10.0); - st.assign_filtration(st.find({0,2}), 9.0); - st.assign_filtration(st.find({0,1,6,7}), 50.0); - st.assign_filtration(st.find({0,1,6}), 49.0); - st.assign_filtration(st.find({0,1,7}), 48.0); - // Other copy simplex tree - typeST st_other_copy = st; - - std::cout << "Check the simplex_tree is not modified in case of non-decreasing filtration values" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_other_copy); - -} - typedef boost::mpl::list<boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, boost::property<vertex_filtration_t, double>, @@ -896,8 +814,8 @@ typedef boost::mpl::list<boost::adjacency_list<boost::setS, boost::vecS, boost:: boost::property<edge_filtration_t, double>>> list_of_graph_variants; BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_variants) { - std::cout << "********************************************************************" << std::endl; - std::cout << "INSERT GRAPH" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "INSERT GRAPH" << std::endl; Graph g(3); // filtration value 0 everywhere @@ -924,18 +842,18 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_va st2.insert_graph(g); BOOST_CHECK(st2.num_simplices() == 6); - std::cout << "st1 is" << std::endl; - std::cout << st1 << std::endl; + std::clog << "st1 is" << std::endl; + std::clog << st1 << std::endl; - std::cout << "st2 is" << std::endl; - std::cout << st2 << std::endl; + std::clog << "st2 is" << std::endl; + std::clog << st2 << std::endl; BOOST_CHECK(st1 == st2); } BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested_variants) { - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST INSERT DUPLICATED VERTICES" << std::endl; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST INSERT DUPLICATED VERTICES" << std::endl; typeST st; typename typeST::Simplex_handle sh; @@ -943,25 +861,25 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested std::tie(sh, success) = st.insert_simplex_and_subfaces({1}); BOOST_CHECK(success); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl; + std::clog << "st.dimension(sh)= " << st.dimension(sh) << std::endl; BOOST_CHECK(st.dimension(sh) == 0); std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 2}); BOOST_CHECK(success); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl; + std::clog << "st.dimension(sh)= " << st.dimension(sh) << std::endl; BOOST_CHECK(st.dimension(sh) == 0); std::tie(sh, success) = st.insert_simplex_and_subfaces({3, 3, 3}); BOOST_CHECK(success); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl; + std::clog << "st.dimension(sh)= " << st.dimension(sh) << std::endl; BOOST_CHECK(st.dimension(sh) == 0); std::tie(sh, success) = st.insert_simplex_and_subfaces({4, 4, 4, 4}); BOOST_CHECK(success); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl; + std::clog << "st.dimension(sh)= " << st.dimension(sh) << std::endl; BOOST_CHECK(st.dimension(sh) == 0); - std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() + std::clog << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() << " - num_simplices = " << st.num_simplices() << std::endl; BOOST_CHECK(st.dimension() == 0); BOOST_CHECK(st.num_simplices() == st.num_vertices()); @@ -969,10 +887,10 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 1, 1, 2}); BOOST_CHECK(success); BOOST_CHECK(sh != st.null_simplex()); - std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl; + std::clog << "st.dimension(sh)= " << st.dimension(sh) << std::endl; BOOST_CHECK(st.dimension(sh) == 1); - std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() + std::clog << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() << " - num_simplices = " << st.num_simplices() << std::endl; BOOST_CHECK(st.dimension() == 1); BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1); @@ -982,9 +900,155 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested BOOST_CHECK(!success); BOOST_CHECK(sh == st.null_simplex()); - std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() + std::clog << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices() << " - num_simplices = " << st.num_simplices() << std::endl; BOOST_CHECK(st.dimension() == 1); BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1); +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(generators, typeST, list_of_tested_variants) { + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST FIND GENERATORS" << std::endl; + { + typeST st; + st.insert_simplex_and_subfaces({0,1,2,3,4,5,6},0); + st.assign_filtration(st.find({0,2,4}), 10); + st.assign_filtration(st.find({1,5}), 20); + st.assign_filtration(st.find({1,2,4}), 30); + st.assign_filtration(st.find({3}), 5); + st.make_filtration_non_decreasing(); + BOOST_CHECK(st.filtration(st.find({1,2}))==0); + BOOST_CHECK(st.filtration(st.find({0,1,2,3,4}))==30); + BOOST_CHECK(st.minimal_simplex_with_same_filtration(st.find({0,1,2,3,4,5}))==st.find({1,2,4})); + BOOST_CHECK(st.minimal_simplex_with_same_filtration(st.find({0,2,3}))==st.find({3})); + auto s=st.minimal_simplex_with_same_filtration(st.find({0,2,6})); + BOOST_CHECK(s==st.find({0})||s==st.find({2})||s==st.find({6})); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({2}))==2); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({1,5}))==st.null_vertex()); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({5,6}))>=5); + } + { + typeST st; + st.insert_simplex_and_subfaces({0,1}, 8); + st.insert_simplex_and_subfaces({0,2}, 10); + st.insert_simplex_and_subfaces({3,4}, 6); + st.insert_simplex_and_subfaces({1,2}, 5); + st.insert_simplex_and_subfaces({1,5}, 4); + st.insert_simplex_and_subfaces({0,5}, 3); + st.insert_simplex_and_subfaces({2,5}, 2); + st.insert_simplex_and_subfaces({1,3}, 9); + st.expansion(50); + BOOST_CHECK(st.edge_with_same_filtration(st.find({0,1,2,5}))==st.find({0,2})); + BOOST_CHECK(st.edge_with_same_filtration(st.find({1,5}))==st.find({1,5})); + } +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_reset_filtration, typeST, list_of_tested_variants) { + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST RESET FILTRATION" << std::endl; + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 3.); + st.insert_simplex_and_subfaces({3, 0}, 2.); + st.insert_simplex_and_subfaces({3, 4, 5}, 3.); + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.); + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + for (auto f_simplex : st.skeleton_simplex_range(3)) { + std::clog << "vertex = ("; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::clog << vertex << ","; + } + std::clog << ") - filtration = " << st.filtration(f_simplex); + std::clog << " - dimension = " << st.dimension(f_simplex) << std::endl; + // Guaranteed by construction + BOOST_CHECK(st.filtration(f_simplex) >= 2.); + } + + // dimension until 5 even if simplex tree is of dimension 3 to test the limits + for(int dimension = 5; dimension >= 0; dimension --) { + std::clog << "### reset_filtration - dimension = " << dimension << "\n"; + st.reset_filtration(0., dimension); + for (auto f_simplex : st.skeleton_simplex_range(3)) { + std::clog << "vertex = ("; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::clog << vertex << ","; + } + std::clog << ") - filtration = " << st.filtration(f_simplex); + std::clog << " - dimension = " << st.dimension(f_simplex) << std::endl; + if (st.dimension(f_simplex) < dimension) + BOOST_CHECK(st.filtration(f_simplex) >= 2.); + else + BOOST_CHECK(st.filtration(f_simplex) == 0.); + } + } + +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_boundaries_and_opposite_vertex_iterator, typeST, list_of_tested_variants) { + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF BOUNDARIES AND OPPOSITE VERTEX ITERATORS" << std::endl; + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 3.); + st.insert_simplex_and_subfaces({3, 0}, 2.); + st.insert_simplex_and_subfaces({3, 4, 5}, 3.); + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + using Simplex = std::vector<typename typeST::Vertex_handle>; + // simplices must be kept sorted by vertex number for std::vector to use operator== - cf. last BOOST_CHECK + std::vector<Simplex> simplices = {{0, 1, 2}, {0, 3}, {0, 1, 6, 7}, {3, 4, 5}, {3, 5}, {2}}; + for (auto simplex : simplices) { + Simplex opposite_vertices; + for(auto boundary_and_opposite_vertex : st.boundary_opposite_vertex_simplex_range(st.find(simplex))) { + Simplex output; + for (auto vertex : st.simplex_vertex_range(boundary_and_opposite_vertex.first)) { + std::clog << vertex << " "; + output.emplace_back(vertex); + } + std::clog << " - opposite vertex = " << boundary_and_opposite_vertex.second << std::endl; + // Check that boundary simplex + opposite vertex = simplex given as input + output.emplace_back(boundary_and_opposite_vertex.second); + std::sort(output.begin(), output.end()); + BOOST_CHECK(simplex == output); + opposite_vertices.emplace_back(boundary_and_opposite_vertex.second); + } + // Check that the list of all opposite vertices = simplex given as input + // no opposite vertices if simplex given as input is of dimension 1 + std::sort(opposite_vertices.begin(), opposite_vertices.end()); + if (simplex.size() > 1) + BOOST_CHECK(simplex == opposite_vertices); + else + BOOST_CHECK(opposite_vertices.size() == 0); + } +} + +BOOST_AUTO_TEST_CASE(batch_vertices) { + typedef Simplex_tree<> typeST; + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST BATCH VERTEX INSERTION" << std::endl; + typeST st; + st.insert_simplex_and_subfaces({3}, 1.5); + std::vector verts { 2, 3, 5, 6 }; + st.insert_batch_vertices(verts); + BOOST_CHECK(st.num_vertices() == 4); + BOOST_CHECK(st.num_simplices() == 4); + BOOST_CHECK(st.filtration(st.find({2})) == 0.); + BOOST_CHECK(st.filtration(st.find({3})) == 1.5); } |