diff options
author | mcarrier <mcarrier@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-03-24 07:39:45 +0000 |
---|---|---|
committer | mcarrier <mcarrier@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-03-24 07:39:45 +0000 |
commit | 6a1d7a51c3ac46b51d2613d58e63d948b4ca7789 (patch) | |
tree | 80950ffe9e1e06ba4cbe5366bdb747ca49e4ae0c /src/Bottleneck_distance | |
parent | 57a4ff3594b485a65fef206e03245a995f2feaf7 (diff) | |
parent | f48eae4cd7dc50dbbe0c8ec4f63bb98dda51a5d8 (diff) |
Merged latest trunk changes to Nerve_GIC
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Nerve_GIC@2230 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: bccc1dde37a431fd2b2808549c308482480e8778
Diffstat (limited to 'src/Bottleneck_distance')
-rw-r--r-- | src/Bottleneck_distance/benchmark/CMakeLists.txt | 3 | ||||
-rw-r--r-- | src/Bottleneck_distance/concept/Persistence_diagram.h | 13 | ||||
-rw-r--r-- | src/Bottleneck_distance/doc/COPYRIGHT | 19 | ||||
-rw-r--r-- | src/Bottleneck_distance/doc/Intro_bottleneck_distance.h | 10 | ||||
-rw-r--r-- | src/Bottleneck_distance/example/CMakeLists.txt | 2 | ||||
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/Bottleneck.h | 21 | ||||
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/Persistence_graph.h | 10 | ||||
-rw-r--r-- | src/Bottleneck_distance/test/CMakeLists.txt | 3 |
8 files changed, 64 insertions, 17 deletions
diff --git a/src/Bottleneck_distance/benchmark/CMakeLists.txt b/src/Bottleneck_distance/benchmark/CMakeLists.txt index 355e8d31..c99e0373 100644 --- a/src/Bottleneck_distance/benchmark/CMakeLists.txt +++ b/src/Bottleneck_distance/benchmark/CMakeLists.txt @@ -7,5 +7,8 @@ project(Bottleneck_distance_benchmark) if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.8.0) add_executable ( bottleneck_chrono bottleneck_chrono.cpp ) + if (TBB_FOUND) + target_link_libraries(bottleneck_chrono ${TBB_LIBRARIES}) + endif(TBB_FOUND) endif () endif() diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 2706716b..b157f22a 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -25,24 +25,25 @@ namespace Gudhi { -namespace bottleneck_distance { +namespace persistence_diagram { -/** \brief Concept of Diagram_point. std::get<0>(point) must return the birth of the corresponding component and std::get<1>(point) its death. +/** \brief Concept of point in a persistence diagram. std::get<0>(point) must return the birth of the corresponding component and std::get<1>(point) its death. + * Both should be convertible to `double`. * A valid implementation of this concept is std::pair<double,double>. * Death should be larger than birth, death can be std::numeric_limits<double>::infinity() for components which stay alive. * * \ingroup bottleneck_distance */ -typename Diagram_point; +struct DiagramPoint{}; -/** \brief Concept of persistence diagram. It's a range of Diagram_point. +/** \brief Concept of persistence diagram. It is a range of `DiagramPoint`. * std::begin(diagram) and std::end(diagram) must return corresponding iterators. * * \ingroup bottleneck_distance */ -typename Persistence_Diagram; +struct PersistenceDiagram{}; -} // namespace bottleneck_distance +} // namespace persistence_diagram } // namespace Gudhi diff --git a/src/Bottleneck_distance/doc/COPYRIGHT b/src/Bottleneck_distance/doc/COPYRIGHT new file mode 100644 index 00000000..179740a6 --- /dev/null +++ b/src/Bottleneck_distance/doc/COPYRIGHT @@ -0,0 +1,19 @@ +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. + +Author(s): François Godi + +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 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/>. diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 21187f9c..3998fe8d 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -26,7 +26,7 @@ // needs namespace for Doxygen to link on classes namespace Gudhi { // needs namespace for Doxygen to link on classes -namespace bottleneck_distance { +namespace persistence_diagram { /** \defgroup bottleneck_distance Bottleneck distance * @@ -35,16 +35,16 @@ namespace bottleneck_distance { * * \section bottleneckdefinition Definition * - * The bottleneck distance measures the similarity between two persistence diagrams. It's the shortest distance b for which there exists a perfect matching between - * the points of the two diagrams (completed with all the points on the diagonal in order to ignore cardinality mismatchs) such that - * any couple of matched points are at distance at most b. + * The bottleneck distance measures the similarity between two persistence diagrams. It is the shortest distance b for + * which there exists a perfect matching between the points of the two diagrams (completed with all the points on the + * diagonal in order to ignore cardinality mismatchs) such that any couple of matched points are at distance at most b. * * \image html perturb_pd.png On this picture, the red edges represent the matching. The bottleneck distance is the length of the longest edge. * */ /** @} */ // end defgroup bottleneck_distance -} // namespace bottleneck_distance +} // namespace persistence_diagram } // namespace Gudhi diff --git a/src/Bottleneck_distance/example/CMakeLists.txt b/src/Bottleneck_distance/example/CMakeLists.txt index b36d0f34..55f22c01 100644 --- a/src/Bottleneck_distance/example/CMakeLists.txt +++ b/src/Bottleneck_distance/example/CMakeLists.txt @@ -13,6 +13,8 @@ if(CGAL_FOUND) add_executable (alpha_rips_persistence_bottleneck_distance alpha_rips_persistence_bottleneck_distance.cpp) target_link_libraries(alpha_rips_persistence_bottleneck_distance ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) if (TBB_FOUND) + target_link_libraries(bottleneck_read_file_example ${TBB_LIBRARIES}) + target_link_libraries(bottleneck_basic_example ${TBB_LIBRARIES}) target_link_libraries(alpha_rips_persistence_bottleneck_distance ${TBB_LIBRARIES}) endif(TBB_FOUND) add_test(alpha_rips_persistence_bottleneck_distance ${CMAKE_CURRENT_BINARY_DIR}/alpha_rips_persistence_bottleneck_distance diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index b5641e29..b90a0ee0 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -80,11 +80,22 @@ double bottleneck_distance_exact(Persistence_graph& g) { return sd.at(lower_bound_i); } -/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams (see concepts). - * If the last parameter e is not 0, you get an additive e-approximation, which is a lot faster to compute whatever is - * e. - * Thus, by default, e is a very small positive double, actually the smallest double possible such that the - * floating-point inaccuracies don't lead to a failure of the algorithm. +/** \brief Function to compute the Bottleneck distance between two persistence diagrams. + * + * \tparam Persistence_diagram1,Persistence_diagram2 + * models of the concept `PersistenceDiagram`. + * \param[in] e + * \parblock + * If `e` is 0, this uses an expensive algorithm to compute the exact distance. + * + * If `e` is not 0, it asks for an additive `e`-approximation, and currently + * also allows a small multiplicative error (the last 2 or 3 bits of the + * mantissa may be wrong). This version of the algorithm takes advantage of the + * limited precision of `double` and is usually a lot faster to compute, + * whatever the value of `e`. + * + * Thus, by default, `e` is the smallest positive double. + * \endparblock * * \ingroup bottleneck_distance */ diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index 39efc082..44f4b827 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -25,6 +25,10 @@ #include <gudhi/Internal_point.h> +#ifdef GUDHI_USE_TBB +#include <tbb/parallel_sort.h> +#endif + #include <vector> #include <algorithm> #include <limits> // for numeric_limits @@ -40,7 +44,7 @@ namespace persistence_diagram { */ class Persistence_graph { public: - /** \internal \brief Constructor taking 2 Persistence_Diagrams (concept) as parameters. */ + /** \internal \brief Constructor taking 2 PersistenceDiagrams (concept) as parameters. */ template<typename Persistence_diagram1, typename Persistence_diagram2> Persistence_graph(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e); /** \internal \brief Is the given point from U the projection of a point in V ? */ @@ -144,7 +148,11 @@ inline std::vector<double> Persistence_graph::sorted_distances() const { for (int v_point_index = 0; v_point_index < size(); ++v_point_index) distances.push_back(distance(u_point_index, v_point_index)); } +#ifdef GUDHI_USE_TBB + tbb::parallel_sort(distances.begin(), distances.end()); +#else std::sort(distances.begin(), distances.end()); +#endif return distances; } diff --git a/src/Bottleneck_distance/test/CMakeLists.txt b/src/Bottleneck_distance/test/CMakeLists.txt index 6c8f112d..3e61f4cf 100644 --- a/src/Bottleneck_distance/test/CMakeLists.txt +++ b/src/Bottleneck_distance/test/CMakeLists.txt @@ -17,6 +17,9 @@ if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.8.0) add_executable ( bottleneckUT bottleneck_unit_test.cpp ) target_link_libraries(bottleneckUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(bottleneckUT ${TBB_LIBRARIES}) + endif(TBB_FOUND) # Unitary tests add_test(NAME bottleneckUT COMMAND ${CMAKE_CURRENT_BINARY_DIR}/bottleneckUT |