diff options
Diffstat (limited to 'src')
15 files changed, 718 insertions, 555 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 7b30f77a..f0af1a6d 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -47,6 +47,7 @@ else() add_subdirectory(example/Hasse_complex) add_subdirectory(example/Alpha_complex) add_subdirectory(example/Bottleneck) + add_subdirectory(example/Bottleneck) # GudhUI add_subdirectory(GudhUI) diff --git a/src/Contraction/example/Garland_heckbert/Error_quadric.h b/src/Contraction/example/Garland_heckbert/Error_quadric.h index 725a3a56..72134c9d 100644 --- a/src/Contraction/example/Garland_heckbert/Error_quadric.h +++ b/src/Contraction/example/Garland_heckbert/Error_quadric.h @@ -122,7 +122,7 @@ public : * Return the point such that it minimizes the gradient of the quadric.
* Det must be passed with the determinant value of the gradient (should be non zero).
*/
- inline Point solve_linear_gradient(double det = grad_determinant()) const{
+ inline Point solve_linear_gradient(double det) const{
return Point({
(-coeff[1]*coeff[5]*coeff[8]+coeff[1]*coeff[7]*coeff[6]+coeff[2]*coeff[8]*coeff[4]-coeff[2]*coeff[5]*coeff[6]-coeff[3]*coeff[4]*coeff[7]+coeff[3]*coeff[5]*coeff[5])/ det,
(coeff[0]*coeff[5]*coeff[8]-coeff[0]*coeff[7]*coeff[6]-coeff[5]*coeff[2]*coeff[3]-coeff[1]*coeff[2]*coeff[8]+coeff[6]*coeff[2]*coeff[2]+coeff[1]*coeff[3]*coeff[7])/det,
diff --git a/src/GudhUI/CMakeLists.txt b/src/GudhUI/CMakeLists.txt index ddbae969..9348868a 100644 --- a/src/GudhUI/CMakeLists.txt +++ b/src/GudhUI/CMakeLists.txt @@ -5,6 +5,7 @@ find_package(CGAL COMPONENTS Qt4) find_package(Qt4) find_package(QGLViewer) find_package(OpenGL) + message("CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS}") message("CMAKE_CXX_FLAGS_DEBUG ${CMAKE_CXX_FLAGS_DEBUG}") message("CMAKE_CXX_FLAGS_RELEASE ${CMAKE_CXX_FLAGS_RELEASE}") @@ -66,5 +67,5 @@ if ( CGAL_FOUND AND QT4_FOUND AND OPENGL_FOUND AND QGLVIEWER_FOUND ) target_link_libraries( GudhUI ${OPENGL_gl_LIBRARY} ${OPENGL_glu_LIBRARY} ) else() - message(STATUS "NOTICE: This demo requires CGAL, the QGLViewer, OpenGL and Qt4, and will not be compiled.") + message(STATUS "NOTICE: GudhUI requires CGAL, the QGLViewer, OpenGL and Qt4, and will not be compiled.") endif() diff --git a/src/GudhUI/model/Model.h b/src/GudhUI/model/Model.h index 87545989..17a7d278 100644 --- a/src/GudhUI/model/Model.h +++ b/src/GudhUI/model/Model.h @@ -315,7 +315,8 @@ private: void run_chomp(){ save_complex_in_file_for_chomp(); std::cout << "Call CHOMP library\n"; - system("utils/homsimpl chomp.sim"); + int returnValue = system("utils/homsimpl chomp.sim"); + std::cout << "CHOMP returns" << returnValue << std::endl; } void save_complex_in_file_for_chomp(){ diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index b0d68f09..8bd265d8 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -37,6 +37,7 @@ #include <list> #include <vector> #include <set> +#include <fstream> // std::ofstream namespace Gudhi { diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 5239c859..247630cc 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -20,8 +20,8 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ -#define SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ +#ifndef SIMPLEX_TREE_H_ +#define SIMPLEX_TREE_H_ #include <gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h> #include <gudhi/Simplex_tree/Simplex_tree_siblings.h> @@ -35,6 +35,7 @@ #include <algorithm> #include <utility> #include <vector> +#include <functional> // for greater<> namespace Gudhi { /** \defgroup simplex_tree Filtered Complexes @@ -83,9 +84,8 @@ namespace Gudhi { * */ template<typename IndexingTag = linear_indexing_tag, -typename FiltrationValue = double, typename SimplexKey = int // must be a signed integer type -, typename VertexHandle = int // must be a signed integer type, int convertible to it -// , bool ContiguousVertexHandles = true //true is Vertex_handles are exactly the set [0;n) +typename FiltrationValue = double, typename SimplexKey = int // must be a signed integer type +, typename VertexHandle = int // must be a signed integer type, int convertible to it > class Simplex_tree { public: @@ -121,7 +121,7 @@ class Simplex_tree { public: /** \brief Handle type to a simplex contained in the simplicial complex represented - * byt he simplex tree. */ + * by the simplex tree. */ typedef typename Dictionary::iterator Simplex_handle; private: @@ -155,6 +155,8 @@ class Simplex_tree { typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Simplex_vertex_iterator; /** \brief Range over the vertices of a simplex. */ typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range; + /** \brief Range over the cofaces of a simplex. */ + typedef std::vector<Simplex_handle> Cofaces_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -187,7 +189,6 @@ class Simplex_tree { * @{ */ /** \brief Returns a range over the vertices of the simplicial complex. - * * The order is increasing according to < on Vertex_handles.*/ Complex_vertex_range complex_vertex_range() { return Complex_vertex_range( @@ -252,6 +253,7 @@ class Simplex_tree { * 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 return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -299,7 +301,7 @@ class Simplex_tree { } /** @} */ // end constructor/destructor private: - /** Recursive deletion. */ + // Recursive deletion void rec_delete(Siblings * sib) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { if (has_children(sh)) { @@ -313,21 +315,21 @@ class Simplex_tree { /** \brief Returns the key associated to a simplex. * * The filtration must be initialized. */ - Simplex_key key(Simplex_handle sh) { + static Simplex_key key(Simplex_handle sh) { return sh->second.key(); } /** \brief Returns the simplex associated to a key. * * The filtration must be initialized. */ - Simplex_handle simplex(Simplex_key key) { + Simplex_handle simplex(Simplex_key key) const { return filtration_vect_[key]; } /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ - Filtration_value filtration(Simplex_handle sh) const { + static Filtration_value filtration(Simplex_handle sh) { if (sh != null_simplex()) { return sh->second.filtration(); } else { @@ -353,13 +355,13 @@ class Simplex_tree { * associated to the simplices in the simplicial complex. * * One can call filtration(null_simplex()). */ - Simplex_handle null_simplex() const { + static Simplex_handle null_simplex() { return Dictionary_it(NULL); } /** \brief Returns a key different for all keys associated to the * simplices of the simplicial complex. */ - Simplex_key null_key() const { + static Simplex_key null_key() { return -1; } @@ -415,8 +417,8 @@ class Simplex_tree { */ template<class RandomAccessVertexRange> Simplex_handle find(RandomAccessVertexRange & s) { - if (s.begin() == s.end()) - std::cerr << "Empty simplex \n"; + if (s.begin() == s.end()) // Empty simplex + return null_simplex(); sort(s.begin(), s.end()); @@ -471,8 +473,8 @@ class Simplex_tree { if (simplex.empty()) { return std::pair<Simplex_handle, bool>(null_simplex(), true); } - - sort(simplex.begin(), simplex.end()); // must be sorted in increasing order + // must be sorted in increasing order + sort(simplex.begin(), simplex.end()); Siblings * curr_sib = &root_; std::pair<Simplex_handle, bool> res_insert; @@ -485,12 +487,15 @@ class Simplex_tree { curr_sib = res_insert.first->second.children(); } res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); - if (!res_insert.second) { // if already in the complex - if (res_insert.first->second.filtration() > filtration) { // if filtration value modified + if (!res_insert.second) { + // if already in the complex + if (res_insert.first->second.filtration() > filtration) { + // if filtration value modified res_insert.first->second.assign_filtration(filtration); return res_insert; } - return std::pair<Simplex_handle, bool>(null_simplex(), false); // if filtration value unchanged + // if filtration value unchanged + return std::pair<Simplex_handle, bool>(null_simplex(), false); } // otherwise the insertion has succeeded return res_insert; @@ -599,10 +604,8 @@ class Simplex_tree { void initialize_filtration() { filtration_vect_.clear(); filtration_vect_.reserve(num_simplices()); - for (auto cpx_it = complex_simplex_range().begin(); - cpx_it != complex_simplex_range().end(); ++cpx_it) { - filtration_vect_.push_back(*cpx_it); - } + for (Simplex_handle sh : complex_simplex_range()) + filtration_vect_.push_back(sh); // the stable sort ensures the ordering heuristic std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), @@ -610,6 +613,92 @@ class Simplex_tree { } private: + /** Recursive search of cofaces + * This function uses DFS + *\param vertices contains a list of vertices, which represent the vertices of the simplex not found yet. + *\param curr_nbVertices represents the number of vertices of the simplex we reached by going through the tree. + *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. + *\param star true if we need the star of the simplex + *\param nbVertices number of vertices of the cofaces we search + * Prefix actions : When the bottom vertex matches with the current vertex in the tree, we remove the bottom vertex from vertices. + * Infix actions : Then we call or not the recursion. + * Postfix actions : Finally, we add back the removed vertex into vertices, and remove this vertex from curr_nbVertices so that we didn't change the parameters. + * If the vertices list is empty, we need to check if curr_nbVertices matches with the dimension of the cofaces asked. + */ + void rec_coface(std::vector<Vertex_handle> &vertices, Siblings *curr_sib, int curr_nbVertices, + std::vector<Simplex_handle>& cofaces, bool star, int nbVertices) { + if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices + return; + for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) { + if (vertices.empty()) { + // 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 + bool addCoface = (star || curr_nbVertices == nbVertices); + if (addCoface) + cofaces.push_back(simplex); + if ((!addCoface || star) && has_children(simplex)) // Rec call + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + } else { + if (simplex->first == vertices.back()) { + // If curr_sib matches with the top vertex + bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = vertices.size() == 1 && equalDim; + if (addCoface) + cofaces.push_back(simplex); + if ((!addCoface || star) && has_children(simplex)) { + // Rec call + Vertex_handle tmp = vertices.back(); + vertices.pop_back(); + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + vertices.push_back(tmp); + } + } else if (simplex->first > vertices.back()) { + return; + } else { + // (simplex->first < vertices.back() + if (has_children(simplex)) + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + } + } + } + } + + public: + /** \brief Compute the star of a n simplex + * \param simplex represent the simplex of which we search the star + * \return Vector of Simplex_handle, empty vector if no cofaces found. + */ + + Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) { + return cofaces_simplex_range(simplex, 0); + } + + /** \brief Compute the cofaces of a n simplex + * \param simplex represent the n-simplex of which we search the n+codimension cofaces + * \param codimension The function returns the n+codimension-cofaces of the n-simplex. If codimension = 0, + * return all cofaces (equivalent of star function) + * \return Vector of Simplex_handle, empty vector if no cofaces found. + */ + + Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) { + Cofaces_simplex_range cofaces; + // codimension must be positive or null integer + assert(codimension >= 0); + Simplex_vertex_range rg = simplex_vertex_range(simplex); + std::vector<Vertex_handle> copy(rg.begin(), rg.end()); + if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 || + (codimension == 0 && static_cast<int>(copy.size()) > dimension_)) // n+codimension greater than dimension_ + return cofaces; + // must be sorted in decreasing order + assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>())); + bool star = codimension == 0; + rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size())); + return cofaces; + } + + private: /** \brief Returns true iff the list of vertices of sh1 * is smaller than the list of vertices of sh2 w.r.t. * lexicographic order on the lists read in reverse. @@ -647,8 +736,8 @@ class Simplex_tree { if (st_->filtration(sh1) != st_->filtration(sh2)) { return st_->filtration(sh1) < st_->filtration(sh2); } - - return st_->reverse_lexicographic_order(sh1, sh2); // is sh1 a proper subface of sh2 + // is sh1 a proper subface of sh2 + return st_->reverse_lexicographic_order(sh1, sh2); } Simplex_tree * st_; @@ -675,7 +764,8 @@ class Simplex_tree { * must be undirected_tag. */ template<class OneSkeletonGraph> void insert_graph(const OneSkeletonGraph& skel_graph) { - assert(num_simplices() == 0); // the simplex tree must be empty + // the simplex tree must be empty + assert(num_simplices() == 0); if (boost::num_vertices(skel_graph) == 0) { return; @@ -704,7 +794,8 @@ class Simplex_tree { ++e_it) { auto u = source(*e_it, skel_graph); auto v = target(*e_it, skel_graph); - if (u < v) { // count edges only once { std::swap(u,v); } // u < v + if (u < v) { + // count edges only once { std::swap(u,v); } // u < v auto sh = find_vertex(u); if (!has_children(sh)) { sh->second.assign_children(new Siblings(&root_, sh->first)); @@ -755,16 +846,16 @@ class Simplex_tree { static std::vector<std::pair<Vertex_handle, Node> > inter; // static, not thread-safe. for (Dictionary_it s_h = siblings->members().begin(); - s_h != siblings->members().end(); ++s_h, ++next) { + s_h != siblings->members().end(); ++s_h, ++next) { Simplex_handle root_sh = find_vertex(s_h->first); if (has_children(root_sh)) { intersection( - inter, // output intersection - next, // begin - siblings->members().end(), // end - root_sh->second.children()->members().begin(), - root_sh->second.children()->members().end(), - s_h->second.filtration()); + inter, // output intersection + next, // begin + siblings->members().end(), // end + root_sh->second.children()->members().begin(), + root_sh->second.children()->members().end(), + s_h->second.filtration()); if (inter.size() != 0) { this->num_simplices_ += inter.size(); Siblings * new_sib = new Siblings(siblings, // oncles @@ -774,7 +865,8 @@ class Simplex_tree { s_h->second.assign_children(new_sib); siblings_expansion(new_sib, k - 1); } else { - s_h->second.assign_children(siblings); // ensure the children property + // ensure the children property + s_h->second.assign_children(siblings); inter.clear(); } } @@ -786,40 +878,25 @@ class Simplex_tree { static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection, Dictionary_it begin1, Dictionary_it end1, Dictionary_it begin2, Dictionary_it end2, - Filtration_value filtration) { + Filtration_value filtration_) { if (begin1 == end1 || begin2 == end2) return; // ----->> while (true) { if (begin1->first == begin2->first) { - intersection.push_back( - std::pair<Vertex_handle, Node>( - begin1->first, - Node(NULL, maximum(begin1->second.filtration(), begin2->second.filtration(), filtration)))); - ++begin1; - ++begin2; - if (begin1 == end1 || begin2 == end2) + Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_}); + intersection.emplace_back(begin1->first, Node(NULL, filt)); + if (++begin1 == end1 || ++begin2 == end2) + return; // ----->> + } else if (begin1->first < begin2->first) { + if (++begin1 == end1) + return; + } else /* begin1->first > begin2->first */ { + if (++begin2 == end2) return; // ----->> - } else { - if (begin1->first < begin2->first) { - ++begin1; - if (begin1 == end1) - return; - } else { - ++begin2; - if (begin2 == end2) - return; // ----->> - } } } } - /** Maximum over 3 values.*/ - static Filtration_value maximum(Filtration_value a, Filtration_value b, - Filtration_value c) { - Filtration_value max = (a < b) ? b : a; - return ((max < c) ? c : max); - } - public: /** \brief Write the hasse diagram of the simplicial complex in os. * @@ -864,6 +941,7 @@ std::ostream& operator<<(std::ostream & os, Simplex_tree<T1, T2, T3> & st) { } return os; } + template<typename T1, typename T2, typename T3> std::istream& operator>>(std::istream & is, Simplex_tree<T1, T2, T3> & st) { // assert(st.num_simplices() == 0); @@ -873,16 +951,19 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T1, T2, T3> & st) { typename Simplex_tree<T1, T2, T3>::Filtration_value max_fil = 0; int max_dim = -1; size_t num_simplices = 0; - while (read_simplex(is, simplex, fil)) { // read all simplices in the file as a list of vertices + while (read_simplex(is, simplex, fil)) { + // read all simplices in the file as a list of vertices ++num_simplices; - int dim = static_cast<int>(simplex.size() - 1); // Warning : simplex_size needs to be casted in int - Can be 0 + // Warning : simplex_size needs to be casted in int - Can be 0 + int dim = static_cast<int> (simplex.size() - 1); if (max_dim < dim) { max_dim = dim; } if (max_fil < fil) { max_fil = fil; } - st.insert_simplex(simplex, fil); // insert every simplex in the simplex tree + // insert every simplex in the simplex tree + st.insert_simplex(simplex, fil); simplex.clear(); } st.set_num_simplices(num_simplices); @@ -891,8 +972,8 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T1, T2, T3> & st) { return is; } - /** @} */ // end defgroup simplex_tree + } // namespace Gudhi -#endif // SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ +#endif // SIMPLEX_TREE_H_ diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 6b0a1f3d..7f2172a2 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -1,9 +1,11 @@ #define BOOST_TEST_MODULE simplex_tree test #include <boost/test/included/unit_test.hpp> +#include <boost/range/adaptor/reversed.hpp> #include <boost/system/error_code.hpp> #include <boost/chrono/thread_clock.hpp> #include <iostream> #include <string> +#include <algorithm> #include <utility> // std::pair, std::make_pair @@ -21,7 +23,7 @@ typedef std::pair<typeST::Simplex_handle, bool> typePairSimplexBool; typedef std::vector<Vertex_handle> typeVectorVertex; typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; -const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) -1; +const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) - 1; const Filtration_value DEFAULT_FILTRATION_VALUE = (const Filtration_value) 0.0; void test_empty_simplex_tree(typeST& tst) { @@ -40,25 +42,24 @@ void test_iterators_on_empty_simplex_tree(typeST& tst) { std::cout << "Iterator on vertices: " << std::endl; for (auto vertex : tst.complex_vertex_range()) { std::cout << "vertice:" << vertex << std::endl; - BOOST_CHECK(false); // shall be empty + BOOST_CHECK(false); // shall be empty } std::cout << "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 + BOOST_CHECK(simplex != simplex); // shall be empty - to remove warning of non-used simplex } std::cout << "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 + BOOST_CHECK(false); // shall be empty std::cout << "test_iterators_on_empty_simplex_tree - filtration=" << tst.filtration(f_simplex) << std::endl; } } -BOOST_AUTO_TEST_CASE( simplex_tree_when_empty ) -{ +BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) { const Filtration_value DEFAULT_FILTRATION_VALUE = 0; // TEST OF DEFAULT CONSTRUCTOR @@ -66,29 +67,28 @@ BOOST_AUTO_TEST_CASE( simplex_tree_when_empty ) std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; typeST st; - test_empty_simplex_tree (st); + test_empty_simplex_tree(st); - test_iterators_on_empty_simplex_tree (st); + test_iterators_on_empty_simplex_tree(st); // TEST OF EMPTY INSERTION std::cout << "TEST OF EMPTY INSERTION" << std::endl; typeVectorVertex simplexVectorEmpty; BOOST_CHECK(simplexVectorEmpty.empty() == true); typePairSimplexBool returnEmptyValue = st.insert_simplex(simplexVectorEmpty, - DEFAULT_FILTRATION_VALUE); + DEFAULT_FILTRATION_VALUE); BOOST_CHECK(returnEmptyValue.first == typeST::Simplex_handle(NULL)); BOOST_CHECK(returnEmptyValue.second == true); - test_empty_simplex_tree (st); + test_empty_simplex_tree(st); - test_iterators_on_empty_simplex_tree (st); + test_iterators_on_empty_simplex_tree(st); } bool AreAlmostTheSame(float a, float b) { return std::fabs(a - b) < std::numeric_limits<float>::epsilon(); } -BOOST_AUTO_TEST_CASE( simplex_tree_from_file ) -{ +BOOST_AUTO_TEST_CASE(simplex_tree_from_file) { // TEST OF INSERTION std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl; @@ -108,16 +108,14 @@ BOOST_AUTO_TEST_CASE( simplex_tree_from_file ) BOOST_CHECK(st.filtration() == 0.4); int previous_size = 0; - for( auto f_simplex : st.filtration_simplex_range() ) - { + for (auto f_simplex : st.filtration_simplex_range()) { // Size of simplex int size = 0; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { + for (auto vertex : st.simplex_vertex_range(f_simplex)) { size++; } - BOOST_CHECK(AreAlmostTheSame(st.filtration(f_simplex),(0.1* size))); // Specific test: filtration = 0.1 * simplex_size - BOOST_CHECK(previous_size <= size);// Check list is sorted (because of sorted filtrations in simplex_tree.txt) + BOOST_CHECK(AreAlmostTheSame(st.filtration(f_simplex), (0.1 * size))); // Specific test: filtration = 0.1 * simplex_size + BOOST_CHECK(previous_size <= size); // Check list is sorted (because of sorted filtrations in simplex_tree.txt) previous_size = size; } simplex_tree_stream.close(); @@ -127,13 +125,12 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p auto f_simplex = simplexTree.filtration_simplex_range().begin() + pos; std::cout << "test_simplex_tree_contains - filtration=" << simplexTree.filtration(*f_simplex) << "||" << simplex.second << std::endl; - BOOST_CHECK( AreAlmostTheSame(simplexTree.filtration(*f_simplex),simplex.second) ); + BOOST_CHECK(AreAlmostTheSame(simplexTree.filtration(*f_simplex), simplex.second)); - int simplexIndex=simplex.first.size()-1; - for( auto vertex : simplexTree.simplex_vertex_range(*f_simplex) ) - { + int simplexIndex = simplex.first.size() - 1; + for (auto vertex : simplexTree.simplex_vertex_range(*f_simplex)) { std::cout << "test_simplex_tree_contains - vertex=" << vertex << "||" << simplex.first.at(simplexIndex) << std::endl; - BOOST_CHECK(vertex == simplex.first.at(simplexIndex)); + BOOST_CHECK(vertex == simplex.first.at(simplexIndex)); BOOST_CHECK(simplexIndex >= 0); simplexIndex--; } @@ -141,7 +138,7 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p void test_simplex_tree_insert_returns_true(const typePairSimplexBool& returnValue) { BOOST_CHECK(returnValue.second == true); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned != typeST::Simplex_handle(NULL)); } @@ -170,8 +167,23 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons BOOST_CHECK(simplexTree.num_simplices() == nb_simplices); } -BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) -{ +void test_cofaces(typeST& st, std::vector<Vertex_handle> v, int dim, std::vector<typeST::Simplex_handle> res) { + typeST::Cofaces_simplex_range cofaces; + if (dim == 0) + cofaces = st.star_simplex_range(st.find(v)); + else + cofaces = st.cofaces_simplex_range(st.find(v), dim); + for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) { + typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); + for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { + std::cout << "(" << *vertex << ")"; + } + std::cout << std::endl; + BOOST_CHECK(std::find(res.begin(), res.end(), *simplex) != res.end()); + } +} + +BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { const Filtration_value FIRST_FILTRATION_VALUE = 0.1; const Filtration_value SECOND_FILTRATION_VALUE = 0.2; const Filtration_value THIRD_FILTRATION_VALUE = 0.3; @@ -190,88 +202,88 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) std::cout << " - INSERT 0" << std::endl; typeVectorVertex firstSimplexVector; firstSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( firstSimplexVector.size() == 1 ); + BOOST_CHECK(firstSimplexVector.size() == 1); typeSimplex firstSimplex = std::make_pair( - firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); typePairSimplexBool returnValue = st.insert_simplex(firstSimplex.first, - firstSimplex.second); + firstSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, firstSimplexVector.size(), firstSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)1 ); + BOOST_CHECK(st.num_vertices() == (size_t) 1); // ++ SECOND std::cout << " - INSERT 1" << std::endl; typeVectorVertex secondSimplexVector; secondSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( secondSimplexVector.size() == 1 ); + BOOST_CHECK(secondSimplexVector.size() == 1); typeSimplex secondSimplex = std::make_pair( - secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( secondSimplex.first, secondSimplex.second ); + st.insert_simplex(secondSimplex.first, secondSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, secondSimplexVector.size(), secondSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)2 ); + BOOST_CHECK(st.num_vertices() == (size_t) 2); // ++ THIRD std::cout << " - INSERT (0,1)" << std::endl; typeVectorVertex thirdSimplexVector; thirdSimplexVector.push_back(FIRST_VERTEX_HANDLE); thirdSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( thirdSimplexVector.size() == 2 ); + BOOST_CHECK(thirdSimplexVector.size() == 2); typeSimplex thirdSimplex = std::make_pair( - thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( thirdSimplex.first, thirdSimplex.second ); + st.insert_simplex(thirdSimplex.first, thirdSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, thirdSimplexVector.size(), thirdSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)2 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 2); // Not incremented !! // ++ FOURTH std::cout << " - INSERT 2" << std::endl; typeVectorVertex fourthSimplexVector; fourthSimplexVector.push_back(THIRD_VERTEX_HANDLE); - BOOST_CHECK( fourthSimplexVector.size() == 1 ); + BOOST_CHECK(fourthSimplexVector.size() == 1); typeSimplex fourthSimplex = std::make_pair( - fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( fourthSimplex.first, fourthSimplex.second ); + st.insert_simplex(fourthSimplex.first, fourthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, fourthSimplexVector.size(), fourthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); + BOOST_CHECK(st.num_vertices() == (size_t) 3); // ++ FIFTH std::cout << " - INSERT (2,0)" << std::endl; typeVectorVertex fifthSimplexVector; fifthSimplexVector.push_back(THIRD_VERTEX_HANDLE); fifthSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( fifthSimplexVector.size() == 2 ); + BOOST_CHECK(fifthSimplexVector.size() == 2); typeSimplex fifthSimplex = std::make_pair( - fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( fifthSimplex.first, fifthSimplex.second ); + st.insert_simplex(fifthSimplex.first, fifthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, fifthSimplexVector.size(), fifthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SIXTH std::cout << " - INSERT (2,1)" << std::endl; typeVectorVertex sixthSimplexVector; sixthSimplexVector.push_back(THIRD_VERTEX_HANDLE); sixthSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( sixthSimplexVector.size() == 2 ); + BOOST_CHECK(sixthSimplexVector.size() == 2); typeSimplex sixthSimplex = std::make_pair( - sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( sixthSimplex.first, sixthSimplex.second ); + st.insert_simplex(sixthSimplex.first, sixthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, sixthSimplexVector.size(), sixthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SEVENTH std::cout << " - INSERT (2,1,0)" << std::endl; @@ -279,61 +291,61 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) seventhSimplexVector.push_back(THIRD_VERTEX_HANDLE); seventhSimplexVector.push_back(SECOND_VERTEX_HANDLE); seventhSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( seventhSimplexVector.size() == 3 ); + BOOST_CHECK(seventhSimplexVector.size() == 3); typeSimplex seventhSimplex = std::make_pair( - seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); + seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( seventhSimplex.first, seventhSimplex.second ); + st.insert_simplex(seventhSimplex.first, seventhSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, seventhSimplexVector.size(), seventhSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ EIGHTH std::cout << " - INSERT 3" << std::endl; typeVectorVertex eighthSimplexVector; eighthSimplexVector.push_back(FOURTH_VERTEX_HANDLE); - BOOST_CHECK( eighthSimplexVector.size() == 1 ); + BOOST_CHECK(eighthSimplexVector.size() == 1); typeSimplex eighthSimplex = std::make_pair( - eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( eighthSimplex.first, eighthSimplex.second ); + st.insert_simplex(eighthSimplex.first, eighthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // ++ NINETH std::cout << " - INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector; ninethSimplexVector.push_back(FOURTH_VERTEX_HANDLE); ninethSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( ninethSimplexVector.size() == 2 ); + BOOST_CHECK(ninethSimplexVector.size() == 2); typeSimplex ninethSimplex = std::make_pair( - ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( ninethSimplex.first, ninethSimplex.second ); + st.insert_simplex(ninethSimplex.first, ninethSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, ninethSimplexVector.size(), ninethSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! // ++ TENTH std::cout << " - INSERT 0 (already inserted)" << std::endl; typeVectorVertex tenthSimplexVector; tenthSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( tenthSimplexVector.size() == 1 ); + BOOST_CHECK(tenthSimplexVector.size() == 1); typeSimplex tenthSimplex = std::make_pair( - tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); // With a different filtration value + tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); // With a different filtration value returnValue = - st.insert_simplex ( tenthSimplex.first, tenthSimplex.second ); + st.insert_simplex(tenthSimplex.first, tenthSimplex.second); BOOST_CHECK(returnValue.second == false); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented !! - BOOST_CHECK( st.dimension() == dim_max ); - BOOST_CHECK( AreAlmostTheSame(st.filtration(), max_fil) ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! + BOOST_CHECK(st.dimension() == dim_max); + BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); // ++ ELEVENTH std::cout << " - INSERT (2,1,0) (already inserted)" << std::endl; @@ -341,18 +353,18 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) eleventhSimplexVector.push_back(THIRD_VERTEX_HANDLE); eleventhSimplexVector.push_back(SECOND_VERTEX_HANDLE); eleventhSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( eleventhSimplexVector.size() == 3 ); + BOOST_CHECK(eleventhSimplexVector.size() == 3); typeSimplex eleventhSimplex = std::make_pair( - eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); + eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( eleventhSimplex.first, eleventhSimplex.second ); + st.insert_simplex(eleventhSimplex.first, eleventhSimplex.second); BOOST_CHECK(returnValue.second == false); - shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); - BOOST_CHECK( st.num_vertices() == (size_t)4 );// Not incremented !! - BOOST_CHECK( st.dimension() == dim_max ); - BOOST_CHECK( AreAlmostTheSame(st.filtration(), max_fil) ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! + BOOST_CHECK(st.dimension() == dim_max); + BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); /* Inserted simplex: */ /* 1 */ @@ -372,43 +384,40 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) // [0.3] 2 1 0 // !! Be careful, simplex are sorted by filtration value on insertion !! std::cout << "simplex_tree_insertion - first - 0" << std::endl; - test_simplex_tree_contains(st, firstSimplex, 0);// (0) -> 0 + test_simplex_tree_contains(st, firstSimplex, 0); // (0) -> 0 std::cout << "simplex_tree_insertion - second - 1" << std::endl; - test_simplex_tree_contains(st, secondSimplex, 1);// (1) -> 1 + test_simplex_tree_contains(st, secondSimplex, 1); // (1) -> 1 std::cout << "simplex_tree_insertion - third - 4" << std::endl; - test_simplex_tree_contains(st, thirdSimplex, 4);// (0,1) -> 4 + test_simplex_tree_contains(st, thirdSimplex, 4); // (0,1) -> 4 std::cout << "simplex_tree_insertion - fourth - 2" << std::endl; - test_simplex_tree_contains(st, fourthSimplex, 2);// (2) -> 2 + test_simplex_tree_contains(st, fourthSimplex, 2); // (2) -> 2 std::cout << "simplex_tree_insertion - fifth - 5" << std::endl; - test_simplex_tree_contains(st, fifthSimplex, 5);// (2,0) -> 5 + test_simplex_tree_contains(st, fifthSimplex, 5); // (2,0) -> 5 std::cout << "simplex_tree_insertion - sixth - 6" << std::endl; - test_simplex_tree_contains(st, sixthSimplex, 6);//(2,1) -> 6 + test_simplex_tree_contains(st, sixthSimplex, 6); //(2,1) -> 6 std::cout << "simplex_tree_insertion - seventh - 8" << std::endl; - test_simplex_tree_contains(st, seventhSimplex, 8);// (2,1,0) -> 8 + test_simplex_tree_contains(st, seventhSimplex, 8); // (2,1,0) -> 8 std::cout << "simplex_tree_insertion - eighth - 3" << std::endl; - test_simplex_tree_contains(st, eighthSimplex, 3);// (3) -> 3 + test_simplex_tree_contains(st, eighthSimplex, 3); // (3) -> 3 std::cout << "simplex_tree_insertion - nineth - 7" << std::endl; - test_simplex_tree_contains(st, ninethSimplex, 7);// (3,0) -> 7 + 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() << " - filtration " << st.filtration() << std::endl; std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for( auto f_simplex : st.filtration_simplex_range() ) - { + for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { - std::cout << (int)vertex << " "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; } std::cout << std::endl; } } -BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) -{ - Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle)0; +BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { + Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle) 0; Vertex_handle SECOND_VERTEX_HANDLE = (Vertex_handle) 1; Vertex_handle THIRD_VERTEX_HANDLE = (Vertex_handle) 2; Vertex_handle FOURTH_VERTEX_HANDLE = (Vertex_handle) 3; @@ -428,39 +437,39 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) SimplexVector1.push_back(THIRD_VERTEX_HANDLE); SimplexVector1.push_back(SECOND_VERTEX_HANDLE); SimplexVector1.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector1.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector1 ); + BOOST_CHECK(SimplexVector1.size() == 3); + st.insert_simplex_and_subfaces(SimplexVector1); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // +3 (2, 1 and 0 are not existing) + BOOST_CHECK(st.num_vertices() == (size_t) 3); // +3 (2, 1 and 0 are not existing) // ++ SECOND std::cout << " - INSERT 3" << std::endl; typeVectorVertex SimplexVector2; SimplexVector2.push_back(FOURTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector2.size() == 1 ); - st.insert_simplex_and_subfaces ( SimplexVector2 ); + BOOST_CHECK(SimplexVector2.size() == 1); + st.insert_simplex_and_subfaces(SimplexVector2); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // +1 (3 is not existing) + BOOST_CHECK(st.num_vertices() == (size_t) 4); // +1 (3 is not existing) // ++ THIRD std::cout << " - INSERT (0,3)" << std::endl; typeVectorVertex SimplexVector3; SimplexVector3.push_back(FOURTH_VERTEX_HANDLE); SimplexVector3.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector3.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector3 ); + BOOST_CHECK(SimplexVector3.size() == 2); + st.insert_simplex_and_subfaces(SimplexVector3); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented (all are existing) // ++ FOURTH std::cout << " - INSERT (1,0) (already inserted)" << std::endl; typeVectorVertex SimplexVector4; SimplexVector4.push_back(SECOND_VERTEX_HANDLE); SimplexVector4.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector4.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector4 ); + BOOST_CHECK(SimplexVector4.size() == 2); + st.insert_simplex_and_subfaces(SimplexVector4); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented (all are existing) // ++ FIFTH std::cout << " - INSERT (3,4,5)" << std::endl; @@ -468,10 +477,10 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) SimplexVector5.push_back(FOURTH_VERTEX_HANDLE); SimplexVector5.push_back(FIFTH_VERTEX_HANDLE); SimplexVector5.push_back(SIXTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector5.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector5 ); + BOOST_CHECK(SimplexVector5.size() == 3); + st.insert_simplex_and_subfaces(SimplexVector5); - BOOST_CHECK( st.num_vertices() == (size_t)6 ); + BOOST_CHECK(st.num_vertices() == (size_t) 6); // ++ SIXTH std::cout << " - INSERT (0,1,6,7)" << std::endl; @@ -480,10 +489,10 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) SimplexVector6.push_back(SECOND_VERTEX_HANDLE); SimplexVector6.push_back(SEVENTH_VERTEX_HANDLE); SimplexVector6.push_back(EIGHTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector6.size() == 4 ); - st.insert_simplex_and_subfaces ( SimplexVector6 ); + BOOST_CHECK(SimplexVector6.size() == 4); + st.insert_simplex_and_subfaces(SimplexVector6); - BOOST_CHECK( st.num_vertices() == (size_t)8 ); // +2 (6 and 7 are not existing - 0 and 1 are already existing) + BOOST_CHECK(st.num_vertices() == (size_t) 8); // +2 (6 and 7 are not existing - 0 and 1 are already existing) /* Inserted simplex: */ /* 1 6 */ @@ -506,13 +515,13 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); - test_simplex_tree_contains(st,simplexPair1,6); // (2,1,0) is in position 6 - test_simplex_tree_contains(st,simplexPair2,7); // (3) is in position 7 - test_simplex_tree_contains(st,simplexPair3,8); // (3,0) is in position 8 - test_simplex_tree_contains(st,simplexPair4,2); // (1,0) is in position 2 - test_simplex_tree_contains(st,simplexPair5,14); // (3,4,5) is in position 14 - test_simplex_tree_contains(st,simplexPair6,26); // (7,6,1,0) is in position 26 - + test_simplex_tree_contains(st, simplexPair1, 6); // (2,1,0) is in position 6 + test_simplex_tree_contains(st, simplexPair2, 7); // (3) is in position 7 + test_simplex_tree_contains(st, simplexPair3, 8); // (3,0) is in position 8 + test_simplex_tree_contains(st, simplexPair4, 2); // (1,0) is in position 2 + test_simplex_tree_contains(st, simplexPair5, 14); // (3,4,5) is in position 14 + test_simplex_tree_contains(st, simplexPair6, 26); // (7,6,1,0) is in position 26 + // ------------------------------------------------------------------------------------------------------------------ // Find in the simplex_tree // ------------------------------------------------------------------------------------------------------------------ @@ -547,7 +556,7 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << "***- NO IT ISN'T\n"; // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); - + typeVectorVertex otherSimplexVector; otherSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); otherSimplexVector.push_back(SECOND_VERTEX_HANDLE); @@ -572,19 +581,128 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << "***- 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() << " - filtration " << st.filtration() << std::endl; std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for( auto f_simplex : st.filtration_simplex_range() ) - { + for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { - std::cout << (int)vertex << " "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; } std::cout << std::endl; } + std::cout << "********************************************************************" << std::endl; + // TEST COFACE ALGORITHM + st.set_dimension(3); + std::cout << "COFACE ALGORITHM" << std::endl; + std::vector<Vertex_handle> v; + std::vector<Vertex_handle> simplex; + std::vector<typeST::Simplex_handle> result; + v.push_back(3); + std::cout << "First test : " << std::endl; + std::cout << "Star of (3):" << std::endl; + + simplex.push_back(3); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(3); + simplex.push_back(0); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(4); + simplex.push_back(3); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(5); + simplex.push_back(4); + simplex.push_back(3); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(5); + simplex.push_back(3); + result.push_back(st.find(simplex)); + simplex.clear(); + + test_cofaces(st, v, 0, result); + v.clear(); + result.clear(); + + v.push_back(1); + v.push_back(7); + std::cout << "Second test : " << std::endl; + std::cout << "Star of (1,7): " << std::endl; + + simplex.push_back(7); + simplex.push_back(1); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(7); + simplex.push_back(6); + simplex.push_back(1); + simplex.push_back(0); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(7); + simplex.push_back(1); + simplex.push_back(0); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(7); + simplex.push_back(6); + simplex.push_back(1); + result.push_back(st.find(simplex)); + simplex.clear(); + + test_cofaces(st, v, 0, result); + result.clear(); + + std::cout << "Third test : " << std::endl; + std::cout << "2-dimension Cofaces of simplex(1,7) : " << std::endl; + + simplex.push_back(7); + simplex.push_back(1); + simplex.push_back(0); + result.push_back(st.find(simplex)); + simplex.clear(); + + simplex.push_back(7); + simplex.push_back(6); + simplex.push_back(1); + result.push_back(st.find(simplex)); + simplex.clear(); + + test_cofaces(st, v, 1, result); + result.clear(); + + std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension) :" << std::endl; + test_cofaces(st, v, 5, result); + // std::cout << "Cofaces with an empty codimension" << std::endl; + // test_cofaces(st, v, -1, result); + // std::cout << "Cofaces in an empty simplex tree" << std::endl; + // typeST empty_tree; + // test_cofaces(empty_tree, v, 1, result); + // std::cout << "Cofaces of an empty simplex" << std::endl; + // v.clear(); + // test_cofaces(st, v, 1, result); + + /* + // TEST Off read + std::cout << "********************************************************************" << std::endl; + typeST st2; + st2.tree_from_off("test.off"); + std::cout << st2; + */ + } diff --git a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp index 92fa17f3..126e32ec 100644 --- a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp +++ b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp @@ -64,8 +64,10 @@ int main (int argc, char *argv[]){ // or edges, complex.num_vertices() and complex.num_edges() are // more appropriated! unsigned num_vertices = 0; - for(auto v : complex.vertex_range()) - ++num_vertices; + for(auto v : complex.vertex_range()) { + std::cout << "Vertex " << v <<std::endl; + ++num_vertices; + } // such loop can also be done directly with distance as iterators are STL compliant auto edges = complex.edge_range(); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 049db6d5..289819b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -109,7 +109,7 @@ and point access in addition. \subsection Visitor The class Skeleton_blocker_complex has a visitor that is called when usual operations such as adding an edge or remove a vertex are called. -You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the \ref contr package. +You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the \ref contr package). diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h index aaaab8b0..6ad1fdd3 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -107,7 +107,7 @@ class Skeleton_blocker_off_visitor_reader { } void done() { - complex_ = make_complex_from_top_faces(maximal_faces_.begin(), maximal_faces_.end(), + complex_ = make_complex_from_top_faces<Complex>(maximal_faces_.begin(), maximal_faces_.end(), points_.begin(), points_.end() ); } }; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h index 10d64e98..0a2fcb9a 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -69,7 +69,9 @@ class Skeleton_blocker_simplex { } Skeleton_blocker_simplex(std::initializer_list<T>& list) { - for_each(list.begin(), list.end(), add_vertex); + std::for_each(list.begin(), list.end(), [&] (T const& elt) { + add_vertex(elt); + }); } template<typename ... Args> diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index e906df75..40e26c68 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -75,25 +75,11 @@ class Skeleton_blocker_sub_complex : public ComplexType { typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; protected: - ///** - //* @brief Returns true iff the simplex formed by all vertices contained in 'addresses_sigma_in_link' - //* but 'vertex_to_be_ignored' is in 'link' - //*/ - /* - template<typename T> friend bool - proper_face_in_union( - Skeleton_blocker_sub_complex<T> & link, - std::vector<boost::optional<typename T::Vertex_handle> > & addresses_sigma_in_link, - int vertex_to_be_ignored);*/ - + /** * @brief Determines whether all proper faces of simplex 'sigma' belong to 'link1' \cup 'link2' * where 'link1' and 'link2' are subcomplexes of the same complex of type ComplexType */ - // template<typename T> friend bool - // proper_faces_in_union(Skeleton_blocker_simplex<typename T::Root_vertex_handle> & sigma, Skeleton_blocker_sub_complex<T> & link1, Skeleton_blocker_sub_complex<T> & link2){ - // template<typename T> friend bool - // proper_faces_in_union(Skeleton_blocker_simplex<typename T::Root_vertex_handle> & sigma, Skeleton_blocker_sub_complex<T> & link1, Skeleton_blocker_sub_complex<T> & link2); typedef std::map<Root_vertex_handle, Vertex_handle> IdAddressMap; typedef typename IdAddressMap::value_type AddressPair; typedef typename IdAddressMap::iterator IdAddressMapIterator; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h index 666ce430..f9d4d072 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -1,46 +1,42 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_KELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ +#include "boost/iterator/iterator_facade.hpp" + #include <memory> #include <list> #include <iostream> -#include "gudhi/Utils.h" -#include "boost/iterator/iterator_facade.hpp" - #include "gudhi/Skeleton_blocker_link_complex.h" #include "gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h" - #include "gudhi/Skeleton_blocker/internal/Trie.h" - +#include "gudhi/Utils.h" namespace Gudhi { - namespace skbl { - /** * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all * simplices around a vertex OR @@ -49,299 +45,268 @@ namespace skbl { * The iteration is done by computing a trie with the link and doing a breadth-first traversal * of the trie. */ -template<typename SkeletonBlockerComplex,typename Link> +template<typename SkeletonBlockerComplex, typename Link> class Simplex_around_vertex_iterator : - public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex,Link> +public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> , typename SkeletonBlockerComplex::Simplex_handle , boost::forward_traversal_tag , typename SkeletonBlockerComplex::Simplex_handle -> -{ - friend class boost::iterator_core_access; - typedef SkeletonBlockerComplex Complex; - typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; - - - typedef typename Link::Vertex_handle Link_vertex_handle; - // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion - - typedef typename Gudhi::skbl::Trie<Simplex_handle> Trie; - - -private: - const Complex* complex; - Vertex_handle v; - std::shared_ptr<Link> link_v; - std::shared_ptr<Trie> trie; - std::list<Trie*> nodes_to_be_seen; // todo deque - -public: - Simplex_around_vertex_iterator():complex(0){ - } - - Simplex_around_vertex_iterator(const Complex* complex_,Vertex_handle v_): - complex(complex_), - v(v_), - link_v(new Link(*complex_,v_)), - trie(new Trie(v_)){ - compute_trie_and_nodes_to_be_seen(); - } - - // todo avoid useless copy - // todo currently just work if copy begin iterator - Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other): - complex(other.complex), - v(other.v), - link_v(other.link_v), - trie(other.trie), - nodes_to_be_seen(other.nodes_to_be_seen){ - if(!other.is_end()){ - } - } - - /** - * returns an iterator to the end - */ - Simplex_around_vertex_iterator(const Complex* complex_,Vertex_handle v_,bool end): - complex(complex_), - v(v_){ - set_end(); - } - -private: - - - void compute_trie_and_nodes_to_be_seen(){ - // once we go through every simplices passing through v0 - // we remove v0. That way, it prevents from passing a lot of times - // though edges leaving v0. - // another solution would have been to provides an adjacency iterator - // to superior vertices that avoids lower ones. - while(!link_v->empty()){ - auto v0 = *(link_v->vertex_range().begin()); - trie->add_child(build_trie(v0,trie.get())); - link_v->remove_vertex(v0); - } - nodes_to_be_seen.push_back(trie.get()); - } - - Trie* build_trie(Link_vertex_handle link_vh,Trie* parent){ - Trie* res = new Trie(parent_vertex(link_vh),parent); - for(Link_vertex_handle nv : link_v->vertex_range(link_vh)) { - if(link_vh < nv){ - Simplex_handle simplex_node_plus_nv(res->simplex()); - simplex_node_plus_nv.add_vertex(parent_vertex(nv)); - if(complex->contains(simplex_node_plus_nv)){ - res->add_child(build_trie(nv,res)); - } - } - } - return res; - } - - bool is_node_in_complex(Trie* trie){ - return true; - } - - Vertex_handle parent_vertex(Link_vertex_handle link_vh) const{ - return complex->convert_handle_from_another_complex(*link_v,link_vh); - } - - - -public: - - friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi){ - stream<< savi.trie<< std::endl; ; - stream << "("<<savi.nodes_to_be_seen.size()<<") nodes to see\n"; - return stream; - } - - bool equal(const Simplex_around_vertex_iterator& other) const{ - bool same_complex = (complex == other.complex); - if(!same_complex) - return false; - - if(!(v == other.v)) - return false; - - bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty(); - if(both_empty) - return true; - - bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); - - if(!both_non_empty) return false; //one is empty the other is not - - bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); - return same_node; - } - - void increment(){ - assert(!is_end()); - Trie* first_node = nodes_to_be_seen.front(); - - nodes_to_be_seen.pop_front(); - - for(auto childs : first_node->childs){ - nodes_to_be_seen.push_back(childs.get()); - } - - } - - Simplex_handle dereference() const{ - assert(!nodes_to_be_seen.empty()); - Trie* first_node = nodes_to_be_seen.front(); - return first_node->simplex(); - } - -//private: - Simplex_handle get_trie_address() const{ - assert(!nodes_to_be_seen.empty()); - return nodes_to_be_seen.front(); - } - -private: - void set_end(){ - nodes_to_be_seen.clear(); - } - - bool is_end() const{ - return nodes_to_be_seen.empty(); - } +> { + friend class boost::iterator_core_access; + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex_handle Simplex_handle; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + typedef typename Gudhi::skbl::Trie<Simplex_handle> Trie; + + private: + const Complex* complex; + Vertex_handle v; + std::shared_ptr<Link> link_v; + std::shared_ptr<Trie> trie; + std::list<Trie*> nodes_to_be_seen; // todo deque + + public: + Simplex_around_vertex_iterator() : complex(0) {} + + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) : + complex(complex_), + v(v_), + link_v(new Link(*complex_, v_)), + trie(new Trie(v_)) { + compute_trie_and_nodes_to_be_seen(); + } + + // todo avoid useless copy + // todo currently just work if copy begin iterator + Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other) : + complex(other.complex), + v(other.v), + link_v(other.link_v), + trie(other.trie), + nodes_to_be_seen(other.nodes_to_be_seen) { + if (!other.is_end()) {} + } + + /** + * returns an iterator to the end + */ + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_, bool end) : + complex(complex_), + v(v_) { + set_end(); + } + + private: + void compute_trie_and_nodes_to_be_seen() { + // once we go through every simplices passing through v0 + // we remove v0. That way, it prevents from passing a lot of times + // though edges leaving v0. + // another solution would have been to provides an adjacency iterator + // to superior vertices that avoids lower ones. + while (!link_v->empty()) { + auto v0 = *(link_v->vertex_range().begin()); + trie->add_child(build_trie(v0, trie.get())); + link_v->remove_vertex(v0); + } + nodes_to_be_seen.push_back(trie.get()); + } + + Trie* build_trie(Link_vertex_handle link_vh, Trie* parent) { + Trie* res = new Trie(parent_vertex(link_vh), parent); + for (Link_vertex_handle nv : link_v->vertex_range(link_vh)) { + if (link_vh < nv) { + Simplex_handle simplex_node_plus_nv(res->simplex()); + simplex_node_plus_nv.add_vertex(parent_vertex(nv)); + if (complex->contains(simplex_node_plus_nv)) { + res->add_child(build_trie(nv, res)); + } + } + } + return res; + } + + bool is_node_in_complex(Trie* trie) { + return true; + } + + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link_v, link_vh); + } + + public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi) { + stream << savi.trie << std::endl; + stream << "(" << savi.nodes_to_be_seen.size() << ") nodes to see\n"; + return stream; + } + + bool equal(const Simplex_around_vertex_iterator& other) const { + bool same_complex = (complex == other.complex); + if (!same_complex) + return false; + + if (!(v == other.v)) + return false; + + bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty(); + if (both_empty) + return true; + + bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); + + if (!both_non_empty) return false; //one is empty the other is not + + bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); + return same_node; + } + + void increment() { + assert(!is_end()); + Trie* first_node = nodes_to_be_seen.front(); + + nodes_to_be_seen.pop_front(); + + for (auto childs : first_node->childs) { + nodes_to_be_seen.push_back(childs.get()); + } + + } + + Simplex_handle dereference() const { + assert(!nodes_to_be_seen.empty()); + Trie* first_node = nodes_to_be_seen.front(); + return first_node->simplex(); + } + + Simplex_handle get_trie_address() const { + assert(!nodes_to_be_seen.empty()); + return nodes_to_be_seen.front(); + } + + private: + void set_end() { + nodes_to_be_seen.clear(); + } + + bool is_end() const { + return nodes_to_be_seen.empty(); + } }; - - template<typename SkeletonBlockerComplex> class Simplex_iterator : - public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> +public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> , typename SkeletonBlockerComplex::Simplex_handle , boost::forward_traversal_tag , typename SkeletonBlockerComplex::Simplex_handle -> -{ - typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; - - friend class boost::iterator_core_access; - - template<class SkBlDS> friend class Skeleton_blocker_complex; - - - typedef SkeletonBlockerComplex Complex; - typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; - - typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; - - - typedef typename Link::Vertex_handle Link_vertex_handle; - -private: - - const Complex* complex_; - Complex_vertex_iterator current_vertex_; - - typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex,Link> SAVI; - SAVI current_simplex_around_current_vertex_; - SAVI simplices_around_current_vertex_end_; - - -public: - Simplex_iterator():complex_(0){} - - // should not be called if the complex is empty - Simplex_iterator(const Complex* complex): - complex_(complex), - current_vertex_(complex->vertex_range().begin()), - current_simplex_around_current_vertex_(complex,*current_vertex_), - simplices_around_current_vertex_end_(complex,*current_vertex_,true) - { - assert(!complex->empty()); - } - -private: - // todo return to private - Simplex_iterator(const Complex* complex,bool end): - complex_(complex) - { - set_end(); - } - -public: - - Simplex_iterator(const Simplex_iterator& other) - : - complex_(other.complex_), - current_vertex_(other.current_vertex_), - current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_), - simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) - { - } - - friend Simplex_iterator make_begin_iterator(const Complex* complex){ - if(complex->empty()) - return make_end_simplex_iterator(complex); - else - return Simplex_iterator(complex); - } - - friend Simplex_iterator make_end_simplex_iterator(const Complex* complex){ - return Simplex_iterator(complex,true); - } - - bool equal(const Simplex_iterator& other) const{ - if(complex_!=other.complex_) return false; - if(current_vertex_!=other.current_vertex_) return false; - if(is_end() && other.is_end()) return true; - if(current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_) - return false; - return true; - } - - void increment(){ - if(current_simplex_around_current_vertex_!= simplices_around_current_vertex_end_){ - current_simplex_around_current_vertex_.increment(); - if( current_simplex_around_current_vertex_== simplices_around_current_vertex_end_) - goto_next_vertex(); - } - else{ - goto_next_vertex(); - } - } - - void goto_next_vertex(){ - current_vertex_.increment(); - if(!is_end()){ - current_simplex_around_current_vertex_= SAVI(complex_,*current_vertex_); - simplices_around_current_vertex_end_ = SAVI(complex_,*current_vertex_,true); - } - } - - Simplex_handle dereference() const{ - return current_simplex_around_current_vertex_.dereference(); - } - -private: - void set_end(){ - current_vertex_ = complex_->vertex_range().end(); - } - - bool is_end() const{ - return (current_vertex_ == complex_->vertex_range().end()); - } +> { + typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; + + friend class boost::iterator_core_access; + + template<class SkBlDS> friend class Skeleton_blocker_complex; + + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex_; + Complex_vertex_iterator current_vertex_; + + typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> SAVI; + SAVI current_simplex_around_current_vertex_; + SAVI simplices_around_current_vertex_end_; + + public: + Simplex_iterator() : complex_(0) { } + + Simplex_iterator(const Complex* complex) : + complex_(complex), + current_vertex_(complex->vertex_range().begin()), + current_simplex_around_current_vertex_(complex, *current_vertex_), + simplices_around_current_vertex_end_(complex, *current_vertex_, true) { + // should not be called if the complex is empty + assert(!complex->empty()); + } + + private: + // todo return to private + Simplex_iterator(const Complex* complex, bool end) : + complex_(complex) { + set_end(); + } + + public: + Simplex_iterator(const Simplex_iterator& other) + : + complex_(other.complex_), + current_vertex_(other.current_vertex_), + current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_), + simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) { } + + friend Simplex_iterator make_begin_iterator(const Complex* complex) { + if (complex->empty()) + return make_end_simplex_iterator(complex); + else + return Simplex_iterator(complex); + } + + friend Simplex_iterator make_end_simplex_iterator(const Complex* complex) { + return Simplex_iterator(complex, true); + } + + bool equal(const Simplex_iterator& other) const { + if (complex_ != other.complex_) return false; + if (current_vertex_ != other.current_vertex_) return false; + if (is_end() && other.is_end()) return true; + if (current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_) + return false; + return true; + } + + void increment() { + if (current_simplex_around_current_vertex_ != simplices_around_current_vertex_end_) { + current_simplex_around_current_vertex_.increment(); + if (current_simplex_around_current_vertex_ == simplices_around_current_vertex_end_) + goto_next_vertex(); + } else { + goto_next_vertex(); + } + } + + void goto_next_vertex() { + current_vertex_.increment(); + if (!is_end()) { + current_simplex_around_current_vertex_ = SAVI(complex_, *current_vertex_); + simplices_around_current_vertex_end_ = SAVI(complex_, *current_vertex_, true); + } + } + + Simplex_handle dereference() const { + return current_simplex_around_current_vertex_.dereference(); + } + + private: + void set_end() { + current_vertex_ = complex_->vertex_range().end(); + } + + bool is_end() const { + return (current_vertex_ == complex_->vertex_range().end()); + } }; +} // namespace skbl -} - -} // namespace GUDHI - - - - +} // namespace Gudhi -#endif /* SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ */ +#endif // GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h index 437482cb..3eff1ba3 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -79,23 +79,6 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { (*this)[Vertex_handle(current++)].point() = Point(point->begin(), point->end()); } - template<typename SimpleHandleOutputIterator, typename PointIterator> - friend Skeleton_blocker_geometric_complex make_complex_from_top_faces( - SimpleHandleOutputIterator simplex_begin, - SimpleHandleOutputIterator simplex_end, - PointIterator points_begin, - PointIterator points_end, - bool is_flag_complex = false) { - Skeleton_blocker_geometric_complex complex; - unsigned current = 0; - complex = - make_complex_from_top_faces<Skeleton_blocker_geometric_complex>(simplex_begin, simplex_end, is_flag_complex); - for (auto point = points_begin; point != points_end; ++point) - // complex.point(Vertex_handle(current++)) = Point(point->begin(),point->end()); - complex.point(Vertex_handle(current++)) = Point(*point); - return complex; - } - /** * @brief Constructor with a list of simplices. * Points of every vertex are the point constructed with default constructor. @@ -215,6 +198,25 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { } }; + +template<typename SkeletonBlockerGeometricComplex, typename SimpleHandleOutputIterator, typename PointIterator> +SkeletonBlockerGeometricComplex make_complex_from_top_faces( + SimpleHandleOutputIterator simplex_begin, + SimpleHandleOutputIterator simplex_end, + PointIterator points_begin, + PointIterator points_end, + bool is_flag_complex = false) { + typedef SkeletonBlockerGeometricComplex SBGC; + SkeletonBlockerGeometricComplex complex; + unsigned current = 0; + complex = + make_complex_from_top_faces<SBGC>(simplex_begin, simplex_end, is_flag_complex); + for (auto point = points_begin; point != points_end; ++point) + // complex.point(Vertex_handle(current++)) = Point(point->begin(),point->end()); + complex.point(typename SBGC::Vertex_handle(current++)) = typename SBGC::Point(*point); + return complex; +} + } // namespace skbl } // namespace Gudhi diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 86a12d90..57e1daf0 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -208,7 +208,8 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex_hand } /** - * @brief add a maximal simplex plus all its cofaces. + * @brief add a maximal simplex plus all its cofaces. All vertices lower than the higher vertex of + * sigma must already be present. * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge). */ template<typename SkeletonBlockerDS> @@ -223,7 +224,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex_hand for (auto u_it = sigma.begin(); u_it != sigma.end(); ++u_it) for (auto v_it = u_it; ++v_it != sigma.end(); /**/) { - std::cout << "add edge" << *u_it << " " << *v_it << std::endl; + // std::cout << "add edge" << *u_it << " " << *v_it << std::endl; add_edge(*u_it, *v_it); } remove_blocker_include_in_simplex(sigma); @@ -338,9 +339,11 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vertex_handle b) { assert(this->contains_vertex(a)); assert(this->contains_vertex(b)); - assert(this->contains_edge(a, b)); - // if some blockers passes through 'ab', we remove them. + if(this->contains_edge(a, b)) + this->add_edge(a, b); + + // if some blockers passes through 'ab', we need to remove them. if (!link_condition(a, b)) delete_blockers_around_edge(a, b); |