From d85314eb2cd5b8487ee5cc5c9069e1c8ff311931 Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 3 Jun 2016 10:22:53 +0000 Subject: CGAL+ VERSION git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@1246 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b9bde0a97e56042b84d1850dea34e559dc196b91 --- .../example/bottleneck_example.cpp | 6 +-- .../include/gudhi/Graph_matching.h | 48 ++++++++++++++++++---- .../include/gudhi/Persistence_diagrams_graph.h | 1 + .../include/gudhi/Planar_neighbors_finder.h | 2 +- src/Bottleneck_distance/test/bottleneck_chrono.cpp | 4 +- 5 files changed, 47 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp index c6a06235..b3d26f3c 100644 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_example.cpp @@ -34,9 +34,9 @@ int main() { v2.push_back(std::pair(2.8,4.45)); v2.push_back(std::pair(9.5,14.1)); + double b = Gudhi::Bottleneck_distance::compute(v1, v2, 0.0001); + std::cout << "Approx. bottleneck distance = " << b << std::endl; - double b = Gudhi::Bottleneck_distance::compute(v1, v2); - + b = Gudhi::Bottleneck_distance::compute(v1, v2); std::cout << "Bottleneck distance = " << b << std::endl; - } diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index f0ce633f..69470067 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -209,6 +209,43 @@ double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diag return sd->at(idmin); } +template +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { + if(e< std::numeric_limits::min()) + return compute_exactly(diag1, diag2); + G::initialize(diag1, diag2, e); + int in = G::diameter()/e; + 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; + while (idmin != idmax) { + int step = static_cast((idmax - idmin) / alpha); + m.set_r(e*(idmin + step)); + while (m.multi_augment()); + //The above while compute a maximum matching (according to the r setted before) + if (m.perfect()) { + idmax = idmin + step; + m = biggest_unperfect; + } else { + biggest_unperfect = m; + idmin = idmin + step + 1; + } + } + return e*(idmin); +} + + + +} // namespace Bottleneck_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ + +/* Dichotomic version template double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { if(e< std::numeric_limits::min()) @@ -221,16 +258,11 @@ double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &di m.set_r((d+f)/2.); while (m.multi_augment()); //The above while compute a maximum matching (according to the r setted before) - if (m.perfect()) + if (m.perfect()) f = (d+f)/2.; - else + else d= (d+f)/2.; } return d; -} +} */ -} // namespace Bottleneck_distance - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h index 52e7c583..e31b2dae 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h @@ -129,6 +129,7 @@ inline int G::size() { inline std::shared_ptr< std::vector > G::sorted_distances() { // could be optimized std::set sorted_distances; + sorted_distances.emplace(0.); 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)); diff --git a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h index c0b6383f..3f3723c3 100644 --- a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h @@ -94,7 +94,7 @@ private: }; /** \internal \typedef \brief Planar_neighbors_finder is the used implementation. */ -typedef Naive_pnf Planar_neighbors_finder; +typedef Cgal_pnf Planar_neighbors_finder; inline Naive_pnf::Naive_pnf(double r_) : r(r_), grid() { } diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp index cde8afb1..8b49b6be 100644 --- a/src/Bottleneck_distance/test/bottleneck_chrono.cpp +++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp @@ -33,7 +33,7 @@ int main(){ std::ofstream objetfichier; objetfichier.open("results.csv", std::ios::out); - for(int n=0; n<=2500; n+=250){ + 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; @@ -51,7 +51,7 @@ int main(){ 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.01); + 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)); -- cgit v1.2.3