Added the file for knn landmarks (no CGAL include yet). New algorithm for landmark selection: now 10 times faster!

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

Former-commit-id: 9de270bd67ac33fd1079de7692dd8974441db606

5 files changed, 303 insertions, 52 deletions

diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt
index 14d23551..fa594de7 100644
--- a/src/Witness_complex/example/CMakeLists.txt
+++ b/src/Witness_complex/example/CMakeLists.txt
@@ -14,9 +14,9 @@ project(GUDHIWitnessComplex)
    add_executable ( simple_witness_complex simple_witness_complex.cpp )
    add_test(simple_witness_complex ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complex)
 
-   #add_executable( witness_complex_from_file witness_complex_from_file.cpp )
+   add_executable( witness_complex_from_file witness_complex_from_file.cpp )
    #target_link_libraries(witness_complex_from_file ${EIGEN3_LIBRARIES} ${CGAL_LIBRARY})
-   #add_test( witness_complex_from_bunny &{CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100)   
+   add_test( witness_complex_from_bunny &{CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100)   
    
    add_executable( witness_complex_from_off witness_complex_from_off.cpp )
    
@@ -35,7 +35,7 @@ if(GMP_FOUND AND CGAL_FOUND)
    INCLUDE_DIRECTORIES(${EIGEN3_INCLUDE_DIRS})
    INCLUDE_DIRECTORIES(${GMP_INCLUDE_DIR})
    INCLUDE_DIRECTORIES(${CGAL_INCLUDE_DIRS})
-   add_executable (witness_complex_from_file witness_complex_from_file.cpp )
-   target_link_libraries(witness_complex_from_file ${GMP_LIBRARIES} ${EIGEN3_LIBRARIES} ${CGAL_LIBRARY})
-   add_test(witness_complex_from_file ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100)
+   add_executable (witness_complex_knn_landmarks witness_complex_knn_landmarks.cpp )
+   target_link_libraries(witness_complex_knn_landmarks ${EIGEN3_LIBRARIES} ${CGAL_LIBRARY})
+   add_test(witness_complex_knn_landmarks ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_knn_landmarks ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100)
 endif()
diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp
index cf09899b..b842574b 100644
--- a/src/Witness_complex/example/witness_complex_from_file.cpp
+++ b/src/Witness_complex/example/witness_complex_from_file.cpp
@@ -109,9 +109,11 @@ int main (int argc, char * const argv[])
   witnessComplex.setNbL(nbL);
   //  witnessComplex.witness_complex_from_points(point_vector);
   std::vector<std::vector< int > > WL;
+  std::set<int> L;
   start = clock();
   //witnessComplex.landmark_choice_by_furthest_points(point_vector, point_vector.size(), WL);
-  witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), WL);
+  witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), L);
+  witnessComplex.nearest_landmarks(point_vector,L,WL);
   end = clock();
   std::cout << "Landmark choice took "
             << (double)(end-start)/CLOCKS_PER_SEC << " s. \n";
diff --git a/src/Witness_complex/example/witness_complex_from_off.cpp b/src/Witness_complex/example/witness_complex_from_off.cpp
index 04d4e601..948f09a8 100644
--- a/src/Witness_complex/example/witness_complex_from_off.cpp
+++ b/src/Witness_complex/example/witness_complex_from_off.cpp
@@ -148,9 +148,11 @@ int main (int argc, char * const argv[])
   witnessComplex.setNbL(nbL);
   //  witnessComplex.witness_complex_from_points(point_vector);
   std::vector<std::vector< int > > WL;
+  std::set<int> L;
   start = clock();
   //witnessComplex.landmark_choice_by_furthest_points(point_vector, point_vector.size(), WL);
-  witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), WL);
+  witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), L);
+  witnessComplex.nearest_landmarks(point_vector,L,WL);
   end = clock();
   std::cout << "Landmark choice took "
             << (double)(end-start)/CLOCKS_PER_SEC << " s. \n";
