diff options
author | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2015-06-25 10:19:49 +0000 |
---|---|---|
committer | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2015-06-25 10:19:49 +0000 |
commit | ef48b9447c7270ba63d45a76e4d2e6ecb1a7d199 (patch) | |
tree | 1b1497c1fa1b23488e6ad55dd7b23362332c7068 | |
parent | a242702ce22f379e11708cbf32a7e7433c4c5d01 (diff) |
tests unitaires terminés
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@647 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: aca61ea029d72ddfbf8eca3e4db00da3e7b268c3
-rw-r--r-- | src/Bottleneck/example/CMakeLists.txt | 23 | ||||
-rw-r--r-- | src/Bottleneck/include/gudhi/Graph_matching.h | 284 | ||||
-rw-r--r-- | src/Bottleneck/include/gudhi/Layered_neighbors_finder.h | 8 | ||||
-rw-r--r-- | src/Bottleneck/include/gudhi/Neighbors_finder.h | 93 | ||||
-rw-r--r-- | src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h | 27 | ||||
-rw-r--r-- | src/Bottleneck/include/gudhi/Planar_neighbors_finder.h | 16 | ||||
-rw-r--r-- | src/Bottleneck/test/CMakeLists.txt | 6 | ||||
-rw-r--r-- | src/Bottleneck/test/bottleneck_unit_test.cpp | 187 |
8 files changed, 385 insertions, 259 deletions
diff --git a/src/Bottleneck/example/CMakeLists.txt b/src/Bottleneck/example/CMakeLists.txt index 2ff009c4..8bf61c50 100644 --- a/src/Bottleneck/example/CMakeLists.txt +++ b/src/Bottleneck/example/CMakeLists.txt @@ -1,5 +1,24 @@ cmake_minimum_required(VERSION 2.6) project(GUDHIBottleneckExample) -add_executable ( RandomDiagrams random_diagrams.cpp ) -add_test(RandomDiagrams ${CMAKE_CURRENT_BINARY_DIR}/RandomDiagrams) +if (GCOVR_PATH) + # for gcovr to make coverage reports - Corbera Jenkins plugin + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fprofile-arcs -ftest-coverage") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -fprofile-arcs -ftest-coverage") +endif() +if (GPROF_PATH) + # for gprof to make coverage reports - Jenkins + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg") +endif() + message("CMAKE_CXX_FLAGS = ${CMAKE_CXX_FLAGS}") + message("CMAKE_CXX_FLAGS_DEBUG = ${CMAKE_CXX_FLAGS_DEBUG}") + message("CMAKE_CXX_FLAGS_RELEASE = ${CMAKE_CXX_FLAGS_RELEASE}") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wpedantic -Wsign-compare") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O0") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE}") + +add_executable ( BottleneckExample example.cpp ) + diff --git a/src/Bottleneck/include/gudhi/Graph_matching.h b/src/Bottleneck/include/gudhi/Graph_matching.h index 4cd3180e..9f36e936 100644 --- a/src/Bottleneck/include/gudhi/Graph_matching.h +++ b/src/Bottleneck/include/gudhi/Graph_matching.h @@ -22,12 +22,12 @@ #ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ #define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ - +//#define DEBUG #include <deque> #include <list> #include <vector> -#include "gudhi/Layered_neighbors_finder.h" +#include "Layered_neighbors_finder.h" namespace Gudhi { @@ -37,158 +37,182 @@ template<typename Persistence_diagram1, typename Persistence_diagram2> double bottleneck_distance(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); class Graph_matching { - public: - explicit Graph_matching(const Persistence_diagrams_graph& g); - Graph_matching& operator=(const Graph_matching& m); - bool perfect() const; - bool multi_augment(); - void set_r(double r); - - private: - const Persistence_diagrams_graph& g; - double r; - std::vector<int> v_to_u; - std::list<int> unmatched_in_u; - - Layered_neighbors_finder* layering() const; - bool augment(Layered_neighbors_finder* layered_nf, int u_start_index, int max_depth); - void update(std::deque<int>* path); +public: + explicit Graph_matching(const Persistence_diagrams_graph& g); + Graph_matching& operator=(const Graph_matching& m); + bool perfect() const; + bool multi_augment(); + void set_r(double r); + +private: + const Persistence_diagrams_graph& g; + double r; + std::vector<int> v_to_u; + std::list<int> unmatched_in_u; + + std::unique_ptr<Layered_neighbors_finder> layering() const; + bool augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth); + void update(std::deque<int> & path); }; Graph_matching::Graph_matching(const Persistence_diagrams_graph& g) - : g(g), r(0), v_to_u(g.size()), 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); + : 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); } Graph_matching& Graph_matching::operator=(const Graph_matching& m) { - r = m.r; - v_to_u = m.v_to_u; - unmatched_in_u = m.unmatched_in_u; - return *this; + r = m.r; + v_to_u = m.v_to_u; + unmatched_in_u = m.unmatched_in_u; + return *this; } -inline bool Graph_matching::perfect() const { - return unmatched_in_u.empty(); +/* inline */ bool Graph_matching::perfect() const { +#ifdef DEBUG + std::cout << " perfect? unmatched_in_u.size = " << unmatched_in_u.size() << std::endl << std::flush; +#endif + return unmatched_in_u.empty(); } -inline bool Graph_matching::multi_augment() { - if (perfect()) - return false; - Layered_neighbors_finder* layered_nf = layering(); - double rn = sqrt(g.size()); - int nblmax = layered_nf->vlayers_number()*2 + 1; - // verification of a necessary criterion - if ((unmatched_in_u.size() > rn && nblmax > rn) || nblmax == 0) - return false; - bool successful = false; - std::list<int>* tries = new std::list<int>(unmatched_in_u); - for (auto it = tries->cbegin(); it != tries->cend(); it++) - successful = successful || augment(layered_nf, *it, nblmax); - delete tries; - delete layered_nf; - return successful; +/* inline */ bool Graph_matching::multi_augment() { + if (perfect()) + return false; +#ifdef DEBUG + std::cout << " multi augment" << std::endl << std::flush; +#endif + Layered_neighbors_finder layered_nf = *layering(); + double rn = sqrt(g.size()); + int max_depth = layered_nf.vlayers_number()*2 - 1; +#ifdef DEBUG + std::cout<< " nb_max_layer = " << max_depth << std::endl << std::flush; +#endif + // verification of a necessary criterion + if (max_depth <0 || (unmatched_in_u.size() > rn && max_depth >= rn)) + return false; + bool successful = false; + std::list<int> tries(unmatched_in_u); + for (auto it = tries.cbegin(); it != tries.cend(); it++){ + const bool tmp = augment(layered_nf, *it, max_depth); //force augment evaluation even if successful is already true + successful = successful || tmp; + } + return successful; } -inline void Graph_matching::set_r(double r) { - this->r = r; +/* inline */ void Graph_matching::set_r(double r) { + this->r = r; } -Layered_neighbors_finder* Graph_matching::layering() const { - bool end = false; - int layer = 0; - std::list<int> u_vertices(unmatched_in_u); - std::list<int> v_vertices; - Neighbors_finder nf(g, r); - Layered_neighbors_finder* layered_nf = new Layered_neighbors_finder(g, r); - for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) - nf.add(v_point_index); - while (!u_vertices.empty()) { - for (auto it = u_vertices.cbegin(); it != u_vertices.cend(); ++it) { - std::list<int>* u_succ = nf.pull_all_near(*it); - for (auto it = u_succ->cbegin(); it != u_succ->cend(); ++it) { - layered_nf->add(*it, layer); - v_vertices.emplace_back(*it); - } - delete u_succ; - } - u_vertices.clear(); - for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++) { - if (v_to_u.at(*it) == null_point_index()) - end = true; - else - u_vertices.emplace_back(v_to_u.at(*it)); - } - if (end) - return layered_nf; - v_vertices.clear(); - layer++; - } - return layered_nf; +bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth) { +#ifdef DEBUG + std::cout << " augment" << std::endl << std::flush; +#endif +#ifdef DEBUG + std::cout << " u_start_index = " << u_start_index << std::endl << std::flush; +#endif + std::deque<int> path; + path.emplace_back(u_start_index); + // u_start is a point from U + do { +#ifdef DEBUG + std::cout << " do" << std::endl << std::flush; + std::cout << " path.size = " << static_cast<int>(path.size()) << std::endl << std::flush; +#endif + if (static_cast<int>(path.size()) > max_depth) { + path.pop_back(); + path.pop_back(); + } + if (path.empty()) + return false; + path.emplace_back(layered_nf.pull_near(path.back(), static_cast<int>(path.size())/2)); + while (path.back() == null_point_index()) { + path.pop_back(); + path.pop_back(); + if (path.empty()) + return false; + path.pop_back(); + path.emplace_back(layered_nf.pull_near(path.back(), path.size() / 2)); + } + path.emplace_back(v_to_u.at(path.back())); +#ifdef DEBUG + std::cout << " v_to_u = " << path.back() << std::endl << std::flush; +#endif + } while (path.back() != null_point_index()); + path.pop_back(); + update(path); + return true; } -bool Graph_matching::augment(Layered_neighbors_finder *layered_nf, int u_start_index, int max_depth) { - std::deque<int>* path = new std::deque<int>(); - path->emplace_back(u_start_index); - // start is a point from U - do { - if (static_cast<int>(path->size()) > max_depth) { - path->pop_back(); - path->pop_back(); - } - if (path->empty()) - return false; - int w = path->back(); - path->emplace_back(layered_nf->pull_near(w, path->size() / 2)); - while (path->back() == null_point_index()) { - path->pop_back(); - path->pop_back(); - if (path->empty()) - return false; - path->pop_back(); - path->emplace_back(layered_nf->pull_near(path->back(), path->size() / 2)); +std::unique_ptr<Layered_neighbors_finder> Graph_matching::layering() const { +#ifdef DEBUG + std::cout << " layering" << std::endl << std::flush; +#endif + bool end = false; + int layer = 0; + std::list<int> u_vertices(unmatched_in_u); + std::list<int> v_vertices; + Neighbors_finder nf(g, r); + for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) + nf.add(v_point_index); + std::unique_ptr<Layered_neighbors_finder> layered_nf(new Layered_neighbors_finder(g, r)); + while (!u_vertices.empty()) { + for (auto it = u_vertices.cbegin(); it != u_vertices.cend(); ++it) { + std::unique_ptr< std::list<int> > u_succ = std::move(nf.pull_all_near(*it)); + for (auto it = u_succ->cbegin(); it != u_succ->cend(); ++it) { + layered_nf->add(*it, layer); + v_vertices.emplace_back(*it); + } + } + u_vertices.clear(); + for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++) { + if (v_to_u.at(*it) == null_point_index()) + end = true; + else + u_vertices.emplace_back(v_to_u.at(*it)); + } + if (end) + return layered_nf; + v_vertices.clear(); + layer++; } - path->emplace_back(v_to_u.at(path->back())); - } while (path->back() != null_point_index()); - path->pop_back(); - update(path); - delete path; - return true; + return layered_nf; } -void Graph_matching::update(std::deque<int> *path) { - unmatched_in_u.remove(path->front()); - for (auto it = path->cbegin(); it != path->cend(); ++it) { - int tmp = *it; - ++it; - v_to_u[*it] = tmp; - } +void Graph_matching::update(std::deque<int>& path) { +#ifdef DEBUG + std::cout << " update" << std::endl << std::flush; +#endif + unmatched_in_u.remove(path.front()); + for (auto it = path.cbegin(); it != path.cend(); ++it) { + int tmp = *it; + ++it; + v_to_u[*it] = tmp; + } } template<typename Persistence_diagram1, typename Persistence_diagram2> double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { - Persistence_diagrams_graph g(diag1, diag2, e); - std::vector<double>* sd = g.sorted_distances(); - int idmin = 0; - int idmax = sd->size() - 1; - double alpha = pow(sd->size(), 0.25); - Graph_matching m(g); - Graph_matching biggest_unperfect(g); - while (idmin != idmax) { - int pas = static_cast<int>((idmax - idmin) / alpha); - m.set_r(sd->at(idmin + pas)); - while (m.multi_augment()) {} - if (m.perfect()) { - idmax = idmin + pas; - m = biggest_unperfect; - } else { - biggest_unperfect = m; - idmin = idmin + pas + 1; + Persistence_diagrams_graph g(diag1, diag2, e); + std::unique_ptr< std::vector<double> > sd = std::move(g.sorted_distances()); + int idmin = 0; + int idmax = sd->size() - 1; + double alpha = pow(sd->size(), 0.25); + Graph_matching m(g); + Graph_matching biggest_unperfect(g); + while (idmin != idmax) { + int pas = static_cast<int>((idmax - idmin) / alpha); + m.set_r(sd->at(idmin + pas)); + while (m.multi_augment()); + if (m.perfect()) { + idmax = idmin + pas; + m = biggest_unperfect; + } else { + biggest_unperfect = m; + idmin = idmin + pas + 1; + } } - } - double b = sd->at(idmin); - delete sd; - return b; + double b = sd->at(idmin); + return b; } } // namespace bottleneck diff --git a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h b/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h index 80e5b5ed..1cf83393 100644 --- a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h @@ -51,20 +51,20 @@ class Layered_neighbors_finder { Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_diagrams_graph& g, double r) : g(g), r(r), neighbors_finder() { } -inline void Layered_neighbors_finder::add(int v_point_index, int vlayer) { +/* 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(Neighbors_finder(g, r)); neighbors_finder.at(vlayer).add(v_point_index); } -inline int Layered_neighbors_finder::pull_near(int u_point_index, int vlayer) { +/* inline */ int Layered_neighbors_finder::pull_near(int u_point_index, int vlayer) { if (static_cast<int> (neighbors_finder.size()) <= vlayer) return null_point_index(); return neighbors_finder.at(vlayer).pull_near(u_point_index); } -inline int Layered_neighbors_finder::vlayers_number() const { - return neighbors_finder.size(); +/* inline */ int Layered_neighbors_finder::vlayers_number() const { + return static_cast<int>(neighbors_finder.size()); } } // namespace bottleneck diff --git a/src/Bottleneck/include/gudhi/Neighbors_finder.h b/src/Bottleneck/include/gudhi/Neighbors_finder.h index 6a05e1a0..0fad9889 100644 --- a/src/Bottleneck/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Neighbors_finder.h @@ -26,7 +26,7 @@ #include <unordered_set> #include <list> -#include "gudhi/Planar_neighbors_finder.h" +#include "Planar_neighbors_finder.h" namespace Gudhi { @@ -37,56 +37,65 @@ namespace bottleneck { // V's points have to be added manually using their index. A neighbor returned is automatically removed. class Neighbors_finder { - public: - Neighbors_finder(const Persistence_diagrams_graph& g, double r); - void add(int v_point_index); - int pull_near(int u_point_index); - std::list<int>* pull_all_near(int u_point_index); - - private: - const Persistence_diagrams_graph& g; - const double r; - Planar_neighbors_finder planar_neighbors_f; - std::unordered_set<int> projections_f; +public: + Neighbors_finder(const Persistence_diagrams_graph& g, double r); + void add(int v_point_index); + int pull_near(int u_point_index); + std::unique_ptr< std::list<int> > pull_all_near(int u_point_index); + +private: + const Persistence_diagrams_graph& g; + const double r; + Planar_neighbors_finder planar_neighbors_f; + std::unordered_set<int> projections_f; + void remove(int v_point_index); + bool contains(int v_point_index); }; Neighbors_finder::Neighbors_finder(const Persistence_diagrams_graph& g, double r) : g(g), r(r), planar_neighbors_f(g, r), projections_f() { } -inline void Neighbors_finder::add(int v_point_index) { - if (g.on_the_v_diagonal(v_point_index)) - projections_f.emplace(v_point_index); - else - planar_neighbors_f.add(v_point_index); +/* inline */ void Neighbors_finder::add(int v_point_index) { + if (g.on_the_v_diagonal(v_point_index)) + projections_f.emplace(v_point_index); + else + planar_neighbors_f.add(v_point_index); } -inline int Neighbors_finder::pull_near(int u_point_index) { - int v_challenger = g.corresponding_point_in_v(u_point_index); - if (planar_neighbors_f.contains(v_challenger) && g.distance(u_point_index, v_challenger) < r) { - planar_neighbors_f.remove(v_challenger); - return v_challenger; - } - if (g.on_the_u_diagonal(u_point_index)) { - auto it = projections_f.cbegin(); - if (it != projections_f.cend()) { - int tmp = *it; - projections_f.erase(it); - return tmp; - } - } else { - return planar_neighbors_f.pull_near(u_point_index); - } - return null_point_index(); +/* inline */ void Neighbors_finder::remove(int v_point_index) { + if(v_point_index == null_point_index()) + return; + if (g.on_the_v_diagonal(v_point_index)) + projections_f.erase(v_point_index); + else + planar_neighbors_f.remove(v_point_index); +} + +/* inline */ bool Neighbors_finder::contains(int v_point_index) { + return planar_neighbors_f.contains(v_point_index) || (projections_f.count(v_point_index)>0); } -inline std::list<int>* Neighbors_finder::pull_all_near(int u_point_index) { - std::list<int>* all_pull = planar_neighbors_f.pull_all_near(u_point_index); - int last_pull = pull_near(u_point_index); - while (last_pull != null_point_index()) { - all_pull->emplace_back(last_pull); - last_pull = pull_near(u_point_index); - } - return all_pull; +/* 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.cbegin()!=projections_f.cend()) + tmp = *projections_f.cbegin(); + else if (contains(c) && (g.distance(u_point_index, c) <= r)) + tmp = c; + else + tmp = planar_neighbors_f.pull_near(u_point_index); + remove(tmp); + return tmp; +} + +std::unique_ptr< std::list<int> > Neighbors_finder::pull_all_near(int u_point_index) { + std::unique_ptr< std::list<int> > all_pull = std::move(planar_neighbors_f.pull_all_near(u_point_index)); + int last_pull = pull_near(u_point_index); + while (last_pull != null_point_index()) { + all_pull->emplace_back(last_pull); + last_pull = pull_near(u_point_index); + } + return all_pull; } } // namespace bottleneck diff --git a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h index 105f9059..644c1cd8 100644 --- a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h @@ -55,7 +55,7 @@ class Persistence_diagrams_graph { int corresponding_point_in_v(int u_point_index) const; double distance(int u_point_index, int v_point_index) const; int size() const; - std::vector<double>* sorted_distances(); + std::unique_ptr< std::vector<double> > sorted_distances(); private: std::vector<Diagram_point> u; @@ -64,7 +64,7 @@ class Persistence_diagrams_graph { Diagram_point get_v_point(int v_point_index) const; }; -inline int null_point_index() { +/* inline */ int null_point_index() { return -1; } @@ -85,47 +85,48 @@ Persistence_diagrams_graph::Persistence_diagrams_graph(const Persistence_diagram Persistence_diagrams_graph::Persistence_diagrams_graph() : u(), v() { } -inline bool Persistence_diagrams_graph::on_the_u_diagonal(int u_point_index) const { +/* inline */ bool Persistence_diagrams_graph::on_the_u_diagonal(int u_point_index) const { return u_point_index >= static_cast<int> (u.size()); } -inline bool Persistence_diagrams_graph::on_the_v_diagonal(int v_point_index) const { +/* inline */ bool Persistence_diagrams_graph::on_the_v_diagonal(int v_point_index) const { return v_point_index >= static_cast<int> (v.size()); } -inline int Persistence_diagrams_graph::corresponding_point_in_u(int v_point_index) const { +/* inline */ int Persistence_diagrams_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()); } -inline int Persistence_diagrams_graph::corresponding_point_in_v(int u_point_index) const { +/* inline */ int Persistence_diagrams_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()); } -inline double Persistence_diagrams_graph::distance(int u_point_index, int v_point_index) const { +/* inline */ double Persistence_diagrams_graph::distance(int u_point_index, int v_point_index) const { // could be optimized for the case where one point is the projection of the other if (on_the_u_diagonal(u_point_index) && on_the_v_diagonal(v_point_index)) return 0; Diagram_point p_u = get_u_point(u_point_index); Diagram_point p_v = get_v_point(v_point_index); - return (std::max)(std::fabs(p_u.first - p_v.first), std::fabs(p_u.second - p_v.second)); + return std::max(std::fabs(p_u.first - p_v.first), std::fabs(p_u.second - p_v.second)); } -inline int Persistence_diagrams_graph::size() const { +/* inline */ int Persistence_diagrams_graph::size() const { return static_cast<int> (u.size() + v.size()); } -inline std::vector<double>* Persistence_diagrams_graph::sorted_distances() { +/* inline */ std::unique_ptr< std::vector<double> > Persistence_diagrams_graph::sorted_distances() { // could be optimized std::set<double> sorted_distances; 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)); - return new std::vector<double>(sorted_distances.cbegin(), sorted_distances.cend()); + std::unique_ptr< std::vector<double> > sd_up(new std::vector<double>(sorted_distances.cbegin(), sorted_distances.cend())); + return sd_up; } -inline Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) const { +/* inline */ Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) const { if (!on_the_u_diagonal(u_point_index)) return u.at(u_point_index); Diagram_point projector = v.at(corresponding_point_in_v(u_point_index)); @@ -133,7 +134,7 @@ inline Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) return Diagram_point(x, x); } -inline Diagram_point Persistence_diagrams_graph::get_v_point(int v_point_index) const { +/* inline */ Diagram_point Persistence_diagrams_graph::get_v_point(int v_point_index) const { if (!on_the_v_diagonal(v_point_index)) return v.at(v_point_index); Diagram_point projector = u.at(corresponding_point_in_u(v_point_index)); diff --git a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h index 3d04aa97..e558239d 100644 --- a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h @@ -45,7 +45,7 @@ class Abstract_planar_neighbors_finder { virtual void remove(int v_point_index) = 0; virtual bool contains(int v_point_index) const = 0; virtual int pull_near(int u_point_index) = 0; - virtual std::list<int>* pull_all_near(int u_point_index); + virtual std::unique_ptr< std::list<int> > pull_all_near(int u_point_index); protected: const Persistence_diagrams_graph& g; @@ -74,10 +74,10 @@ typedef Naive_pnf Planar_neighbors_finder; Abstract_planar_neighbors_finder::Abstract_planar_neighbors_finder(const Persistence_diagrams_graph& g, double r) : g(g), r(r) { } -inline Abstract_planar_neighbors_finder::~Abstract_planar_neighbors_finder() { } +/* inline */ Abstract_planar_neighbors_finder::~Abstract_planar_neighbors_finder() { } -inline std::list<int>* Abstract_planar_neighbors_finder::pull_all_near(int u_point_index) { - std::list<int>* all_pull = new std::list<int>(); +/* inline */ std::unique_ptr< std::list<int> > Abstract_planar_neighbors_finder::pull_all_near(int u_point_index) { + std::unique_ptr< std::list<int> > all_pull(new std::list<int>); int last_pull = pull_near(u_point_index); while (last_pull != null_point_index()) { all_pull->emplace_back(last_pull); @@ -89,19 +89,19 @@ inline std::list<int>* Abstract_planar_neighbors_finder::pull_all_near(int u_poi Naive_pnf::Naive_pnf(const Persistence_diagrams_graph& g, double r) : Abstract_planar_neighbors_finder(g, r), candidates() { } -inline void Naive_pnf::add(int v_point_index) { +/* inline */ void Naive_pnf::add(int v_point_index) { candidates.emplace(v_point_index); } -inline void Naive_pnf::remove(int v_point_index) { +/* inline */ void Naive_pnf::remove(int v_point_index) { candidates.erase(v_point_index); } -inline bool Naive_pnf::contains(int v_point_index) const { +/* inline */ bool Naive_pnf::contains(int v_point_index) const { return (candidates.count(v_point_index) > 0); } -inline int Naive_pnf::pull_near(int u_point_index) { +/* inline */ int Naive_pnf::pull_near(int u_point_index) { for (auto it = candidates.begin(); it != candidates.end(); ++it) if (g.distance(u_point_index, *it) <= r) { int tmp = *it; diff --git a/src/Bottleneck/test/CMakeLists.txt b/src/Bottleneck/test/CMakeLists.txt index 3dfd80cd..8e4371b8 100644 --- a/src/Bottleneck/test/CMakeLists.txt +++ b/src/Bottleneck/test/CMakeLists.txt @@ -13,6 +13,12 @@ if (GPROF_PATH) set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg") set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg") endif() + message("CMAKE_CXX_FLAGS = ${CMAKE_CXX_FLAGS}") + message("CMAKE_CXX_FLAGS_DEBUG = ${CMAKE_CXX_FLAGS_DEBUG}") + message("CMAKE_CXX_FLAGS_RELEASE = ${CMAKE_CXX_FLAGS_RELEASE}") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wpedantic -Wsign-compare") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O0") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE}") add_executable ( BottleneckUT bottleneck_unit_test.cpp ) target_link_libraries(BottleneckUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) diff --git a/src/Bottleneck/test/bottleneck_unit_test.cpp b/src/Bottleneck/test/bottleneck_unit_test.cpp index ea7f51f2..77f45867 100644 --- a/src/Bottleneck/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck/test/bottleneck_unit_test.cpp @@ -2,14 +2,15 @@ #include <boost/test/included/unit_test.hpp> #include <random> -#include "gudhi/Graph_matching.h" +#include "../include/gudhi/Graph_matching.h" using namespace Gudhi::bottleneck; -Persistence_diagrams_graph* random_graph_generator(){ - int n1 = 100; - int n2 = 120; - double upper_bound = 80; +int n1 = 81; // a natural number >0 +int n2 = 180; // a natural number >0 +double upper_bound = 400.5; // any real >0 + +std::unique_ptr<Persistence_diagrams_graph> random_graph_generator(){ // Random construction std::uniform_real_distribution<double> unif(0.,upper_bound); std::default_random_engine re; @@ -24,73 +25,83 @@ Persistence_diagrams_graph* random_graph_generator(){ double b = unif(re); v2.emplace_back(std::min(a,b), std::max(a,b)); } - return new Persistence_diagrams_graph(v1, v2, 0.); + return std::unique_ptr<Persistence_diagrams_graph>(new Persistence_diagrams_graph(v1, v2, 0.)); } + BOOST_AUTO_TEST_CASE(global){ - int n = 100; - // Random construction + 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; std::vector< std::pair<double, double> > v1, v2; - for (int i = 0; i < n; i++) { - int a = rand() % n; - v1.emplace_back(a, a + rand() % (n - a)); - int b = rand() % n; - v2.emplace_back(b, b + rand() % (n - b)); + for (int i = 0; i < n1; 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); } - // - BOOST_CHECK(bottleneck_distance(v1, v2, 1.) == 98); + BOOST_CHECK(bottleneck_distance(v1, v2) <= upper_bound/100.); } BOOST_AUTO_TEST_CASE(persistence_diagrams_graph) { - Persistence_diagrams_graph* g = random_graph_generator(); - std::vector<double>* d = g->sorted_distances(); + std::unique_ptr<Persistence_diagrams_graph> g = std::move(random_graph_generator()); + std::unique_ptr< std::vector<double> > d = std::move(g->sorted_distances()); // - BOOST_CHECK(!g->on_the_u_diagonal(99)); - BOOST_CHECK(!g->on_the_u_diagonal(100)); - BOOST_CHECK(!g->on_the_u_diagonal(119)); - BOOST_CHECK(g->on_the_u_diagonal(120)); - BOOST_CHECK(!g->on_the_v_diagonal(99)); - BOOST_CHECK(g->on_the_v_diagonal(100)); - BOOST_CHECK(g->on_the_v_diagonal(119)); - BOOST_CHECK(g->on_the_v_diagonal(120)); + 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)==120); - BOOST_CHECK(g->corresponding_point_in_u(100)==0); - BOOST_CHECK(g->corresponding_point_in_v(0)==100); - BOOST_CHECK(g->corresponding_point_in_v(120)==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()==220); + BOOST_CHECK(g->size()==(n1+n2)); // - BOOST_CHECK((int) d->size() <= 220*220 - 100*120 + 1); // could be more strict + 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,99))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(0,100))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(0,119))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(0,120))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(0,219))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,0))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,99))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,100))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,119))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,120))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(100,219))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,0))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,99))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,100))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,119))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,120))==1); - BOOST_CHECK(std::count(d->begin(), d->end(), g->distance(219,219))==1); - // - delete g; - delete d; + 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(planar_nf) { - Persistence_diagrams_graph* g = random_graph_generator(); +BOOST_AUTO_TEST_CASE(planar_neighbors_finder) { + std::unique_ptr<Persistence_diagrams_graph> g = std::move(random_graph_generator()); Planar_neighbors_finder pnf = Planar_neighbors_finder(*g,1.); - for(int v_point_index=0; v_point_index<100; v_point_index+=2) + for(int v_point_index=0; v_point_index<n1; v_point_index+=2) pnf.add(v_point_index); + // + BOOST_CHECK(pnf.contains(0)); + BOOST_CHECK(!pnf.contains(1)); + BOOST_CHECK(pnf.contains(2)); + BOOST_CHECK(!pnf.contains(3)); + // pnf.remove(0); pnf.remove(1); // @@ -99,14 +110,70 @@ BOOST_AUTO_TEST_CASE(planar_nf) { BOOST_CHECK(pnf.contains(2)); BOOST_CHECK(!pnf.contains(3)); // - int v_point_index_1 = pnf.pull_near(120/2); - BOOST_CHECK((v_point_index_1 == -1) || (g->distance(120/2,v_point_index_1)<1.)); + int v_point_index_1 = pnf.pull_near(n2/2); + BOOST_CHECK((v_point_index_1 == -1) || (g->distance(n2/2,v_point_index_1)<=1.)); BOOST_CHECK(!pnf.contains(v_point_index_1)); - int v_point_index_2 = pnf.pull_near(120/2); - BOOST_CHECK((v_point_index_2 == -1) || (g->distance(120/2,v_point_index_2)<1.)); - BOOST_CHECK(!pnf.contains(v_point_index_2)); - BOOST_CHECK((v_point_index_2 != -1) || (v_point_index_1 == -1)); + std::list<int> l = *pnf.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.); + BOOST_CHECK(v); + int v_point_index_2 = pnf.pull_near(n2/2); + BOOST_CHECK(v_point_index_2 == -1); pnf.add(v_point_index_1); BOOST_CHECK(pnf.contains(v_point_index_1)); } + +BOOST_AUTO_TEST_CASE(neighbors_finder) { + std::unique_ptr<Persistence_diagrams_graph> g = std::move(random_graph_generator()); + Neighbors_finder nf = Neighbors_finder(*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.)); + std::list<int> 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.); + 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) { + std::unique_ptr<Persistence_diagrams_graph> g = std::move(random_graph_generator()); + Layered_neighbors_finder lnf = Layered_neighbors_finder(*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.)); + 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.)); + v_point_index_2 = lnf.pull_near(n2/2,0); + BOOST_CHECK(v_point_index_2 == -1); +} + + +BOOST_AUTO_TEST_CASE(graph_matching) { + std::unique_ptr<Persistence_diagrams_graph> g = std::move(random_graph_generator()); + Graph_matching m1(*g); + m1.set_r(0.); + int e = 0; + while (m1.multi_augment()) + ++e; + BOOST_CHECK(e <= 2*sqrt(2*(n1+n2))); + Graph_matching m2 = m1; + BOOST_CHECK(!m2.multi_augment()); + m2.set_r(upper_bound); + e = 0; + while (m2.multi_augment()) + ++e; + BOOST_CHECK(e <= 2*sqrt(2*(n1+n2))); + BOOST_CHECK(m2.perfect()); + BOOST_CHECK(!m1.perfect()); +} |