From a99d289c4f37766bc262baa980284fa1a9816d42 Mon Sep 17 00:00:00 2001 From: skachano Date: Mon, 27 Apr 2015 16:23:54 +0000 Subject: Added the file for knn landmarks (no CGAL include yet). New algorithm for landmark selection: now 10 times faster! git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/witness@580 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9de270bd67ac33fd1079de7692dd8974441db606 --- src/Witness_complex/example/CMakeLists.txt | 10 +- .../example/witness_complex_from_file.cpp | 4 +- .../example/witness_complex_from_off.cpp | 4 +- .../example/witness_complex_knn_landmarks.cpp | 161 +++++++++++++++++++ .../include/gudhi/Witness_complex.h | 176 +++++++++++++++------ 5 files changed, 303 insertions(+), 52 deletions(-) create mode 100644 src/Witness_complex/example/witness_complex_knn_landmarks.cpp (limited to 'src/Witness_complex') diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index 14d23551..fa594de7 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -14,9 +14,9 @@ project(GUDHIWitnessComplex) add_executable ( simple_witness_complex simple_witness_complex.cpp ) add_test(simple_witness_complex ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complex) - #add_executable( witness_complex_from_file witness_complex_from_file.cpp ) + 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_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_from_off witness_complex_from_off.cpp ) @@ -35,7 +35,7 @@ if(GMP_FOUND AND CGAL_FOUND) INCLUDE_DIRECTORIES(${EIGEN3_INCLUDE_DIRS}) INCLUDE_DIRECTORIES(${GMP_INCLUDE_DIR}) INCLUDE_DIRECTORIES(${CGAL_INCLUDE_DIRS}) - add_executable (witness_complex_from_file witness_complex_from_file.cpp ) - target_link_libraries(witness_complex_from_file ${GMP_LIBRARIES} ${EIGEN3_LIBRARIES} ${CGAL_LIBRARY}) - add_test(witness_complex_from_file ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100) + add_executable (witness_complex_knn_landmarks witness_complex_knn_landmarks.cpp ) + target_link_libraries(witness_complex_knn_landmarks ${EIGEN3_LIBRARIES} ${CGAL_LIBRARY}) + add_test(witness_complex_knn_landmarks ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_knn_landmarks ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100) endif() diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index cf09899b..b842574b 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -109,9 +109,11 @@ int main (int argc, char * const argv[]) witnessComplex.setNbL(nbL); // witnessComplex.witness_complex_from_points(point_vector); std::vector > WL; + std::set L; 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(), WL); + witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), L); + witnessComplex.nearest_landmarks(point_vector,L,WL); end = clock(); std::cout << "Landmark choice took " << (double)(end-start)/CLOCKS_PER_SEC << " s. \n"; diff --git a/src/Witness_complex/example/witness_complex_from_off.cpp b/src/Witness_complex/example/witness_complex_from_off.cpp index 04d4e601..948f09a8 100644 --- a/src/Witness_complex/example/witness_complex_from_off.cpp +++ b/src/Witness_complex/example/witness_complex_from_off.cpp @@ -148,9 +148,11 @@ int main (int argc, char * const argv[]) witnessComplex.setNbL(nbL); // witnessComplex.witness_complex_from_points(point_vector); std::vector > WL; + std::set L; 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(), WL); + witnessComplex.landmark_choice_by_random_points(point_vector, point_vector.size(), L); + witnessComplex.nearest_landmarks(point_vector,L,WL); end = clock(); std::cout << "Landmark choice took " << (double)(end-start)/CLOCKS_PER_SEC << " s. \n"; diff --git a/src/Witness_complex/example/witness_complex_knn_landmarks.cpp b/src/Witness_complex/example/witness_complex_knn_landmarks.cpp new file mode 100644 index 00000000..2003f218 --- /dev/null +++ b/src/Witness_complex/example/witness_complex_knn_landmarks.cpp @@ -0,0 +1,161 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2015 INRIA Sophia Antipolis-Méditerranée (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#include +#include +#include + +#include +#include +//#include + +//#include "gudhi/graph_simplicial_complex.h" +#include "gudhi/Witness_complex.h" +#include "gudhi/reader_utils.h" +//#include + +//#include +//#include +#include + +using namespace Gudhi; +//using namespace boost::filesystem; + +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::vector< std::vector > Point_Vector; +//typedef std::pair typeSimplex; +//typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; + + +/** + * \brief Customized version of read_points + * which takes into account a possible nbP first line + * + */ +inline void +read_points_cust ( std::string file_name , std::vector< std::vector< double > > & points) +{ + std::ifstream in_file (file_name.c_str(),std::ios::in); + if(!in_file.is_open()) + { + std::cerr << "Unable to open file " << file_name << std::endl; + return; + } + std::string line; + double x; + while( getline ( in_file , line ) ) + { + std::vector< double > point; + std::istringstream iss( line ); + while(iss >> x) { point.push_back(x); } + if (point.size() != 1) + points.push_back(point); + } + in_file.close(); +} + +void write_wl( std::string file_name, std::vector< std::vector > & WL) +{ + std::ofstream ofs (file_name, std::ofstream::out); + for (auto w : WL) + { + for (auto l: w) + ofs << l << " "; + ofs << "\n"; + } + ofs.close(); +} + +int main (int argc, char * const argv[]) +{ + if (argc != 3) + { + std::cerr << "Usage: " << argv[0] + << " 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"; + 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 > WL; + std::set L; + int nbP = point_vector.size(); + start = clock(); + //witnessComplex.landmark_choice_by_furthest_points(point_vector, point_vector.size(), WL); + witnessComplex.landmark_choice_by_random_points(point_vector, nbP, L); + witnessComplex.nearest_landmarks(point_vector,L,WL); + end = clock(); + std::cout << "Landmark choice 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); + start = clock(); + witnessComplex.witness_complex(WL); + // + end = clock(); + std::cout << "Howdy world! The process 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/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 3c030c45..2ccaa416 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -32,7 +32,8 @@ #include "gudhi/Simplex_tree.h" #include #include -#include +#include +#include #include #include #include @@ -40,9 +41,9 @@ // Needed for nearest neighbours //#include -#include -#include -#include +//#include +//#include +//#include // Needed for the adjacency graph in bad link search #include @@ -233,12 +234,12 @@ namespace Gudhi { * FURTHEST_POINT_STRATEGY and RANDOM_POINT_STRATEGY and * density must be set to the right value for DENSITY_STRATEGY */ - void witness_complex_from_points(Point_Vector point_vector) - { - std::vector > WL; - landmark_choice_by_random_points(point_vector, point_vector.size(), WL); - witness_complex(WL); - } + // void witness_complex_from_points(Point_Vector point_vector) + // { + // std::vector > WL; + // landmark_choice_by_random_points(point_vector, point_vector.size(), WL); + // witness_complex(WL); + // } private: @@ -468,75 +469,160 @@ private: * */ - template - void landmark_choice_by_random_points(Point_Vector &W, int nbP, KNearestNeighbours &WL) + // template + // void landmark_choice_by_random_points(Point_Vector &W, int nbP, KNearestNeighbours &WL) + // { + // std::cout << "Enter landmark_choice_by_random_points "<< std::endl; + // //std::cout << "W="; print_vvector(W); + // std::unordered_set< int > chosen_landmarks; // landmark set + + // Point_Vector wit_land_dist(nbP,std::vector()); // distance matrix witness x landmarks + + // WL = KNearestNeighbours(nbP,std::vector()); + // int current_number_of_landmarks=0; // counter for landmarks + + // srand(24660); + // int chosen_landmark = rand()%nbP; + // double curr_dist; + + // //int j; + // //int temp_swap_int; + // //double temp_swap_double; + + + // for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) + // { + // while (chosen_landmarks.find(chosen_landmark) != chosen_landmarks.end()) + // { + // srand((int)clock()); + // chosen_landmark = rand()% nbP; + // //std::cout << chosen_landmark << "\n"; + // } + // chosen_landmarks.insert(chosen_landmark); + // //std::cout << "**********Entered loop with current number of landmarks = " << current_number_of_landmarks << std::endl; + // //std::cout << "WL="; print_vvector(WL); + // //std::cout << "WLD="; print_vvector(wit_land_dist); + // //std::cout << "landmarks="; print_vector(chosen_landmarks); std::cout << std::endl; + // for (auto v: WL) + // v.push_back(current_number_of_landmarks); + // for (int i = 0; i < nbP; ++i) + // { + // // iteration on points in W. update of distance vectors + + // //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl; + // //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl; + // curr_dist = euclidean_distance(W[i],W[chosen_landmark]); + // //std::cout << "The problem is not in distance function\n"; + // wit_land_dist[i].push_back(curr_dist); + // WL[i].push_back(current_number_of_landmarks); + // //std::cout << "Push't back\n"; + // //j = current_number_of_landmarks; + // //std::cout << "First half complete\n"; + // //std::cout << "result WL="; print_vvector(WL); + // //std::cout << "result WLD="; print_vvector(wit_land_dist); + // //std::cout << "End loop\n"; + // } + // } + // for (int i = 0; i < nbP; i++) + // { + // sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];}); + // } + // //std::cout << endl; + // } + + /** \brief Landmark choice strategy by taking random vertices for landmarks. + * + */ + + // template + void landmark_choice_by_random_points(Point_Vector &W, int nbP, std::set &L) { std::cout << "Enter landmark_choice_by_random_points "<< std::endl; //std::cout << "W="; print_vvector(W); - std::unordered_set< int > chosen_landmarks; // landmark set + //std::unordered_set< int > chosen_landmarks; // landmark set Point_Vector wit_land_dist(nbP,std::vector()); // distance matrix witness x landmarks - WL = KNearestNeighbours(nbP,std::vector()); + //WL = KNearestNeighbours(nbP,std::vector()); int current_number_of_landmarks=0; // counter for landmarks srand(24660); int chosen_landmark = rand()%nbP; - double curr_dist; - + //double curr_dist; //int j; //int temp_swap_int; - //double temp_swap_double; - - + //double temp_swap_double; for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) { - while (chosen_landmarks.find(chosen_landmark) != chosen_landmarks.end()) + while (L.find(chosen_landmark) != L.end()) { srand((int)clock()); chosen_landmark = rand()% nbP; //std::cout << chosen_landmark << "\n"; } - chosen_landmarks.insert(chosen_landmark); + L.insert(chosen_landmark); //std::cout << "**********Entered loop with current number of landmarks = " << current_number_of_landmarks << std::endl; //std::cout << "WL="; print_vvector(WL); //std::cout << "WLD="; print_vvector(wit_land_dist); //std::cout << "landmarks="; print_vector(chosen_landmarks); std::cout << std::endl; - for (auto v: WL) - v.push_back(current_number_of_landmarks); - for (int i = 0; i < nbP; ++i) - { - // iteration on points in W. update of distance vectors + // for (auto v: WL) + // v.push_back(current_number_of_landmarks); + // for (int i = 0; i < nbP; ++i) + // { + // // iteration on points in W. update of distance vectors - //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl; - //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl; - curr_dist = euclidean_distance(W[i],W[chosen_landmark]); - //std::cout << "The problem is not in distance function\n"; - wit_land_dist[i].push_back(curr_dist); - WL[i].push_back(current_number_of_landmarks); - //std::cout << "Push't back\n"; - //j = current_number_of_landmarks; - //std::cout << "First half complete\n"; - //std::cout << "result WL="; print_vvector(WL); - //std::cout << "result WLD="; print_vvector(wit_land_dist); - //std::cout << "End loop\n"; - } - } - for (int i = 0; i < nbP; i++) - { - sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];}); + // //std::cout << "In the loop with i=" << i << " and landmark=" << chosen_landmarks[current_number_of_landmarks] << std::endl; + // //std::cout << "W[i]="; print_vector(W[i]); std::cout << " W[landmark]="; print_vector(W[chosen_landmarks[current_number_of_landmarks]]); std::cout << std::endl; + // curr_dist = euclidean_distance(W[i],W[chosen_landmark]); + // //std::cout << "The problem is not in distance function\n"; + // wit_land_dist[i].push_back(curr_dist); + // WL[i].push_back(current_number_of_landmarks); + // //std::cout << "Push't back\n"; + // //j = current_number_of_landmarks; + // //std::cout << "First half complete\n"; + // //std::cout << "result WL="; print_vvector(WL); + // //std::cout << "result WLD="; print_vvector(wit_land_dist); + // //std::cout << "End loop\n"; + // } } + // for (int i = 0; i < nbP; i++) + // { + // sort(WL[i].begin(), WL[i].end(), [&](int j1, int j2){return wit_land_dist[i][j1] < wit_land_dist[i][j2];}); + // } //std::cout << endl; } + /** \brief Construct the matrix |W|x(D+1) of D+1 closest landmarks * where W is the set of witnesses and D is the ambient dimension */ template - void nearest_landmarks(Point_Vector &W, std::unordered_set &L, KNearestNeighbours &WL) + void nearest_landmarks(Point_Vector &W, std::set &L, KNearestNeighbours &WL) { int D = W[0].size(); - + int nbP = W.size(); + WL = KNearestNeighbours(nbP,std::vector()); + typedef std::pair dist_i; + typedef bool (*comp)(dist_i,dist_i); + for (int W_i = 0; W_i < nbP; W_i++) + { + //std::cout << "<<<<<<<<<<<<<<" << W_i <<"\n"; + std::priority_queue, comp> l_heap([&](dist_i j1, dist_i j2){return j1.first > j2.first;}); + std::set::iterator L_it; + int L_i; + for (L_it = L.begin(), L_i=0; L_it != L.end(); L_it++, L_i++) + { + dist_i dist = std::make_pair(euclidean_distance(W[W_i],W[*L_it]), L_i); + l_heap.push(dist); + } + for (int i = 0; i < D+1; i++) + { + dist_i dist = l_heap.top(); + WL[W_i].push_back(dist.second); + //std::cout << dist.first << " " << dist.second << std::endl; + l_heap.pop(); + } + } } /** \brief Search and output links around vertices that are not pseudomanifolds -- cgit v1.2.3