diff --git a/src/Witness_complex/example/witness_complex_knn_landmarks.cpp b/src/Witness_complex/example/witness_complex_knn_landmarks.cpp
new file mode 100644
index 00000000..2003f218
--- /dev/null
+++ b/src/Witness_complex/example/witness_complex_knn_landmarks.cpp
@@ -0,0 +1,161 @@
+/*    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 <iostream>
+#include <fstream>
+#include <ctime>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+//#include <stdlib.h>
+
+//#include "gudhi/graph_simplicial_complex.h"
+#include "gudhi/Witness_complex.h"
+#include "gudhi/reader_utils.h"
+//#include <boost/filesystem.hpp>
+
+//#include <CGAL/Delaunay_triangulation.h>
+//#include <CGAL/Epick_d.h>
+#include <CGAL/K_neighbor_search.h>
+
+using namespace Gudhi;
+//using namespace boost::filesystem;
+
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef std::vector< std::vector <double> > Point_Vector;
+//typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex;
+//typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool;
+
+
+/**
+ * \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();
+}
+
+void write_wl( std::string file_name, std::vector< std::vector <int> > & WL)
+{
+  std::ofstream ofs (file_name, std::ofstream::out);
+  for (auto w : WL)
+    {
+      for (auto l: w)
+        ofs << l << " ";
+      ofs << "\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;
+    }
+  /*
+  boost::filesystem::path p;
+
+  for (; argc > 2; --argc, ++argv)
+    p /= argv[1];
+  */
+  std::string file_name   = argv[1];
+  int nbL       = atoi(argv[2]);
+  
+  clock_t start, end;
+  //Construct the Simplex Tree
+  Witness_complex<> witnessComplex;
+ 
+  std::cout << "Let the carnage begin!\n";
+  Point_Vector point_vector;
+  read_points_cust(file_name, point_vector);
+  //std::cout << "Successfully read the points\n";
+  witnessComplex.setNbL(nbL);
+  //  witnessComplex.witness_complex_from_points(point_vector);
+  std::vector<std::vector< int > > WL;
+  std::set<int> L;
+  int nbP = point_vector.size();
+  start = clock();
+  //witnessComplex.landmark_choice_by_furthest_points(point_vector, point_vector.size(), WL);
+  witnessComplex.landmark_choice_by_random_points(point_vector, nbP, L);
+  witnessComplex.nearest_landmarks(point_vector,L,WL);
+  end = clock();
+  std::cout << "Landmark choice took "
+            << (double)(end-start)/CLOCKS_PER_SEC << " s. \n";
+  // Write the WL matrix in a file
+  mkdir("output", S_IRWXU);
+  const size_t last_slash_idx = file_name.find_last_of("/");
+  if (std::string::npos != last_slash_idx)
+    {
+      file_name.erase(0, last_slash_idx + 1);
+    }
+  std::string out_file = "output/"+file_name+"_"+argv[2]+".wl";
+  //write_wl(out_file,WL);
+  start = clock();
+  witnessComplex.witness_complex(WL);
+  //
+  end = clock();
+  std::cout << "Howdy world! The process took "
+       << (double)(end-start)/CLOCKS_PER_SEC << " s. \n";
+  /*
+  char buffer[100];
+  int i = sprintf(buffer,"%s_%s_result.txt",argv[1],argv[2]);
+  if (i >= 0)
+    {
+      std::string out_file = (std::string)buffer;
+      std::ofstream ofs (out_file, std::ofstream::out);
+      witnessComplex.st_to_file(ofs);
+      ofs.close();
+    }
+  */
+
+  out_file = "output/"+file_name+"_"+argv[2]+".stree";
+  std::ofstream ofs (out_file, std::ofstream::out);
+  witnessComplex.st_to_file(ofs);
+  ofs.close();
+
+  out_file = "output/"+file_name+"_"+argv[2]+".badlinks";
+  std::ofstream ofs2(out_file, std::ofstream::out);
+  witnessComplex.write_bad_links(ofs2);
+  ofs2.close();
+}
diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h
index 3c030c45..2ccaa416 100644
--- a/src/Witness_complex/include/gudhi/Witness_complex.h
+++ b/src/Witness_complex/include/gudhi/Witness_complex.h
@@ -32,7 +32,8 @@
 #include "gudhi/Simplex_tree.h"
 #include <vector>
 #include <list>
-#include <unordered_set>
+#include <set>
+#include <queue>
 #include <limits>
 #include <math.h>
 #include <ctime>
@@ -40,9 +41,9 @@
 
 // Needed for nearest neighbours
 //#include <CGAL/Delaunay_triangulation.h>
-#include <CGAL/Epick_d.h>
-#include <CGAL/K_neighbor_search.h>
-#include <CGAL/Search_traits_d.h>
+//#include <CGAL/Epick_d.h>
+//#include <CGAL/K_neighbor_search.h>
+//#include <CGAL/Search_traits_d.h>
 
 // Needed for the adjacency graph in bad link search
 #include <boost/graph/graph_traits.hpp>
