diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-01-07 15:22:47 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-01-07 15:22:47 +0000 |
commit | de4811fa72c90b38357bbddec3d2ea5b282642b3 (patch) | |
tree | b844f902c6a98d1c9dda74434245223e1d9a394c /src/Persistent_cohomology | |
parent | 0a5b697f959d673fd51d70058fd3fe90f7c15125 (diff) | |
parent | d91d9248c66451a765f58b6d03db2124b52c3ae2 (diff) |
Backmerge from trunk
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/tbb@953 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 06624ae4ed4031c7bae56e0b8fa305a318b934bc
Diffstat (limited to 'src/Persistent_cohomology')
11 files changed, 126 insertions, 28 deletions
diff --git a/src/Persistent_cohomology/concept/FilteredComplex.h b/src/Persistent_cohomology/concept/FilteredComplex.h index 1834903b..e124d524 100644 --- a/src/Persistent_cohomology/concept/FilteredComplex.h +++ b/src/Persistent_cohomology/concept/FilteredComplex.h @@ -65,9 +65,9 @@ struct FilteredComplex Simplex_key key ( Simplex_handle sh ); /** \brief Returns the simplex associated to a key. * - * If key is different from null_key(), there must be a unique - * simplex having this key. */ - Simplex_handle simplex ( Simplex_key key ); + * If key is different from null_key(), returns the simplex that + * has index idx in the filtration. */ + Simplex_handle simplex ( Simplex_key idx ); /** \brief Assign a key to a simplex. */ void assign_key(Simplex_handle sh, Simplex_key key); diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt index ea69352e..50d10025 100644 --- a/src/Persistent_cohomology/example/CMakeLists.txt +++ b/src/Persistent_cohomology/example/CMakeLists.txt @@ -5,6 +5,10 @@ project(GUDHIExPersCohom) add_definitions( -DBOOST_ALL_NO_LIB ) add_definitions( -DBOOST_ALL_DYN_LINK ) +add_executable(plain_homology plain_homology.cpp) +target_link_libraries(plain_homology ${Boost_SYSTEM_LIBRARY}) +add_test(plain_homology ${CMAKE_CURRENT_BINARY_DIR}/plain_homology) + add_executable(persistence_from_simple_simplex_tree persistence_from_simple_simplex_tree.cpp) target_link_libraries(persistence_from_simple_simplex_tree ${Boost_SYSTEM_LIBRARY}) add_test(persistence_from_simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_simple_simplex_tree 1 0) diff --git a/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp b/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp index 6d5eebcf..92c0b065 100644 --- a/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp +++ b/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp @@ -66,7 +66,8 @@ typedef Alpha_shape_3::Edge Edge_3; typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list; // gudhi type definition -typedef Simplex_tree<>::Vertex_handle Simplex_tree_vertex; +typedef Simplex_tree<Simplex_tree_options_fast_persistence> ST; +typedef ST::Vertex_handle Simplex_tree_vertex; typedef std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex > Alpha_shape_simplex_tree_map; typedef std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex> Alpha_shape_simplex_tree_pair; typedef std::vector< Simplex_tree_vertex > Simplex_tree_vector_vertex; @@ -184,7 +185,7 @@ int main(int argc, char * const argv[]) { // Loop on objects vector Vertex_list vertex_list; - Simplex_tree<> simplex_tree; + ST simplex_tree; Alpha_shape_simplex_tree_map map_cgal_simplex_tree; std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin(); int dim_max = 0; @@ -281,7 +282,7 @@ int main(int argc, char * const argv[]) { std::cout << "Simplex_tree dim: " << simplex_tree.dimension() << std::endl; // Compute the persistence diagram of the complex - Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(simplex_tree); + Persistent_cohomology< ST, Field_Zp > pcoh(simplex_tree); // initializes the coefficient field for homology pcoh.init_coefficients(coeff_field_characteristic); diff --git a/src/Persistent_cohomology/example/performance_rips_persistence.cpp b/src/Persistent_cohomology/example/performance_rips_persistence.cpp index fc48d6b1..b4d282ac 100644 --- a/src/Persistent_cohomology/example/performance_rips_persistence.cpp +++ b/src/Persistent_cohomology/example/performance_rips_persistence.cpp @@ -86,7 +86,7 @@ int main(int argc, char * argv[]) { std::cout << "Compute Rips graph in " << elapsed_sec << " ms.\n"; // Construct the Rips complex in a Simplex Tree - Simplex_tree<> st; + Simplex_tree<Simplex_tree_options_fast_persistence> st; start = std::chrono::system_clock::now(); // insert the proximity graph in the simplex tree diff --git a/src/Persistent_cohomology/example/persistence_from_file.cpp b/src/Persistent_cohomology/example/persistence_from_file.cpp index 8eb8d0f3..67235467 100644 --- a/src/Persistent_cohomology/example/persistence_from_file.cpp +++ b/src/Persistent_cohomology/example/persistence_from_file.cpp @@ -54,7 +54,7 @@ int main(int argc, char * argv[]) { << std::endl; std::cout << " - p=" << p << " - min_persistence=" << min_persistence << std::endl; - // Construct the Rips complex in a Simplex Tree + // Read the list of simplices from a file. Simplex_tree<> simplex_tree; std::ifstream simplex_tree_stream(simplex_tree_file); diff --git a/src/Persistent_cohomology/example/plain_homology.cpp b/src/Persistent_cohomology/example/plain_homology.cpp new file mode 100644 index 00000000..0a692717 --- /dev/null +++ b/src/Persistent_cohomology/example/plain_homology.cpp @@ -0,0 +1,84 @@ +/* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (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/>. + */ + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> + +using namespace Gudhi; + +/* We could perfectly well use the default Simplex_tree<> (which uses + * Simplex_tree_options_full_featured), the following simply demonstrates + * how to save on storage by not storing a filtration value. */ + +struct MyOptions : Simplex_tree_options_full_featured { + // Implicitly use 0 as filtration value for all simplices + static const bool store_filtration = false; + // The persistence algorithm needs this + static const bool store_key = true; + // I have few vertices + typedef short Vertex_handle; +}; +typedef Simplex_tree<MyOptions> ST; + +int main() { + ST st; + + /* Complex to build. */ + /* 1 3 */ + /* o---o */ + /* /X\ / */ + /* o---o o */ + /* 2 0 4 */ + + const short triangle012[] = {0, 1, 2}; + const short edge03[] = {0, 3}; + const short edge13[] = {1, 3}; + const short vertex4[] = {4}; + st.insert_simplex_and_subfaces(triangle012); + st.insert_simplex_and_subfaces(edge03); + st.insert_simplex(edge13); + st.insert_simplex(vertex4); + // FIXME: Remove this line + st.set_dimension(2); + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + + // Class for homology computation + persistent_cohomology::Persistent_cohomology<ST, persistent_cohomology::Field_Zp> pcoh(st); + + // Initialize the coefficient field Z/2Z for homology + pcoh.init_coefficients(2); + + // Compute the persistence diagram of the complex + pcoh.compute_persistent_cohomology(); + + // Print the result. The format is, on each line: 2 dim 0 inf + // where 2 represents the field, dim the dimension of the feature. + // 2 0 0 inf + // 2 0 0 inf + // 2 1 0 inf + // means that in Z/2Z-homology, the Betti numbers are b0=2 and b1=1. + pcoh.output_diagram(); +} diff --git a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp index 5277bf7a..c5cd775d 100644 --- a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp +++ b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp @@ -68,7 +68,8 @@ int main(int argc, char * argv[]) { , euclidean_distance<Point_t>); // Construct the Rips complex in a Simplex Tree - Simplex_tree<> st; + typedef Simplex_tree<Simplex_tree_options_fast_persistence> ST; + ST st; // insert the proximity graph in the simplex tree st.insert_graph(prox_graph); // expand the graph until dimension dim_max @@ -78,7 +79,7 @@ int main(int argc, char * argv[]) { st.initialize_filtration(); // Compute the persistence diagram of the complex - Persistent_cohomology< Simplex_tree<>, Multi_field > pcoh(st); + Persistent_cohomology<ST, Multi_field > pcoh(st); // initializes the coefficient field for homology pcoh.init_coefficients(min_p, max_p); // compute persistent homology, disgarding persistent features of life shorter than min_persistence diff --git a/src/Persistent_cohomology/example/rips_persistence.cpp b/src/Persistent_cohomology/example/rips_persistence.cpp index 9b1ef42f..2d926a0d 100644 --- a/src/Persistent_cohomology/example/rips_persistence.cpp +++ b/src/Persistent_cohomology/example/rips_persistence.cpp @@ -65,7 +65,8 @@ int main(int argc, char * argv[]) { , euclidean_distance<Point_t>); // Construct the Rips complex in a Simplex Tree - Simplex_tree<> st; + typedef Simplex_tree<Simplex_tree_options_fast_persistence> ST; + ST st; // insert the proximity graph in the simplex tree st.insert_graph(prox_graph); // expand the graph until dimension dim_max @@ -78,7 +79,7 @@ int main(int argc, char * argv[]) { st.initialize_filtration(); // Compute the persistence diagram of the complex - persistent_cohomology::Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(st); + persistent_cohomology::Persistent_cohomology<ST, Field_Zp > pcoh(st); // initializes the coefficient field for homology pcoh.init_coefficients(p); diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index d096792f..643b810c 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -27,7 +27,6 @@ #include <gudhi/Persistent_cohomology/Field_Zp.h> #include <gudhi/Simple_object_pool.h> -#include <boost/tuple/tuple.hpp> #include <boost/intrusive/set.hpp> #include <boost/pending/disjoint_sets.hpp> #include <boost/intrusive/list.hpp> @@ -223,7 +222,7 @@ class Persistent_cohomology { // Sparse column type for the annotation of the boundary of an element. typedef std::vector<std::pair<Simplex_key, Arith_element> > A_ds_type; // Persistent interval type. The Arith_element field is used for the multi-field framework. - typedef boost::tuple<Simplex_handle, Simplex_handle, Arith_element> Persistent_interval; + typedef std::tuple<Simplex_handle, Simplex_handle, Arith_element> Persistent_interval; /** \brief Initializes the Persistent_cohomology class. * @@ -431,9 +430,12 @@ class Persistent_cohomology { std::map<Simplex_key, Arith_element> & map_a_ds, Simplex_handle sigma, int dim_sigma) { // traverses the boundary of sigma, keeps track of the annotation vectors, - // with multiplicity, in a map. - std::map<Column *, int> annotations_in_boundary; - std::pair<typename std::map<Column *, int>::iterator, bool> result_insert_bound; + // with multiplicity. We used to sum the coefficients directly in + // annotations_in_boundary by using a map, we now do it later. + typedef std::pair<Column *, int> annotation_t; + // Danger: not thread-safe! + static std::vector<annotation_t> annotations_in_boundary; + annotations_in_boundary.clear(); int sign = 1 - 2 * (dim_sigma % 2); // \in {-1,1} provides the sign in the // alternate sum in the boundary. Simplex_key key; @@ -445,22 +447,29 @@ class Persistent_cohomology { // Find its annotation vector curr_col = ds_repr_[dsets_.find_set(key)]; if (curr_col != NULL) { // and insert it in annotations_in_boundary with multyiplicative factor "sign". - result_insert_bound = annotations_in_boundary.insert(std::pair<Column *, int>(curr_col, sign)); - if (!(result_insert_bound.second)) { - result_insert_bound.first->second += sign; - } + annotations_in_boundary.emplace_back(curr_col, sign); } } sign = -sign; } + // Place identical annotations consecutively so we can easily sum their multiplicities. + std::sort(annotations_in_boundary.begin(), annotations_in_boundary.end(), + [](annotation_t const& a, annotation_t const& b) { return a.first < b.first; }); + // Sum the annotations with multiplicity, using a map<key,coeff> // to represent a sparse vector. std::pair<typename std::map<Simplex_key, Arith_element>::iterator, bool> result_insert_a_ds; - for (auto ann_ref : annotations_in_boundary) { - if (ann_ref.second != coeff_field_.additive_identity()) { // For all columns in the boundary, - for (auto cell_ref : ann_ref.first->col_) { // insert every cell in map_a_ds with multiplicity - Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, ann_ref.second); // coefficient * multiplicity + for (auto ann_it = annotations_in_boundary.begin(); ann_it != annotations_in_boundary.end(); /**/) { + Column* col = ann_it->first; + int mult = ann_it->second; + while (++ann_it != annotations_in_boundary.end() && ann_it->first == col) { + mult += ann_it->second; + } + // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0. + if (mult != coeff_field_.additive_identity()) { // For all columns in the boundary, + for (auto cell_ref : col->col_) { // insert every cell in map_a_ds with multiplicity + Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, mult); // coefficient * multiplicity if (w_y != coeff_field_.additive_identity()) { // if != 0 result_insert_a_ds = map_a_ds.insert(std::pair<Simplex_key, Arith_element>(cell_ref.key_, w_y)); diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h index 0591fc95..38bc08d1 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h @@ -81,8 +81,7 @@ class Multi_field { // set m to primorial(bound_prime) prod_characteristics_ = 1; for (auto p : primes_) { - mpz_mul_ui(prod_characteristics_.get_mpz_t(), - prod_characteristics_.get_mpz_t(), p); + prod_characteristics_ *= p; } // Uvect_ diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h index 612658e6..5deb2d88 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h @@ -23,7 +23,6 @@ #ifndef PERSISTENT_COHOMOLOGY_PERSISTENT_COHOMOLOGY_COLUMN_H_ #define PERSISTENT_COHOMOLOGY_PERSISTENT_COHOMOLOGY_COLUMN_H_ -#include <boost/tuple/tuple.hpp> #include <boost/intrusive/set.hpp> #include <boost/intrusive/list.hpp> |