diff options
5 files changed, 47 insertions, 14 deletions
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<double,double>(2.8,4.45)); v2.push_back(std::pair<double,double>(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 @@ -214,6 +214,43 @@ double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &di if(e< std::numeric_limits<double>::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<int>((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<typename Persistence_diagram1, typename Persistence_diagram2> +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { + if(e< std::numeric_limits<double>::min()) + return compute_exactly(diag1, diag2); + G::initialize(diag1, diag2, e); double d = 0.; double f = G::diameter(); while (f-d > e){ @@ -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<double> > G::sorted_distances() { // could be optimized std::set<double> 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<double> unif1(0.,upper_bound); std::uniform_real_distribution<double> 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<int,std::milli> millisecs_t; millisecs_t duration(std::chrono::duration_cast<millisecs_t>(end-start)); |