Added witness_complex function carcas

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

Former-commit-id: 542dd6740b0ae233ea5fb8ea5c6fe313bf1f27d9

1 files changed, 77 insertions, 36 deletions

diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h
index fbebea57..0651e38e 100644
--- a/src/Witness_complex/include/gudhi/Witness_complex.h
+++ b/src/Witness_complex/include/gudhi/Witness_complex.h
@@ -27,8 +27,10 @@
 #include <algorithm>
 #include <utility>
 #include "gudhi/reader_utils.h"
+#include "gudhi/distance_functions.h"
 #include "gudhi/Simplex_tree.h"
 #include <vector>
+#include <forward_list>
 #include <math.h>
 
 namespace Gudhi {
@@ -40,14 +42,16 @@ template<typename FiltrationValue = double,
 class Simplex_tree;
   */  
 
-    /*  
+      
 template<typename FiltrationValue = double,
          typename SimplexKey      = int,
          typename VertexHandle    = int>
-class Witness_complex: public Simplex_tree {
-  //class Witness_complex: public Simplex_tree<FiltrationValue, SimplexKey, VertexHandle> {
+    class Witness_complex: public Simplex_tree<> {
+    //class Witness_complex: public Simplex_tree<FiltrationValue, SimplexKey, VertexHandle> {
+    //class Witness_complex {
 public:
 
+//Simplex_tree<> st;
 // typedef int                      Simplex_handle; //index in vector complex_
  
 // typedef typename std::vector< Simplex_handle >::iterator    Boundary_simplex_iterator;
@@ -88,50 +92,86 @@ public:
   /* \brief Set of nodes sharing a same parent in the simplex tree. */
 // typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings;
 
-/*
-  typedef std::vector< double > Point_t;
- typedef std::vector< Point_t > Point_Vector;
 
+typedef std::vector< double > Point_t;
+typedef std::vector< Point_t > Point_Vector;
+
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex;
+typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool;
+/*
 Witness_complex(int number_of_landmarks, std::string file_name)
 {
-  /*
-  Point_Vector & points;
-  read_points(file_name, points);
-  landmark_extraction(points);
-  */
-/*  
 }
-
-private:
-
+*/
 
 /**
- * \brief Permutes the vector in such a way that the landmarks appear first
+ * /brief Iterative construction of the witness complex basing on a matrix of k nearest neighbours of the form {witnesses}x{landmarks}.
+ * Landmarks are supposed to be in [0,nbL-1]
  */
 
-/*
-void landmark_extraction(int nbP, Point_Vector & points, int inL)
+template< typename KNearestNeighbours >
+void witness_complex(KNearestNeighbours & knn)
 {
-  int i,j;
-  for (i = 0; i != nbP; ++i)
-    {
-      for (j = 0; j != nbP; )
+    int k=1; /* current dimension in iterative construction */
+    //Construction of the active witness list
+    int nbW = knn.size();
+    int nbL = knn.at(0).size();
+    VertexHandle vh;
+    typeVectorVertex vv;
+    typeSimplex simplex;
+    typePairSimplexBool returnValue;
+    /* The list of still useful witnesses
+     * it will diminuish in the course of iterations
+     */
+    std::forward_list<int> active_w = new std::forward_list<int>();
+    for (int i=0; i != nbW; ++i) {
+        // initial fill of active witnesses list
+        active_w.push_front(i);
     }
+    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
+        vh = (Vertex_handle)i;
+        vv = {i};
+        /* TODO Filtration */
+        simplex = std::make_pair(vv,Filtration_value(0.0));
+        returnValue = this.insert_simplex(simplex.first, simplex.second);
+        /* TODO Error if not inserted : normally no need here though*/
+    }
+    while (!active_w.empty() && k+1 < nbL ) {
+        std::forward_list<int>::iterator it = active_w.begin();
+        while (it != active_w.end()) {
+            typeVectorVertex simplex_vector;
+            for (int i=0; i != k+1; ++i) {
+                // create a (k+1) element array for the given active landmark
+                /*
+                typeVectorVertex::iterator itSV = simplex_vector.begin();
+                while (itSV != simplex_vector.end() && *itSV < knn[*it][i]) {
+                    itSV++;
+                }
+                simplex_vector.insert(itSV,knn[*it][i]);
+                */
+                simplex_vector.push_back(knn[*it][i]);
+            }
+            /* THE INSERTION: Checking if all the subfaces are in the simplex tree is mandatory */
+            bool ok = all_faces_in(simplex_vecter);
+            returnValue = this.insert_simplex(simplex_vector,0.0);
+        }
+    } 
 }
-*/
 
-  /*
-  
-double distPoints(Point_t &p, Point_t &q) {
-	double dist = 0.;
-        Point_t::iterator itp = p.begin();
-        Point_t::iterator itq = q.begin();
-	while(itp!=p.end()) {
-		dist += (*itp - *itq)*(*itp - *itq);
-		itp++; itq++;}
-	return dist;
+private:
+
+bool all_faces_in(typeVectorVertex v)
+{
+return true;
 }
 
+/**
+ * \brief Permutes the vector in such a way that the landmarks appear first
+ */
+
 void furthestPoints(Point_Vector &W, int nbP, std::string file_land, int dim, int nbL, Point_Vector &L) {
   //std::cout << "Enter furthestPoints "<< endl;
   //Point_Vector *L = new Point_Vector();
@@ -154,7 +194,8 @@ void furthestPoints(Point_Vector &W, int nbP, std::string file_land, int dim, in
       //compute distance from w and L
       mindist = 100000.;
       for(Point_Vector::iterator itL = L.begin(); itL != L.end(); itL++) {
-        curr_dist = distPoints(*itW,*itL);
+          //curr_dist = distPoints(*itW,*itL);
+          curr_dist = euclidean_distance(*itW,*itL);
         if(curr_dist < mindist) {
           mindist = curr_dist;
         }
@@ -174,9 +215,9 @@ void furthestPoints(Point_Vector &W, int nbP, std::string file_land, int dim, in
   //std::cout << endl;
   return L;
 }
-  */
+  
 }; //class Witness_complex
-*/
+
   
 } // namespace Guhdi