From 3b5b94c90c81ae4938a89b2b4df8b1173f100ee3 Mon Sep 17 00:00:00 2001 From: fgodi Date: Thu, 2 Jun 2016 17:09:48 +0000 Subject: renaming git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@1240 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 53bcbf20e176a21dc41ef3c4d4295b1e9aa959b0 --- src/Bottleneck_distance/concept/Persistence_diagram.h | 7 +++++++ 1 file changed, 7 insertions(+) create mode 100644 src/Bottleneck_distance/concept/Persistence_diagram.h (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h new file mode 100644 index 00000000..4951af32 --- /dev/null +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -0,0 +1,7 @@ + + +struct Persistence_Diagram +{ + const_iterator cbegin() const; + const_iterator cend() const; +}; -- cgit v1.2.3 From 284a45fc6ffcf049e667065acda71c17165b4f5c Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 3 Jun 2016 12:28:19 +0000 Subject: concept git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@1247 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 7bfce006ccae0784f3e0f3747f670eddaa9aba48 --- src/Bottleneck_distance/concept/Diagram_point.h | 6 ------ src/Bottleneck_distance/concept/Persistence_diagram.h | 15 +++++++++++++-- 2 files changed, 13 insertions(+), 8 deletions(-) delete mode 100644 src/Bottleneck_distance/concept/Diagram_point.h (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Diagram_point.h b/src/Bottleneck_distance/concept/Diagram_point.h deleted file mode 100644 index ce9c6d5b..00000000 --- a/src/Bottleneck_distance/concept/Diagram_point.h +++ /dev/null @@ -1,6 +0,0 @@ - - -struct Diagram_point{ - double first; - double second; -}; diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 4951af32..27a258d8 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -1,7 +1,18 @@ +namespace Gudhi { +namespace Bottleneck_distance { +namespace Concept { +struct Diagram_point{ + double first; + double second; +}; struct Persistence_Diagram { - const_iterator cbegin() const; - const_iterator cend() const; + const_iterator cbegin() const; + const_iterator cend() const; }; + +} //namespace Concept +} //namespace Bottleneck_distance +} //namespace Gudhi -- cgit v1.2.3 From 9ffc108705ace9910cabc79225d984fe1d15b794 Mon Sep 17 00:00:00 2001 From: fgodi Date: Mon, 26 Sep 2016 12:55:44 +0000 Subject: tentative ajout documentation bottleneck git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1567 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5177eb3197263cfe272f981439317cdb4e8909c3 --- .../concept/Persistence_diagram.h | 8 +++++ .../doc/Intro_bottleneck_distance.h | 40 ++++++++++++++++++++++ .../include/gudhi/Graph_matching.h | 3 +- 3 files changed, 49 insertions(+), 2 deletions(-) create mode 100644 src/Bottleneck_distance/doc/Intro_bottleneck_distance.h (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 27a258d8..bd90cc11 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -2,11 +2,19 @@ namespace Gudhi { namespace Bottleneck_distance { namespace Concept { +/** \brief Concept of persistence diagram point. The double first is the birth of the component and the double second is the death of the component. + * + * \ingroup bottleneck_distance + */ struct Diagram_point{ double first; double second; }; +/** \brief Concept of persistence diagram. + * + * \ingroup bottleneck_distance + */ struct Persistence_Diagram { const_iterator cbegin() const; diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h new file mode 100644 index 00000000..2cf10975 --- /dev/null +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -0,0 +1,40 @@ +/* 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): François Godi + * + * Copyright (C) 2015 INRIA Sophia-Antipolis (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 . + */ + +#ifndef DOC_BOTTLENECK_DISTANCE_H_ +#define DOC_BOTTLENECK_DISTANCE_H_ + +// needs namespace for Doxygen to link on classes +namespace Gudhi { +// needs namespace for Doxygen to link on classes +namespace Bottleneck_distance { + +/** \defgroup bottleneck_distance Bottleneck distance + * + * \author François Godi + * + */ + +} // namespace Bottleneck_distance + +} // namespace Gudhi + diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index 69470067..7a8c8ee0 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -31,8 +31,7 @@ namespace Gudhi { namespace Bottleneck_distance { -/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. - * +/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. You get an additive e-approximation. * * * \ingroup bottleneck_distance -- cgit v1.2.3 From 7a701f8a2326268b2aadb369fbc0848b227078a1 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 27 Sep 2016 08:53:57 +0000 Subject: Fix naming conventions and cpplint Add Bottleneck_distance to GUDHI_MODULES in GUDHI_user_version_target.txt git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1569 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b96a2be25477ddf227e43d9941989f93a0f626bb --- .../concept/Persistence_diagram.h | 37 +++++++++++++++++++--- .../doc/Intro_bottleneck_distance.h | 9 ++++-- .../example/bottleneck_example.cpp | 13 ++++---- .../include/gudhi/CGAL/Miscellaneous.h | 2 +- .../include/gudhi/Graph_matching.h | 10 +++--- .../include/gudhi/Internal_point.h | 10 +++--- .../include/gudhi/Neighbors_finder.h | 10 +++--- .../include/gudhi/Persistence_diagrams_graph.h | 10 +++--- .../include/gudhi/Planar_neighbors_finder.h | 10 +++--- src/Bottleneck_distance/test/bottleneck_chrono.cpp | 2 +- .../test/bottleneck_unit_test.cpp | 2 +- src/cmake/modules/GUDHI_user_version_target.txt | 2 +- 12 files changed, 74 insertions(+), 43 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index bd90cc11..4c69343c 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -1,6 +1,31 @@ +/* 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): François Godi + * + * Copyright (C) 2016 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 . + */ + +#ifndef CONCEPT_BOTTLENECK_DISTANCE_PERSISTENCE_DIAGRAM_H_ +#define CONCEPT_BOTTLENECK_DISTANCE_PERSISTENCE_DIAGRAM_H_ + namespace Gudhi { -namespace Bottleneck_distance { -namespace Concept { + +namespace bottleneck_distance { /** \brief Concept of persistence diagram point. The double first is the birth of the component and the double second is the death of the component. * @@ -21,6 +46,8 @@ struct Persistence_Diagram const_iterator cend() const; }; -} //namespace Concept -} //namespace Bottleneck_distance -} //namespace Gudhi +} // namespace bottleneck_distance + +} // namespace Gudhi + +#endif // CONCEPT_BOTTLENECK_DISTANCE_PERSISTENCE_DIAGRAM_H_ diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 2cf10975..9a792048 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -26,15 +26,20 @@ // needs namespace for Doxygen to link on classes namespace Gudhi { // needs namespace for Doxygen to link on classes -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \defgroup bottleneck_distance Bottleneck distance * * \author François Godi + * @{ * + * \section bottleneckdefinition Definition + * + * Bottleneck distance is blablabla... */ +/** @} */ // end defgroup bottleneck_distance -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp index 472c5c84..0bec9746 100644 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_example.cpp @@ -28,12 +28,9 @@ #include #include -using namespace std; - -//PD: I am using this type of procedures a lot in Gudhi stat. We should make one for all at some point. std::vector< std::pair > read_diagram_from_file( const char* filename ) { - ifstream in; + std::ifstream in; in.open( filename ); std::vector< std::pair > result; if ( !in.is_open() ) @@ -58,13 +55,15 @@ std::vector< std::pair > read_diagram_from_file( const char* fil } in.close(); return result; -}//read_diagram_from_file +} //read_diagram_from_file int main( int argc , char** argv ) { if ( argc < 3 ) { - std::cout << "To run this program please provide as an input two files with persistence diagrams. Each file should contain a birth-death pair per line. Third, optional parameter is an error bound on a bottleneck distance (set by default to zero). The program will now terminate \n"; + std::cout << "To run this program please provide as an input two files with persistence diagrams. Each file " << + "should contain a birth-death pair per line. Third, optional parameter is an error bound on a bottleneck" << + " distance (set by default to zero). The program will now terminate \n"; } std::vector< std::pair< double , double > > diag1 = read_diagram_from_file( argv[1] ); std::vector< std::pair< double , double > > diag2 = read_diagram_from_file( argv[2] ); @@ -73,6 +72,6 @@ int main( int argc , char** argv ) { tolerance = atof( argv[3] ); } - double b = Gudhi::Bottleneck_distance::compute(diag1, diag2, tolerance); + double b = Gudhi::bottleneck_distance::compute(diag1, diag2, tolerance); std::cout << "The distance between the diagrams is : " << b << ". The tolerace is : " << tolerance << std::endl; } diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Miscellaneous.h b/src/Bottleneck_distance/include/gudhi/CGAL/Miscellaneous.h index 21be0bc7..91632149 100644 --- a/src/Bottleneck_distance/include/gudhi/CGAL/Miscellaneous.h +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Miscellaneous.h @@ -27,7 +27,7 @@ namespace CGAL { -typedef Gudhi::Bottleneck_distance::Internal_point Internal_point; +typedef Gudhi::bottleneck_distance::Internal_point Internal_point; template <> struct Kernel_traits { diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index 7a8c8ee0..5f579a0c 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -20,8 +20,8 @@ * along with this program. If not, see . */ -#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ +#ifndef GRAPH_MATCHING_H_ +#define GRAPH_MATCHING_H_ #include @@ -29,7 +29,7 @@ namespace Gudhi { -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. You get an additive e-approximation. * @@ -238,11 +238,11 @@ double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &di -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ +#endif // GRAPH_MATCHING_H_ /* Dichotomic version template diff --git a/src/Bottleneck_distance/include/gudhi/Internal_point.h b/src/Bottleneck_distance/include/gudhi/Internal_point.h index 2080900d..f05d5fc9 100644 --- a/src/Bottleneck_distance/include/gudhi/Internal_point.h +++ b/src/Bottleneck_distance/include/gudhi/Internal_point.h @@ -20,12 +20,12 @@ * along with this program. If not, see . */ -#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ +#ifndef INTERNAL_POINT_H_ +#define INTERNAL_POINT_H_ namespace Gudhi { -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \internal \brief Returns the used index for encoding none of the points */ int null_point_index(); @@ -67,8 +67,8 @@ inline int null_point_index() { return -1; } -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ +#endif // INTERNAL_POINT_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index 7ad79126..1bd5879c 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -20,15 +20,15 @@ * along with this program. If not, see . */ -#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ +#ifndef NEIGHBORS_FINDER_H_ +#define NEIGHBORS_FINDER_H_ #include #include namespace Gudhi { -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \internal \brief data structure used to find any point (including projections) in V near to a query point from U * (which can be a projection). @@ -147,8 +147,8 @@ inline int Layered_neighbors_finder::vlayers_number() const { return static_cast(neighbors_finder.size()); } -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ +#endif // NEIGHBORS_FINDER_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h index e31b2dae..1f6d6683 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h @@ -20,8 +20,8 @@ * along with this program. If not, see . */ -#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ +#ifndef PERSISTENCE_DIAGRAMS_GRAPH_H_ +#define PERSISTENCE_DIAGRAMS_GRAPH_H_ #include #include @@ -34,7 +34,7 @@ namespace Gudhi { -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \internal \brief Structure representing an euclidean bipartite graph containing @@ -162,8 +162,8 @@ inline double G::diameter() { return max; } -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ +#endif // PERSISTENCE_DIAGRAMS_GRAPH_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h index 30f7dc3c..bf70ed0b 100644 --- a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h @@ -20,8 +20,8 @@ * along with this program. If not, see . */ -#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ +#ifndef PLANAR_NEIGHBORS_FINDER_H_ +#define PLANAR_NEIGHBORS_FINDER_H_ #include #include @@ -40,7 +40,7 @@ namespace Gudhi { -namespace Bottleneck_distance { +namespace bottleneck_distance { /** \internal \brief Structure used to find any point in V near (according to the planar distance) to a query point from U. * @@ -217,8 +217,8 @@ inline std::shared_ptr< std::list > Cgal_pnf::pull_all_near(int u_point_ind } -} // namespace Bottleneck_distance +} // namespace bottleneck_distance } // namespace Gudhi -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ +#endif // PLANAR_NEIGHBORS_FINDER_H_ diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp index 8b49b6be..8b143b18 100644 --- a/src/Bottleneck_distance/test/bottleneck_chrono.cpp +++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp @@ -24,7 +24,7 @@ #include #include -using namespace Gudhi::Bottleneck_distance; +using namespace Gudhi::bottleneck_distance; double upper_bound = 400.; // any real >0 diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index d5b71156..d2331c5d 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -27,7 +27,7 @@ #include #include -using namespace Gudhi::Bottleneck_distance; +using namespace Gudhi::bottleneck_distance; int n1 = 81; // a natural number >0 int n2 = 180; // a natural number >0 diff --git a/src/cmake/modules/GUDHI_user_version_target.txt b/src/cmake/modules/GUDHI_user_version_target.txt index 805f0a83..de16ef4c 100644 --- a/src/cmake/modules/GUDHI_user_version_target.txt +++ b/src/cmake/modules/GUDHI_user_version_target.txt @@ -48,7 +48,7 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy_directory ${CMAKE_SOURCE_DIR}/src/GudhUI ${GUDHI_USER_VERSION_DIR}/GudhUI) - set(GUDHI_MODULES "common;Alpha_complex;Bitmap_cubical_complex;Contraction;Hasse_complex;Persistent_cohomology;Simplex_tree;Skeleton_blocker;Witness_complex") + set(GUDHI_MODULES "common;Alpha_complex;Bitmap_cubical_complex;Bottleneck_distance;Contraction;Hasse_complex;Persistent_cohomology;Simplex_tree;Skeleton_blocker;Witness_complex") foreach(GUDHI_MODULE ${GUDHI_MODULES}) # doc files -- cgit v1.2.3 From 5bd04a9433462965aecf000e5044e70405e968ff Mon Sep 17 00:00:00 2001 From: fgodi Date: Wed, 23 Nov 2016 16:57:49 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1780 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9001cd1b33dfea3b34e5d12ef8e20b5624a50ba9 --- .../concept/Persistence_diagram.h | 11 +++++------ .../example/bottleneck_example.cpp | 2 +- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 20 +++++++------------- .../include/gudhi/Persistence_diagrams_graph.h | 4 ++-- .../test/bottleneck_unit_test.cpp | 1 + 5 files changed, 16 insertions(+), 22 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 4c69343c..1ab768ba 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -27,23 +27,22 @@ namespace Gudhi { namespace bottleneck_distance { -/** \brief Concept of persistence diagram point. The double first is the birth of the component and the double second is the death of the component. +/** \brief Concept of persistence diagram point. get<0>() must return the birth of the component and get<1>() its death. * * \ingroup bottleneck_distance */ struct Diagram_point{ - double first; - double second; + double get(); }; -/** \brief Concept of persistence diagram. +/** \brief Concept of persistence diagram. It's a range of Diagram_point. * * \ingroup bottleneck_distance */ struct Persistence_Diagram { - const_iterator cbegin() const; - const_iterator cend() const; + const_iterator begin(); + const_iterator end(); }; } // namespace bottleneck_distance diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp index fd0f8ed5..b1b98a82 100644 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_example.cpp @@ -73,5 +73,5 @@ int main( int argc , char** argv ) tolerance = atof( argv[3] ); } double b = Gudhi::bottleneck_distance::compute(diag1, diag2, tolerance); - std::cout << "The distance between the diagrams is : " << b << ". The tolerace is : " << tolerance << std::endl; + std::cout << "The distance between the diagrams is : " << b << ". The tolerance is : " << tolerance << std::endl; } diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index 1ae7788c..71845e25 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -29,17 +29,6 @@ namespace Gudhi { namespace bottleneck_distance { -/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. You get an additive e-approximation. - * - * - * \ingroup bottleneck_distance - */ -template -double compute(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); - -template -double compute_exactly(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2); - template double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { G::initialize(diag1, diag2, 0.); @@ -66,9 +55,14 @@ double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diag return sd.at(idmin); } +/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. + * If the last parameter e is not 0 (default value if not explicited), you get an additive e-approximation. + * + * \ingroup bottleneck_distance + */ template -double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { - if(e< std::numeric_limits::min()) +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=0.) { + if(e == 0.) return compute_exactly(diag1, diag2); G::initialize(diag1, diag2, e); int in = G::diameter()/e; diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h index 7af149e4..7d37b9e0 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h @@ -83,10 +83,10 @@ inline void G::initialize(const Persistence_diagram1 &diag1, v.clear(); for (auto it = diag1.cbegin(); it != diag1.cend(); ++it) if (it->second - it->first > e) - u.push_back(Internal_point(it->first, it->second, u.size())); + u.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), u.size())); for (auto it = diag2.cbegin(); it != diag2.cend(); ++it) if (it->second - it->first > e) - v.push_back(Internal_point(it->first, it->second, v.size())); + v.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), v.size())); if (u.size() < v.size()) swap(u, v); } diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index b757ce54..e2cd3c05 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -186,4 +186,5 @@ BOOST_AUTO_TEST_CASE(global){ v2.emplace_back(std::max(a,b),std::max(a,b)+y); } BOOST_CHECK(compute(v1, v2) <= upper_bound/100.); + BOOST_CHECK(compute(v1, v2, upper_bound/1000.) <= upper_bound/100. + upper_bound/1000.); } -- cgit v1.2.3 From 135c83e90e3c0421f6ca08622552edf5e18023d6 Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 25 Nov 2016 13:22:08 +0000 Subject: copyrigths git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1784 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0f17a81c0c8ef507d49f0b8a78afc195a957e7f1 --- .../concept/Persistence_diagram.h | 4 +- .../doc/Intro_bottleneck_distance.h | 4 +- .../example/bottleneck_example.cpp | 4 +- src/Bottleneck_distance/test/bottleneck_chrono.cpp | 49 +++++++++++----------- .../test/bottleneck_unit_test.cpp | 4 +- 5 files changed, 32 insertions(+), 33 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 1ab768ba..fe13e859 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -2,9 +2,9 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author(s): François Godi + * Author: François Godi * - * Copyright (C) 2016 INRIA + * 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 diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index ccb558c5..1f443f7f 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -2,9 +2,9 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author(s): François Godi + * Author: François Godi * - * Copyright (C) 2015 INRIA Sophia-Antipolis (France) + * Copyright (C) 2015 INRIA (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 diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp index b1b98a82..28e458a5 100644 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_example.cpp @@ -2,9 +2,9 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author(s): Francois Godi, small modifications by Pawel Dlotko + * Authors: Francois Godi, small modifications by Pawel Dlotko * - * Copyright (C) 2015 INRIA Saclay (France) + * Copyright (C) 2015 INRIA (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 diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp index 4c4f4ee6..a7440ecd 100644 --- a/src/Bottleneck_distance/test/bottleneck_chrono.cpp +++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp @@ -2,9 +2,9 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author(s): Francois Godi + * Author: Francois Godi * - * Copyright (C) 2015 INRIA Sophia-Antipolis (France) + * Copyright (C) 2015 INRIA (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 @@ -34,29 +34,28 @@ int main(){ std::ofstream objetfichier; objetfichier.open("results.csv", std::ios::out); - for(int n=0; n<=4000; n+=400){ - std::uniform_real_distribution unif1(0.,upper_bound); - std::uniform_real_distribution unif2(upper_bound/1000.,upper_bound/100.); - std::default_random_engine re; - std::vector< std::pair > v1, v2; - for (int i = 0; i < n; i++) { - double a = unif1(re); - double b = unif1(re); - double x = unif2(re); - double y = unif2(re); - v1.emplace_back(std::min(a,b), std::max(a,b)); - v2.emplace_back(std::min(a,b)+std::min(x,y), std::max(a,b)+std::max(x,y)); - if(i%5==0) - v1.emplace_back(std::min(a,b),std::min(a,b)+x); - if(i%3==0) - v2.emplace_back(std::max(a,b),std::max(a,b)+y); - } - std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now(); - double b = compute(v1,v2, 0.0001); - std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); - typedef std::chrono::duration millisecs_t; - millisecs_t duration(std::chrono::duration_cast(end-start)); - objetfichier << n << ";" << duration.count() << ";" << b << std::endl; + int n = 1200; + std::uniform_real_distribution unif1(0.,upper_bound); + std::uniform_real_distribution unif2(upper_bound/1000.,upper_bound/100.); + std::default_random_engine re; + std::vector< std::pair > v1, v2; + for (int i = 0; i < n; i++) { + double a = unif1(re); + double b = unif1(re); + double x = unif2(re); + double y = unif2(re); + v1.emplace_back(std::min(a,b), std::max(a,b)); + v2.emplace_back(std::min(a,b)+std::min(x,y), std::max(a,b)+std::max(x,y)); + if(i%5==0) + v1.emplace_back(std::min(a,b),std::min(a,b)+x); + if(i%3==0) + v2.emplace_back(std::max(a,b),std::max(a,b)+y); } + std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now(); + double b = compute(v1,v2, 0.0001); + std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); + typedef std::chrono::duration millisecs_t; + millisecs_t duration(std::chrono::duration_cast(end-start)); + objetfichier << n << ";" << duration.count() << ";" << b << std::endl; objetfichier.close(); } diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index e2cd3c05..31ba18ad 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -2,9 +2,9 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author(s): Francois Godi + * Author: Francois Godi * - * Copyright (C) 2015 INRIA Sophia-Antipolis (France) + * Copyright (C) 2015 INRIA (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 -- cgit v1.2.3 From cc1e554f26765bf9993079bef608d9bc4a3308c8 Mon Sep 17 00:00:00 2001 From: fgodi Date: Mon, 28 Nov 2016 14:15:22 +0000 Subject: graph no longer static git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1790 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6bbb8dfaffd09a81ccafac6919e073ed74b9c7e6 --- .../concept/Persistence_diagram.h | 4 +- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 22 +++--- .../include/gudhi/Construct_coord_iterator.h | 42 ---------- .../include/gudhi/Graph_matching.h | 18 +++-- .../include/gudhi/Internal_point.h | 18 ++++- .../include/gudhi/Neighbors_finder.h | 36 +++++---- .../test/bottleneck_unit_test.cpp | 92 ++++++++++++---------- 7 files changed, 107 insertions(+), 125 deletions(-) delete mode 100644 src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index fe13e859..2ca10094 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -41,8 +41,8 @@ struct Diagram_point{ */ struct Persistence_Diagram { - const_iterator begin(); - const_iterator end(); + iterator begin(); + iterator end(); }; } // namespace bottleneck_distance diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index bb0a13d2..52de30be 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -31,14 +31,14 @@ namespace bottleneck_distance { template double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { - G::initialize(diag1, diag2, 0.); - std::vector sd(G::sorted_distances()); + Persistence_graph g(diag1, diag2, 0.); + std::vector sd(g.sorted_distances()); int idmin = 0; int idmax = sd.size() - 1; - // alpha can be modified, this will change the complexity + // alpha can change the complexity double alpha = pow(sd.size(), 0.25); - Graph_matching m; - Graph_matching biggest_unperfect; + Graph_matching m(g); + Graph_matching biggest_unperfect(g); while (idmin != idmax) { int step = static_cast((idmax - idmin) / alpha); m.set_r(sd.at(idmin + step)); @@ -64,14 +64,14 @@ template double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=0.) { if(e == 0.) return compute_exactly(diag1, diag2); - G::initialize(diag1, diag2, e); - int in = G::diameter()/e + 1; + Persistence_graph g(diag1, diag2, e); + int in = g.diameter_bound()/e + 1; int idmin = 0; int idmax = in; - // alpha can be modified, this will change the complexity - double alpha = pow(in, 0.25); - Graph_matching m; - Graph_matching biggest_unperfect; + // alpha can change the complexity + double alpha = pow(in, 0.10); + Graph_matching m(g); + Graph_matching biggest_unperfect(g); while (idmin != idmax) { int step = static_cast((idmax - idmin) / alpha); m.set_r(e*(idmin + step)); diff --git a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h b/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h deleted file mode 100644 index 0959dd03..00000000 --- a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h +++ /dev/null @@ -1,42 +0,0 @@ -/* 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: Francois Godi - * - * Copyright (C) 2015 INRIA (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 . - */ - -#ifndef SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ -#define SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ - -#include - -namespace CGAL { - -typedef Gudhi::bottleneck_distance::Internal_point Internal_point; - -struct Construct_coord_iterator { - typedef const double* result_type; - const double* operator()(const Internal_point& p) const - { return p.vec; } - const double* operator()(const Internal_point& p, int) const - { return p.vec+2; } -}; - -} //namespace CGAL - -#endif // SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index fa20b2a2..10b7073a 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -36,7 +36,7 @@ namespace bottleneck_distance { class Graph_matching { public: /** \internal \brief Constructor constructing an empty matching. */ - explicit Graph_matching(); + explicit Graph_matching(Persistence_graph &g); /** \internal \brief Copy operator. */ Graph_matching& operator=(const Graph_matching& m); /** \internal \brief Is the matching perfect ? */ @@ -47,6 +47,7 @@ public: void set_r(double r); private: + Persistence_graph& g; double r; /** \internal \brief Given a point from V, provides its matched point in U, null_point_index() if there isn't. */ std::vector v_to_u; @@ -61,13 +62,14 @@ private: void update(std::vector & path); }; -inline Graph_matching::Graph_matching() - : r(0.), v_to_u(G::size(), null_point_index()), unmatched_in_u() { - for (int u_point_index = 0; u_point_index < G::size(); ++u_point_index) +inline Graph_matching::Graph_matching(Persistence_graph& g) + : g(g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u() { + for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index) unmatched_in_u.emplace_back(u_point_index); } inline Graph_matching& Graph_matching::operator=(const Graph_matching& m) { + g = m.g; r = m.r; v_to_u = m.v_to_u; unmatched_in_u = m.unmatched_in_u; @@ -83,7 +85,7 @@ inline bool Graph_matching::multi_augment() { return false; Layered_neighbors_finder layered_nf(layering()); int max_depth = layered_nf.vlayers_number()*2 - 1; - double rn = sqrt(G::size()); + double rn = sqrt(g.size()); // verification of a necessary criterion in order to shortcut if possible if (max_depth <0 || (unmatched_in_u.size() > rn && max_depth >= rn)) return false; @@ -130,10 +132,10 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u inline Layered_neighbors_finder Graph_matching::layering() const { std::list u_vertices(unmatched_in_u); std::list v_vertices; - Neighbors_finder nf(r); - for (int v_point_index = 0; v_point_index < G::size(); ++v_point_index) + Neighbors_finder nf(g, r); + for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) nf.add(v_point_index); - Layered_neighbors_finder layered_nf(r); + Layered_neighbors_finder layered_nf(g, r); for(int layer = 0; !u_vertices.empty(); layer++) { // one layer is one step in the BFS for (auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) { diff --git a/src/Bottleneck_distance/include/gudhi/Internal_point.h b/src/Bottleneck_distance/include/gudhi/Internal_point.h index 78aad470..1a050d48 100644 --- a/src/Bottleneck_distance/include/gudhi/Internal_point.h +++ b/src/Bottleneck_distance/include/gudhi/Internal_point.h @@ -35,7 +35,7 @@ struct Internal_point { double vec[2]; int point_index; Internal_point() {} - Internal_point(double x, double y, int p_i = null_point_index()) { vec[0]=x; vec[1]=y; point_index = p_i; } + Internal_point(double x, double y, int p_i) { vec[0]=x; vec[1]=y; point_index = p_i; } double x() const { return vec[ 0 ]; } double y() const { return vec[ 1 ]; } double& x() { return vec[ 0 ]; } @@ -44,7 +44,7 @@ struct Internal_point { { return point_index==p.point_index; } - bool operator!=(const Internal_point& p) const { return ! (*this == p); } + bool operator!=(const Internal_point& p) const { return !(*this == p); } }; inline int null_point_index() { @@ -55,4 +55,18 @@ inline int null_point_index() { } // namespace Gudhi +namespace CGAL { + +typedef Gudhi::bottleneck_distance::Internal_point Internal_point; + +struct Construct_coord_iterator { + typedef const double* result_type; + const double* operator()(const Internal_point& p) const + { return p.vec; } + const double* operator()(const Internal_point& p, int) const + { return p.vec+2; } +}; + +} //namespace CGAL + #endif // INTERNAL_POINT_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index f2d9abb2..f28e21a2 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -31,8 +31,8 @@ #include #include -#include -#include +#include +#include #include @@ -57,7 +57,7 @@ class Neighbors_finder { public: /** \internal \brief Constructor taking the near distance definition as parameter. */ - Neighbors_finder(double r); + Neighbors_finder(const Persistence_graph& g, double r); /** \internal \brief A point added will be possibly pulled. */ void add(int v_point_index); /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ @@ -66,6 +66,7 @@ public: std::vector pull_all_near(int u_point_index); private: + const Persistence_graph& g; const double r; Kd_tree kd_t; std::unordered_set projections_f; @@ -81,7 +82,7 @@ private: class Layered_neighbors_finder { public: /** \internal \brief Constructor taking the near distance definition as parameter. */ - Layered_neighbors_finder(double r); + Layered_neighbors_finder(const Persistence_graph& g, double r); /** \internal \brief A point added will be possibly pulled. */ void add(int v_point_index, int vlayer); /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ @@ -90,43 +91,44 @@ public: int vlayers_number() const; private: + const Persistence_graph& g; const double r; std::vector> neighbors_finder; }; -inline Neighbors_finder::Neighbors_finder(double r) : - r(r), kd_t(), projections_f() { } +inline Neighbors_finder::Neighbors_finder(const Persistence_graph& g, double r) : + g(g), r(r), kd_t(), projections_f() { } inline void Neighbors_finder::add(int v_point_index) { - if (G::on_the_v_diagonal(v_point_index)) + if (g.on_the_v_diagonal(v_point_index)) projections_f.emplace(v_point_index); else - kd_t.insert(G::get_v_point(v_point_index)); + kd_t.insert(g.get_v_point(v_point_index)); } inline int Neighbors_finder::pull_near(int u_point_index) { int tmp; - int c = G::corresponding_point_in_v(u_point_index); - if (G::on_the_u_diagonal(u_point_index) && !projections_f.empty()){ + int c = g.corresponding_point_in_v(u_point_index); + if (g.on_the_u_diagonal(u_point_index) && !projections_f.empty()){ //Any pair of projection is at distance 0 tmp = *projections_f.cbegin(); projections_f.erase(tmp); } - else if (projections_f.count(c) && (G::distance(u_point_index, c) <= r)){ + else if (projections_f.count(c) && (g.distance(u_point_index, c) <= r)){ //Is the query point near to its projection ? tmp = c; projections_f.erase(tmp); } else{ //Is the query point near to a V point in the plane ? - Internal_point u_point = G::get_u_point(u_point_index); + Internal_point u_point = g.get_u_point(u_point_index); std::vector w = {1., 1.}; K_neighbor_search search(kd_t, u_point, 0., true, Distance(0, 2, w)); auto it = search.begin(); - if(it==search.end() || G::distance(u_point_index, it->first.point_index) > r) + if(it==search.end() || g.distance(u_point_index, it->first.point_index) > r) return null_point_index(); tmp = it->first.point_index; - kd_t.remove(G::get_v_point(tmp)); + kd_t.remove(g.get_v_point(tmp)); } return tmp; } @@ -141,12 +143,12 @@ inline std::vector Neighbors_finder::pull_all_near(int u_point_index) { return all_pull; } -inline Layered_neighbors_finder::Layered_neighbors_finder(double r) : - r(r), neighbors_finder() { } +inline Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_graph& g, double r) : + g(g), r(r), neighbors_finder() { } inline void Layered_neighbors_finder::add(int v_point_index, int vlayer) { for (int l = neighbors_finder.size(); l <= vlayer; l++) - neighbors_finder.emplace_back(std::shared_ptr(new Neighbors_finder(r))); + neighbors_finder.emplace_back(std::shared_ptr(new Neighbors_finder(g, r))); neighbors_finder.at(vlayer)->add(v_point_index); } diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index 7edfa062..2237b073 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -34,11 +34,13 @@ int n1 = 81; // a natural number >0 int n2 = 180; // a natural number >0 double upper_bound = 406.43; // any real >0 + +std::uniform_real_distribution unif(0.,upper_bound); +std::default_random_engine re; +std::vector< std::pair > v1, v2; + BOOST_AUTO_TEST_CASE(persistence_diagrams_graph){ // Random construction - std::uniform_real_distribution unif(0.,upper_bound); - std::default_random_engine re; - std::vector< std::pair > v1, v2; for (int i = 0; i < n1; i++) { double a = unif(re); double b = unif(re); @@ -49,83 +51,87 @@ BOOST_AUTO_TEST_CASE(persistence_diagrams_graph){ double b = unif(re); v2.emplace_back(std::min(a,b), std::max(a,b)); } - G::initialize(v1, v2, 0.); - std::vector d(G::sorted_distances()); + Persistence_graph g(v1, v2, 0.); + std::vector d(g.sorted_distances()); // - BOOST_CHECK(!G::on_the_u_diagonal(n1-1)); - BOOST_CHECK(!G::on_the_u_diagonal(n1)); - BOOST_CHECK(!G::on_the_u_diagonal(n2-1)); - BOOST_CHECK(G::on_the_u_diagonal(n2)); - BOOST_CHECK(!G::on_the_v_diagonal(n1-1)); - BOOST_CHECK(G::on_the_v_diagonal(n1)); - BOOST_CHECK(G::on_the_v_diagonal(n2-1)); - BOOST_CHECK(G::on_the_v_diagonal(n2)); + BOOST_CHECK(!g.on_the_u_diagonal(n1-1)); + BOOST_CHECK(!g.on_the_u_diagonal(n1)); + BOOST_CHECK(!g.on_the_u_diagonal(n2-1)); + BOOST_CHECK(g.on_the_u_diagonal(n2)); + BOOST_CHECK(!g.on_the_v_diagonal(n1-1)); + BOOST_CHECK(g.on_the_v_diagonal(n1)); + BOOST_CHECK(g.on_the_v_diagonal(n2-1)); + BOOST_CHECK(g.on_the_v_diagonal(n2)); // - BOOST_CHECK(G::corresponding_point_in_u(0)==n2); - BOOST_CHECK(G::corresponding_point_in_u(n1)==0); - BOOST_CHECK(G::corresponding_point_in_v(0)==n1); - BOOST_CHECK(G::corresponding_point_in_v(n2)==0); + BOOST_CHECK(g.corresponding_point_in_u(0)==n2); + BOOST_CHECK(g.corresponding_point_in_u(n1)==0); + BOOST_CHECK(g.corresponding_point_in_v(0)==n1); + BOOST_CHECK(g.corresponding_point_in_v(n2)==0); // - BOOST_CHECK(G::size()==(n1+n2)); + BOOST_CHECK(g.size()==(n1+n2)); // BOOST_CHECK((int) d.size() <= (n1+n2)*(n1+n2) - n1*n2 + 1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,0))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,n1-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,n1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,n2-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,n2))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(0,(n1+n2)-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,0))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,n1-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,n1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,n2-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,n2))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance(n1,(n1+n2)-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,0))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,n1-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,n1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,n2-1))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,n2))==1); - BOOST_CHECK(std::count(d.begin(), d.end(), G::distance((n1+n2)-1,(n1+n2)-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,0))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n1-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n2-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n2))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,(n1+n2)-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,0))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,n1-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,n1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,n2-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,n2))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(n1,(n1+n2)-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,0))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,n1-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,n1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,n2-1))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,n2))==1); + BOOST_CHECK(std::count(d.begin(), d.end(), g.distance((n1+n2)-1,(n1+n2)-1))==1); } BOOST_AUTO_TEST_CASE(neighbors_finder) { - Neighbors_finder nf(1.); + Persistence_graph g(v1, v2, 0.); + Neighbors_finder nf(g, 1.); for(int v_point_index=1; v_point_index<((n2+n1)*9/10); v_point_index+=2) nf.add(v_point_index); // int v_point_index_1 = nf.pull_near(n2/2); - BOOST_CHECK((v_point_index_1 == -1) || (G::distance(n2/2,v_point_index_1)<=1.)); + BOOST_CHECK((v_point_index_1 == -1) || (g.distance(n2/2,v_point_index_1)<=1.)); std::vector l = nf.pull_all_near(n2/2); bool v = true; for(auto it = l.cbegin(); it != l.cend(); ++it) - v = v && (G::distance(n2/2,*it)>1.); + v = v && (g.distance(n2/2,*it)>1.); BOOST_CHECK(v); int v_point_index_2 = nf.pull_near(n2/2); BOOST_CHECK(v_point_index_2 == -1); } BOOST_AUTO_TEST_CASE(layered_neighbors_finder) { - Layered_neighbors_finder lnf(1.); + Persistence_graph g(v1, v2, 0.); + Layered_neighbors_finder lnf(g, 1.); for(int v_point_index=1; v_point_index<((n2+n1)*9/10); v_point_index+=2) lnf.add(v_point_index, v_point_index % 7); // int v_point_index_1 = lnf.pull_near(n2/2,6); - BOOST_CHECK((v_point_index_1 == -1) || (G::distance(n2/2,v_point_index_1)<=1.)); + BOOST_CHECK((v_point_index_1 == -1) || (g.distance(n2/2,v_point_index_1)<=1.)); int v_point_index_2 = lnf.pull_near(n2/2,6); BOOST_CHECK(v_point_index_2 == -1); v_point_index_1 = lnf.pull_near(n2/2,0); - BOOST_CHECK((v_point_index_1 == -1) || (G::distance(n2/2,v_point_index_1)<=1.)); + BOOST_CHECK((v_point_index_1 == -1) || (g.distance(n2/2,v_point_index_1)<=1.)); v_point_index_2 = lnf.pull_near(n2/2,0); BOOST_CHECK(v_point_index_2 == -1); } BOOST_AUTO_TEST_CASE(graph_matching) { - Graph_matching m1; + Persistence_graph g(v1, v2, 0.); + Graph_matching m1(g); m1.set_r(0.); int e = 0; while (m1.multi_augment()) ++e; + BOOST_CHECK(e > 0); BOOST_CHECK(e <= 2*sqrt(2*(n1+n2))); Graph_matching m2 = m1; BOOST_CHECK(!m2.multi_augment()); -- cgit v1.2.3 From 759b53891e1572df0ea0562828fcd88d8f8f3031 Mon Sep 17 00:00:00 2001 From: fgodi Date: Tue, 29 Nov 2016 09:00:07 +0000 Subject: basic example, infinity git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1797 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 23432677e7f1628dda596e9ba31138fc5063a608 --- .../concept/Persistence_diagram.h | 3 +- src/Bottleneck_distance/example/CMakeLists.txt | 3 +- .../example/bottleneck_basic_example.cpp | 48 ++++++++++++++ .../example/bottleneck_example.cpp | 77 ---------------------- .../example/bottleneck_read_file_example.cpp | 77 ++++++++++++++++++++++ .../include/gudhi/Persistence_graph.h | 5 +- .../test/bottleneck_unit_test.cpp | 4 +- 7 files changed, 134 insertions(+), 83 deletions(-) create mode 100644 src/Bottleneck_distance/example/bottleneck_basic_example.cpp delete mode 100644 src/Bottleneck_distance/example/bottleneck_example.cpp create mode 100644 src/Bottleneck_distance/example/bottleneck_read_file_example.cpp (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 2ca10094..d55f5573 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -27,7 +27,8 @@ namespace Gudhi { namespace bottleneck_distance { -/** \brief Concept of persistence diagram point. get<0>() must return the birth of the component and get<1>() its death. +/** \brief Concept of Diagram_point. get<0>() must return the birth of the corresponding component and get<1>() its death. + * If the component stay alive, get<1>() must return std::numeric_limits::infinity(). * * \ingroup bottleneck_distance */ diff --git a/src/Bottleneck_distance/example/CMakeLists.txt b/src/Bottleneck_distance/example/CMakeLists.txt index 6f3204f6..cd53ccfc 100644 --- a/src/Bottleneck_distance/example/CMakeLists.txt +++ b/src/Bottleneck_distance/example/CMakeLists.txt @@ -6,7 +6,8 @@ project(Bottleneck_distance_examples) if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.8.0) if (EIGEN3_FOUND) - add_executable (bottleneck_example bottleneck_example.cpp) + add_executable (bottleneck_read_file_example bottleneck_read_file_example.cpp) + add_executable (bottleneck_basic_example bottleneck_basic_example.cpp) endif() endif () endif() diff --git a/src/Bottleneck_distance/example/bottleneck_basic_example.cpp b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp new file mode 100644 index 00000000..95548579 --- /dev/null +++ b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp @@ -0,0 +1,48 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Authors: Francois Godi, small modifications by Pawel Dlotko + * + * Copyright (C) 2015 INRIA (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 . + */ + +#include +#include + +int main() { + + std::vector< std::pair > v1, v2; + + v1.emplace_back(2.7, 3.7); + v1.emplace_back(9.6, 14.); + v1.emplace_back(34.2, 34.974); + v1.emplace_back(3., std::numeric_limits::infinity()); + + v2.emplace_back(2.8, 4.45); + v2.emplace_back(9.5, 14.1); + v2.emplace_back(3.2, std::numeric_limits::infinity()); + + + double b = Gudhi::bottleneck_distance::compute(v1, v2); + + std::cout << "Bottleneck distance = " << b << std::endl; + + b = Gudhi::bottleneck_distance::compute(v1, v2, 0.1); + + std::cout << "Approx bottleneck distance = " << b << std::endl; + +} diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp deleted file mode 100644 index 28e458a5..00000000 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ /dev/null @@ -1,77 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Authors: Francois Godi, small modifications by Pawel Dlotko - * - * Copyright (C) 2015 INRIA (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 . - */ - -#define CGAL_HAS_THREADS - -#include -#include -#include -#include -#include - -std::vector< std::pair > read_diagram_from_file( const char* filename ) -{ - std::ifstream in; - in.open( filename ); - std::vector< std::pair > result; - if ( !in.is_open() ) - { - std::cerr << "File : " << filename << " do not exist. The program will now terminate \n"; - throw "File do not exist \n"; - } - - std::string line; - while (!in.eof()) - { - getline(in,line); - if ( line.length() != 0 ) - { - std::stringstream lineSS; - lineSS << line; - double beginn, endd; - lineSS >> beginn; - lineSS >> endd; - result.push_back( std::make_pair( beginn , endd ) ); - } - } - in.close(); - return result; -} //read_diagram_from_file - -int main( int argc , char** argv ) -{ - if ( argc < 3 ) - { - std::cout << "To run this program please provide as an input two files with persistence diagrams. Each file " << - "should contain a birth-death pair per line. Third, optional parameter is an error bound on a bottleneck" << - " distance (set by default to zero). The program will now terminate \n"; - } - std::vector< std::pair< double , double > > diag1 = read_diagram_from_file( argv[1] ); - std::vector< std::pair< double , double > > diag2 = read_diagram_from_file( argv[2] ); - double tolerance = 0; - if ( argc == 4 ) - { - tolerance = atof( argv[3] ); - } - double b = Gudhi::bottleneck_distance::compute(diag1, diag2, tolerance); - std::cout << "The distance between the diagrams is : " << b << ". The tolerance is : " << tolerance << std::endl; -} diff --git a/src/Bottleneck_distance/example/bottleneck_read_file_example.cpp b/src/Bottleneck_distance/example/bottleneck_read_file_example.cpp new file mode 100644 index 00000000..4a503e4c --- /dev/null +++ b/src/Bottleneck_distance/example/bottleneck_read_file_example.cpp @@ -0,0 +1,77 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Authors: Francois Godi, small modifications by Pawel Dlotko + * + * Copyright (C) 2015 INRIA (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 . + */ + +#define CGAL_HAS_THREADS + +#include +#include +#include +#include +#include + +std::vector< std::pair > read_diagram_from_file( const char* filename ) +{ + std::ifstream in; + in.open( filename ); + std::vector< std::pair > result; + if ( !in.is_open() ) + { + std::cerr << "File : " << filename << " do not exist. The program will now terminate \n"; + throw "File do not exist \n"; + } + + std::string line; + while (!in.eof()) + { + getline(in,line); + if ( line.length() != 0 ) + { + std::stringstream lineSS; + lineSS << line; + double beginn, endd; + lineSS >> beginn; + lineSS >> endd; + result.push_back( std::make_pair( beginn , endd ) ); + } + } + in.close(); + return result; +} //read_diagram_from_file + +int main( int argc , char** argv ) +{ + if ( argc < 3 ) + { + std::cout << "To run this program please provide as an input two files with persistence diagrams. Each file " << + "should contain a birth-death pair per line. Third, optional parameter is an error bound on a bottleneck" << + " distance (set by default to zero). The program will now terminate \n"; + } + std::vector< std::pair< double , double > > diag1 = read_diagram_from_file( argv[1] ); + std::vector< std::pair< double , double > > diag2 = read_diagram_from_file( argv[2] ); + double tolerance = 0.; + if ( argc == 4 ) + { + tolerance = atof( argv[3] ); + } + double b = Gudhi::bottleneck_distance::compute(diag1, diag2, tolerance); + std::cout << "The distance between the diagrams is : " << b << ". The tolerance is : " << tolerance << std::endl; +} diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index a4ea6968..506dba52 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -74,10 +74,10 @@ Persistence_graph::Persistence_graph(const Persistence_diagram1 &diag1, : u(), v() { for (auto it = diag1.cbegin(); it != diag1.cend(); ++it) - if (it->second - it->first > e) + if (it->second != std::numeric_limits::infinity() && it->second - it->first > e) u.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), u.size())); for (auto it = diag2.cbegin(); it != diag2.cend(); ++it) - if (it->second - it->first > e) + if (it->second != std::numeric_limits::infinity() && it->second - it->first > e) v.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), v.size())); if (u.size() < v.size()) swap(u, v); @@ -120,6 +120,7 @@ inline std::vector Persistence_graph::sorted_distances() const { for (int u_point_index = 0; u_point_index < size(); ++u_point_index) for (int v_point_index = 0; v_point_index < size(); ++v_point_index) sorted_distances.emplace(distance(u_point_index, v_point_index)); + sorted_distances.emplace(std::numeric_limits::infinity()); return std::vector(sorted_distances.begin(),sorted_distances.end()); } diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index 2237b073..84101274 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -39,7 +39,7 @@ std::uniform_real_distribution unif(0.,upper_bound); std::default_random_engine re; std::vector< std::pair > v1, v2; -BOOST_AUTO_TEST_CASE(persistence_diagrams_graph){ +BOOST_AUTO_TEST_CASE(persistence_graph){ // Random construction for (int i = 0; i < n1; i++) { double a = unif(re); @@ -70,7 +70,7 @@ BOOST_AUTO_TEST_CASE(persistence_diagrams_graph){ // BOOST_CHECK(g.size()==(n1+n2)); // - BOOST_CHECK((int) d.size() <= (n1+n2)*(n1+n2) - n1*n2 + 1); + BOOST_CHECK((int) d.size() <= (n1+n2)*(n1+n2) - n1*n2 + 2); BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,0))==1); BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n1-1))==1); BOOST_CHECK(std::count(d.begin(), d.end(), g.distance(0,n1))==1); -- cgit v1.2.3 From d0db67f8ff185a7698d2f6643d86e43955bab882 Mon Sep 17 00:00:00 2001 From: fgodi Date: Tue, 6 Dec 2016 16:20:10 +0000 Subject: infinite points separately computed git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1828 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5d1cd63a1b8ff26feffce86a4febe2f42d52340d --- .../concept/Persistence_diagram.h | 16 ++++------- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 11 +++++--- .../include/gudhi/Persistence_graph.h | 33 +++++++++++++--------- 3 files changed, 33 insertions(+), 27 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index d55f5573..e4766628 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -27,24 +27,20 @@ namespace Gudhi { namespace bottleneck_distance { -/** \brief Concept of Diagram_point. get<0>() must return the birth of the corresponding component and get<1>() its death. - * If the component stay alive, get<1>() must return std::numeric_limits::infinity(). +/** \brief Concept of Diagram_point. std::get<0>(point) must return the birth of the corresponding component and std::get<1>(point) its death. + * A valid implementation of this concept is std::pair. + * Birth must be 0 or positive, death should be larger than birth, death can be std::numeric_limits::infinity() for components which stay alive. * * \ingroup bottleneck_distance */ -struct Diagram_point{ - double get(); -}; +struct Diagram_point; /** \brief Concept of persistence diagram. It's a range of Diagram_point. + * std::begin(diagram) and std::end(diagram) must return corresponding iterators. * * \ingroup bottleneck_distance */ -struct Persistence_Diagram -{ - iterator begin(); - iterator end(); -}; +struct Persistence_Diagram; } // namespace bottleneck_distance diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index 20225e80..4a69fb96 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -24,12 +24,13 @@ #define BOTTLENECK_H_ #include +#include namespace Gudhi { namespace bottleneck_distance { -/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. +/** \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 (default value if not explicited), you get an additive e-approximation. * * \ingroup bottleneck_distance @@ -37,7 +38,8 @@ namespace bottleneck_distance { template double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=0.) { Persistence_graph g(diag1, diag2, e); - if(!g.alive_match()) + double b = g.bottleneck_alive(); + if(b == std::numeric_limits::infinity()) return std::numeric_limits::infinity(); std::vector sd; if(e == 0.) @@ -45,7 +47,7 @@ double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &di long idmin = 0; long idmax = e==0. ? sd.size() - 1 : g.diameter_bound()/e + 1; // alpha can change the complexity - double alpha = pow(idmax, 0.25); + double alpha = std::pow(idmax, 0.25); Graph_matching m(g); Graph_matching biggest_unperfect(g); while (idmin != idmax) { @@ -61,7 +63,8 @@ double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &di idmin = idmin + step + 1; } } - return e == 0. ? sd.at(idmin) : e*(idmin); + b = std::max(b, e == 0. ? sd.at(idmin) : e*(idmin)); + return b; } diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index d31a4826..8accb926 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -55,7 +55,7 @@ public: /** \internal \brief Returns size = |U| = |V|. */ int size() const; /** \internal \brief Is there as many infinite points (alive components) in both diagrams ? */ - bool alive_match() const; + double bottleneck_alive() const; /** \internal \brief Returns the O(n^2) sorted distances between the points. */ std::vector sorted_distances() const; /** \internal \brief Returns an upper bound for the diameter of the convex hull of all non infinite points */ @@ -68,26 +68,29 @@ public: private: std::vector u; std::vector v; - int alive_count; + std::vector u_alive; + std::vector v_alive; }; template Persistence_graph::Persistence_graph(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) - : u(), v(), alive_count(0) + : u(), v(), u_alive(), v_alive() { for (auto it = std::begin(diag1); it != std::end(diag1); ++it){ if(std::get<1>(*it) == std::numeric_limits::infinity()) - alive_count++; - if (std::get<1>(*it) - std::get<0>(*it) > e) + u_alive.push_back(std::get<0>(*it)); + else if (std::get<1>(*it) - std::get<0>(*it) > e) u.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), u.size())); } for (auto it = std::begin(diag2); it != std::end(diag2); ++it){ if(std::get<1>(*it) == std::numeric_limits::infinity()) - alive_count--; - if (std::get<1>(*it) - std::get<0>(*it) > e) + v_alive.push_back(std::get<0>(*it)); + else if (std::get<1>(*it) - std::get<0>(*it) > e) v.push_back(Internal_point(std::get<0>(*it), std::get<1>(*it), v.size())); } + std::sort(u_alive.begin(), u_alive.end()); + std::sort(v_alive.begin(), v_alive.end()); if (u.size() < v.size()) swap(u, v); } @@ -115,8 +118,6 @@ inline double Persistence_graph::distance(int u_point_index, int v_point_index) return 0.; Internal_point p_u = get_u_point(u_point_index); Internal_point p_v = get_v_point(v_point_index); - if(p_u.y() == p_v.y()) - return std::fabs(p_u.x() - p_v.x()); return std::max(std::fabs(p_u.x() - p_v.x()), std::fabs(p_u.y() - p_v.y())); } @@ -124,8 +125,13 @@ inline int Persistence_graph::size() const { return static_cast (u.size() + v.size()); } -inline bool Persistence_graph::alive_match() const{ - return alive_count==0; +inline double Persistence_graph::bottleneck_alive() const{ + if(u_alive.size() != v_alive.size()) + return std::numeric_limits::infinity(); + double max = 0.; + for(auto it_u=u_alive.cbegin(), it_v=v_alive.cbegin();it_u != u_alive.cend();++it_u, ++it_v) + max = std::max(max, std::fabs(*it_u - *it_v)); + return max; } inline std::vector Persistence_graph::sorted_distances() const { @@ -159,12 +165,13 @@ inline Internal_point Persistence_graph::get_v_point(int v_point_index) const { inline double Persistence_graph::diameter_bound() const { double max = 0.; for(auto it = u.cbegin(); it != u.cend(); it++) - max = std::max(max,it->y() == std::numeric_limits::infinity() ? it->x() : it->y()); + max = std::max(max, it->y()); for(auto it = v.cbegin(); it != v.cend(); it++) - max = std::max(max,it->y() == std::numeric_limits::infinity() ? it->x() : it->y()); + max = std::max(max, it->y()); return max; } + } // namespace bottleneck_distance } // namespace Gudhi -- cgit v1.2.3 From f1a8c07758aa66c3a95effd7a898e8a063b5f3ce Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 16 Dec 2016 12:56:39 +0000 Subject: small modifications (doc) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1899 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e1a9e88af05611d3572830a719ca9ee0d042144e --- src/Bottleneck_distance/concept/Persistence_diagram.h | 2 +- src/Bottleneck_distance/test/bottleneck_chrono.cpp | 3 +-- 2 files changed, 2 insertions(+), 3 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index e4766628..2d841086 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -29,7 +29,7 @@ namespace bottleneck_distance { /** \brief Concept of Diagram_point. std::get<0>(point) must return the birth of the corresponding component and std::get<1>(point) its death. * A valid implementation of this concept is std::pair. - * Birth must be 0 or positive, death should be larger than birth, death can be std::numeric_limits::infinity() for components which stay alive. + * Death should be larger than birth, death can be std::numeric_limits::infinity() for components which stay alive. * * \ingroup bottleneck_distance */ diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp index 1bff96f4..0a3bb012 100644 --- a/src/Bottleneck_distance/test/bottleneck_chrono.cpp +++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp @@ -51,9 +51,8 @@ int main(){ if(i%3==0) v2.emplace_back(std::max(a,b),std::max(a,b)+y); } - double epsilon = std::numeric_limits::epsilon(); std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now(); - double b = bottleneck_distance(v1,v2, epsilon); + double b = bottleneck_distance(v1, v2); std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); typedef std::chrono::duration millisecs_t; millisecs_t duration(std::chrono::duration_cast(end-start)); -- cgit v1.2.3 From c0ee17043a446279b63bd65482c82ebe207dc9d2 Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 16 Dec 2016 12:57:35 +0000 Subject: small modifications git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1900 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 31538228069cb6ef867be8aac231f11b5c8689f6 --- src/Bottleneck_distance/concept/Persistence_diagram.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/Bottleneck_distance/concept/Persistence_diagram.h') diff --git a/src/Bottleneck_distance/concept/Persistence_diagram.h b/src/Bottleneck_distance/concept/Persistence_diagram.h index 2d841086..2706716b 100644 --- a/src/Bottleneck_distance/concept/Persistence_diagram.h +++ b/src/Bottleneck_distance/concept/Persistence_diagram.h @@ -33,14 +33,14 @@ namespace bottleneck_distance { * * \ingroup bottleneck_distance */ -struct Diagram_point; +typename Diagram_point; /** \brief Concept of persistence diagram. It's a range of Diagram_point. * std::begin(diagram) and std::end(diagram) must return corresponding iterators. * * \ingroup bottleneck_distance */ -struct Persistence_Diagram; +typename Persistence_Diagram; } // namespace bottleneck_distance -- cgit v1.2.3