diff options
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 69 | ||||
| -rw-r--r-- | src/Simplex_tree/test/simplex_tree_unit_test.cpp | 71 |
2 files changed, 118 insertions, 22 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 79c7cd2e..63671d63 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -314,7 +314,8 @@ class Simplex_tree { } /** rec_copy: DFS, inserts simplices when reaching a leaf.*/ - void rec_copy(Siblings * sib, std::vector<Vertex_handle> v) + template <typename RandomAccessVertexRange> + void rec_copy(Siblings * sib, RandomAccessVertexRange v) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { @@ -361,7 +362,40 @@ class Simplex_tree { } public: + /** \brief Prints the simplex_tree hierarchically. */ + void print_tree() + { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) + { + std::cout << sh->first << " "; + if (has_children(sh)) + { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + std::cout << std::endl; + } + } + + + /** \brief Recursively prints the simplex_tree, using DFS. */ + private: + void rec_print(Siblings * sib) + { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + { + std::cout << " " << sh->first << " "; + if (has_children(sh)) + { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + } + } + public: /** \brief Checks whether or not two simplex trees are equal. */ bool operator ==(Simplex_tree st2) @@ -490,7 +524,7 @@ bool has_children(Simplex_handle sh) { */ template<class RandomAccessVertexRange> Simplex_handle find(RandomAccessVertexRange & s) { - std::vector<Vertex_handle> copy = s; + RandomAccessVertexRange copy = s; sort(s.begin(), s.end()); return find_rec(s); } @@ -581,7 +615,7 @@ public: template<class RandomAccessVertexRange> std::pair<Simplex_handle, bool> insert_simplex(RandomAccessVertexRange & simplex, Filtration_value filtration) { - std::vector<Vertex_handle> copy = simplex; + RandomAccessVertexRange copy = simplex; sort(copy.begin(), copy.end()); return insert_simplex_rec(copy, filtration); } @@ -720,6 +754,35 @@ std::pair<Simplex_handle, bool> insert_simplex(RandomAccessVertexRange & simplex is_before_in_filtration(this)); } +/** \brief Contracts two edges + \param deleted The base of the edge to be contracted + \param remaining The new vertex with children and variables of the former +*/ + void edge_contraction(Simplex_handle & deleted, Simplex_handle & remaining) + { + Siblings * sibDeleted, * sibRemaining; // We need the siblings + sibDeleted = (has_children(deleted) ? deleted->second.children()->oncles() : deleted->second.children()); + sibRemaining = (has_children(remaining) ? remaining->second.children()->oncles() : remaining->second.children()); + // Add all edges to vertex + if (has_children(deleted)) + { + std::deque<Vertex_handle> v; + Vertex_handle vertex = sibRemaining->parent_; + Siblings * sib_tmp = sibRemaining->oncles(); + while (vertex != -1) + { + v.push_front(vertex); + vertex = sib_tmp->parent_; + sib_tmp = sib_tmp->oncles(); + } + v.push_back(remaining->first); + v.push_back(deleted->first); + rec_copy(deleted->second.children(), v); + } + // Delete the contracted edge + sibDeleted->members().erase(deleted->first); + } + private: /** \brief Returns true iff the list of vertices of sh1 * is smaller than the list of vertices of sh2 w.r.t. diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 1f99cfe7..7ab5c24e 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -588,23 +588,56 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << std::endl; } - // TEST Copy constructor / Move - std::cout << "Printing st" << std::endl; - std::cout << &st << std::endl; - std::cout << st; - typeST st3 = st; - BOOST_CHECK(st == st3); - typeST st_move = std::move(st); - std::cout << "Printing a copy of st" << std::endl; - std::cout << &st3 << std::endl; - std::cout << st3; - BOOST_CHECK(st_move == st3); - std::cout << "Printing a move of st" << std::endl; - std::cout << &st_move << std::endl; - std::cout << st_move; - typeST st_empty; - BOOST_CHECK(st == st_empty); - std::cout << "Printing st again" << std::endl; - std::cout << &st << std::endl; - std::cout << st; + std::cout << "********************************************************************" << std::endl; + // TEST Copy constructor / Move + std::cout << "Printing st" << std::endl; + std::cout << &st << std::endl; + st.print_tree(); + typeST st_copy_1 = st; + BOOST_CHECK(st == st_copy_1); + typeST st_move = std::move(st); + std::cout << "Printing a copy of st" << std::endl; + std::cout << &st_copy_1 << std::endl; + st_copy_1.print_tree(); + BOOST_CHECK(st_move == st_copy_1); + std::cout << "Printing a move of st" << std::endl; + std::cout << &st_move << std::endl; + st_move.print_tree(); + typeST st_empty; + BOOST_CHECK(st == st_empty); + std::cout << "Printing st again" << std::endl; + std::cout << &st << std::endl; + st.print_tree(); + + std::cout << "********************************************************************" << std::endl; + // TEST Edge_contraction + typeST st_copy_2 = st_copy_1, st_copy_3 = st_copy_1; + std::vector<Vertex_handle> v1, v2; + v1.push_back(3); + v2.push_back(0); + typeST::Simplex_handle s1; + typeST::Simplex_handle s2; + s1 = st_copy_1.find(v1); + s2 = st_copy_1.find(v2); + st_copy_1.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (3, 0) contracted, 3 being contracted in 0" << std::endl; + st_copy_1.print_tree(); + v1.clear(); + v2.clear(); + v1.push_back(3); + v2.push_back(1); + s1 = st_copy_2.find(v1); + s2 = st_copy_2.find(v2); + st_copy_2.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (3, 1) contracted, 3 being contracted in 1" << std::endl; + st_copy_2.print_tree(); + v1.clear(); + v2.clear(); + v1.push_back(4); + v2.push_back(3); + s1 = st_copy_3.find(v1); + s2 = st_copy_3.find(v2); + st_copy_3.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (4, 3) contracted, 4 being contracted in 3" << std::endl; + st_copy_3.print_tree(); } |