@@ -233,12 +234,12 @@ namespace Gudhi {
      * FURTHEST_POINT_STRATEGY and RANDOM_POINT_STRATEGY and
      * density must be set to the right value for DENSITY_STRATEGY
      */
-  void witness_complex_from_points(Point_Vector point_vector)
-  {
-    std::vector<std::vector< int > > WL;
-    landmark_choice_by_random_points(point_vector, point_vector.size(), WL);
-    witness_complex(WL);
-  }
+  // void witness_complex_from_points(Point_Vector point_vector)
+  // {
+  //   std::vector<std::vector< int > > WL;
+  //   landmark_choice_by_random_points(point_vector, point_vector.size(), WL);
+  //   witness_complex(WL);
+  // }
   
 private:
 
@@ -468,75 +469,160 @@ private:
      *
      */
 
-    template <typename KNearestNeighbours>
-    void landmark_choice_by_random_points(Point_Vector &W, int nbP, KNearestNeighbours &WL)
+    // template <typename KNearestNeighbours>
+    // void landmark_choice_by_random_points(Point_Vector &W, int nbP, KNearestNeighbours &WL)
+    // {
+    //   std::cout << "Enter landmark_choice_by_random_points "<< std::endl;
+    //   //std::cout << "W="; print_vvector(W);
+    //   std::unordered_set< int >  chosen_landmarks;              // landmark set
+
+    //   Point_Vector wit_land_dist(nbP,std::vector<double>());    // distance matrix witness x landmarks
+
+    //   WL = KNearestNeighbours(nbP,std::vector<int>());                             
+    //   int current_number_of_landmarks=0;                        // counter for landmarks 
+
+    //   srand(24660);
+    //   int chosen_landmark = rand()%nbP;
+    //   double curr_dist;
+      
+    //   //int j;
+    //   //int temp_swap_int;                                        
+    //   //double temp_swap_double;
+
+      
+    //   for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++)
+    //     {
+    //       while (chosen_landmarks.find(chosen_landmark) != chosen_landmarks.end())
+    //         {
+    //           srand((int)clock());
+    //           chosen_landmark = rand()% nbP;
+    //           //std::cout << chosen_landmark << "\n";
+    //         }
+    //       chosen_landmarks.insert(chosen_landmark);
+    //       //std::cout << "**********Entered loop with current number of landmarks = " << current_number_of_landmarks << std::endl;
+    //       //std::cout << "WL="; print_vvector(WL);
+    //       //std::cout << "WLD="; print_vvector(wit_land_dist);
+    //       //std::cout << "landmarks="; print_vector(chosen_landmarks); std::cout << std::endl;
+    //       for (auto v: WL)
+    //         v.push_back(current_number_of_landmarks);
+    //       for (int i = 0; i < nbP; ++i)
+    //         {
+    //           // iteration on points in W. update of distance vectors
+              
+    //           //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl;
+    //           //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl;
+    //           curr_dist = euclidean_distance(W[i],W[chosen_landmark]);
+    //           //std::cout << "The problem is not in distance function\n";
+    //           wit_land_dist[i].push_back(curr_dist);
+    //           WL[i].push_back(current_number_of_landmarks);
+    //           //std::cout << "Push't back\n";
+    //           //j = current_number_of_landmarks;
+    //           //std::cout << "First half complete\n";
+    //           //std::cout << "result WL="; print_vvector(WL);
+    //           //std::cout << "result WLD="; print_vvector(wit_land_dist);
+    //           //std::cout << "End loop\n";
+    //         }
+    //     }
+    //   for (int i = 0; i < nbP; i++)
+    //     {
+    //       sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];});
+    //     }
+    //   //std::cout << endl;
+    // }
+
+    /** \brief Landmark choice strategy by taking random vertices for landmarks.
+     *
+     */
+
+    //    template <typename KNearestNeighbours>
+    void landmark_choice_by_random_points(Point_Vector &W, int nbP, std::set<int> &L)
     {
       std::cout << "Enter landmark_choice_by_random_points "<< std::endl;
       //std::cout << "W="; print_vvector(W);
-      std::unordered_set< int >  chosen_landmarks;              // landmark set
+      //std::unordered_set< int >  chosen_landmarks;              // landmark set
 
       Point_Vector wit_land_dist(nbP,std::vector<double>());    // distance matrix witness x landmarks
 
-      WL = KNearestNeighbours(nbP,std::vector<int>());                             
+      //WL = KNearestNeighbours(nbP,std::vector<int>());                             
       int current_number_of_landmarks=0;                        // counter for landmarks 
 
       srand(24660);
       int chosen_landmark = rand()%nbP;
-      double curr_dist;
-      
+      //double curr_dist;
       //int j;
       //int temp_swap_int;                                        
-      //double temp_swap_double;
-
-      
+      //double temp_swap_double; 
       for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++)
         {
-          while (chosen_landmarks.find(chosen_landmark) != chosen_landmarks.end())
+          while (L.find(chosen_landmark) != L.end())
             {
               srand((int)clock());
               chosen_landmark = rand()% nbP;
               //std::cout << chosen_landmark << "\n";
             }
-          chosen_landmarks.insert(chosen_landmark);
+          L.insert(chosen_landmark);
           //std::cout << "**********Entered loop with current number of landmarks = " << current_number_of_landmarks << std::endl;
           //std::cout << "WL="; print_vvector(WL);
           //std::cout << "WLD="; print_vvector(wit_land_dist);
           //std::cout << "landmarks="; print_vector(chosen_landmarks); std::cout << std::endl;
-          for (auto v: WL)
-            v.push_back(current_number_of_landmarks);
-          for (int i = 0; i < nbP; ++i)
-            {
-              // iteration on points in W. update of distance vectors
+          // for (auto v: WL)
+          //   v.push_back(current_number_of_landmarks);
+          // for (int i = 0; i < nbP; ++i)
+          //   {
+          //     // iteration on points in W. update of distance vectors
               
-              //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl;
-              //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl;
-              curr_dist = euclidean_distance(W[i],W[chosen_landmark]);
-              //std::cout << "The problem is not in distance function\n";
-              wit_land_dist[i].push_back(curr_dist);
-              WL[i].push_back(current_number_of_landmarks);
-              //std::cout << "Push't back\n";
-              //j = current_number_of_landmarks;
-              //std::cout << "First half complete\n";
-              //std::cout << "result WL="; print_vvector(WL);
-              //std::cout << "result WLD="; print_vvector(wit_land_dist);
-              //std::cout << "End loop\n";
-            }
-        }
-      for (int i = 0; i < nbP; i++)
-        {
-          sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];});
+          //     //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl;
+          //     //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl;
+          //     curr_dist = euclidean_distance(W[i],W[chosen_landmark]);
+          //     //std::cout << "The problem is not in distance function\n";
+          //     wit_land_dist[i].push_back(curr_dist);
+          //     WL[i].push_back(current_number_of_landmarks);
+          //     //std::cout << "Push't back\n";
+          //     //j = current_number_of_landmarks;
+          //     //std::cout << "First half complete\n";
+          //     //std::cout << "result WL="; print_vvector(WL);
+          //     //std::cout << "result WLD="; print_vvector(wit_land_dist);
+          //     //std::cout << "End loop\n";
+          //   }
         }
