diff options
Diffstat (limited to 'src/Witness_complex/include')
4 files changed, 43 insertions, 28 deletions
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 index 44bf9dbb..0b196f18 100644 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h +++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h @@ -31,18 +31,22 @@ * \ingroup witness_complex */ -class Landmark_choice_by_random_point { +class Landmark_choice_by_furthest_point { +public: + /** * \brief Landmark choice strategy by iteratively adding the furthest witness from the - * current landmark set as the new landmark. It takes a random access range `points` and + * 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_points(Point_random_access_range &points, - KNearestNeighbours &knn) + Landmark_choice_by_furthest_point(Point_random_access_range &points, + int nbL, + KNearestNeighbours &knn) { int nb_points = points.end() - points.begin(); std::vector<std::vector<double>> wit_land_dist(nb_points, std::vector<double>()); // distance matrix witness x landmarks 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 index bc3e72d9..fa822591 100644 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h +++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h @@ -33,18 +33,19 @@ class Landmark_choice_by_random_point { - +public: + /** \brief Landmark choice strategy by taking random vertices for landmarks. - * It takes a random access range points and outputs a matrix {witness}*{closest landmarks} - * in knn. + * \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> - void landmark_choice_by_random_points(Point_random_access_range &points, KNearestNeighbours &knn) + Landmark_choice_by_random_point(Point_random_access_range &points, int nbL, KNearestNeighbours &knn) { int nbP = points.end() - points.begin(); - std::set<int> &landmarks; + std::set<int> landmarks; int current_number_of_landmarks=0; // counter for landmarks int chosen_landmark = rand()%nbP; @@ -55,9 +56,10 @@ class Landmark_choice_by_random_point { landmarks.insert(chosen_landmark); } - int D = points.begin().size(); + 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;}); @@ -68,7 +70,7 @@ class Landmark_choice_by_random_point { 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 < D+1; i++) + for (int i = 0; i < dim+1; i++) { dist_i dist = l_heap.top(); knn[points_i].push_back(dist.second); diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index b218611b..791d0e45 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -73,10 +73,11 @@ namespace Gudhi { 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_tree<>::Simplex_handle, bool > typePairSimplexBool; + typedef std::pair< Simplex_handle, bool > typePairSimplexBool; typedef int Witness_id; typedef int Landmark_id; @@ -204,11 +205,12 @@ namespace Gudhi { public: /** - * \brief Verification if every simplex in the complex is witnessed. + * \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 & knn) + bool is_witness_complex(KNearestNeighbors & knn, bool print_output) { //bool final_result = true; for (Simplex_handle sh: sc.complex_simplex_range()) @@ -231,19 +233,25 @@ namespace Gudhi { if (has_vertices) { is_witnessed = true; - std::cout << "The simplex "; - print_vector(simplex); - std::cout << " is witnessed by the witness "; - print_vector(w); - std::cout << std::endl; + 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) { - std::cout << "The following simplex is not witnessed "; - print_vector(simplex); - std::cout << std::endl; + if (print_output) + { + std::cout << "The following simplex is not witnessed "; + print_vector(simplex); + std::cout << std::endl; + } assert(is_witnessed); return false; } diff --git a/src/Witness_complex/include/gudhi/Witness_complex_doc.h b/src/Witness_complex/include/gudhi/Witness_complex_doc.h index 22cfe992..446f0d11 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex_doc.h +++ b/src/Witness_complex/include/gudhi/Witness_complex_doc.h @@ -21,14 +21,15 @@ \section Implementation - Two classes are implemented in this module: Gudhi::Witness_complex and Gudhi::Relaxed_witness_complex. + The principal class of this module is Gudhi::Witness_complex. - While Gudhi::Witness_complex represents the classical witness complex, Gudhi::Relaxed_witness_complex takes an additional positive real parameter \f$ \alpha \f$ and constructs simplices \f$ \sigma \f$, for which - there exists \f$ w \in W \f$, such that \f$ d(p,w) < d(q,w) + \alpha \f$ for all \f$ p \in \sigma, q \in L\setminus \sigma \f$. - - In both cases, the constructors take a {witness}x{closest_landmarks} table, + In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, which 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. |