diff options
Diffstat (limited to 'src/common')
-rw-r--r-- | src/common/benchmark/CMakeLists.txt | 3 | ||||
-rw-r--r-- | src/common/benchmark/Graph_simplicial_complex_benchmark.cpp | 150 | ||||
-rw-r--r-- | src/common/doc/examples.h | 5 | ||||
-rw-r--r-- | src/common/doc/file_formats.h | 6 | ||||
-rw-r--r-- | src/common/doc/installation.h | 34 | ||||
-rw-r--r-- | src/common/doc/main_page.h | 24 | ||||
-rw-r--r-- | src/common/include/gudhi/Unitary_tests_utils.h | 2 | ||||
-rw-r--r-- | src/common/include/gudhi/graph_simplicial_complex.h | 2 | ||||
-rw-r--r-- | src/common/include/gudhi/reader_utils.h | 4 |
9 files changed, 197 insertions, 33 deletions
diff --git a/src/common/benchmark/CMakeLists.txt b/src/common/benchmark/CMakeLists.txt new file mode 100644 index 00000000..a3787d6e --- /dev/null +++ b/src/common/benchmark/CMakeLists.txt @@ -0,0 +1,3 @@ +project(common_benchmark) + +add_executable(Graph_simplicial_complex_benchmark Graph_simplicial_complex_benchmark.cpp) diff --git a/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp b/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp new file mode 100644 index 00000000..825d6cb5 --- /dev/null +++ b/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp @@ -0,0 +1,150 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2018 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 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/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Clock.h> +#include <gudhi/Points_off_io.h> + +#include <boost/graph/adjacency_list.hpp> + +#include <iostream> +#include <string> +#include <vector> +#include <limits> // for numeric limits +#include <fstream> +#include <cassert> + + +std::ofstream results_csv("results.csv"); + +template< typename Adjacency_list, typename ForwardPointRange, typename Distance > +Adjacency_list proximity_graph_computation(const ForwardPointRange& points, double threshold, Distance distance) { + std::vector<std::pair< int, int >> edges; + std::vector< double > edges_fil; + std::map< int, double > vertices; + + int idx_u, idx_v; + double fil; + idx_u = 0; + for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { + idx_v = idx_u + 1; + for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { + fil = distance(*it_u, *it_v); + if (fil <= threshold) { + edges.emplace_back(idx_u, idx_v); + edges_fil.push_back(fil); + } + } + ++idx_u; + } + + // Points are labeled from 0 to idx_u-1 + Adjacency_list skel_graph(edges.begin(), edges.end(), edges_fil.begin(), idx_u); + + auto vertex_prop = boost::get(Gudhi::vertex_filtration_t(), skel_graph); + + typename boost::graph_traits<Adjacency_list>::vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); + vi != vi_end; ++vi) { + boost::put(vertex_prop, *vi, 0.); + } + + return skel_graph; +} + +template <typename Adjacency_list> +void benchmark_proximity_graph(const std::string& msg, const std::string& off_file_name) { + Gudhi::Points_off_reader<std::vector<double>> off_reader(off_file_name); + assert(off_reader.is_valid()); + + std::cout << "+ " << msg << std::endl; + + results_csv << "\"nb_points\";" + << "\"nb_simplices\";" + << "\"compute proximity graph(sec.)\";" + << "\"complex_creation_time(sec.)\";" + << "\"" << msg << "\";" << std::endl; + + Gudhi::Clock pg_compute_proximity_graph(" benchmark_proximity_graph - compute proximity graph"); + pg_compute_proximity_graph.begin(); + // benchmark begin + Adjacency_list proximity_graph = proximity_graph_computation<Adjacency_list>(off_reader.get_point_cloud(), + std::numeric_limits<double>::infinity(), + Gudhi::Euclidean_distance()); + // benchmark end + pg_compute_proximity_graph.end(); + std::cout << pg_compute_proximity_graph; + + Gudhi::Simplex_tree<> complex; + Gudhi::Clock st_create_clock(" benchmark_proximity_graph - complex creation"); + st_create_clock.begin(); + // benchmark begin + complex.insert_graph(proximity_graph); + // benchmark end + st_create_clock.end(); + std::cout << st_create_clock; + + results_csv << off_reader.get_point_cloud().size() << ";" << complex.num_simplices() << ";" + << pg_compute_proximity_graph.num_seconds() << ";" + << st_create_clock.num_seconds() << ";" << std::endl; + + std::cout << " benchmark_proximity_graph - nb simplices = " << complex.num_simplices() << std::endl; +} + +int main(int argc, char * const argv[]) { + std::string off_file_name(argv[1]); + + // The fastest, the less memory used + using vecSdirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<vecSdirectedS>("vecSdirectedS", off_file_name); + + using vecSundirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<vecSundirectedS>("vecSundirectedS", off_file_name); + + using vecSbidirectionalS = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<vecSbidirectionalS>("vecSbidirectionalS", off_file_name); + + using setSdirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<setSdirectedS>("setSdirectedS", off_file_name); + + using setSundirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<setSundirectedS>("setSundirectedS", off_file_name); + + using setSbidirectionalS = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, + boost::property<Gudhi::vertex_filtration_t, double>, + boost::property<Gudhi::edge_filtration_t, double>>; + benchmark_proximity_graph<setSbidirectionalS>("setSbidirectionalS", off_file_name); + + return 0; +} diff --git a/src/common/doc/examples.h b/src/common/doc/examples.h index 40f202c7..c19b3444 100644 --- a/src/common/doc/examples.h +++ b/src/common/doc/examples.h @@ -53,10 +53,7 @@ * @example Spatial_searching/example_spatial_searching.cpp * @example Alpha_complex/alpha_complex_3d_persistence.cpp * @example Alpha_complex/alpha_complex_persistence.cpp - * @example Alpha_complex/weighted_periodic_alpha_complex_3d_persistence.cpp - * @example Alpha_complex/weighted_alpha_complex_3d_persistence.cpp - * @example Alpha_complex/periodic_alpha_complex_3d_persistence.cpp - * @example Alpha_complex/exact_alpha_complex_3d_persistence.cpp + * @example Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp * @example Bottleneck_distance/bottleneck_distance.cpp * @example Witness_complex/weak_witness_persistence.cpp * @example Witness_complex/strong_witness_persistence.cpp diff --git a/src/common/doc/file_formats.h b/src/common/doc/file_formats.h index 523153b8..23214e25 100644 --- a/src/common/doc/file_formats.h +++ b/src/common/doc/file_formats.h @@ -72,7 +72,7 @@ namespace Gudhi { \section FileFormatsPerseus Perseus - This file format is the format used by the Perseus software + This file format is a format inspired from the Perseus software (http://www.sas.upenn.edu/~vnanda/perseus/) by Vidit Nanda. The first line contains a number d begin the dimension of the bitmap (2 in the example below). Next d lines are the numbers of top dimensional cubes in each dimensions (3 and 3 @@ -118,6 +118,10 @@ namespace Gudhi { Indicate that we have imposed periodic boundary conditions in the direction x, but not in the direction y. Other sample files can be found in the `data/bitmap` folder. + + \note Unlike in Perseus format the filtration on the maximal cubes can be any double precision number. + Consequently one cannot mark the cubes that are not present with `-1`'s. To do that please set their filtration value + to \f$+\infty\f$ (aka. `inf` in the file). */ } // namespace Gudhi diff --git a/src/common/doc/installation.h b/src/common/doc/installation.h index c27e4f56..8fb8b330 100644 --- a/src/common/doc/installation.h +++ b/src/common/doc/installation.h @@ -5,7 +5,7 @@ * Examples of GUDHI headers inclusion can be found in \ref utilities. * * \section compiling Compiling - * The library uses c++11 and requires <a target="_blank" href="http://www.boost.org/">Boost</a> ≥ 1.48.0 + * The library uses c++11 and requires <a target="_blank" href="http://www.boost.org/">Boost</a> ≥ 1.56.0 * and <a target="_blank" href="https://www.cmake.org/">CMake</a> ≥ 3.1. * It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2015. * @@ -18,7 +18,7 @@ cmake .. make \endverbatim * By default, examples are disabled. You can activate their compilation with * <a href="https://cmake.org/cmake/help/v3.0/manual/ccmake.1.html">ccmake</a> (on Linux and Mac OSX), - * <a href="https://cmake.org/cmake/help/v3.0/manual/cmake-gui.1.html">cmake-gui</a> (on Windows) or y mofifying the + * <a href="https://cmake.org/cmake/help/v3.0/manual/cmake-gui.1.html">cmake-gui</a> (on Windows) or by modifying the * cmake command as follows : \verbatim cmake -DWITH_GUDHI_EXAMPLE=ON .. make \endverbatim @@ -72,12 +72,6 @@ make doxygen * * The following examples/utilities require the <a target="_blank" href="http://www.cgal.org/">Computational Geometry Algorithms * Library</a> (CGAL \cite cgal:eb-15b) and will not be built if CGAL is not installed: - * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_3d_persistence.cpp</a> - * \li <a href="_alpha_complex_2exact_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/exact_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_alpha_complex_2weighted_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/weighted_alpha_complex_3d_persistence.cpp</a> * \li <a href="_simplex_tree_2example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html"> * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> * @@ -100,8 +94,6 @@ make doxygen * Alpha_complex/Alpha_complex_from_points.cpp</a> * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html"> * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a> * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> * Persistent_cohomology/custom_persistence_sort.cpp</a> * @@ -135,6 +127,12 @@ make doxygen * \li <a href="_tangential_complex_2example_with_perturb_8cpp-example.html"> * Tangential_complex/example_with_perturb.cpp</a> * + * The following example requires CGAL version ≥ 4.11.0: + * \li <a href="_alpha_complex_2_weighted_alpha_complex_3d_from_points_8cpp-example.html"> + * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a> + * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html"> + * Alpha_complex/alpha_complex_3d_persistence.cpp</a> + * * \subsection eigen3 Eigen3 * The \ref alpha_complex data structure and few examples requires * <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen3</a> is a C++ template library for linear algebra: @@ -148,8 +146,10 @@ make doxygen * Alpha_complex/Alpha_complex_from_points.cpp</a> * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html"> * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a> + * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html"> + * Alpha_complex/alpha_complex_3d_persistence.cpp</a> + * \li <a href="_alpha_complex_2_weighted_alpha_complex_3d_from_points_8cpp-example.html"> + * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a> * \li <a href="_bottleneck_distance_2alpha_rips_persistence_bottleneck_distance_8cpp-example.html"> * Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp.cpp</a> * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> @@ -195,12 +195,6 @@ make doxygen * Alpha_complex/alpha_complex_3d_persistence.cpp</a> * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html"> * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="_alpha_complex_2exact_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/exact_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_alpha_complex_2weighted_alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/weighted_alpha_complex_3d_persistence.cpp</a> * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_8cpp-example.html"> * Bitmap_cubical_complex/cubical_complex_persistence.cpp</a> * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_periodic_boundary_conditions_8cpp-example.html"> @@ -239,10 +233,6 @@ make doxygen * Persistent_cohomology/rips_multifield_persistence.cpp</a> * \li <a href="_persistent_cohomology_2rips_persistence_step_by_step_8cpp-example.html"> * Persistent_cohomology/rips_persistence_step_by_step.cpp</a> - * \li <a href="_persistent_cohomology_2exact_alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/exact_alpha_complex_3d_persistence.cpp</a> - * \li <a href="_persistent_cohomology_2weighted_alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/weighted_alpha_complex_3d_persistence.cpp</a> * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html"> * Persistent_cohomology/custom_persistence_sort.cpp</a> * \li <a href="_rips_complex_2example_one_skeleton_rips_from_points_8cpp-example.html"> diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index db1e80ce..afe9b68c 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -29,7 +29,9 @@ <b>Author:</b> Vincent Rouvreau<br> <b>Introduced in:</b> GUDHI 1.3.0<br> <b>Copyright:</b> GPL v3<br> - <b>Requires:</b> \ref cgal ≥ 4.7.0 and \ref eigen3 + <b>Requires:</b> \ref eigen3 and<br> + \ref cgal ≥ 4.7.0 for Alpha_complex<br> + \ref cgal ≥ 4.11.0 for Alpha_complex_3d </td> <td width="75%"> Alpha_complex is a simplicial complex constructed from the finite cells of a Delaunay Triangulation.<br> @@ -38,7 +40,8 @@ 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 the complex.<br> - <b>User manual:</b> \ref alpha_complex - <b>Reference manual:</b> Gudhi::alpha_complex::Alpha_complex + <b>User manual:</b> \ref alpha_complex - <b>Reference manual:</b> Gudhi::alpha_complex::Alpha_complex and + Gudhi::alpha_complex::Alpha_complex_3d </td> </tr> </table> @@ -168,6 +171,23 @@ </td> </tr> </table> + \subsection ToplexMapDataStructure Toplex Map + \image html "map.png" "Toplex map representation" +<table border="0"> + <tr> + <td width="25%"> + <b>Author:</b> François Godi<br> + <b>Introduced in:</b> GUDHI 2.1.0<br> + <b>Copyright:</b> GPL v3<br> + </td> + <td width="75%"> + The Toplex map data structure is composed firstly of a raw storage of toplices (the maximal simplices) + and secondly of a map which associate any vertex to a set of pointers toward all toplices + containing this vertex. + <b>User manual:</b> \ref toplex_map - <b>Reference manual:</b> Gudhi::Toplex_map + </td> + </tr> + \subsection WitnessComplexDataStructure Witness complex \image html "Witness_complex_representation.png" "Witness complex representation" <table border="0"> diff --git a/src/common/include/gudhi/Unitary_tests_utils.h b/src/common/include/gudhi/Unitary_tests_utils.h index e07c8d42..22f00212 100644 --- a/src/common/include/gudhi/Unitary_tests_utils.h +++ b/src/common/include/gudhi/Unitary_tests_utils.h @@ -34,7 +34,7 @@ void GUDHI_TEST_FLOAT_EQUALITY_CHECK(FloatingType a, FloatingType b, std::cout << "GUDHI_TEST_FLOAT_EQUALITY_CHECK - " << a << " versus " << b << " | diff = " << std::fabs(a - b) << " - epsilon = " << epsilon << std::endl; #endif - BOOST_CHECK(std::fabs(a - b) < epsilon); + BOOST_CHECK(std::fabs(a - b) <= epsilon); } #endif // UNITARY_TESTS_UTILS_H_ diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h index 49fe56cc..0d81ca71 100644 --- a/src/common/include/gudhi/graph_simplicial_complex.h +++ b/src/common/include/gudhi/graph_simplicial_complex.h @@ -49,7 +49,7 @@ struct vertex_filtration_t { * */ template <typename SimplicialComplexForProximityGraph> -using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS +using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS , boost::property < vertex_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value > , boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>; diff --git a/src/common/include/gudhi/reader_utils.h b/src/common/include/gudhi/reader_utils.h index 26eeb76d..0ee7649d 100644 --- a/src/common/include/gudhi/reader_utils.h +++ b/src/common/include/gudhi/reader_utils.h @@ -172,10 +172,10 @@ bool read_simplex(std::istream& in_, std::vector<Vertex_handle>& simplex, Filtra if (!(in_ >> dim)) return false; Vertex_handle v; for (int i = 0; i < dim + 1; ++i) { - in_ >> v; + if (!(in_ >> v)) return false; simplex.push_back(v); } - in_ >> fil; + if (!(in_ >> fil)) return false; in_.ignore((std::numeric_limits<std::streamsize>::max)(), '\n'); // ignore until the carriage return return true; } |