From 0e17d3cc8b89fc9fae4f358bb6a8cedaeaff6f0b Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 14 Feb 2019 14:32:14 +0000 Subject: Fix of duplicated vertices in list. Modify dimension computation. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/simplex_tree_insert_duplicated_vertices_fix_vincent@4107 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e6ac9ee4c9d34e59c07d9f5b16b13b5151608009 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 36 +++++++++++++++++++-------- 1 file changed, 25 insertions(+), 11 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 4b18651c..6bb42037 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -787,19 +787,22 @@ class Simplex_tree { private: /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted template> - std::pair insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex, Filtration_value filt = 0) { + std::pair 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(std::distance(first, last)) - 1); - return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt); + return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt, 0); } // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. template - std::pair rec_insert_simplex_and_subfaces_sorted(Siblings* sib, ForwardVertexIterator first, ForwardVertexIterator last, Filtration_value filt) { + std::pair rec_insert_simplex_and_subfaces_sorted(Siblings* sib, + ForwardVertexIterator first, + ForwardVertexIterator last, + Filtration_value filt, + int dimension) { // 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 @@ -811,19 +814,30 @@ 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; + // Next iteration to avoid consecutive equal values + while ((vertex_one == *first) && (first < last)) { + ++first; + } + // End of insertion + if (first == last) { + dimension_ = (std::max)(dimension_, dimension); + return insertion_result; + } if (!has_children(simplex_one)) // TODO: have special code here, we know we are building the whole subtree from scratch. simplex_one->second.assign_children(new Siblings(sib, vertex_one)); - auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt); + ++dimension; + auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt, dimension); // No need to continue if the full simplex was already there with a low enough filtration value. - if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt); + if (res.first != null_simplex()) { + rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt, dimension); + } return res; } -- cgit v1.2.3 From e6676dce1b5faa2c61707968e1e0588e5c47edbf Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 27 Jun 2019 17:47:58 +0200 Subject: code review: test if first!=last before dereferencing first --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 80d8dfb9..519703e6 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -821,7 +821,7 @@ class Simplex_tree { } } // Next iteration to avoid consecutive equal values - while ((vertex_one == *first) && (first < last)) { + while ((first < last) && (vertex_one == *first)) { ++first; } // End of insertion -- cgit v1.2.3 From 6aee9ea232820f3fefd3cfd8d194834c4ed9fd22 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 27 Jun 2019 18:45:50 +0200 Subject: Code review : call std::unique right after std::sort. Repetition has been removed --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 519703e6..9d6e50c6 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -775,27 +775,18 @@ class Simplex_tree { std::vector 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"); ) - return insert_simplex_and_subfaces_sorted(copy, filtration); + return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration, 0); } private: - /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted - template> - std::pair 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"); - return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt, 0); - } // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. template std::pair rec_insert_simplex_and_subfaces_sorted(Siblings* sib, -- cgit v1.2.3 From 4b5f5c47e681a92f85d390cc5763f39a033ba354 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 28 Jun 2019 16:11:49 +0200 Subject: We can now roll back rec_insert_simplex_and_subfaces_sorted and dimension computation --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 28 +++++++++------------------ 1 file changed, 9 insertions(+), 19 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 9d6e50c6..f1697955 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -782,18 +782,19 @@ class Simplex_tree { 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(std::distance(copy.begin(), copy.end())) - 1); - return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration, 0); + return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration); } private: // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. template std::pair rec_insert_simplex_and_subfaces_sorted(Siblings* sib, - ForwardVertexIterator first, - ForwardVertexIterator last, - Filtration_value filt, - int dimension) { + 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 @@ -811,24 +812,13 @@ class Simplex_tree { insertion_result.first = null_simplex(); } } - // Next iteration to avoid consecutive equal values - while ((first < last) && (vertex_one == *first)) { - ++first; - } - // End of insertion - if (first == last) { - dimension_ = (std::max)(dimension_, dimension); - return insertion_result; - } + if (++first == last) return insertion_result; if (!has_children(simplex_one)) // TODO: have special code here, we know we are building the whole subtree from scratch. simplex_one->second.assign_children(new Siblings(sib, vertex_one)); - ++dimension; - auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt, dimension); + auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt); // No need to continue if the full simplex was already there with a low enough filtration value. - if (res.first != null_simplex()) { - rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt, dimension); - } + if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt); return res; } -- cgit v1.2.3 From 642c4d7dcfca0d28bfed72448bc03502228af6da Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 28 Jun 2019 17:12:26 +0200 Subject: Code review: Keep the comment that returning true is strange --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index f1697955..f7bb720c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -765,7 +765,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 -- cgit v1.2.3