diff options
Diffstat (limited to 'src/Simplex_tree')
14 files changed, 446 insertions, 185 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 73b2c6f9..81d352fc 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -29,7 +29,7 @@ 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() 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/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp index df52bf43..eef8b665 100644 --- a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp +++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp @@ -42,7 +42,7 @@ int main(int argc, char* const argv[]) { std::clog << vertex << ", "; } std::clog << "] ( " << stree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // 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::clog << " + 1. ) = " << result << std::endl; diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp index e8bec596..965711da 100644 --- a/src/Simplex_tree/example/simple_simplex_tree.cpp +++ b/src/Simplex_tree/example/simple_simplex_tree.cpp @@ -129,7 +129,7 @@ int main(int argc, char* const argv[]) { std::clog << " - 3 NOT INSERTED" << std::endl; } - // ++ NINETH + // ++ NINTH std::clog << " * INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector = {3, 0}; returnValue = simplexTree.insert_simplex(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 85d6c3b0..4177a0b8 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -24,6 +24,8 @@ #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 @@ -42,6 +44,10 @@ 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. @@ -97,8 +103,7 @@ 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; @@ -187,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. */ @@ -296,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 * @{ */ @@ -676,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 @@ -691,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))) { @@ -717,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; } @@ -760,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 @@ -942,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); @@ -1060,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. @@ -1081,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) { @@ -1090,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 @@ -1123,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. * @@ -1280,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(); @@ -1302,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 { @@ -1312,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 */ @@ -1465,7 +1509,7 @@ class Simplex_tree { 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); } @@ -1569,7 +1613,7 @@ class Simplex_tree { Simplex_tree st_copy = *this; // Add point for coning the simplicial complex - this->insert_simplex({maxvert}, -3); + this->insert_simplex_raw({maxvert}, -3); // For each simplex std::vector<Vertex_handle> vr; @@ -1775,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 ee64a277..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,19 +15,19 @@ #include <gudhi/Debug_utils.h> #include <boost/iterator/iterator_facade.hpp> -#include <boost/version.hpp> #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.*/ @@ -72,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.*/ @@ -124,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_; } @@ -179,8 +180,118 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< 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 cf2b0153..25b562e0 100644 --- a/src/Simplex_tree/test/CMakeLists.txt +++ b/src/Simplex_tree/test/CMakeLists.txt @@ -34,3 +34,9 @@ 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 229ae46f..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 @@ -98,8 +98,16 @@ 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); 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 881a06ae..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.); -bool AreAlmostTheSame(float a, float b) { - return std::fabs(a - b) < std::numeric_limits<float>::epsilon(); + 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; + } + + 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; @@ -64,7 +93,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li std::clog << vertex << ", "; } std::clog << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // 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::clog << " + 1. ) = " << result << std::endl; @@ -72,9 +101,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li return result; }); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_with_blockers_3\n"; - std::clog << "********************************************************************\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"; @@ -89,15 +115,23 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li 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; @@ -126,7 +160,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li std::clog << vertex << ", "; } std::clog << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // 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::clog << " + 1. ) = " << result << std::endl; @@ -134,9 +168,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li return result; }); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_with_blockers_2\n"; - std::clog << "********************************************************************\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"; @@ -151,14 +182,22 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li 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; @@ -175,10 +214,66 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_var simplex_tree.insert_simplex({5, 6}, 10.); simplex_tree.insert_simplex({6}, 10.); - simplex_tree.expansion(3); + 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; + + 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(3); 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"; @@ -192,16 +287,25 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_var 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,9 +324,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_v simplex_tree.expansion(2); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_2\n"; - std::clog << "********************************************************************\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"; @@ -236,10 +337,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_v 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_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index bdd41d34..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" @@ -285,7 +287,7 @@ 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 + // ++ NINTH std::clog << " - INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector{3, 0}; BOOST_CHECK(ninethSimplexVector.size() == 2); @@ -359,7 +361,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var test_simplex_tree_contains(st, seventhSimplex, 8); // (2,1,0) -> 8 std::clog << "simplex_tree_insertion - eighth - 3" << std::endl; test_simplex_tree_contains(st, eighthSimplex, 3); // (3) -> 3 - std::clog << "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 @@ -991,3 +993,62 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_reset_filtration, typeST, list_of_tes } +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); +} |