Merged last trunk modifications

Make Witness compile and test


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

Former-commit-id: e6eec55ac0a4cc66da3bb081a222cae5b998c1cf

4 files changed, 113 insertions, 18 deletions

diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp
index 6a203383..59dd28e0 100644
--- a/src/Witness_complex/example/witness_complex_from_file.cpp
+++ b/src/Witness_complex/example/witness_complex_from_file.cpp
@@ -26,7 +26,9 @@
 #include <gudhi/Points_off_io.h>
 #include <gudhi/Simplex_tree.h>
 #include <gudhi/Witness_complex.h>
-#include <gudhi/Landmark_choice_by_random_point.h>
+#include <gudhi/Construct_closest_landmark_table.h>
+#include <gudhi/pick_n_random_points.h>
+#include <gudhi/reader_utils.h>
 
 #include <iostream>
 #include <fstream>
@@ -36,6 +38,7 @@
 
 typedef std::vector< int > typeVectorVertex;
 typedef std::vector< std::vector <double> > Point_Vector;
+typedef Gudhi::Simplex_tree<> Simplex_tree;
 
 int main(int argc, char * const argv[]) {
   if (argc != 3) {
@@ -49,7 +52,7 @@ int main(int argc, char * const argv[]) {
   clock_t start, end;
 
   // Construct the Simplex Tree
-  Gudhi::Simplex_tree<> simplex_tree;
+  Simplex_tree simplex_tree;
 
   // Read the OFF file (input file name given as parameter) and triangulate points
   Gudhi::Points_off_reader<std::vector <double>> off_reader(off_file_name);
@@ -65,7 +68,9 @@ int main(int argc, char * const argv[]) {
   // Choose landmarks
   start = clock();
   std::vector<std::vector< int > > knn;
-  Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, nbL, knn);
+  Point_Vector landmarks;
+  Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks));
+  Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(point_vector, landmarks, knn);
   end = clock();
   std::cout << "Landmark choice for " << nbL << " landmarks took "
       << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n";
diff --git a/src/Witness_complex/example/witness_complex_sphere.cpp b/src/Witness_complex/example/witness_complex_sphere.cpp
index b26c9f36..7ab86cc0 100644
--- a/src/Witness_complex/example/witness_complex_sphere.cpp
+++ b/src/Witness_complex/example/witness_complex_sphere.cpp
@@ -27,7 +27,8 @@
 
 #include <gudhi/Simplex_tree.h>
 #include <gudhi/Witness_complex.h>
-#include <gudhi/Landmark_choice_by_random_point.h>
+#include <gudhi/Construct_closest_landmark_table.h>
+#include <gudhi/pick_n_random_points.h>
 #include <gudhi/reader_utils.h>
 
 #include <iostream>
@@ -39,6 +40,8 @@
 
 #include "generators.h"
 
+typedef Gudhi::Simplex_tree<> Simplex_tree;
+
 /** Write a gnuplot readable file.
  *  Data range is a random access range of pairs (arg, value)
  */
@@ -61,13 +64,13 @@ int main(int argc, char * const argv[]) {
   clock_t start, end;
 
   // Construct the Simplex Tree
-  Gudhi::Simplex_tree<> simplex_tree;
+  Simplex_tree simplex_tree;
 
   std::vector< std::pair<int, double> > l_time;
 
   // Read the point file
   for (int nbP = 500; nbP < 10000; nbP += 500) {
-    Point_Vector point_vector;
+    Point_Vector point_vector, landmarks;
     generate_points_sphere(point_vector, nbP, 4);
     std::cout << "Successfully generated " << point_vector.size() << " points.\n";
     std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n";
@@ -75,7 +78,8 @@ int main(int argc, char * const argv[]) {
     // Choose landmarks
     start = clock();
     std::vector<std::vector< int > > knn;
-    Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, number_of_landmarks, knn);
+    Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks));
+    Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(point_vector, landmarks, knn);
 
     // Compute witness complex
     Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree);
