diff options
| -rw-r--r-- | src/Doxyfile | 4 | ||||
| -rw-r--r-- | src/Witness_complex/doc/bench_Cy8.png | bin | 0 -> 15254 bytes | |||
| -rw-r--r-- | src/Witness_complex/doc/bench_sphere.png | bin | 0 -> 16614 bytes | |||
| -rw-r--r-- | src/Witness_complex/example/CMakeLists.txt | 26 | ||||
| -rw-r--r-- | src/Witness_complex/example/simple_witness_complex.cpp | 4 | ||||
| -rw-r--r-- | src/Witness_complex/example/witness_complex_from_file.cpp | 90 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h | 12 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h | 16 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex.h | 32 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex_doc.h | 11 |
10 files changed, 98 insertions, 97 deletions
diff --git a/src/Doxyfile b/src/Doxyfile index faa0d3fe..6585e50c 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -834,8 +834,8 @@ EXAMPLE_RECURSIVE = NO IMAGE_PATH = doc/Skeleton_blocker/ \ doc/common/ \ - doc/Contraction/ - + doc/Contraction/ \ + doc/Witness_complex/ # The INPUT_FILTER tag can be used to specify a program that doxygen should # invoke to filter for each input file. Doxygen will invoke the filter program diff --git a/src/Witness_complex/doc/bench_Cy8.png b/src/Witness_complex/doc/bench_Cy8.png Binary files differnew file mode 100644 index 00000000..d9045294 --- /dev/null +++ b/src/Witness_complex/doc/bench_Cy8.png diff --git a/src/Witness_complex/doc/bench_sphere.png b/src/Witness_complex/doc/bench_sphere.png Binary files differnew file mode 100644 index 00000000..ba6bb381 --- /dev/null +++ b/src/Witness_complex/doc/bench_sphere.png diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index 83f9c71c..4f5e33d4 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -6,6 +6,30 @@ project(GUDHIWitnessComplex) add_test(simple_witness_complex ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complex) 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_executable( witness_complex_bench witness_complex_bench.cpp ) + add_test( witness_complex_bench_from_bunny &{CMAKE_CURRENT_BINARY_DIR}/witness_complex_bench ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100) + +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.6.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + include( ${CGAL_USE_FILE} ) + + 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_bench2 witness_complex_bench2.cpp ) + target_link_libraries(witness_complex_bench2 ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Alpha shapes feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Alpha shapes feature. Version 4.6.0 is required.") + endif () +endif() diff --git a/src/Witness_complex/example/simple_witness_complex.cpp b/src/Witness_complex/example/simple_witness_complex.cpp index 6731f135..bcbf2362 100644 --- a/src/Witness_complex/example/simple_witness_complex.cpp +++ b/src/Witness_complex/example/simple_witness_complex.cpp @@ -50,8 +50,8 @@ int main (int argc, char * const argv[]) typeVectorVertex witness10 = {5,0,1,3,6,2,4}; knn.push_back(witness10); typeVectorVertex witness11 = {5,6,1,0,2,3,4}; knn.push_back(witness11); typeVectorVertex witness12 = {1,6,0,5,2,3,4}; knn.push_back(witness12); - WitnessComplex witnessComplex(knn, complex, 7); - if (witnessComplex.is_witness_complex(knn)) + WitnessComplex witnessComplex(knn, complex, 7, 7); + if (witnessComplex.is_witness_complex(knn, true)) std::cout << "Witness complex is good\n"; else std::cout << "Witness complex is bad\n"; diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 70c81528..6add4e0a 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -26,21 +26,18 @@ #include <sys/types.h> #include <sys/stat.h> -//#include <stdlib.h> -//#include "gudhi/graph_simplicial_complex.h" +#include "gudhi/Simplex_tree.h" #include "gudhi/Witness_complex.h" +#include "gudhi/Landmark_choice_by_random_point.h" #include "gudhi/reader_utils.h" -//#include <boost/filesystem.hpp> 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; +typedef Witness_complex< Simplex_tree<> > WitnessComplex; /** * \brief Customized version of read_points @@ -69,15 +66,15 @@ read_points_cust ( std::string file_name , std::vector< std::vector< double > > in_file.close(); } -void write_wl( std::string file_name, std::vector< std::vector <int> > & WL) +/** 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 (file_name, std::ofstream::out); - for (auto w : WL) - { - for (auto l: w) - ofs << l << " "; - ofs << "\n"; - } + std::ofstream ofs(filename, std::ofstream::out); + for (auto entry: data) + ofs << entry.first << ", " << entry.second << "\n"; ofs.close(); } @@ -89,68 +86,33 @@ int main (int argc, char * const argv[]) << " 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"; + + // Construct the Simplex Tree + Simplex_tree<> simplex_tree; + + // Read the point file 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; + std::cout << "Successfully read " << point_vector.size() << " points.\n"; + std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; + + // Choose landmarks 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(), L); - witnessComplex.nearest_landmarks(point_vector,L,WL); + std::vector<std::vector< int > > knn; + Landmark_choice_by_random_point(point_vector, nbL, knn); end = clock(); std::cout << "Landmark choice for " << nbL << " landmarks 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); + + // Compute witness complex start = clock(); - witnessComplex.witness_complex(WL); - // + WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); end = clock(); - std::cout << "Howdy world! The process took " + std::cout << "Witness complex 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/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. |
