diff options
author | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-06-03 10:22:53 +0000 |
---|---|---|
committer | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-06-03 10:22:53 +0000 |
commit | d85314eb2cd5b8487ee5cc5c9069e1c8ff311931 (patch) | |
tree | 04bec913dbb862c98eae08baa9d42200f67c482b /src/Bottleneck_distance/include | |
parent | 714a97d8b9c64a0a5ccc837184def8122ec8b4cd (diff) |
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
Diffstat (limited to 'src/Bottleneck_distance/include')
3 files changed, 42 insertions, 9 deletions
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() { } |