From 3d5bf7ed64b155894787cb356aead439977643e4 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 22 Sep 2016 14:38:46 +0000 Subject: New template function create_complex for Alpha_complex to create the simplicial complex git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alpha_complex_create_complex@1540 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 24e53dc58d158166b976dd09760ad0e2acaf8e36 --- src/Alpha_complex/doc/Intro_alpha_complex.h | 36 ++- src/Alpha_complex/doc/alpha_complex_doc.ipe | 315 +-------------------- src/Alpha_complex/doc/alpha_complex_doc.png | Bin 25554 -> 18720 bytes .../example/Alpha_complex_from_off.cpp | 40 +-- .../example/Alpha_complex_from_points.cpp | 38 +-- src/Alpha_complex/include/gudhi/Alpha_complex.h | 139 ++++----- src/Alpha_complex/test/Alpha_complex_unit_test.cpp | 116 ++++---- .../example/alpha_complex_persistence.cpp | 63 +++-- .../example/custom_persistence_sort.cpp | 89 +++--- 9 files changed, 293 insertions(+), 543 deletions(-) diff --git a/src/Alpha_complex/doc/Intro_alpha_complex.h b/src/Alpha_complex/doc/Intro_alpha_complex.h index f3126169..4ca3271b 100644 --- a/src/Alpha_complex/doc/Intro_alpha_complex.h +++ b/src/Alpha_complex/doc/Intro_alpha_complex.h @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2015 INRIA Saclay (France) + * 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 @@ -39,7 +39,8 @@ namespace alpha_complex { * Alpha_complex is a simplicial complex * constructed from the finite cells of a Delaunay Triangulation. * - * The filtration value of each simplex is computed as the square of the circumradius of the simplex if the circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration + * The filtration value of each simplex is computed as the square of the circumradius of the simplex if the + * circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration * values of the codimension 1 cofaces that make it not Gabriel otherwise. * * All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into @@ -47,23 +48,24 @@ namespace alpha_complex { * * \image html "alpha_complex_representation.png" "Alpha-complex representation" * - * Alpha_complex is constructing a `Simplex_tree` using Delaunay Triangulation * \cite cgal:hdj-t-15b from CGAL (the Computational Geometry - * Algorithms Library \cite cgal:eb-15b). + * Algorithms Library \cite cgal:eb-15b) and is able to create a `Simplicial_complex_for_alpha`. * * The complex is a template class requiring an Epick_d dD Geometry Kernel * \cite cgal:s-gkd-15b from CGAL as template parameter. * - * \remark When Alpha_complex is constructed with an infinite value of alpha, the complex is a Delaunay complex. + * \remark When the simplicial complex is constructed with an infinite value of alpha, the complex is a Delaunay + * complex. * * \section pointsexample Example from points * - * This example builds the Delaunay triangulation from the given points in a 2D static kernel, and initializes the - * alpha complex with it. + * This example builds the Delaunay triangulation from the given points in a 2D static kernel, and creates a + * `Simplex_tree` with it. * - * Then, it is asked to display information about the alpha complex. + * Then, it is asked to display information about the simplicial complex. * * \include Alpha_complex/Alpha_complex_from_points.cpp * @@ -76,13 +78,15 @@ namespace alpha_complex { * * \include Alpha_complex/alphaoffreader_for_doc_60.txt * - * \section algorithm Algorithm + * \section createcomplexalgorithm Create complex algorithm * * \subsection datastructure Data structure * - * In order to build the alpha complex, first, a Simplex tree is built from the cells of a Delaunay Triangulation. - * (The filtration value is set to NaN, which stands for unknown value): - * \image html "alpha_complex_doc.png" "Simplex tree structure construction example" + * In order to create the simplicial complex, first, it is built from the cells of the Delaunay Triangulation. + * The filtration values are set to NaN, which stands for unknown value. + * + * In example, : + * \image html "alpha_complex_doc.png" "Simplicial complex structure construction example" * * \subsection filtrationcomputation Filtration value computation algorithm * @@ -129,12 +133,14 @@ namespace alpha_complex { * * \subsubsection nondecreasing Non decreasing filtration values * - * As the squared radii computed by CGAL are an approximation, it might happen that these alpha squared values do not quite define a proper filtration (i.e. non-decreasing with respect to inclusion). - * We fix that up by calling `Simplex_tree::make_filtration_non_decreasing()`. + * As the squared radii computed by CGAL are an approximation, it might happen that these alpha squared values do not + * quite define a proper filtration (i.e. non-decreasing with respect to inclusion). + * We fix that up by calling `Simplicial_complex_for_alpha::make_filtration_non_decreasing()`. * * \subsubsection pruneabove Prune above given filtration value * - * The simplex tree is pruned from the given maximum alpha squared value (cf. `Simplex_tree::prune_above_filtration()`). + * The simplex tree is pruned from the given maximum alpha squared value (cf. + * `Simplicial_complex_for_alpha::prune_above_filtration()`). * In the following example, the value is given by the user as argument of the program. * * diff --git a/src/Alpha_complex/doc/alpha_complex_doc.ipe b/src/Alpha_complex/doc/alpha_complex_doc.ipe index baf0d26a..71e5ce6c 100644 --- a/src/Alpha_complex/doc/alpha_complex_doc.ipe +++ b/src/Alpha_complex/doc/alpha_complex_doc.ipe @@ -1,7 +1,7 @@ - + @@ -278,35 +278,7 @@ h 320 580 l 280 660 l - -4 0 0 4 320 704 e - - -322.919 706.788 m -317.189 701.058 l -317.189 701.203 l - - -317.551 706.934 m -322.629 701.058 l - - -240 620 m -220 600 l - - -240 620 m -220 640 l - -Simplex tree structure - -280 630 m -170 630 l - - -280 610 m -170 610 l - +Simplicial complex data structure : @@ -314,282 +286,11 @@ h -2 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -2 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -4 -1 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -4 -3 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -2 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -3 -6 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -4 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 -6 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -5 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -292 716 m -292 728 l -316 728 l -316 716 l -h - - -316 716 m -316 728 l -340 728 l -340 716 l -h - - -340 716 m -340 728 l -364 728 l -364 716 l -h - - -364 716 m -364 728 l -388 728 l -388 716 l -h - - -388 716 m -388 728 l -412 728 l -412 716 l -h - - -412 716 m -412 728 l -436 728 l -436 716 l -h - - -436 716 m -436 728 l -460 728 l -460 716 l -h - -0 -1 -2 -3 -4 -5 -6 - -436 708 m -436 716 l - - -364 708 m -364 716 l - - -364 688 m -364 696 l - - -320 688 m -320 696 l - - -296 708 m -308 716 l -308 716 l - - -264 688 m -268 696 l - - -292 688 m -292 696 l - - -388 736 m -388 728 l - - -372 612 m -376 620 l - - -448 612 m -448 620 l - -3 - -300 688 m -300 676 l -312 676 l -312 688 l -h - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -364 688 m -364 696 l - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -436 708 m -436 716 l - - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -300 688 m -300 676 l -312 676 l -312 688 l -h - -6 - -436 708 m -436 716 l - +insert simplex and subfaces [0,1,2] +insert simplex and subfaces [1,2,3] +insert simplex and subfaces [0,2,4] +insert simplex and subfaces [2,3,6] +insert simplex and subfaces [2,4,6] +insert simplex and subfaces [4,5,6] diff --git a/src/Alpha_complex/doc/alpha_complex_doc.png b/src/Alpha_complex/doc/alpha_complex_doc.png index 0b6201da..170bae80 100644 Binary files a/src/Alpha_complex/doc/alpha_complex_doc.png and b/src/Alpha_complex/doc/alpha_complex_doc.png differ diff --git a/src/Alpha_complex/example/Alpha_complex_from_off.cpp b/src/Alpha_complex/example/Alpha_complex_from_off.cpp index 7836d59a..31f8e10c 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_off.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_off.cpp @@ -1,4 +1,7 @@ #include +// to construct a simplex_tree from alpha complex +#include + #include #include @@ -21,7 +24,7 @@ int main(int argc, char **argv) { // Init of an alpha complex from an OFF file // ---------------------------------------------------------------------------- typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; - Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_name, alpha_square_max_value); + Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_name); std::streambuf* streambufffer; std::ofstream ouput_file_stream; @@ -33,23 +36,26 @@ int main(int argc, char **argv) { streambufffer = std::cout.rdbuf(); } - std::ostream output_stream(streambufffer); - - // ---------------------------------------------------------------------------- - // Display information about the alpha complex - // ---------------------------------------------------------------------------- - output_stream << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << - " - " << alpha_complex_from_file.num_simplices() << " simplices - " << - alpha_complex_from_file.num_vertices() << " vertices." << std::endl; - - output_stream << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; - for (auto f_simplex : alpha_complex_from_file.filtration_simplex_range()) { - output_stream << " ( "; - for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { - output_stream << vertex << " "; + Gudhi::Simplex_tree<> simplex; + if (alpha_complex_from_file.create_complex(simplex, alpha_square_max_value)) { + std::ostream output_stream(streambufffer); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + output_stream << "Alpha complex is of dimension " << simplex.dimension() << + " - " << simplex.num_simplices() << " simplices - " << + simplex.num_vertices() << " vertices." << std::endl; + + output_stream << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : simplex.filtration_simplex_range()) { + output_stream << " ( "; + for (auto vertex : simplex.simplex_vertex_range(f_simplex)) { + output_stream << vertex << " "; + } + output_stream << ") -> " << "[" << simplex.filtration(f_simplex) << "] "; + output_stream << std::endl; } - output_stream << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; - output_stream << std::endl; } ouput_file_stream.close(); return 0; diff --git a/src/Alpha_complex/example/Alpha_complex_from_points.cpp b/src/Alpha_complex/example/Alpha_complex_from_points.cpp index 49f77276..fa3c1efc 100644 --- a/src/Alpha_complex/example/Alpha_complex_from_points.cpp +++ b/src/Alpha_complex/example/Alpha_complex_from_points.cpp @@ -1,5 +1,8 @@ -#include #include +// to construct a simplex_tree from alpha complex +#include + +#include #include #include @@ -40,23 +43,26 @@ int main(int argc, char **argv) { // ---------------------------------------------------------------------------- // Init of an alpha complex from the list of points // ---------------------------------------------------------------------------- - Gudhi::alpha_complex::Alpha_complex alpha_complex_from_points(points, alpha_square_max_value); + Gudhi::alpha_complex::Alpha_complex alpha_complex_from_points(points); - // ---------------------------------------------------------------------------- - // Display information about the alpha complex - // ---------------------------------------------------------------------------- - std::cout << "Alpha complex is of dimension " << alpha_complex_from_points.dimension() << - " - " << alpha_complex_from_points.num_simplices() << " simplices - " << - alpha_complex_from_points.num_vertices() << " vertices." << std::endl; - - std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; - for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { - std::cout << " ( "; - for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) { - std::cout << vertex << " "; + Gudhi::Simplex_tree<> simplex; + if (alpha_complex_from_points.create_complex(simplex, alpha_square_max_value)) { + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Alpha complex is of dimension " << simplex.dimension() << + " - " << simplex.num_simplices() << " simplices - " << + simplex.num_vertices() << " vertices." << std::endl; + + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : simplex.filtration_simplex_range()) { + std::cout << " ( "; + for (auto vertex : simplex.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << ") -> " << "[" << simplex.filtration(f_simplex) << "] "; + std::cout << std::endl; } - std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] "; - std::cout << std::endl; } return 0; } diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 2c95ceb4..66a55ac7 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2015 INRIA Saclay (France) + * 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 @@ -23,9 +23,6 @@ #ifndef ALPHA_COMPLEX_H_ #define ALPHA_COMPLEX_H_ -// to construct a simplex_tree from Delaunay_triangulation -#include -#include #include // to construct Alpha_complex from a OFF file of points #include @@ -74,7 +71,7 @@ namespace alpha_complex { * */ template> -class Alpha_complex : public Simplex_tree<> { +class Alpha_complex { public: // Add an int in TDS to save point index in the structure typedef CGAL::Triangulation_data_structure { typedef Kernel Geom_traits; private: - // From Simplex_tree - // Type required to insert into a simplex_tree (with or without subfaces). - typedef std::vector Vector_vertex; - - // Simplex_result is the type returned from simplex_tree insert function. - typedef typename std::pair Simplex_result; - typedef typename Kernel::Compute_squared_radius_d Squared_Radius; typedef typename Kernel::Side_of_bounded_sphere_d Is_Gabriel; typedef typename Kernel::Point_dimension_d Point_Dimension; @@ -111,7 +101,7 @@ class Alpha_complex : public Simplex_tree<> { typedef typename Delaunay_triangulation::size_type size_type; // Map type to switch from simplex tree vertex handle to CGAL vertex iterator. - typedef typename std::map< Vertex_handle, CGAL_vertex_iterator > Vector_vertex_iterator; + typedef typename std::map< std::size_t, CGAL_vertex_iterator > Vector_vertex_iterator; private: /** \brief Vertex iterator vector to switch from simplex tree vertex handle to CGAL vertex iterator. @@ -130,10 +120,8 @@ class Alpha_complex : public Simplex_tree<> { * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. * * @param[in] off_file_name OFF file [path and] name. - * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. */ - Alpha_complex(const std::string& off_file_name, - Filtration_value max_alpha_square = std::numeric_limits::infinity()) + Alpha_complex(const std::string& off_file_name) : triangulation_(nullptr) { Gudhi::Points_off_reader off_reader(off_file_name); if (!off_reader.is_valid()) { @@ -141,7 +129,7 @@ class Alpha_complex : public Simplex_tree<> { exit(-1); // ----- >> } - init_from_range(off_reader.get_point_cloud(), max_alpha_square); + init_from_range(off_reader.get_point_cloud()); } /** \brief Alpha_complex constructor from a list of points. @@ -149,7 +137,6 @@ class Alpha_complex : public Simplex_tree<> { * Duplicate points are inserted once in the Alpha_complex. This is the reason why the vertices may be not contiguous. * * @param[in] points Range of points to triangulate. Points must be in Kernel::Point_d - * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. * * The type InputPointRange must be a range for which std::begin and * std::end return input iterators on a Kernel::Point_d. @@ -157,10 +144,9 @@ class Alpha_complex : public Simplex_tree<> { * @post Compare num_simplices with InputPointRange points number (not the same in case of duplicate points). */ template - Alpha_complex(const InputPointRange& points, - Filtration_value max_alpha_square = std::numeric_limits::infinity()) + Alpha_complex(const InputPointRange& points) : triangulation_(nullptr) { - init_from_range(points, max_alpha_square); + init_from_range(points); } /** \brief Alpha_complex destructor. @@ -183,13 +169,13 @@ class Alpha_complex : public Simplex_tree<> { * @return The point found. * @exception std::out_of_range In case vertex is not found (cf. std::vector::at). */ - Point_d get_point(Vertex_handle vertex) const { + Point_d get_point(std::size_t vertex) const { return vertex_handle_to_iterator_.at(vertex)->point(); } private: template - void init_from_range(const InputPointRange& points, Filtration_value max_alpha_square) { + void init_from_range(const InputPointRange& points) { auto first = std::begin(points); auto last = std::end(points); if (first != last) { @@ -216,38 +202,54 @@ class Alpha_complex : public Simplex_tree<> { pos->data() = index; hint = pos->full_cell(); } - init(max_alpha_square); } } - /** \brief Initialize the Alpha_complex from the Delaunay triangulation. + public: + template + bool create_complex(Simplicial_complex& complex) { + typedef typename Simplicial_complex::Filtration_value Filtration_value; + return create_complex(complex, std::numeric_limits::infinity()); + } + + /** \brief Initialize the simplicial complex from the Delaunay triangulation. * - * @param[in] max_alpha_square maximum for alpha square value. + * \tparam Simplicial_complex must meet Simplicial_complex_for_alpha concept. + * + * @param[in] complex Simplicial_complex to be created. + * @param[in] max_alpha_square maximum for alpha square value. Default value is +\f$\infty\f$. + * + * @return true if creation succeeds, false otherwise. * * @warning Delaunay triangulation must be already constructed with at least one vertex and dimension must be more * than 0. * * Initialization can be launched once. */ - void init(Filtration_value max_alpha_square) { + template + bool create_complex(Simplicial_complex& complex, Filtration_value max_alpha_square) { + // From Simplicial_complex type required to insert into a simplicial complex (with or without subfaces). + typedef typename Simplicial_complex::Vertex_handle Vertex_handle; + typedef std::vector Vector_vertex; + if (triangulation_ == nullptr) { - std::cerr << "Alpha_complex init - Cannot init from a NULL triangulation\n"; - return; // ----- >> + std::cerr << "Alpha_complex cannot create_complex from a NULL triangulation\n"; + return false; // ----- >> } if (triangulation_->number_of_vertices() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a triangulation without vertices\n"; - return; // ----- >> + std::cerr << "Alpha_complex cannot create_complex from a triangulation without vertices\n"; + return false; // ----- >> } if (triangulation_->maximal_dimension() < 1) { - std::cerr << "Alpha_complex init - Cannot init from a zero-dimension triangulation\n"; - return; // ----- >> + std::cerr << "Alpha_complex cannot create_complex from a zero-dimension triangulation\n"; + return false; // ----- >> } - if (num_vertices() > 0) { - std::cerr << "Alpha_complex init - Cannot init twice\n"; - return; // ----- >> + if (complex.num_vertices() > 0) { + std::cerr << "Alpha_complex create_complex - complex is not empty\n"; + return false; // ----- >> } - - set_dimension(triangulation_->maximal_dimension()); + + complex.set_dimension(triangulation_->maximal_dimension()); // -------------------------------------------------------------------------------------------- // double map to retrieve simplex tree vertex handles from CGAL vertex iterator and vice versa @@ -282,7 +284,7 @@ class Alpha_complex : public Simplex_tree<> { std::cout << std::endl; #endif // DEBUG_TRACES // Insert each simplex and its subfaces in the simplex tree - filtration is NaN - insert_simplex_and_subfaces(vertexVector, std::numeric_limits::quiet_NaN()); + complex.insert_simplex_and_subfaces(vertexVector, std::numeric_limits::quiet_NaN()); } // -------------------------------------------------------------------------------------------- @@ -290,16 +292,16 @@ class Alpha_complex : public Simplex_tree<> { // Will be re-used many times Vector_of_CGAL_points pointVector; // ### For i : d -> 0 - for (int decr_dim = dimension(); decr_dim >= 0; decr_dim--) { + for (int decr_dim = complex.dimension(); decr_dim >= 0; decr_dim--) { // ### Foreach Sigma of dim i - for (auto f_simplex : skeleton_simplex_range(decr_dim)) { - int f_simplex_dim = dimension(f_simplex); + for (auto f_simplex : complex.skeleton_simplex_range(decr_dim)) { + int f_simplex_dim = complex.dimension(f_simplex); if (decr_dim == f_simplex_dim) { pointVector.clear(); #ifdef DEBUG_TRACES std::cout << "Sigma of dim " << decr_dim << " is"; #endif // DEBUG_TRACES - for (auto vertex : simplex_vertex_range(f_simplex)) { + for (auto vertex : complex.simplex_vertex_range(f_simplex)) { pointVector.push_back(get_point(vertex)); #ifdef DEBUG_TRACES std::cout << " " << vertex; @@ -309,7 +311,7 @@ class Alpha_complex : public Simplex_tree<> { std::cout << std::endl; #endif // DEBUG_TRACES // ### If filt(Sigma) is NaN : filt(Sigma) = alpha(Sigma) - if (std::isnan(filtration(f_simplex))) { + if (std::isnan(complex.filtration(f_simplex))) { Filtration_value alpha_complex_filtration = 0.0; // No need to compute squared_radius on a single point - alpha is 0.0 if (f_simplex_dim > 0) { @@ -318,12 +320,12 @@ class Alpha_complex : public Simplex_tree<> { alpha_complex_filtration = squared_radius(pointVector.begin(), pointVector.end()); } - assign_filtration(f_simplex, alpha_complex_filtration); + complex.assign_filtration(f_simplex, alpha_complex_filtration); #ifdef DEBUG_TRACES - std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << filtration(f_simplex) << std::endl; + std::cout << "filt(Sigma) is NaN : filt(Sigma) =" << complex.filtration(f_simplex) << std::endl; #endif // DEBUG_TRACES } - propagate_alpha_filtration(f_simplex, decr_dim); + propagate_alpha_filtration(complex, f_simplex, decr_dim); } } } @@ -331,36 +333,45 @@ class Alpha_complex : public Simplex_tree<> { // -------------------------------------------------------------------------------------------- // As Alpha value is an approximation, we have to make filtration non decreasing while increasing the dimension - bool modified_filt = make_filtration_non_decreasing(); + bool modified_filt = complex.make_filtration_non_decreasing(); // Remove all simplices that have a filtration value greater than max_alpha_square // Remark: prune_above_filtration does not require initialize_filtration to be done before. - modified_filt |= prune_above_filtration(max_alpha_square); + modified_filt |= complex.prune_above_filtration(max_alpha_square); if (modified_filt) { - initialize_filtration(); + complex.initialize_filtration(); } // -------------------------------------------------------------------------------------------- + return true; } - template - void propagate_alpha_filtration(Simplex_handle f_simplex, int decr_dim) { + private: + template + void propagate_alpha_filtration(Simplicial_complex& complex, Simplex_handle f_simplex, int decr_dim) { + // From Simplicial_complex type required to assign filtration values. + typedef typename Simplicial_complex::Filtration_value Filtration_value; +#ifdef DEBUG_TRACES + typedef typename Simplicial_complex::Vertex_handle Vertex_handle; +#endif // DEBUG_TRACES + // ### Foreach Tau face of Sigma - for (auto f_boundary : boundary_simplex_range(f_simplex)) { + for (auto f_boundary : complex.boundary_simplex_range(f_simplex)) { #ifdef DEBUG_TRACES std::cout << " | --------------------------------------------------\n"; std::cout << " | Tau "; - for (auto vertex : simplex_vertex_range(f_boundary)) { + for (auto vertex : complex.simplex_vertex_range(f_boundary)) { std::cout << vertex << " "; } std::cout << "is a face of Sigma\n"; - std::cout << " | isnan(filtration(Tau)=" << std::isnan(filtration(f_boundary)) << std::endl; + std::cout << " | isnan(complex.filtration(Tau)=" << std::isnan(complex.filtration(f_boundary)) << std::endl; #endif // DEBUG_TRACES // ### If filt(Tau) is not NaN - if (!std::isnan(filtration(f_boundary))) { + if (!std::isnan(complex.filtration(f_boundary))) { // ### filt(Tau) = fmin(filt(Tau), filt(Sigma)) - Filtration_value alpha_complex_filtration = fmin(filtration(f_boundary), filtration(f_simplex)); - assign_filtration(f_boundary, alpha_complex_filtration); + Filtration_value alpha_complex_filtration = fmin(complex.filtration(f_boundary), + complex.filtration(f_simplex)); + complex.assign_filtration(f_boundary, alpha_complex_filtration); #ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << filtration(f_boundary) << std::endl; + std::cout << " | filt(Tau) = fmin(filt(Tau), filt(Sigma)) = " << complex.filtration(f_boundary) << std::endl; #endif // DEBUG_TRACES // ### Else } else { @@ -372,12 +383,12 @@ class Alpha_complex : public Simplex_tree<> { #ifdef DEBUG_TRACES Vertex_handle vertexForGabriel = Vertex_handle(); #endif // DEBUG_TRACES - for (auto vertex : simplex_vertex_range(f_boundary)) { + for (auto vertex : complex.simplex_vertex_range(f_boundary)) { pointVector.push_back(get_point(vertex)); } // Retrieve the Sigma point that is not part of Tau - parameter for is_gabriel function Point_d point_for_gabriel; - for (auto vertex : simplex_vertex_range(f_simplex)) { + for (auto vertex : complex.simplex_vertex_range(f_simplex)) { point_for_gabriel = get_point(vertex); if (std::find(pointVector.begin(), pointVector.end(), point_for_gabriel) == pointVector.end()) { #ifdef DEBUG_TRACES @@ -398,10 +409,10 @@ class Alpha_complex : public Simplex_tree<> { // ### If Tau is not Gabriel of Sigma if (false == is_gab) { // ### filt(Tau) = filt(Sigma) - Filtration_value alpha_complex_filtration = filtration(f_simplex); - assign_filtration(f_boundary, alpha_complex_filtration); + Filtration_value alpha_complex_filtration = complex.filtration(f_simplex); + complex.assign_filtration(f_boundary, alpha_complex_filtration); #ifdef DEBUG_TRACES - std::cout << " | filt(Tau) = filt(Sigma) = " << filtration(f_boundary) << std::endl; + std::cout << " | filt(Tau) = filt(Sigma) = " << complex.filtration(f_boundary) << std::endl; #endif // DEBUG_TRACES } } diff --git a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp index 4d7bf622..0d4132f8 100644 --- a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -33,6 +33,9 @@ #include #include +// to construct a simplex_tree from Delaunay_triangulation +#include +#include // Use dynamic_dimension_tag for the user to be able to set dimension typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel_d; @@ -49,47 +52,35 @@ BOOST_AUTO_TEST_CASE(ALPHA_DOC_OFF_file) { std::cout << "========== OFF FILE NAME = " << off_file_name << " - alpha²=" << max_alpha_square_value << "==========" << std::endl; - Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_name, max_alpha_square_value); + Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_name); - const int DIMENSION = 2; - std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); + Gudhi::Simplex_tree<> simplex_tree_60; + BOOST_CHECK(alpha_complex_from_file.create_complex(simplex_tree_60, max_alpha_square_value)); - const int NUMBER_OF_VERTICES = 7; - std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; - BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); + std::cout << "simplex_tree_60.dimension()=" << simplex_tree_60.dimension() << std::endl; + BOOST_CHECK(simplex_tree_60.dimension() == 2); - const int NUMBER_OF_SIMPLICES = 25; - std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; - BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); + std::cout << "simplex_tree_60.num_vertices()=" << simplex_tree_60.num_vertices() << std::endl; + BOOST_CHECK(simplex_tree_60.num_vertices() == 7); -} + std::cout << "simplex_tree_60.num_simplices()=" << simplex_tree_60.num_simplices() << std::endl; + BOOST_CHECK(simplex_tree_60.num_simplices() == 25); -BOOST_AUTO_TEST_CASE(ALPHA_DOC_OFF_file_filtered) { - // ---------------------------------------------------------------------------- - // - // Init of an alpha-complex from a OFF file - // - // ---------------------------------------------------------------------------- - std::string off_file_name("alphacomplexdoc.off"); - double max_alpha_square_value = 59.0; + max_alpha_square_value = 59.0; std::cout << "========== OFF FILE NAME = " << off_file_name << " - alpha²=" << max_alpha_square_value << "==========" << std::endl; - // Use of the default dynamic kernel - Gudhi::alpha_complex::Alpha_complex<> alpha_complex_from_file(off_file_name, max_alpha_square_value); - - const int DIMENSION = 2; - std::cout << "alpha_complex_from_file.dimension()=" << alpha_complex_from_file.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_file.dimension() == DIMENSION); + Gudhi::Simplex_tree<> simplex_tree_59; + BOOST_CHECK(alpha_complex_from_file.create_complex(simplex_tree_59, max_alpha_square_value)); + + std::cout << "simplex_tree_59.dimension()=" << simplex_tree_59.dimension() << std::endl; + BOOST_CHECK(simplex_tree_59.dimension() == 2); - const int NUMBER_OF_VERTICES = 7; - std::cout << "alpha_complex_from_file.num_vertices()=" << alpha_complex_from_file.num_vertices() << std::endl; - BOOST_CHECK(alpha_complex_from_file.num_vertices() == NUMBER_OF_VERTICES); + std::cout << "simplex_tree_59.num_vertices()=" << simplex_tree_59.num_vertices() << std::endl; + BOOST_CHECK(simplex_tree_59.num_vertices() == 7); - const int NUMBER_OF_SIMPLICES = 23; - std::cout << "alpha_complex_from_file.num_simplices()=" << alpha_complex_from_file.num_simplices() << std::endl; - BOOST_CHECK(alpha_complex_from_file.num_simplices() == NUMBER_OF_SIMPLICES); + std::cout << "simplex_tree_59.num_simplices()=" << simplex_tree_59.num_simplices() << std::endl; + BOOST_CHECK(simplex_tree_59.num_simplices() == 23); } bool are_almost_the_same(float a, float b) { @@ -132,40 +123,43 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { std::cout << "========== Alpha_complex_from_points ==========" << std::endl; + Gudhi::Simplex_tree<> simplex_tree; + BOOST_CHECK(alpha_complex_from_points.create_complex(simplex_tree)); + // Another way to check num_simplices std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; int num_simplices = 0; - for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { num_simplices++; std::cout << " ( "; - for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) { + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { std::cout << vertex << " "; } - std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] "; + std::cout << ") -> " << "[" << simplex_tree.filtration(f_simplex) << "] "; std::cout << std::endl; } BOOST_CHECK(num_simplices == 15); - std::cout << "alpha_complex_from_points.num_simplices()=" << alpha_complex_from_points.num_simplices() << std::endl; - BOOST_CHECK(alpha_complex_from_points.num_simplices() == 15); + std::cout << "simplex_tree.num_simplices()=" << simplex_tree.num_simplices() << std::endl; + BOOST_CHECK(simplex_tree.num_simplices() == 15); - std::cout << "alpha_complex_from_points.dimension()=" << alpha_complex_from_points.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_points.dimension() == 4); - std::cout << "alpha_complex_from_points.num_vertices()=" << alpha_complex_from_points.num_vertices() << std::endl; - BOOST_CHECK(alpha_complex_from_points.num_vertices() == 4); + std::cout << "simplex_tree.dimension()=" << simplex_tree.dimension() << std::endl; + BOOST_CHECK(simplex_tree.dimension() == 4); + std::cout << "simplex_tree.num_vertices()=" << simplex_tree.num_vertices() << std::endl; + BOOST_CHECK(simplex_tree.num_vertices() == 4); - for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { - switch (alpha_complex_from_points.dimension(f_simplex)) { + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + switch (simplex_tree.dimension(f_simplex)) { case 0: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 0.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 0.0)); break; case 1: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 1.0/2.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 1.0/2.0)); break; case 2: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 2.0/3.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 2.0/3.0)); break; case 3: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 3.0/4.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 3.0/4.0)); break; default: BOOST_CHECK(false); // Shall not happen @@ -199,40 +193,40 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { BOOST_CHECK_THROW (alpha_complex_from_points.get_point(1234), std::out_of_range); // Test after prune_above_filtration - bool modified = alpha_complex_from_points.prune_above_filtration(0.6); + bool modified = simplex_tree.prune_above_filtration(0.6); if (modified) { - alpha_complex_from_points.initialize_filtration(); + simplex_tree.initialize_filtration(); } BOOST_CHECK(modified); // Another way to check num_simplices std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; num_simplices = 0; - for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { num_simplices++; std::cout << " ( "; - for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) { + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { std::cout << vertex << " "; } - std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] "; + std::cout << ") -> " << "[" << simplex_tree.filtration(f_simplex) << "] "; std::cout << std::endl; } BOOST_CHECK(num_simplices == 10); - std::cout << "alpha_complex_from_points.num_simplices()=" << alpha_complex_from_points.num_simplices() << std::endl; - BOOST_CHECK(alpha_complex_from_points.num_simplices() == 10); + std::cout << "simplex_tree.num_simplices()=" << simplex_tree.num_simplices() << std::endl; + BOOST_CHECK(simplex_tree.num_simplices() == 10); - std::cout << "alpha_complex_from_points.dimension()=" << alpha_complex_from_points.dimension() << std::endl; - BOOST_CHECK(alpha_complex_from_points.dimension() == 4); - std::cout << "alpha_complex_from_points.num_vertices()=" << alpha_complex_from_points.num_vertices() << std::endl; - BOOST_CHECK(alpha_complex_from_points.num_vertices() == 4); + std::cout << "simplex_tree.dimension()=" << simplex_tree.dimension() << std::endl; + BOOST_CHECK(simplex_tree.dimension() == 4); + std::cout << "simplex_tree.num_vertices()=" << simplex_tree.num_vertices() << std::endl; + BOOST_CHECK(simplex_tree.num_vertices() == 4); - for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { - switch (alpha_complex_from_points.dimension(f_simplex)) { + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + switch (simplex_tree.dimension(f_simplex)) { case 0: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 0.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 0.0)); break; case 1: - BOOST_CHECK(are_almost_the_same(alpha_complex_from_points.filtration(f_simplex), 1.0/2.0)); + BOOST_CHECK(are_almost_the_same(simplex_tree.filtration(f_simplex), 1.0/2.0)); break; default: BOOST_CHECK(false); // Shall not happen diff --git a/src/Persistent_cohomology/example/alpha_complex_persistence.cpp b/src/Persistent_cohomology/example/alpha_complex_persistence.cpp index cb181936..44eda6aa 100644 --- a/src/Persistent_cohomology/example/alpha_complex_persistence.cpp +++ b/src/Persistent_cohomology/example/alpha_complex_persistence.cpp @@ -4,6 +4,8 @@ #include #include +// to construct a simplex_tree from alpha complex +#include #include #include @@ -30,35 +32,38 @@ int main(int argc, char **argv) { // Init of an alpha complex from an OFF file // ---------------------------------------------------------------------------- using Kernel = CGAL::Epick_d< CGAL::Dynamic_dimension_tag >; - Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_points, alpha_square_max_value); - - // ---------------------------------------------------------------------------- - // Display information about the alpha complex - // ---------------------------------------------------------------------------- - std::cout << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << - " - " << alpha_complex_from_file.num_simplices() << " simplices - " << - alpha_complex_from_file.num_vertices() << " vertices." << std::endl; - - // Sort the simplices in the order of the filtration - alpha_complex_from_file.initialize_filtration(); - - std::cout << "Simplex_tree dim: " << alpha_complex_from_file.dimension() << std::endl; - // Compute the persistence diagram of the complex - Gudhi::persistent_cohomology::Persistent_cohomology< Gudhi::alpha_complex::Alpha_complex, - Gudhi::persistent_cohomology::Field_Zp > pcoh(alpha_complex_from_file); - // initializes the coefficient field for homology - pcoh.init_coefficients(coeff_field_characteristic); - - pcoh.compute_persistent_cohomology(min_persistence); - - // Output the diagram in filediag - if (output_file_diag.empty()) { - pcoh.output_diagram(); - } else { - std::cout << "Result in file: " << output_file_diag << std::endl; - std::ofstream out(output_file_diag); - pcoh.output_diagram(out); - out.close(); + Gudhi::alpha_complex::Alpha_complex alpha_complex_from_file(off_file_points); + + Gudhi::Simplex_tree<> simplex; + if (alpha_complex_from_file.create_complex(simplex, alpha_square_max_value)) { + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Simplicial complex is of dimension " << simplex.dimension() << + " - " << simplex.num_simplices() << " simplices - " << + simplex.num_vertices() << " vertices." << std::endl; + + // Sort the simplices in the order of the filtration + simplex.initialize_filtration(); + + std::cout << "Simplex_tree dim: " << simplex.dimension() << std::endl; + // Compute the persistence diagram of the complex + Gudhi::persistent_cohomology::Persistent_cohomology< Gudhi::Simplex_tree<>, + Gudhi::persistent_cohomology::Field_Zp > pcoh(simplex); + // initializes the coefficient field for homology + pcoh.init_coefficients(coeff_field_characteristic); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (output_file_diag.empty()) { + pcoh.output_diagram(); + } else { + std::cout << "Result in file: " << output_file_diag << std::endl; + std::ofstream out(output_file_diag); + pcoh.output_diagram(out); + out.close(); + } } return 0; diff --git a/src/Persistent_cohomology/example/custom_persistence_sort.cpp b/src/Persistent_cohomology/example/custom_persistence_sort.cpp index 9af38611..8e254700 100644 --- a/src/Persistent_cohomology/example/custom_persistence_sort.cpp +++ b/src/Persistent_cohomology/example/custom_persistence_sort.cpp @@ -27,6 +27,8 @@ #include #include +// to construct a simplex_tree from alpha complex +#include #include #include @@ -38,6 +40,9 @@ using Kernel = CGAL::Epick_d< CGAL::Dimension_tag<3> >; using Point = Kernel::Point_d; using Alpha_complex = Gudhi::alpha_complex::Alpha_complex; +using Simplex_tree = Gudhi::Simplex_tree<>; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology< Simplex_tree, + Gudhi::persistent_cohomology::Field_Zp >; std::vector random_points() { // Instanciate a random point generator @@ -60,7 +65,7 @@ std::vector random_points() { * Compare two intervals by dimension, then by length. */ struct cmp_intervals_by_dim_then_length { - explicit cmp_intervals_by_dim_then_length(Alpha_complex * sc) + explicit cmp_intervals_by_dim_then_length(Simplex_tree * sc) : sc_(sc) { } template @@ -71,46 +76,62 @@ struct cmp_intervals_by_dim_then_length { else return (sc_->dimension(get < 0 > (p1)) > sc_->dimension(get < 0 > (p2))); } - Alpha_complex* sc_; + Simplex_tree* sc_; }; int main(int argc, char **argv) { std::vector points = random_points(); + std::cout << "Points size=" << points.size() << std::endl; // Alpha complex persistence computation from generated points - Alpha_complex alpha_complex_from_points(points, 0.6); - - using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology< Alpha_complex, - Gudhi::persistent_cohomology::Field_Zp >; - Persistent_cohomology pcoh(alpha_complex_from_points); - - // initializes the coefficient field for homology - Z/3Z - pcoh.init_coefficients(3); - pcoh.compute_persistent_cohomology(0.2); - - // Custom sort and output persistence - cmp_intervals_by_dim_then_length cmp(&alpha_complex_from_points); - auto persistent_pairs = pcoh.get_persistent_pairs(); - std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); - for (auto pair : persistent_pairs) { - std::cout << alpha_complex_from_points.dimension(get<0>(pair)) << " " - << alpha_complex_from_points.filtration(get<0>(pair)) << " " - << alpha_complex_from_points.filtration(get<1>(pair)) << std::endl; + Alpha_complex alpha_complex_from_points(points); + std::cout << "alpha_complex_from_points" << std::endl; + + Simplex_tree simplex; + std::cout << "simplex" << std::endl; + if (alpha_complex_from_points.create_complex(simplex, 0.6)) { + std::cout << "simplex" << std::endl; + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Simplicial complex is of dimension " << simplex.dimension() << + " - " << simplex.num_simplices() << " simplices - " << + simplex.num_vertices() << " vertices." << std::endl; + + // Sort the simplices in the order of the filtration + simplex.initialize_filtration(); + + std::cout << "Simplex_tree dim: " << simplex.dimension() << std::endl; + + Persistent_cohomology pcoh(simplex); + + // initializes the coefficient field for homology - Z/3Z + pcoh.init_coefficients(3); + pcoh.compute_persistent_cohomology(0.2); + + // Custom sort and output persistence + cmp_intervals_by_dim_then_length cmp(&simplex); + auto persistent_pairs = pcoh.get_persistent_pairs(); + std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); + for (auto pair : persistent_pairs) { + std::cout << simplex.dimension(get<0>(pair)) << " " + << simplex.filtration(get<0>(pair)) << " " + << simplex.filtration(get<1>(pair)) << std::endl; + } + + // Persistent Betti numbers + std::cout << "The persistent Betti numbers in interval [0.40, 0.41] are : "; + for (int dim = 0; dim < simplex.dimension(); dim++) + std::cout << "b" << dim << " = " << pcoh.persistent_betti_number(dim, 0.40, 0.41) << " ; "; + std::cout << std::endl; + + // Betti numbers + std::vector betti_numbers = pcoh.betti_numbers(); + std::cout << "The Betti numbers are : "; + for (std::size_t i = 0; i < betti_numbers.size(); i++) + std::cout << "b" << i << " = " << betti_numbers[i] << " ; "; + std::cout << std::endl; } - - // Persistent Betti numbers - std::cout << "The persistent Betti numbers in interval [0.40, 0.41] are : "; - for (int dim = 0; dim < alpha_complex_from_points.dimension(); dim++) - std::cout << "b" << dim << " = " << pcoh.persistent_betti_number(dim, 0.40, 0.41) << " ; "; - std::cout << std::endl; - - // Betti numbers - std::vector betti_numbers = pcoh.betti_numbers(); - std::cout << "The Betti numbers are : "; - for (std::size_t i = 0; i < betti_numbers.size(); i++) - std::cout << "b" << i << " = " << betti_numbers[i] << " ; "; - std::cout << std::endl; - return 0; } -- cgit v1.2.3