summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorVincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com>2019-08-09 13:56:53 +0200
committerGitHub <noreply@github.com>2019-08-09 13:56:53 +0200
commitc3e26b923680c1ed82369382dbe46cadb2385c53 (patch)
treef99b8160b27fbf15bbd20f3305075200e617c687
parentb8b39d8411f4dfd1fc2a113a473b3f31cda9bb34 (diff)
parent642c4d7dcfca0d28bfed72448bc03502228af6da (diff)
Merge pull request #60 from GUDHI/simplex_tree_insert_duplicated_vertices_fix_vincent
Simplex tree insert duplicated vertices fix vincent
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree.h33
-rw-r--r--src/Simplex_tree/test/simplex_tree_unit_test.cpp63
2 files changed, 74 insertions, 22 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 76b789c4..14b27610 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -755,7 +755,7 @@ class Simplex_tree {
auto last = std::end(Nsimplex);
if (first == last)
- return { null_simplex(), true }; // ----->>
+ return { null_simplex(), true }; // FIXME: false would make more sense to me.
// Copy before sorting
// Thread local is not available on XCode version < V.8 - It will slow down computation
@@ -765,31 +765,26 @@ class Simplex_tree {
std::vector<Vertex_handle> copy;
copy.clear();
copy.insert(copy.end(), first, last);
- std::sort(std::begin(copy), std::end(copy));
+ std::sort(copy.begin(), copy.end());
+ auto last_unique = std::unique(copy.begin(), copy.end());
+ copy.erase(last_unique, copy.end());
GUDHI_CHECK_code(
for (Vertex_handle v : copy)
GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
)
+ // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
+ dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
- return insert_simplex_and_subfaces_sorted(copy, filtration);
+ return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
}
private:
- /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted
- template<class ForwardVertexRange = std::initializer_list<Vertex_handle>>
- std::pair<Simplex_handle, bool> insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex, Filtration_value filt = 0) {
- auto first = std::begin(Nsimplex);
- auto last = std::end(Nsimplex);
- if (first == last)
- return { null_simplex(), true }; // FIXME: false would make more sense to me.
- GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order");
- // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
- dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(first, last)) - 1);
- return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt);
- }
// To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
template<class ForwardVertexIterator>
- std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib, ForwardVertexIterator first, ForwardVertexIterator last, Filtration_value filt) {
+ std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
+ ForwardVertexIterator first,
+ ForwardVertexIterator last,
+ Filtration_value filt) {
// An alternative strategy would be:
// - try to find the complete simplex, if found (and low filtration) exit
// - insert all the vertices at once in sib
@@ -801,10 +796,10 @@ class Simplex_tree {
bool one_is_new = insertion_result.second;
if (!one_is_new) {
if (filtration(simplex_one) > filt) {
- assign_filtration(simplex_one, filt);
+ assign_filtration(simplex_one, filt);
} else {
- // FIXME: this interface makes no sense, and it doesn't seem to be tested.
- insertion_result.first = null_simplex();
+ // FIXME: this interface makes no sense, and it doesn't seem to be tested.
+ insertion_result.first = null_simplex();
}
}
if (++first == last) return insertion_result;
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index b27bbce8..f2a5d54d 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -2,10 +2,11 @@
#include <fstream>
#include <string>
#include <algorithm>
-#include <utility> // std::pair, std::make_pair
-#include <cmath> // float comparison
+#include <utility> // std::pair, std::make_pair
+#include <cmath> // float comparison
#include <limits>
-#include <functional> // greater
+#include <functional> // greater
+#include <tuple> // std::tie
#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE "simplex_tree"
@@ -921,3 +922,59 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_va
BOOST_CHECK(st1 == st2);
}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested_variants) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST INSERT DUPLICATED VERTICES" << std::endl;
+ typeST st;
+
+ typename typeST::Simplex_handle sh;
+ bool success = false;
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({1});
+ BOOST_CHECK(success);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+ BOOST_CHECK(st.dimension(sh) == 0);
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 2});
+ BOOST_CHECK(success);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+ BOOST_CHECK(st.dimension(sh) == 0);
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({3, 3, 3});
+ BOOST_CHECK(success);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+ BOOST_CHECK(st.dimension(sh) == 0);
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({4, 4, 4, 4});
+ BOOST_CHECK(success);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+ BOOST_CHECK(st.dimension(sh) == 0);
+
+ std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+ << " - num_simplices = " << st.num_simplices() << std::endl;
+ BOOST_CHECK(st.dimension() == 0);
+ BOOST_CHECK(st.num_simplices() == st.num_vertices());
+
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({2, 1, 1, 2});
+ BOOST_CHECK(success);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "st.dimension(sh)= " << st.dimension(sh) << std::endl;
+ BOOST_CHECK(st.dimension(sh) == 1);
+
+ std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+ << " - num_simplices = " << st.num_simplices() << std::endl;
+ BOOST_CHECK(st.dimension() == 1);
+ BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1);
+
+ // Already inserted
+ std::tie(sh, success) = st.insert_simplex_and_subfaces({1, 2, 2, 1});
+ BOOST_CHECK(!success);
+ BOOST_CHECK(sh == st.null_simplex());
+
+ std::cout << "dimension =" << st.dimension() << " - num_vertices = " << st.num_vertices()
+ << " - num_simplices = " << st.num_simplices() << std::endl;
+ BOOST_CHECK(st.dimension() == 1);
+ BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1);
+
+}