From 6536cb935d5702425f33d10f514fa450c470096a Mon Sep 17 00:00:00 2001 From: skachano Date: Wed, 18 Mar 2015 17:35:25 +0000 Subject: 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 --- CMakeLists.txt | 2 + .../include/gudhi/Witness_complex.h | 113 ++++++++++++++------- 2 files changed, 79 insertions(+), 36 deletions(-) diff --git a/CMakeLists.txt b/CMakeLists.txt index 3afec463..0c8f6ea3 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -74,6 +74,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) @@ -83,6 +84,7 @@ else() add_subdirectory(src/Skeleton_blocker/example) add_subdirectory(src/Contraction/example) add_subdirectory(src/Hasse_complex/example) + add_subdirectory(src/Witness_complex/example) endif() 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 #include #include "gudhi/reader_utils.h" +#include "gudhi/distance_functions.h" #include "gudhi/Simplex_tree.h" #include +#include #include namespace Gudhi { @@ -40,14 +42,16 @@ template -class Witness_complex: public Simplex_tree { - //class Witness_complex: public Simplex_tree { + class Witness_complex: public Simplex_tree<> { + //class Witness_complex: public Simplex_tree { + //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 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 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 active_w = new std::forward_list(); + 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::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 -- cgit v1.2.3