diff options
author | Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> | 2022-11-09 10:45:26 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-11-09 10:45:26 +0100 |
commit | c47d7ed4537a2fb011eb43e265c777f8581ee9a3 (patch) | |
tree | 2065468a308d59b3120f1bd9f60024c9feca1977 | |
parent | fa6d978ab0b9cffa21bc26a9ccaee4dc0ae78818 (diff) | |
parent | 475a20c0645b079aaf204fd47398b7bb278fb490 (diff) |
Merge pull request #710 from hschreiber/bottleneck_distance_issue_fix
Bottleneck distance issue #701 fix
4 files changed, 123 insertions, 20 deletions
diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index 33f03b9c..c1e10f8e 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -20,6 +20,7 @@ #include <vector> #include <algorithm> #include <limits> // for numeric_limits +#include <cmath> namespace Gudhi { @@ -31,7 +32,7 @@ namespace persistence_diagram { * \ingroup bottleneck_distance */ class Persistence_graph { - public: +public: /** \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); @@ -58,7 +59,7 @@ class Persistence_graph { /** \internal \brief Returns the corresponding internal point */ Internal_point get_v_point(int v_point_index) const; - private: +private: std::vector<Internal_point> u; std::vector<Internal_point> v; double b_alive; @@ -67,30 +68,54 @@ class Persistence_graph { template<typename Persistence_diagram1, typename Persistence_diagram2> Persistence_graph::Persistence_graph(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) - : u(), v(), b_alive(0.) { + : u(), v(), b_alive(0.) { std::vector<double> u_alive; std::vector<double> v_alive; + std::vector<double> u_nalive; + std::vector<double> v_nalive; + int u_inf = 0; + int v_inf = 0; + double inf = std::numeric_limits<double>::infinity(); + double neginf = -inf; + for (auto it = std::begin(diag1); it != std::end(diag1); ++it) { - if (std::get<1>(*it) == std::numeric_limits<double>::infinity()) - 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())); + if (std::get<0>(*it) != inf && std::get<1>(*it) != neginf){ + if (std::get<0>(*it) == neginf && std::get<1>(*it) == inf) + u_inf++; + else if (std::get<0>(*it) == neginf) + u_nalive.push_back(std::get<1>(*it)); + else if (std::get<1>(*it) == inf) + 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<double>::infinity()) - 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())); + if (std::get<0>(*it) != inf && std::get<1>(*it) != neginf){ + if (std::get<0>(*it) == neginf && std::get<1>(*it) == inf) + v_inf++; + else if (std::get<0>(*it) == neginf) + v_nalive.push_back(std::get<1>(*it)); + else if (std::get<1>(*it) == inf) + 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())); + } } if (u.size() < v.size()) swap(u, v); - std::sort(u_alive.begin(), u_alive.end()); - std::sort(v_alive.begin(), v_alive.end()); - if (u_alive.size() != v_alive.size()) { + + if (u_alive.size() != v_alive.size() || u_nalive.size() != v_nalive.size() || u_inf != v_inf) { b_alive = std::numeric_limits<double>::infinity(); } else { + std::sort(u_alive.begin(), u_alive.end()); + std::sort(v_alive.begin(), v_alive.end()); + std::sort(u_nalive.begin(), u_nalive.end()); + std::sort(v_nalive.begin(), v_nalive.end()); for (auto it_u = u_alive.cbegin(), it_v = v_alive.cbegin(); it_u != u_alive.cend(); ++it_u, ++it_v) b_alive = (std::max)(b_alive, std::fabs(*it_u - *it_v)); + for (auto it_u = u_nalive.cbegin(), it_v = v_nalive.cbegin(); it_u != u_nalive.cend(); ++it_u, ++it_v) + b_alive = (std::max)(b_alive, std::fabs(*it_u - *it_v)); } } @@ -104,12 +129,12 @@ inline bool Persistence_graph::on_the_v_diagonal(int v_point_index) const { inline int Persistence_graph::corresponding_point_in_u(int v_point_index) const { return on_the_v_diagonal(v_point_index) ? - v_point_index - static_cast<int> (v.size()) : v_point_index + static_cast<int> (u.size()); + v_point_index - static_cast<int> (v.size()) : v_point_index + static_cast<int> (u.size()); } inline int Persistence_graph::corresponding_point_in_v(int u_point_index) const { return on_the_u_diagonal(u_point_index) ? - u_point_index - static_cast<int> (u.size()) : u_point_index + static_cast<int> (v.size()); + u_point_index - static_cast<int> (u.size()) : u_point_index + static_cast<int> (v.size()); } inline double Persistence_graph::distance(int u_point_index, int v_point_index) const { diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index 44141baa..9872f20c 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -159,3 +159,81 @@ BOOST_AUTO_TEST_CASE(global) { BOOST_CHECK(bottleneck_distance(empty, empty) == 0); BOOST_CHECK(bottleneck_distance(empty, one) == 1); } + +BOOST_AUTO_TEST_CASE(neg_global) { + std::uniform_real_distribution<double> unif1(0., upper_bound); + std::uniform_real_distribution<double> unif2(upper_bound / 10000., upper_bound / 100.); + std::default_random_engine re; + std::vector< std::pair<double, double> > v1, v2; + for (int i = 0; i < n1; i++) { + double a = std::log(unif1(re)); + double b = std::log(unif1(re)); + double x = std::log(unif2(re)); + double y = std::log(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); + } + BOOST_CHECK(bottleneck_distance(v1, v2, 0.) <= upper_bound / 100.); + BOOST_CHECK(bottleneck_distance(v1, v2, upper_bound / 10000.) <= upper_bound / 100. + upper_bound / 10000.); + BOOST_CHECK(std::abs(bottleneck_distance(v1, v2, 0.) - bottleneck_distance(v1, v2, upper_bound / 10000.)) <= upper_bound / 10000.); + + std::vector< std::pair<double, double> > empty; + std::vector< std::pair<double, double> > one = {{8, 10}}; + BOOST_CHECK(bottleneck_distance(empty, empty) == 0); + BOOST_CHECK(bottleneck_distance(empty, one) == 1); +} + +BOOST_AUTO_TEST_CASE(bottleneck_simple_test) { + std::vector< std::pair<double, double> > v1, v2; + double inf = std::numeric_limits<double>::infinity(); + double neginf = -inf; + double b; + + v1.emplace_back(9.6, 14.); + v2.emplace_back(9.5, 14.1); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.09 && b < 0.11); + + v1.emplace_back(-34.974, -34.2); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.386 && b < 0.388); + + v1.emplace_back(neginf, 3.7); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK_EQUAL(b, inf); + + v2.emplace_back(neginf, 4.45); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.74 && b < 0.76); + + v1.emplace_back(-60.6, 52.1); + v2.emplace_back(-61.5, 53.); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.89 && b < 0.91); + + v1.emplace_back(3., inf); + v2.emplace_back(3.2, inf); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.89 && b < 0.91); + + v1.emplace_back(neginf, inf); + v2.emplace_back(neginf, inf); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK(b > 0.89 && b < 0.91); + + v2.emplace_back(6, inf); + + b = Gudhi::persistence_diagram::bottleneck_distance(v1, v2, 0.); + BOOST_CHECK_EQUAL(b, inf); +} diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 8f9151fc..09c2dabf 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -25,7 +25,7 @@ int main(void) { // 10-nearest neighbor query std::clog << "10 nearest neighbors from points[20]:\n"; auto knn_range = points_ds.k_nearest_neighbors(points[20], 10, true); - for (auto const& nghb : knn_range) + for (auto const nghb : knn_range) std::clog << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; // Incremental nearest neighbor query @@ -38,7 +38,7 @@ int main(void) { // 10-furthest neighbor query std::clog << "10 furthest neighbors from points[20]:\n"; auto kfn_range = points_ds.k_furthest_neighbors(points[20], 10, true); - for (auto const& nghb : kfn_range) + for (auto const nghb : kfn_range) std::clog << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; // Incremental furthest neighbor query diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp index d6c6fba3..e9acfaa7 100644 --- a/src/Spatial_searching/test/test_Kd_tree_search.cpp +++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp @@ -45,7 +45,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) { std::vector<std::size_t> knn_result; FT last_dist = -1.; - for (auto const& nghb : kns_range) { + for (auto const nghb : kns_range) { BOOST_CHECK(nghb.second > last_dist); knn_result.push_back(nghb.second); last_dist = nghb.second; @@ -76,7 +76,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) { std::vector<std::size_t> kfn_result; last_dist = kfn_range.begin()->second; - for (auto const& nghb : kfn_range) { + for (auto const nghb : kfn_range) { BOOST_CHECK(nghb.second <= last_dist); kfn_result.push_back(nghb.second); last_dist = nghb.second; |