diff options
author | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-09-28 12:33:22 +0000 |
---|---|---|
committer | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-09-28 12:33:22 +0000 |
commit | d16822ea1d3cedea66dcddd390becdd4cbb557bb (patch) | |
tree | b1c592e415f43c1be425608db861e5348e61dcf3 /src/Witness_complex | |
parent | 1c09c91ddf4d38196a91bbff5ae432fb13be6762 (diff) | |
parent | a138c9ed4fb9770a3612ff4ee0f914942bbe9724 (diff) |
Merged trunk into relaxed witness branch
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/relaxed-witness@1579 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: a9ca2e7a968ebf4bb80cfa795965ae78511e8dd4
Diffstat (limited to 'src/Witness_complex')
-rw-r--r-- | src/Witness_complex/concept/Simplicial_complex_for_witness.h (renamed from src/Witness_complex/concept/Simplicial_complex.h) | 19 | ||||
-rw-r--r-- | src/Witness_complex/doc/Witness_complex_doc.h (renamed from src/Witness_complex/include/gudhi/Witness_complex_doc.h) | 6 | ||||
-rw-r--r-- | src/Witness_complex/doc/Witness_complex_representation.png | bin | 0 -> 48899 bytes | |||
-rw-r--r-- | src/Witness_complex/example/CMakeLists.txt | 47 | ||||
-rw-r--r-- | src/Witness_complex/example/witness_complex_from_file.cpp | 20 | ||||
-rw-r--r-- | src/Witness_complex/example/witness_complex_sphere.cpp | 20 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h | 22 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h | 19 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex.h | 96 | ||||
-rw-r--r-- | src/Witness_complex/test/CMakeLists.txt | 6 | ||||
-rw-r--r-- | src/Witness_complex/test/simple_witness_complex.cpp | 2 | ||||
-rw-r--r-- | src/Witness_complex/test/witness_complex_points.cpp | 4 |
12 files changed, 114 insertions, 147 deletions
diff --git a/src/Witness_complex/concept/Simplicial_complex.h b/src/Witness_complex/concept/Simplicial_complex_for_witness.h index d7f3496d..caaf0db6 100644 --- a/src/Witness_complex/concept/Simplicial_complex.h +++ b/src/Witness_complex/concept/Simplicial_complex_for_witness.h @@ -20,8 +20,8 @@ * 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_ +#ifndef CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_FOR_WITNESS_H_ +#define CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_FOR_WITNESS_H_ namespace Gudhi { @@ -31,7 +31,7 @@ namespace witness_complex { * for a type to implement a simplicial complex, * used for example to build a 'Witness_complex'. */ -struct Simplicial_complex { +struct SimplicialComplexForWitness { /** Handle to specify a simplex. */ typedef unspecified Simplex_handle; /** Handle to specify a vertex. Must be a non-negative integer. */ @@ -40,16 +40,11 @@ struct Simplicial_complex { /** 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; /** @@ -71,19 +66,17 @@ struct Simplicial_complex { */ 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. * */ + template< typedef Input_vertex_range > 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. */ + template< typedef Input_vertex_range > Simplex_handle find(Input_vertex_range const & vertex_range); }; @@ -91,4 +84,4 @@ struct Simplicial_complex { } // namespace Gudhi -#endif // CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_ +#endif // CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_FOR_WITNESS_H_ diff --git a/src/Witness_complex/include/gudhi/Witness_complex_doc.h b/src/Witness_complex/doc/Witness_complex_doc.h index e9f78170..60dfd27b 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex_doc.h +++ b/src/Witness_complex/doc/Witness_complex_doc.h @@ -6,6 +6,8 @@ \author Siargey Kachanovich + \image html "Witness_complex_representation.png" "Witness complex representation" + \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$: @@ -18,7 +20,9 @@ \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. - + + The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + \section Implementation The principal class of this module is Gudhi::Witness_complex. diff --git a/src/Witness_complex/doc/Witness_complex_representation.png b/src/Witness_complex/doc/Witness_complex_representation.png Binary files differnew file mode 100644 index 00000000..1d31a490 --- /dev/null +++ b/src/Witness_complex/doc/Witness_complex_representation.png diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index d6a958b7..4d67e0d0 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -1,5 +1,5 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIWitnessComplex) +project(Witness_complex_examples) # A simple example add_executable( witness_complex_from_file witness_complex_from_file.cpp ) @@ -7,51 +7,10 @@ project(GUDHIWitnessComplex) 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) - add_executable ( relaxed_witness_persistence relaxed_witness_persistence.cpp ) - target_link_libraries(relaxed_witness_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test( relaxed_witness_persistence_10 ${CMAKE_CURRENT_BINARY_DIR}/relaxed_witness_persistence 10) - add_executable ( a0_persistence a0_persistence.cpp ) - target_link_libraries(a0_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test( a0_persistence_10 ${CMAKE_CURRENT_BINARY_DIR}/a0_persistence 10) - add_executable ( bench_rwit bench_rwit.cpp ) - target_link_libraries(bench_rwit ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) - - add_executable ( relaxed_delaunay relaxed_delaunay.cpp ) - target_link_libraries(relaxed_delaunay ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) - add_test( relaxed_delaunay_10 ${CMAKE_CURRENT_BINARY_DIR}/relaxed_delaunay 10) - add_executable ( generate_torus generate_torus.cpp ) - 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(EIGEN3_FOUND) + endif (NOT CGAL_VERSION VERSION_LESS 4.6.0) endif() diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 77109512..53207ad2 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -34,14 +34,9 @@ #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 @@ -68,17 +63,6 @@ read_points_cust(std::string file_name, std::vector< std::vector< double > > & p 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] @@ -91,7 +75,7 @@ int main(int argc, char * const argv[]) { clock_t start, end; // Construct the Simplex Tree - Simplex_tree<> simplex_tree; + Gudhi::Simplex_tree<> simplex_tree; // Read the point file Point_Vector point_vector; @@ -109,7 +93,7 @@ int main(int argc, char * const argv[]) { // Compute witness complex start = clock(); - WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); + Gudhi::witness_complex::witness_complex(knn, nbL, point_vector[0].size(), simplex_tree); 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 index 1ff35bff..b26c9f36 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/witness_complex_sphere.cpp @@ -39,13 +39,6 @@ #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) */ @@ -60,15 +53,15 @@ void write_data(Data_range & data, std::string filename) { int main(int argc, char * const argv[]) { if (argc != 2) { std::cerr << "Usage: " << argv[0] - << " nbL \n"; + << " number_of_landmarks \n"; return 0; } - int nbL = atoi(argv[1]); + int number_of_landmarks = atoi(argv[1]); clock_t start, end; // Construct the Simplex Tree - Simplex_tree<> simplex_tree; + Gudhi::Simplex_tree<> simplex_tree; std::vector< std::pair<int, double> > l_time; @@ -82,14 +75,15 @@ int main(int argc, char * const argv[]) { // Choose landmarks start = clock(); std::vector<std::vector< int > > knn; - Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, nbL, knn); + Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, number_of_landmarks, knn); // Compute witness complex - WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); + Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree); end = clock(); double time = static_cast<double>(end - start) / CLOCKS_PER_SEC; - std::cout << "Witness complex for " << nbL << " landmarks took " + std::cout << "Witness complex for " << number_of_landmarks << " landmarks took " << time << " s. \n"; + std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\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 index 47cd888d..df93155b 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 @@ -23,7 +23,10 @@ #ifndef LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ #define LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ +#include <boost/range/size.hpp> + #include <limits> // for numeric_limits<> +#include <iterator> #include <algorithm> // for sort #include <vector> @@ -31,13 +34,19 @@ namespace Gudhi { namespace witness_complex { - typedef std::vector<int> typeVectorVertex; + typedef std::vector<int> typeVectorVertex; /** + * \ingroup witness_complex * \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`. + * + * 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 + * */ template <typename KNearestNeighbours, @@ -45,7 +54,7 @@ namespace witness_complex { void landmark_choice_by_furthest_point(Point_random_access_range const &points, int nbL, KNearestNeighbours &knn) { - int nb_points = points.end() - points.begin(); + int nb_points = boost::size(points); assert(nb_points >= nbL); // distance matrix witness x landmarks std::vector<std::vector<double>> wit_land_dist(nb_points, std::vector<double>()); @@ -59,6 +68,7 @@ namespace witness_complex { 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 + // or better yet std::uniform_int_distribution int rand_int = rand() % nb_points; int curr_max_w = rand_int; // For testing purposes a pseudo-random number is used here @@ -67,7 +77,7 @@ namespace witness_complex { 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])); + double curr_dist = euclidean_distance(p, *(std::begin(points) + 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]) @@ -81,9 +91,9 @@ namespace witness_complex { curr_max_w = i; } } - for (unsigned i = 0; i < points.size(); ++i) - std::sort(knn[i].begin(), - knn[i].end(), + for (int i = 0; i < nb_points; ++i) + std::sort(std::begin(knn[i]), + std::end(knn[i]), [&wit_land_dist, i](int a, int b) { return wit_land_dist[i][a] < wit_land_dist[i][b]; }); } 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 dc364007..ebf6aad1 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 @@ -23,8 +23,11 @@ #ifndef LANDMARK_CHOICE_BY_RANDOM_POINT_H_ #define LANDMARK_CHOICE_BY_RANDOM_POINT_H_ +#include <boost/range/size.hpp> + #include <queue> // for priority_queue<> #include <utility> // for pair<> +#include <iterator> #include <vector> #include <set> @@ -32,9 +35,17 @@ namespace Gudhi { namespace witness_complex { - /** \brief Landmark choice strategy by taking random vertices for landmarks. + /** + * \ingroup witness_complex + * \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. + * + * 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 and + * Vertex_handle is the label type of a vertex in a simplicial complex. + * Closest_landmark_range needs to have push_back operation. */ template <typename KNearestNeighbours, @@ -42,7 +53,7 @@ namespace witness_complex { void landmark_choice_by_random_point(Point_random_access_range const &points, int nbL, KNearestNeighbours &knn) { - int nbP = points.end() - points.begin(); + int nbP = boost::size(points); assert(nbP >= nbL); std::set<int> landmarks; int current_number_of_landmarks = 0; // counter for landmarks @@ -55,12 +66,12 @@ namespace witness_complex { landmarks.insert(chosen_landmark); } - int dim = points.begin()->size(); + int dim = boost::size(*std::begin(points)); 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) { + 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; diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 34cbc882..489cdf11 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -28,8 +28,7 @@ #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 <boost/range/size.hpp> #include <gudhi/distance_functions.h> @@ -47,12 +46,13 @@ 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> +// /* +// * \private +// \class Witness_complex +// \brief Constructs the witness complex for the given set of witnesses and landmarks. +// \ingroup witness_complex +// */ +template< class SimplicialComplex> class Witness_complex { private: struct Active_witness { @@ -65,13 +65,12 @@ class Witness_complex { }; private: - typedef typename Simplicial_complex::Simplex_handle Simplex_handle; - typedef typename Simplicial_complex::Vertex_handle Vertex_handle; + typedef typename SimplicialComplex::Simplex_handle Simplex_handle; + typedef typename SimplicialComplex::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; @@ -81,19 +80,19 @@ class Witness_complex { typedef std::list< Vertex_handle > ActiveWitnessList; private: - int nbL; // Number of landmarks - Simplicial_complex& sc; // Simplicial complex + int nbL_; // Number of landmarks + SimplicialComplex& sc_; // Simplicial complex public: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - /** @name Constructor + /* @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}. @@ -109,31 +108,29 @@ class Witness_complex { */ template< typename KNearestNeighbors > Witness_complex(KNearestNeighbors const & knn, - Simplicial_complex & sc_, - int nbL_, - int dim) : nbL(nbL_), sc(sc_) { + int nbL, + int dim, + SimplicialComplex & sc) : nbL_(nbL), sc_(sc) { // Construction of the active witness list - int nbW = knn.size(); + int nbW = boost::size(knn); typeVectorVertex vv; 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) { + for (Vertex_handle 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}; - sc.insert_simplex(vv); + 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; @@ -142,9 +139,9 @@ class Witness_complex { if (ok) { for (int i = 0; i != k + 1; ++i) simplex_vector.push_back(knn[*it][i]); - sc.insert_simplex(simplex_vector, 0.0); + sc_.insert_simplex(simplex_vector); // TODO(SK) Error if not inserted : normally no need here though - it++; + ++it; } else { active_w.erase(it++); // First increase the iterator and then erase the previous element } @@ -156,15 +153,13 @@ class Witness_complex { //@} private: - /** \brief Check if the facets of the k-dimensional simplex witnessed + /* \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 = {}; @@ -173,9 +168,8 @@ class Witness_complex { facet.push_back(knn[witness_id][j]); } } // endfor - if (sc.find(facet) == sc.null_simplex()) + if (sc_.find(facet) == sc_.null_simplex()) return false; - // std::cout << "++++ finished loop safely\n"; } // endfor return true; } @@ -194,27 +188,25 @@ class Witness_complex { } 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. - */ + // /* + // * \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()) { + 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)) + for (Vertex_handle 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) + for (Vertex_handle v : simplex) if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) { has_vertices = false; - // break; } if (has_vertices) { is_witnessed = true; @@ -242,6 +234,30 @@ class Witness_complex { } }; + /** + * \ingroup witness_complex + * \brief Iterative construction of the witness complex. + * \details The witness complex is written in simplicial complex 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. + * + * Procedure 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 <class KNearestNeighbors, class SimplicialComplexForWitness> + void witness_complex(KNearestNeighbors const & knn, + int nbL, + int dim, + SimplicialComplexForWitness & sc) { + Witness_complex<SimplicialComplexForWitness>(knn, nbL, dim, sc); + } + } // namespace witness_complex } // namespace Gudhi diff --git a/src/Witness_complex/test/CMakeLists.txt b/src/Witness_complex/test/CMakeLists.txt index 9422c152..bb55b0f1 100644 --- a/src/Witness_complex/test/CMakeLists.txt +++ b/src/Witness_complex/test/CMakeLists.txt @@ -1,17 +1,13 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIWitnessComplexUT) +project(Witness_complex_tests) 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 ) diff --git a/src/Witness_complex/test/simple_witness_complex.cpp b/src/Witness_complex/test/simple_witness_complex.cpp index 7d44b90c..03df78ee 100644 --- a/src/Witness_complex/test/simple_witness_complex.cpp +++ b/src/Witness_complex/test/simple_witness_complex.cpp @@ -53,7 +53,7 @@ BOOST_AUTO_TEST_CASE(simple_witness_complex) { 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); + WitnessComplex witnessComplex(knn, 7, 7, complex); 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 index cb1639e1..bd3df604 100644 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ b/src/Witness_complex/test/witness_complex_points.cpp @@ -52,13 +52,13 @@ BOOST_AUTO_TEST_CASE(witness_complex_points) { Simplex_tree complex1; Gudhi::witness_complex::landmark_choice_by_random_point(points, 100, knn); assert(!knn.empty()); - WitnessComplex witnessComplex1(knn, complex1, 100, 3); + WitnessComplex witnessComplex1(knn, 100, 3, complex1); BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output)); // Second test: furthest choice knn.clear(); Simplex_tree complex2; Gudhi::witness_complex::landmark_choice_by_furthest_point(points, 100, knn); - WitnessComplex witnessComplex2(knn, complex2, 100, 3); + WitnessComplex witnessComplex2(knn, 100, 3, complex2); BOOST_CHECK(witnessComplex2.is_witness_complex(knn, b_print_output)); } |