Merge branch bottleneckDistance on a up-to-date branch

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1492 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: bccdeaf8456b7b88ad2da71205dbb4c5d08a53ee

4 files changed, 290 insertions, 0 deletions

diff --git a/src/Bottleneck_distance/test/CMakeLists.txt b/src/Bottleneck_distance/test/CMakeLists.txt
new file mode 100644
index 00000000..ba0f5fee
--- /dev/null
+++ b/src/Bottleneck_distance/test/CMakeLists.txt
@@ -0,0 +1,29 @@
+cmake_minimum_required(VERSION 2.6)
+project(Bottleneck_distance_tests)
+
+
+if (GCOVR_PATH)
+  # for gcovr to make coverage reports - Corbera Jenkins plugin
+  set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage")
+endif()
+if (GPROF_PATH)
+  # for gprof to make coverage reports - Jenkins
+  set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg")
+endif()
+
+# need CGAL 4.7
+# cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../..
+if(CGAL_FOUND)
+  if (NOT CGAL_VERSION VERSION_LESS 4.7.0)
+    if (EIGEN3_FOUND)
+      add_executable ( bottleneckUT bottleneck_unit_test.cpp )
+      add_executable ( bottleneck_chrono bottleneck_chrono.cpp )
+      target_link_libraries(bottleneckUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+      # Unitary tests
+      add_test(NAME bottleneckUT COMMAND ${CMAKE_CURRENT_BINARY_DIR}/bottleneckUT
+        # XML format for Jenkins xUnit plugin 
+        --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/bottleneckUT.xml --log_level=test_suite --report_level=no)
+    endif()
+  endif ()
+endif()
diff --git a/src/Bottleneck_distance/test/README b/src/Bottleneck_distance/test/README
new file mode 100644
index 00000000..0e7b8673
--- /dev/null
+++ b/src/Bottleneck_distance/test/README
@@ -0,0 +1,12 @@
+To compile:
+***********
+
+cmake .
+make
+
+To launch with details:
+***********************
+
+./BottleneckUnitTest --report_level=detailed --log_level=all 
+
+   ==> echo $? returns 0 in case of success (non-zero otherwise)
diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp
new file mode 100644
index 00000000..8b49b6be
--- /dev/null
+++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp
@@ -0,0 +1,61 @@
+/*    This file is part of the Gudhi Library. The Gudhi library
+ *    (Geometric Understanding in Higher Dimensions) is a generic C++
+ *    library for computational topology.
+ *
+ *    Author(s):       Francois Godi
+ *
+ *    Copyright (C) 2015  INRIA Sophia-Antipolis (France)
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the GNU General Public License as published by
+ *    the Free Software Foundation, either version 3 of the License, or
+ *    (at your option) any later version.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU General Public License for more details.
+ *
+ *    You should have received a copy of the GNU General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <gudhi/Graph_matching.h>
+#include <chrono>
+#include <fstream>
+
+using namespace Gudhi::Bottleneck_distance;
+
+
+double upper_bound = 400.; // any real >0
+
+int main(){
+    std::ofstream objetfichier;
+    objetfichier.open("results.csv", std::ios::out);
+
+    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;
+        std::vector< std::pair<double, double> > v1, v2;
+        for (int i = 0; i < n; 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);
+        }
+        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
+        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));
+        objetfichier << n << ";" << duration.count() << ";" << b << std::endl;
+    }
+    objetfichier.close();
+}
diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp
new file mode 100644
index 00000000..d5b71156
--- /dev/null
+++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp
@@ -0,0 +1,188 @@
+/*    This file is part of the Gudhi Library. The Gudhi library
+ *    (Geometric Understanding in Higher Dimensions) is a generic C++
+ *    library for computational topology.
+ *
+ *    Author(s):       Francois Godi
+ *
+ *    Copyright (C) 2015  INRIA Sophia-Antipolis (France)
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the GNU General Public License as published by
+ *    the Free Software Foundation, either version 3 of the License, or
+ *    (at your option) any later version.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU General Public License for more details.
+ *
+ *    You should have received a copy of the GNU General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#define BOOST_TEST_MODULE bottleneck test
+
+#include <boost/test/included/unit_test.hpp>
+#include <random>
+#include <gudhi/Graph_matching.h>
+
+using namespace Gudhi::Bottleneck_distance;
+
+int n1 = 81; // a natural number >0
+int n2 = 180; // a natural number >0
+double upper_bound = 406.43; // any real >0
+
+BOOST_AUTO_TEST_CASE(persistence_diagrams_graph){
+    // Random construction
+    std::uniform_real_distribution<double> unif(0.,upper_bound);
+    std::default_random_engine re;
+    std::vector< std::pair<double, double> > v1, v2;
+    for (int i = 0; i < n1; i++) {
+        double a = unif(re);
+        double b = unif(re);
+        v1.emplace_back(std::min(a,b), std::max(a,b));
+    }
+    for (int i = 0; i < n2; i++) {
+        double a = unif(re);
+        double b = unif(re);
+        v2.emplace_back(std::min(a,b), std::max(a,b));
+    }
+    G::initialize(v1, v2, 0.);
+    std::shared_ptr< std::vector<double> > d(G::sorted_distances());
+    //
+    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)==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()==(n1+n2));
+    //
+    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,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_neighbors_finder) {
+    Planar_neighbors_finder pnf(1.);
+    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);
+    //
+    BOOST_CHECK(!pnf.contains(0));
+    BOOST_CHECK(!pnf.contains(1));
+    BOOST_CHECK(pnf.contains(2));
+    BOOST_CHECK(!pnf.contains(3));
+    //
+    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));
+    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);
+}
+
+BOOST_AUTO_TEST_CASE(neighbors_finder) {
+    Neighbors_finder nf(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) {
+    Layered_neighbors_finder lnf(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) {
+    Graph_matching m1;
+    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());
+}
+
+BOOST_AUTO_TEST_CASE(global){
+    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 < 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(compute(v1, v2) <= upper_bound/100.);
+}