diff options
Diffstat (limited to 'src/Simplex_tree')
18 files changed, 155 insertions, 84 deletions
diff --git a/src/Simplex_tree/doc/COPYRIGHT b/src/Simplex_tree/doc/COPYRIGHT index 6cde9520..61f17f6d 100644 --- a/src/Simplex_tree/doc/COPYRIGHT +++ b/src/Simplex_tree/doc/COPYRIGHT @@ -1,19 +1,12 @@ -The files of this directory are part of the Gudhi Library. The Gudhi library -(Geometric Understanding in Higher Dimensions) is a generic C++ library for -computational topology. +The files of this directory are part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. +See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. -Author(s): Clément Maria +Author(s): Vincent Rouvreau Copyright (C) 2015 Inria -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 gives everyone the freedoms to use openFrameworks in any context: +commercial or non-commercial, public or private, open or closed source. -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/>. +You should have received a copy of the MIT License along with this program. +If not, see https://opensource.org/licenses/MIT.
\ No newline at end of file diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h index b01e3e92..800879fe 100644 --- a/src/Simplex_tree/doc/Intro_simplex_tree.h +++ b/src/Simplex_tree/doc/Intro_simplex_tree.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp index fb1a3a4c..d716fb1f 100644 --- a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp +++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Vincent Rouvreau * * Copyright (C) 2017 Inria diff --git a/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp index 8803dbb2..e455c426 100644 --- a/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp +++ b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Vincent Rouvreau * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp index 34bfd77c..494f8b1d 100644 --- a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp +++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Vincent Rouvreau * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/example/mini_simplex_tree.cpp b/src/Simplex_tree/example/mini_simplex_tree.cpp index 6370b508..bbc582c7 100644 --- a/src/Simplex_tree/example/mini_simplex_tree.cpp +++ b/src/Simplex_tree/example/mini_simplex_tree.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Marc Glisse * * Copyright (C) 2015 Inria diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp index 6a0a7fc0..4353939f 100644 --- a/src/Simplex_tree/example/simple_simplex_tree.cpp +++ b/src/Simplex_tree/example/simple_simplex_tree.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Vincent Rouvreau * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp b/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp index eb0282f2..f6dfa53c 100644 --- a/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp +++ b/src/Simplex_tree/example/simplex_tree_from_cliques_of_graph.cpp @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 76b789c4..fafdb01c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria @@ -755,7 +753,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 +763,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 +794,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/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h index 7b6dea0f..efccf2f2 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index 26bf0569..ae140859 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index d2b7d8d9..b53bad29 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h index 4df7833c..3e395ae2 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h @@ -1,7 +1,5 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Clément Maria * * Copyright (C) 2014 Inria diff --git a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp index e729cf00..c0615b12 100644 --- a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp @@ -1,3 +1,13 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + #include <iostream> #include <vector> #include <string> diff --git a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp index 19ce3321..fab25eb8 100644 --- a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp @@ -1,3 +1,13 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + #include <iostream> #include <fstream> #include <string> diff --git a/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp index ecb9f025..28c29489 100644 --- a/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp @@ -1,3 +1,13 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + #include <iostream> #define BOOST_TEST_DYN_LINK diff --git a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp index dc37375c..97347992 100644 --- a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp @@ -1,3 +1,13 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + #include <iostream> #define BOOST_TEST_DYN_LINK diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index b27bbce8..58bfa8db 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -1,11 +1,22 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + #include <iostream> #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 +932,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); + +} |