cpplint fixes

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

Former-commit-id: c663c383e09719a8c70c1100bb6e21d8fc49e597

17 files changed, 1154 insertions, 4 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index edf7e63f..6a49185f 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -71,6 +71,7 @@ else()
   include_directories(src/Persistent_cohomology/include/)
   include_directories(src/Simplex_tree/include/)
   include_directories(src/Skeleton_blocker/include/)
+  include_directories(src/Witness_complex/include/)
 
   add_subdirectory(src/Simplex_tree/test)
   add_subdirectory(src/Simplex_tree/example)
@@ -79,6 +80,8 @@ else()
   add_subdirectory(src/Skeleton_blocker/test) 
   add_subdirectory(src/Skeleton_blocker/example) 
   add_subdirectory(src/Contraction/example)
+  add_subdirectory(src/Witness_complex/test)
+  add_subdirectory(src/Witness_complex/example)
 
   # data points generator
   add_subdirectory(data/points/generator)
@@ -88,5 +91,3 @@ else()
   add_subdirectory(src/GudhUI)
 
 endif()  
-
-
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 3c38483c..81e6f864 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -52,6 +52,7 @@ else()
   add_subdirectory(example/Persistent_cohomology)                   
   add_subdirectory(example/Skeleton_blocker)                   
   add_subdirectory(example/Contraction)                   
+  add_subdirectory(example/Witness_complex)
 
   # data points generator
   add_subdirectory(data/points/generator)
diff --git a/src/Doxyfile b/src/Doxyfile
index faa0d3fe..6585e50c 100644
--- a/src/Doxyfile
+++ b/src/Doxyfile
@@ -834,8 +834,8 @@ EXAMPLE_RECURSIVE      = NO
 
 IMAGE_PATH             = doc/Skeleton_blocker/ \
 	doc/common/ \
-	doc/Contraction/
-
+	doc/Contraction/ \
+	doc/Witness_complex/
 
 # The INPUT_FILTER tag can be used to specify a program that doxygen should
 # invoke to filter for each input file. Doxygen will invoke the filter program