diff --git a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h
new file mode 100644
index 00000000..ec93ae71
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h
@@ -0,0 +1,92 @@
+/*    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):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2015  INRIA Sophia Antipolis-Méditerranée (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/>.
+ */
+
+#ifndef CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
+#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
+
+#include <boost/range/size.hpp>
+
+#include <queue>  // for priority_queue<>
+#include <utility>  // for pair<>
+#include <iterator>
+#include <vector>
+#include <set>
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+  /**
+   *  \ingroup witness_complex
+   * \brief Construct the closest landmark tables for all witnesses.
+   *  \details Output a table 'knn', each line of which represents a witness and
+   *   consists of landmarks sorted by
+   *   euclidean distance from the corresponding witness.
+   *
+   *  The type WitnessContainer is a random access range and
+   *  the type LandmarkContainer is a range.
+   *  The type KNearestNeighbors can be seen as 
+   *  Witness_range<Closest_landmark_range<Vertex_handle>>, where
+   *  Witness_range and Closest_landmark_range are random access ranges and
+   *  Vertex_handle is the label type of a vertex in a simplicial complex.
+   *  Closest_landmark_range needs to have push_back operation.
+   */
+
+  template <typename FiltrationValue,
+            typename WitnessContainer,
+            typename LandmarkContainer,
+            typename KNearestNeighbours>
+  void construct_closest_landmark_table(WitnessContainer const &points,
+                                        LandmarkContainer const &landmarks,
+                                        KNearestNeighbours &knn) {
+    int nbP = boost::size(points);
+    assert(nbP >= boost::size(landmarks));
+
+    int dim = boost::size(*std::begin(points));
+    typedef std::pair<double, int> dist_i;
+    typedef bool (*comp)(dist_i, dist_i);
+    knn = KNearestNeighbours(nbP);
+    for (int points_i = 0; points_i < nbP; points_i++) {
+      std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) {
+          return j1.first > j2.first;
+        });
+      typename LandmarkContainer::const_iterator landmarks_it;
+      int landmarks_i = 0;
+      for (landmarks_it = landmarks.begin(), landmarks_i = 0; landmarks_it != landmarks.end();
+           ++landmarks_it, landmarks_i++) {
+        dist_i dist = std::make_pair(euclidean_distance<FiltrationValue>(points[points_i], *landmarks_it),
+                                     landmarks_i);
+        l_heap.push(dist);
+      }
+      for (int i = 0; i < dim + 1; i++) {
+        dist_i dist = l_heap.top();
+        knn[points_i].push_back(dist.second);
+        l_heap.pop();
+      }
+    }
+  }
+
+}  // namespace witness_complex
+
+}  // namespace Gudhi
+
+#endif  // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp
index 03c9adc0..b7067f87 100644
--- a/src/Witness_complex/test/witness_complex_points.cpp
+++ b/src/Witness_complex/test/witness_complex_points.cpp
@@ -27,8 +27,8 @@
 
 #include <gudhi/Simplex_tree.h>
 #include <gudhi/Witness_complex.h>
-#include <gudhi/Landmark_choice_by_random_point.h>
-#include <gudhi/Landmark_choice_by_furthest_point.h>
+#include <gudhi/Construct_closest_landmark_table.h>
+#include <gudhi/pick_n_random_points.h>
 
 #include <iostream>
 #include <vector>
@@ -40,7 +40,7 @@ typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex;
 
 BOOST_AUTO_TEST_CASE(witness_complex_points) {
   std::vector< typeVectorVertex > knn;
-  std::vector< Point > points;
+  std::vector< Point > points, landmarks;
   // Add grid points as witnesses
   for (double i = 0; i < 10; i += 1.0)
     for (double j = 0; j < 10; j += 1.0)
@@ -50,15 +50,9 @@ BOOST_AUTO_TEST_CASE(witness_complex_points) {
   bool b_print_output = false;
   // First test: random choice
   Simplex_tree complex1;
-  Gudhi::witness_complex::landmark_choice_by_random_point(points, 100, knn);
+  Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(landmarks));
+  Gudhi::witness_complex::construct_closest_landmark_table<Simplex_tree::Filtration_value>(points, landmarks, knn);
   assert(!knn.empty());
   WitnessComplex witnessComplex1(knn, 100, 3, complex1);
   BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output));
-
-  // Second test: furthest choice
-  knn.clear();
-  Simplex_tree complex2;
-  Gudhi::witness_complex::landmark_choice_by_furthest_point(points, 100, knn);
-  WitnessComplex witnessComplex2(knn, 100, 3, complex2);
-  BOOST_CHECK(witnessComplex2.is_witness_complex(knn, b_print_output));
 }