+      // for (int i = 0; i < nbP; i++)
+      //   {
+      //     sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];});
+      //   }
       //std::cout << endl;
     }
 
+    
     /** \brief Construct the matrix |W|x(D+1) of D+1 closest landmarks
      *  where W is the set of witnesses and D is the ambient dimension
      */
     template <typename KNearestNeighbours>
-    void nearest_landmarks(Point_Vector &W, std::unordered_set<int> &L, KNearestNeighbours &WL)
+    void nearest_landmarks(Point_Vector &W, std::set<int> &L, KNearestNeighbours &WL)
     {
       int D = W[0].size();
-      
+      int nbP = W.size();
+      WL = KNearestNeighbours(nbP,std::vector<int>());
+      typedef std::pair<double,int> dist_i;
+      typedef bool (*comp)(dist_i,dist_i);
+      for (int W_i = 0; W_i < nbP; W_i++)
+        {
+          //std::cout << "<<<<<<<<<<<<<<" << W_i <<"\n"; 
+          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 L_it;
+          int L_i;
+          for (L_it = L.begin(), L_i=0; L_it != L.end(); L_it++, L_i++)
+            {
+              dist_i dist = std::make_pair(euclidean_distance(W[W_i],W[*L_it]), L_i);
+              l_heap.push(dist);
+            }
+          for (int i = 0; i < D+1; i++)
+            {
+              dist_i dist = l_heap.top();
+              WL[W_i].push_back(dist.second);  
+              //std::cout << dist.first << " " << dist.second << std::endl;
+              l_heap.pop();
+            }
+        }
     }
     
     /** \brief Search and output links around vertices that are not pseudomanifolds