diff --git a/src/Witness_complex/concept/Simplicial_complex.h b/src/Witness_complex/concept/Simplicial_complex.h
new file mode 100644
index 00000000..d7f3496d
--- /dev/null
+++ b/src/Witness_complex/concept/Simplicial_complex.h
@@ -0,0 +1,94 @@
+/*    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) 2014  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 CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_
+#define CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+/** \brief The concept Simplicial_Complex describes the requirements 
+ * for a type to implement a simplicial complex, 
+ * used for example to build a 'Witness_complex'. 
+ */
+struct Simplicial_complex {
+  /** Handle to specify a simplex. */
+  typedef unspecified Simplex_handle;
+  /** Handle to specify a vertex. Must be a non-negative integer. */
+  typedef unspecified Vertex_handle;
+
+  /** Returns a Simplex_hanlde that is different from all simplex handles 
+   * of the simplices. */
+  Simplex_handle null_simplex();
+  /** \brief Returns the number of simplices in the complex.
+   *
+   * Does not count the empty simplex. */
+  size_t num_simplices();
+
+  /** \brief Iterator over the simplices of the complex,
+   * in an arbitrary order.
+   *
+   * 'value_type' must be 'Simplex_handle'.*/
+  typedef unspecified Complex_simplex_iterator;
+  typedef unspecified Complex_simplex_range;
+
+  /**
+   * \brief Returns a range over all the simplices of a
+   * complex.
+   */
+  Complex_simplex_range complex_simplex_range();
+
+  /** \brief Iterator over vertices of a simplex.
+   *
+   * 'value type' must be 'Vertex_handle'.*/
+  typedef unspecified Simplex_vertex_range;
+
+  /** \brief Returns a range over vertices of a given
+   *  simplex. */
+  Simplex_vertex_range simplex_vertex_range(Simplex_handle const & simplex);
+
+  /** \brief Return type of an insertion of a simplex
+   */
+  typedef unspecified Insertion_result_type;
+
+  /** \brief Input range of vertices.
+   * 'value_type' must be 'Vertex_handle'. */
+  typedef unspecified Input_vertex_range;
+
+  /** \brief Inserts a simplex with vertices from a given range
+   *  'vertex_range' in the simplicial complex.
+   *  */
+  Insertion_result_type insert_simplex(Input_vertex_range const & vertex_range);
+
+  /** \brief Finds a simplex with vertices given by a range
+   *
+   * If a simplex exists, its Simplex_handle is returned.
+   * Otherwise null_simplex() is returned. */
+  Simplex_handle find(Input_vertex_range const & vertex_range);
+};
+
+}  // namespace witness_complex
+
+}  // namespace Gudhi
+
+#endif  // CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_
diff --git a/src/Witness_complex/doc/bench_Cy8.png b/src/Witness_complex/doc/bench_Cy8.png
new file mode 100644
index 00000000..d9045294
--- /dev/null
+++ b/src/Witness_complex/doc/bench_Cy8.png
diff --git a/src/Witness_complex/doc/bench_sphere.png b/src/Witness_complex/doc/bench_sphere.png
new file mode 100644
index 00000000..ba6bb381
--- /dev/null
+++ b/src/Witness_complex/doc/bench_sphere.png
diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt
new file mode 100644
index 00000000..b304479e
--- /dev/null
+++ b/src/Witness_complex/example/CMakeLists.txt
@@ -0,0 +1,44 @@
+cmake_minimum_required(VERSION 2.6)
+project(GUDHIWitnessComplex)
+
+# A simple example
+   add_executable( witness_complex_from_file witness_complex_from_file.cpp )
+   add_test( witness_complex_from_bunny ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100)   
+
+if(CGAL_FOUND)
+  if (NOT CGAL_VERSION VERSION_LESS 4.6.0)
+    message(STATUS "CGAL version: ${CGAL_VERSION}.")
+
+    include( ${CGAL_USE_FILE} )
+    # In CMakeLists.txt, when include(${CGAL_USE_FILE}), CXX_FLAGS are overwritten.
+    # cf. http://doc.cgal.org/latest/Manual/installation.html#title40
+    # A workaround is to add "-std=c++11" again.
+    # A fix would be to use https://cmake.org/cmake/help/v3.1/prop_gbl/CMAKE_CXX_KNOWN_FEATURES.html 
+    # or even better https://cmake.org/cmake/help/v3.1/variable/CMAKE_CXX_STANDARD.html
+    # but it implies to use cmake version 3.1 at least.
+    if(NOT MSVC)
+      include(CheckCXXCompilerFlag)
+      CHECK_CXX_COMPILER_FLAG(-std=c++11 COMPILER_SUPPORTS_CXX11)
+      if(COMPILER_SUPPORTS_CXX11)
+        set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+      endif()
+    endif()
+    # - End of workaround
+
+    find_package(Eigen3 3.1.0)
+    if (EIGEN3_FOUND)
+      message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.")
+      include( ${EIGEN3_USE_FILE} )
+      message(STATUS "Eigen3 use file: ${EIGEN3_USE_FILE}.")
+      include_directories (BEFORE "../../include")
+
+      add_executable ( witness_complex_sphere witness_complex_sphere.cpp )
+      target_link_libraries(witness_complex_sphere ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY})
+      add_test( witness_complex_sphere_10 ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_sphere 10)   
+    else()
+      message(WARNING "Eigen3 not found. Version 3.1.0 is required for witness_complex_sphere example.")      
+    endif()
+  else()
+    message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile witness_complex_sphere example. Version 4.6.0 is required.")
+  endif ()
+endif()
diff --git a/src/Witness_complex/example/generators.h b/src/Witness_complex/example/generators.h
new file mode 100644
index 00000000..ac445261
--- /dev/null
+++ b/src/Witness_complex/example/generators.h
@@ -0,0 +1,147 @@
+/*    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 EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_
+#define EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_
+
+#include <CGAL/Epick_d.h>
+#include <CGAL/point_generators_d.h>
+
+#include <fstream>
+#include <string>
+#include <vector>
+
+typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K;
+typedef K::FT FT;
+typedef K::Point_d Point_d;
+typedef std::vector<Point_d> Point_Vector;
+typedef CGAL::Random_points_in_cube_d<Point_d> Random_cube_iterator;
+typedef CGAL::Random_points_in_ball_d<Point_d> Random_point_iterator;
+
+/**
+ * \brief Rock age method of reading off file
+ *
+ */
+inline void
+off_reader_cust(std::string file_name, std::vector<Point_d> & points) {
+  std::ifstream in_file(file_name.c_str(), std::ios::in);
+  if (!in_file.is_open()) {
+    std::cerr << "Unable to open file " << file_name << std::endl;
+    return;
+  }
+  std::string line;
+  double x;
+  // Line OFF. No need in it
+  if (!getline(in_file, line)) {
+    std::cerr << "No line OFF\n";
+    return;
+  }
+  // Line with 3 numbers. No need
+  if (!getline(in_file, line)) {
+    std::cerr << "No line with 3 numbers\n";
+    return;
+  }
+  // Reading points
+  while (getline(in_file, line)) {
+    std::vector< double > point;
+    std::istringstream iss(line);
+    while (iss >> x) {
+      point.push_back(x);
+    }
+    points.push_back(Point_d(point));
+  }
+  in_file.close();
+}
+
+/**
+ * \brief Customized version of read_points
+ * which takes into account a possible nbP first line
+ *
+ */
+inline void
+read_points_cust(std::string file_name, Point_Vector & points) {
+  std::ifstream in_file(file_name.c_str(), std::ios::in);
+  if (!in_file.is_open()) {
+    std::cerr << "Unable to open file " << file_name << std::endl;
+    return;
+  }
+  std::string line;
+  double x;
+  while (getline(in_file, line)) {
+    std::vector< double > point;
+    std::istringstream iss(line);
+    while (iss >> x) {
+      point.push_back(x);
+    }
+    Point_d p(point.begin(), point.end());
+    if (point.size() != 1)
+      points.push_back(p);
+  }
+  in_file.close();
+}
+
+/** \brief Generate points on a grid in a cube of side 2
+ * having {+-1}^D as vertices and insert them in W.
+ * The grid has "width" points on each side. 
+ * If torus is true then it is supposed that the cube represents
+ * a flat torus, hence the opposite borders are associated.
+ * The points on border in this case are not placed twice.
+ */
+void generate_points_grid(Point_Vector& W, int width, int D, bool torus) {
+  int nb_points = 1;
+  for (int i = 0; i < D; ++i)
+    nb_points *= width;
+  for (int i = 0; i < nb_points; ++i) {
+    std::vector<double> point;
+    int cell_i = i;
+    for (int l = 0; l < D; ++l) {
+      if (torus)
+        point.push_back(-1 + (2.0 / (width - 1))*(cell_i % width));
+      else
+        point.push_back(-1 + (2.0 / width)*(cell_i % width));
+      // attention: the bottom and the right are covered too!
+      cell_i /= width;
+    }
+    W.push_back(point);
+  }
+}
+
+/** \brief Generate nbP points uniformly in a cube of side 2
+ * having {+-1}^dim as its vertices and insert them in W.
+ */
+void generate_points_random_box(Point_Vector& W, int nbP, int dim) {
+  Random_cube_iterator rp(dim, 1.0);
+  for (int i = 0; i < nbP; i++) {
+    W.push_back(*rp++);
+  }
+}
+
+/** \brief Generate nbP points uniformly on a (dim-1)-sphere
+ *  and insert them in W.
+ */
+void generate_points_sphere(Point_Vector& W, int nbP, int dim) {
+  CGAL::Random_points_on_sphere_d<Point_d> rp(dim, 1);
+  for (int i = 0; i < nbP; i++)
+    W.push_back(*rp++);
+}
+
+#endif  // EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_
diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp
new file mode 100644
index 00000000..d94502b1
--- /dev/null
+++ b/src/Witness_complex/example/witness_complex_from_file.cpp
@@ -0,0 +1,116 @@
+/*    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/>.
+ */
+
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Witness_complex.h>
+#include <gudhi/Landmark_choice_by_random_point.h>
+#include <gudhi/reader_utils.h>
+
+#include <iostream>
+#include <fstream>
+#include <ctime>
+#include <string>
+#include <vector>
+
+using namespace Gudhi;
+using namespace Gudhi::witness_complex;
+
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef std::vector< std::vector <double> > Point_Vector;
+
+typedef Witness_complex< Simplex_tree<> > WitnessComplex;
+
+/**
+ * \brief Customized version of read_points
+ * which takes into account a possible nbP first line
+ *
+ */
+inline void
+read_points_cust(std::string file_name, std::vector< std::vector< double > > & points) {
+  std::ifstream in_file(file_name.c_str(), std::ios::in);
+  if (!in_file.is_open()) {
+    std::cerr << "Unable to open file " << file_name << std::endl;
+    return;
+  }
+  std::string line;
+  double x;
+  while (getline(in_file, line)) {
+    std::vector< double > point;
+    std::istringstream iss(line);
+    while (iss >> x) {
+      point.push_back(x);
+    }
+    if (point.size() != 1)
+      points.push_back(point);
+  }
+  in_file.close();
+}
+
+/** Write a gnuplot readable file.
+ *  Data range is a random access range of pairs (arg, value)
+ */
+template < typename Data_range >
+void write_data(Data_range & data, std::string filename) {
+  std::ofstream ofs(filename, std::ofstream::out);
+  for (auto entry : data)
+    ofs << entry.first << ", " << entry.second << "\n";
+  ofs.close();
+}
+
+int main(int argc, char * const argv[]) {
+  if (argc != 3) {
+    std::cerr << "Usage: " << argv[0]
+        << " path_to_point_file nbL \n";
+    return 0;
+  }
+
+  std::string file_name = argv[1];
+  int nbL = atoi(argv[2]);
+  clock_t start, end;
+
+  // Construct the Simplex Tree
+  Simplex_tree<> simplex_tree;
+
+  // Read the point file
+  Point_Vector point_vector;
+  read_points_cust(file_name, point_vector);
+  std::cout << "Successfully read " << point_vector.size() << " points.\n";
+  std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n";
+
+  // Choose landmarks
+  start = clock();
+  std::vector<std::vector< int > > knn;
+  Landmark_choice_by_random_point(point_vector, nbL, knn);
+  end = clock();
+  std::cout << "Landmark choice for " << nbL << " landmarks took "
+      << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n";
+
+  // Compute witness complex
+  start = clock();
+  WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size());
+  end = clock();
+  std::cout << "Witness complex 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
new file mode 100644
index 00000000..36f63437
--- /dev/null
+++ b/src/Witness_complex/example/witness_complex_sphere.cpp
@@ -0,0 +1,96 @@
+/*    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/>.
+ */
+#define BOOST_PARAMETER_MAX_ARITY 12
+
+
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Witness_complex.h>
+#include <gudhi/Landmark_choice_by_random_point.h>
+#include <gudhi/reader_utils.h>
+
+#include <iostream>
+#include <fstream>
+#include <ctime>
+#include <utility>
+#include <string>
+#include <vector>
+
+#include "generators.h"
+
+using namespace Gudhi;
+using namespace Gudhi::witness_complex;
+
+typedef std::vector< Vertex_handle > typeVectorVertex;
+
+typedef Witness_complex< Simplex_tree<> > WitnessComplex;
+
+/** Write a gnuplot readable file.
+ *  Data range is a random access range of pairs (arg, value)
+ */
+template < typename Data_range >
+void write_data(Data_range & data, std::string filename) {
+  std::ofstream ofs(filename, std::ofstream::out);
+  for (auto entry : data)
+    ofs << entry.first << ", " << entry.second << "\n";
+  ofs.close();
+}
+
+int main(int argc, char * const argv[]) {
+  if (argc != 2) {
+    std::cerr << "Usage: " << argv[0]
+        << " nbL \n";
+    return 0;
+  }
+
+  int nbL = atoi(argv[1]);
+  clock_t start, end;
+
+  // Construct the 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;
+    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";
+
+    // Choose landmarks
+    start = clock();
+    std::vector<std::vector< int > > knn;
+    Landmark_choice_by_random_point(point_vector, nbL, knn);
+
+    // Compute witness complex
+    WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size());
+    end = clock();
+    double time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
+    std::cout << "Witness complex for " << nbL << " landmarks took "
+        << time << " s. \n";
+    l_time.push_back(std::make_pair(nbP, time));
+  }
+  write_data(l_time, "w_time.dat");
+}
diff --git a/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h b/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h
new file mode 100644
index 00000000..bb7e87f5
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h
@@ -0,0 +1,107 @@
+/*    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 LANDMARK_CHOICE_BY_FURTHEST_POINT_H_
+#define LANDMARK_CHOICE_BY_FURTHEST_POINT_H_
+
+#include <limits>  // for numeric_limits<>
+#include <algorithm>  // for sort
+#include <vector>
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+/**
+ *  \class Landmark_choice_by_furthest_point
+ *  \brief The class `Landmark_choice_by_furthest_point` allows to construct the matrix
+ *  of closest landmarks per witness by iteratively choosing the furthest witness
+ *  from the set of already chosen landmarks as the new landmark. 
+ *  \ingroup witness_complex
+ */
+
+class Landmark_choice_by_furthest_point {
+ private:
+  typedef std::vector<int> typeVectorVertex;
+
+ public:
+    /** 
+   *  \brief Landmark choice strategy by iteratively adding the furthest witness from the
+   *  current landmark set as the new landmark. 
+   *  \details It chooses nbL landmarks from a random access range `points` and
+   *  writes {witness}*{closest landmarks} matrix in `knn`.
+   */
+
+  template <typename KNearestNeighbours,
+  typename Point_random_access_range>
+  Landmark_choice_by_furthest_point(Point_random_access_range const &points,
+                                    int nbL,
+                                    KNearestNeighbours &knn) {
+    int nb_points = points.end() - points.begin();
+    assert(nb_points >= nbL);
+    // distance matrix witness x landmarks
+    std::vector<std::vector<double>> wit_land_dist(nb_points, std::vector<double>());
+    // landmark list
+    typeVectorVertex chosen_landmarks;
+
+    knn = KNearestNeighbours(nb_points, std::vector<int>());
+    int current_number_of_landmarks = 0;  // counter for landmarks
+    double curr_max_dist = 0;  // used for defining the furhest point from L
+    const double infty = std::numeric_limits<double>::infinity();  // infinity (see next entry)
+    std::vector< double > dist_to_L(nb_points, infty);  // vector of current distances to L from points
+
+    // TODO(SK) Consider using rand_r(...) instead of rand(...) for improved thread safety
+    int rand_int = rand() % nb_points;
+    int curr_max_w = rand_int;  // For testing purposes a pseudo-random number is used here
+
+    for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) {
+      // curr_max_w at this point is the next landmark
+      chosen_landmarks.push_back(curr_max_w);
+      unsigned i = 0;
+      for (auto& p : points) {
+        double curr_dist = euclidean_distance(p, *(points.begin() + chosen_landmarks[current_number_of_landmarks]));
+        wit_land_dist[i].push_back(curr_dist);
+        knn[i].push_back(current_number_of_landmarks);
+        if (curr_dist < dist_to_L[i])
+          dist_to_L[i] = curr_dist;
+        ++i;
+      }
+      curr_max_dist = 0;
+      for (i = 0; i < dist_to_L.size(); i++)
+        if (dist_to_L[i] > curr_max_dist) {
+          curr_max_dist = dist_to_L[i];
+          curr_max_w = i;
+        }
+    }
+    for (unsigned i = 0; i < points.size(); ++i)
+      std::sort(knn[i].begin(),
+                knn[i].end(),
+                [&wit_land_dist, i](int a, int b) {
+                  return wit_land_dist[i][a] < wit_land_dist[i][b]; });
+  }
+};
+
+}  // namespace witness_complex
+
+}  // namespace Gudhi
+
+#endif  // LANDMARK_CHOICE_BY_FURTHEST_POINT_H_
diff --git a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h b/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h
new file mode 100644
index 00000000..215c9e65
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h
@@ -0,0 +1,96 @@
+/*    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 LANDMARK_CHOICE_BY_RANDOM_POINT_H_
+#define LANDMARK_CHOICE_BY_RANDOM_POINT_H_
+
+#include <queue>  // for priority_queue<>
+#include <utility>  // for pair<>
+#include <vector>
+#include <set>
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+/** 
+ *  \class Landmark_choice_by_random_point
+ *  \brief The class `Landmark_choice_by_random_point` allows to construct the matrix
+ *  of closest landmarks per witness by iteratively choosing a random non-chosen witness
+ *  as a new landmark. 
+ *  \ingroup witness_complex
+ */
+
+class Landmark_choice_by_random_point {
+ public:
+  /** \brief Landmark choice strategy by taking random vertices for landmarks.
+   *  \details It chooses nbL distinct landmarks from a random access range `points`
+   *  and outputs a matrix {witness}*{closest landmarks} in knn.
+   */
+
+  template <typename KNearestNeighbours,
+  typename Point_random_access_range>
+  Landmark_choice_by_random_point(Point_random_access_range const &points,
+                                  int nbL,
+                                  KNearestNeighbours &knn) {
+    int nbP = points.end() - points.begin();
+    assert(nbP >= nbL);
+    std::set<int> landmarks;
+    int current_number_of_landmarks = 0;  // counter for landmarks
+
+    // TODO(SK) Consider using rand_r(...) instead of rand(...) for improved thread safety
+    int chosen_landmark = rand() % nbP;
+    for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) {
+      while (landmarks.find(chosen_landmark) != landmarks.end())
+        chosen_landmark = rand() % nbP;
+      landmarks.insert(chosen_landmark);
+    }
+
+    int dim = points.begin()->size();
+    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;
+      });
+      std::set<int>::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(points[points_i], points[*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  // LANDMARK_CHOICE_BY_RANDOM_POINT_H_
diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h
new file mode 100644
index 00000000..27f7a9c0
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Witness_complex.h
@@ -0,0 +1,251 @@
+/*    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 WITNESS_COMPLEX_H_
+#define WITNESS_COMPLEX_H_
+
+// Needed for the adjacency graph in bad link search
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
+
+#include <boost/container/flat_map.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+
+#include <gudhi/distance_functions.h>
+
+#include <algorithm>
+#include <utility>
+#include <vector>
+#include <list>
+#include <set>
+#include <queue>
+#include <limits>
+#include <ctime>
+#include <iostream>
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+/** 
+    \class Witness_complex
+    \brief Constructs the witness complex for the given set of witnesses and landmarks.
+    \ingroup witness_complex
+ */
+template< class Simplicial_complex>
+class Witness_complex {
+ private:
+  struct Active_witness {
+    int witness_id;
+    int landmark_id;
+
+    Active_witness(int witness_id_, int landmark_id_)
+        : witness_id(witness_id_),
+        landmark_id(landmark_id_) { }
+  };
+
+ private:
+  typedef typename Simplicial_complex::Simplex_handle Simplex_handle;
+  typedef typename Simplicial_complex::Vertex_handle Vertex_handle;
+
+  typedef std::vector< double > Point_t;
+  typedef std::vector< Point_t > Point_Vector;
+
+  // typedef typename Simplicial_complex::Filtration_value Filtration_value;
+  typedef std::vector< Vertex_handle > typeVectorVertex;
+  typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex;
+  typedef std::pair< Simplex_handle, bool > typePairSimplexBool;
+
+  typedef int Witness_id;
+  typedef int Landmark_id;
+  typedef std::list< Vertex_handle > ActiveWitnessList;
+
+ private:
+  int nbL;  // Number of landmarks
+  double density;  // Desired density
+  Simplicial_complex& sc;  // Simplicial complex
+
+ public:
+  /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  /** @name Constructor
+   */
+
+  //@{
+
+  // Witness_range<Closest_landmark_range<Vertex_handle>>
+
+  /**
+   *  \brief Iterative construction of the witness complex.
+   *  \details The witness complex is written in sc_ basing on a matrix knn of
+   *  nearest neighbours of the form {witnesses}x{landmarks}.
+   *
+   *  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.
+   *
+   *  Constructor takes into account at most (dim+1) 
+   *  first landmarks from each landmark range to construct simplices.
+   *
+   *  Landmarks are supposed to be in [0,nbL_-1]
+   */
+  template< typename KNearestNeighbors >
+  Witness_complex(KNearestNeighbors const & knn,
+                  Simplicial_complex & sc_,
+                  int nbL_,
+                  int dim) : nbL(nbL_), sc(sc_) {
+    // Construction of the active witness list
+    int nbW = knn.size();
+    typeVectorVertex vv;
+    typeSimplex simplex;
+    typePairSimplexBool returnValue;
+    int counter = 0;
+    /* The list of still useful witnesses
+     * it will diminuish in the course of iterations
+     */
+    ActiveWitnessList active_w;  // = new ActiveWitnessList();
+    for (int i = 0; i != nbL; ++i) {
+      // initial fill of 0-dimensional simplices
+      // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore
+      counter++;
+      vv = {i};
+      returnValue = sc.insert_simplex(vv);
+      // TODO(SK) Error if not inserted : normally no need here though
+    }
+    int k = 1; /* current dimension in iterative construction */
+    for (int i = 0; i != nbW; ++i)
+      active_w.push_back(i);
+    // std::cout << "Successfully added edges" << std::endl;
+    while (!active_w.empty() && k < dim) {
+      // std::cout << "Started the step k=" << k << std::endl;
+      typename ActiveWitnessList::iterator it = active_w.begin();
+      while (it != active_w.end()) {
+        typeVectorVertex simplex_vector;
+        /* THE INSERTION: Checking if all the subfaces are in the simplex tree*/
+        bool ok = all_faces_in(knn, *it, k);
+        if (ok) {
+          for (int i = 0; i != k + 1; ++i)
+            simplex_vector.push_back(knn[*it][i]);
+          returnValue = sc.insert_simplex(simplex_vector, 0.0);
+          it++;
+        } else {
+          active_w.erase(it++);  // First increase the iterator and then erase the previous element
+        }
+      }
+      k++;
+    }
+  }
+
+  //@}
+
+ private:
+  /** \brief Check if the facets of the k-dimensional simplex witnessed 
+   *  by witness witness_id are already in the complex.
+   *  inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id
+   */
+  template <typename KNearestNeighbors>
+  bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) {
+    // std::cout << "All face in with the landmark " << inserted_vertex << std::endl;
+    std::vector< Vertex_handle > facet;
+    // Vertex_handle curr_vh = curr_sh->first;
+    // CHECK ALL THE FACETS
+    for (int i = 0; i != k + 1; ++i) {
+      facet = {};
+      for (int j = 0; j != k + 1; ++j) {
+        if (j != i) {
+          facet.push_back(knn[witness_id][j]);
+        }
+      }  // endfor
+      if (sc.find(facet) == sc.null_simplex())
+        return false;
+      // std::cout << "++++ finished loop safely\n";
+    }  // endfor
+    return true;
+  }
+
+  template <typename T>
+  void print_vector(const std::vector<T> v) {
+    std::cout << "[";
+    if (!v.empty()) {
+      std::cout << *(v.begin());
+      for (auto it = v.begin() + 1; it != v.end(); ++it) {
+        std::cout << ",";
+        std::cout << *it;
+      }
+    }
+    std::cout << "]";
+  }
+
+ public:
+  /**
+   *  \brief Verification if every simplex in the complex is witnessed by witnesses in knn.
+   *  \param print_output =true will print the witnesses for each simplex
+   *  \remark Added for debugging purposes.
+   */
+  template< class KNearestNeighbors >
+  bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) {
+    // bool final_result = true;
+    for (Simplex_handle sh : sc.complex_simplex_range()) {
+      bool is_witnessed = false;
+      typeVectorVertex simplex;
+      int nbV = 0;  // number of verticed in the simplex
+      for (int v : sc.simplex_vertex_range(sh))
+        simplex.push_back(v);
+      nbV = simplex.size();
+      for (typeVectorVertex w : knn) {
+        bool has_vertices = true;
+        for (int v : simplex)
+          if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) {
+            has_vertices = false;
+            // break;
+          }
+        if (has_vertices) {
+          is_witnessed = true;
+          if (print_output) {
+            std::cout << "The simplex ";
+            print_vector(simplex);
+            std::cout << " is witnessed by the witness ";
+            print_vector(w);
+            std::cout << std::endl;
+          }
+          break;
+        }
+      }
+      if (!is_witnessed) {
+        if (print_output) {
+          std::cout << "The following simplex is not witnessed ";
+          print_vector(simplex);
+          std::cout << std::endl;
+        }
+        assert(is_witnessed);
+        return false;
+      }
+    }
+    return true;
+  }
+};
+
+}  // namespace witness_complex
+
+}  // namespace Gudhi
+
+#endif  // WITNESS_COMPLEX_H_
diff --git a/src/Witness_complex/include/gudhi/Witness_complex_doc.h b/src/Witness_complex/include/gudhi/Witness_complex_doc.h
new file mode 100644
index 00000000..e9f78170
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Witness_complex_doc.h
@@ -0,0 +1,38 @@
+#ifndef WITNESS_COMPLEX_DOC_H_
+#define WITNESS_COMPLEX_DOC_H_
+
+/**
+   \defgroup witness_complex Witness complex
+
+   \author Siargey Kachanovich
+
+   \section Definitions
+
+   Witness complex \f$ Wit(W,L) \f$  is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$:
+
+   \li \f$W\f$ set of **witnesses** and 
+   \li \f$L \subseteq W\f$ set of **landmarks**.
+
+   The simplices are based on landmarks
+   and a simplex belongs to the witness complex if and only if it is witnessed, that is:
+
+   \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that 
+   w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. 
+      
+   \section Implementation
+
+   The principal class of this module is Gudhi::Witness_complex.
+
+   In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness.
+   This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module.
+
+   *\image html "bench_Cy8.png" "Running time as function on number of landmarks" width=10cm
+   *\image html "bench_sphere.png" "Running time as function on number of witnesses for |L|=300" width=10cm
+   
+
+   \copyright GNU General Public License v3.
+
+
+ */
+
+#endif  // WITNESS_COMPLEX_DOC_H_
diff --git a/src/Witness_complex/test/CMakeLists.txt b/src/Witness_complex/test/CMakeLists.txt
new file mode 100644
index 00000000..9422c152
--- /dev/null
+++ b/src/Witness_complex/test/CMakeLists.txt
@@ -0,0 +1,34 @@
+cmake_minimum_required(VERSION 2.6)
+project(GUDHIWitnessComplexUT)
+
+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()
+
+add_executable ( simple_witness_complexUT simple_witness_complex.cpp )
+target_link_libraries(simple_witness_complexUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+# Unitary tests definition and xml result file generation
+add_test(NAME simple_witness_complexUT
+  COMMAND ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complexUT 
+    # XML format for Jenkins xUnit plugin 
+    --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/simple_witness_complexUT.xml --log_level=test_suite --report_level=no)
+
+add_executable ( witness_complex_pointsUT witness_complex_points.cpp )
+target_link_libraries(witness_complex_pointsUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+# Unitary tests definition and xml result file generation
+add_test(NAME witness_complex_pointsUT
+  COMMAND ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_pointsUT 
+    # XML format for Jenkins xUnit plugin 
+    --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/witness_complex_pointsUT.xml --log_level=test_suite --report_level=no)
+
diff --git a/src/Witness_complex/test/simple_witness_complex.cpp b/src/Witness_complex/test/simple_witness_complex.cpp
new file mode 100644
index 00000000..7d44b90c
--- /dev/null
+++ b/src/Witness_complex/test/simple_witness_complex.cpp
@@ -0,0 +1,59 @@
+/*    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) 2016  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/>.
+ */
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "simple_witness_complex"
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Witness_complex.h>
+
+#include <iostream>
+#include <ctime>
+#include <vector>
+
+typedef Gudhi::Simplex_tree<> Simplex_tree;
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex;
+
+BOOST_AUTO_TEST_CASE(simple_witness_complex) {
+  Simplex_tree complex;
+  std::vector< typeVectorVertex > knn;
+
+  knn.push_back({1, 0, 5, 2, 6, 3, 4});
+  knn.push_back({2, 6, 4, 5, 0, 1, 3});
+  knn.push_back({3, 4, 2, 1, 5, 6, 0});
+  knn.push_back({4, 2, 1, 3, 5, 6, 0});
+  knn.push_back({5, 1, 6, 0, 2, 3, 4});
+  knn.push_back({6, 0, 5, 2, 1, 3, 4});
+  knn.push_back({0, 5, 6, 1, 2, 3, 4});
+  knn.push_back({2, 6, 4, 5, 3, 1, 0});
+  knn.push_back({1, 2, 5, 4, 3, 6, 0});
+  knn.push_back({3, 4, 0, 6, 5, 1, 2});
+  knn.push_back({5, 0, 1, 3, 6, 2, 4});
+  knn.push_back({5, 6, 1, 0, 2, 3, 4});
+  knn.push_back({1, 6, 0, 5, 2, 3, 4});
+  WitnessComplex witnessComplex(knn, complex, 7, 7);
+
+  BOOST_CHECK(witnessComplex.is_witness_complex(knn, false));
+}
diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp
new file mode 100644
index 00000000..78f01e08
--- /dev/null
+++ b/src/Witness_complex/test/witness_complex_points.cpp
@@ -0,0 +1,66 @@
+/*    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) 2016  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/>.
+ */
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "witness_complex_points"
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+#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 <iostream>
+#include <vector>
+
+typedef std::vector<double> Point;
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef Gudhi::Simplex_tree<> Simplex_tree;
+typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex;
+typedef Gudhi::witness_complex::Landmark_choice_by_random_point Landmark_choice_by_random_point;
+typedef Gudhi::witness_complex::Landmark_choice_by_furthest_point Landmark_choice_by_furthest_point;
+
+BOOST_AUTO_TEST_CASE(witness_complex_points) {
+  std::vector< typeVectorVertex > knn;
+  std::vector< Point > points;
+  // Add grid points as witnesses
+  for (double i = 0; i < 10; i += 1.0)
+    for (double j = 0; j < 10; j += 1.0)
+      for (double k = 0; k < 10; k += 1.0)
+        points.push_back(Point({i, j, k}));
+
+  bool b_print_output = false;
+  // First test: random choice
+  Simplex_tree complex1;
+  Landmark_choice_by_random_point lcrp(points, 100, knn);
+  assert(!knn.empty());
+  WitnessComplex witnessComplex1(knn, complex1, 100, 3);
+  assert(witnessComplex1.is_witness_complex(knn, b_print_output));
+
+  // Second test: furthest choice
+  knn.clear();
+  Simplex_tree complex2;
+  Landmark_choice_by_furthest_point lcfp(points, 100, knn);
+  WitnessComplex witnessComplex2(knn, complex2, 100, 3);
+  assert(witnessComplex2.is_witness_complex(knn, b_print_output));
+}