From ab2e89665e16be2dcd36e55df8543d4ff5974675 Mon Sep 17 00:00:00 2001 From: mcarrier Date: Mon, 30 Jan 2017 16:33:22 +0000 Subject: git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Nerve_GIC@2032 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e8901f1be678dbc71b8e6e7b5666cc475b573b1a --- src/Nerve_GIC/example/CMakeLists.txt | 8 +++ src/Nerve_GIC/example/simple_GIC.cpp | 36 ++-------- src/Nerve_GIC/include/gudhi/GIC.h | 127 +++++++++++++++++++++++++++-------- 3 files changed, 115 insertions(+), 56 deletions(-) create mode 100644 src/Nerve_GIC/example/CMakeLists.txt diff --git a/src/Nerve_GIC/example/CMakeLists.txt b/src/Nerve_GIC/example/CMakeLists.txt new file mode 100644 index 00000000..e4debf2d --- /dev/null +++ b/src/Nerve_GIC/example/CMakeLists.txt @@ -0,0 +1,8 @@ +cmake_minimum_required(VERSION 2.6) +project(Nerve_GIC_examples) + +add_executable ( GIC simple_GIC.cpp ) +target_link_libraries(GIC ${Boost_SYSTEM_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(GIC ${TBB_LIBRARIES}) +endif() \ No newline at end of file diff --git a/src/Nerve_GIC/example/simple_GIC.cpp b/src/Nerve_GIC/example/simple_GIC.cpp index 33ebfcbb..d9297d04 100644 --- a/src/Nerve_GIC/example/simple_GIC.cpp +++ b/src/Nerve_GIC/example/simple_GIC.cpp @@ -1,18 +1,9 @@ -#include -// to construct Rips_complex from a OFF file of points -#include -#include -#include #include -#include -#include -#include - void usage(int nbArgs, char * const progName) { std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; - std::cerr << "Usage: " << progName << " filename.off threshold dim_max [ouput_file.txt]\n"; - std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0\n"; + std::cerr << "Usage: " << progName << " filename.off threshold cover [ouput_file.txt]\n"; + std::cerr << " i.e.: " << progName << " ../../data/points/test.off 1.5 test_cov \n"; exit(-1); // ----- >> } @@ -21,30 +12,20 @@ int main(int argc, char **argv) { std::string off_file_name(argv[1]); double threshold = atof(argv[2]); - int dim_max = atoi(argv[3]); + std::string cover_file_name(argv[3]); // Type definitions - using Point = std::vector; - using Simplex_tree = Gudhi::Simplex_tree<>; - using Filtration_value = Simplex_tree::Filtration_value; - using Rips_complex = Gudhi::rips_complex::Rips_complex; using Graph_t = boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS,\ boost::property < vertex_filtration_t, Filtration_value >,\ boost::property < edge_filtration_t, Filtration_value > >; - using Cover = std::map; // ---------------------------------------------------------------------------- // Init of a graph induced complex from an OFF file // ---------------------------------------------------------------------------- - Gudhi::Points_off_reader off_reader(off_file_name); - Rips_complex rips_complex_from_points(off_reader.get_point_cloud(), threshold, Euclidean_distance()); - Simplex_tree st; - rips_complex_from_points.create_complex(st, 1); - Cover C; - Gudhi::graph_induced_complex::Graph_induced_complex GIC(st,C,dim_max); - Simplex_tree stree; - GIC.create_complex(stree); + Gudhi::graph_induced_complex::Graph_induced_complex GIC; + GIC.set_graph_simplex_tree(threshold, off_file_name); GIC.set_cover(cover_file_name); GIC.find_simplices(); + Simplex_tree stree; GIC.create_complex(stree); std::streambuf* streambufffer; std::ofstream ouput_file_stream; @@ -65,14 +46,11 @@ int main(int argc, char **argv) { " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - output_stream << "Iterator on graph induced complex simplices in the filtration order, with [filtration value]:" << - std::endl; + output_stream << "Iterator on graph induced complex simplices" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { - output_stream << " ( "; for (auto vertex : stree.simplex_vertex_range(f_simplex)) { output_stream << vertex << " "; } - output_stream << ") -> " << "[" << stree.filtration(f_simplex) << "] "; output_stream << std::endl; } diff --git a/src/Nerve_GIC/include/gudhi/GIC.h b/src/Nerve_GIC/include/gudhi/GIC.h index d8046611..91f0327e 100644 --- a/src/Nerve_GIC/include/gudhi/GIC.h +++ b/src/Nerve_GIC/include/gudhi/GIC.h @@ -27,6 +27,9 @@ #include #include #include +#include +#include +#include #include @@ -36,7 +39,23 @@ #include #include // for numeric_limits #include // for pair<> - +#include // for greater<> +#include +#include +#include // for std::max +#include // for std::uint32_t + +using Simplex_tree = Gudhi::Simplex_tree<>; +using Filtration_value = Simplex_tree::Filtration_value; +using Rips_complex = Gudhi::rips_complex::Rips_complex; +using Point = std::vector; + +bool simplex_comp(const std::vector& s1, const std::vector& s2){ + if(s1.size() == s2.size()){ + return s1[0] < s2[0]; + } + else return s1.size() < s2.size(); +} namespace Gudhi { @@ -62,20 +81,59 @@ class Graph_induced_complex { private: std::vector > cliques; + private: + std::map > Cov; + + private: + int maximal_dim; + + private: + Simplex_tree<> st; + + public: + void set_cover(const std::string& cover_file_name){ + int vertex_id = 0; Cover_t cov; std::vector cov_elts, cov_number; + std::ifstream input(cover_file_name); std::string line; + while(std::getline(input,line)){ + cov_elts.clear(); std::stringstream stream(line); + while(stream >> cov){cov_elts.push_back(cov); cov_number.push_back(cov);} + Cov.insert(std::pair >(vertex_id, cov_elts)); vertex_id++; + } + std::vector::iterator it; + std::sort(cov_number.begin(),cov_number.end()); it = std::unique(cov_number.begin(),cov_number.end()); + cov_number.resize(std::distance(cov_number.begin(),it)); maximal_dim = cov_number.size(); + return; + } + + public: + void set_graph_simplex_tree(const double& threshold, const std::string& off_file_name){ + Points_off_reader off_reader(off_file_name); + Rips_complex rips_complex_from_points(off_reader.get_point_cloud(), threshold, Euclidean_distance()); + rips_complex_from_points.create_complex(st, 1); + return;} + public: template void create_complex(SimplicialComplexForGIC & complex) { - size_t sz = cliques.size(); - for(int i = 0; i < sz; i++) complex.insert_simplex_and_subfaces(cliques[i]); + size_t sz = cliques.size(); int dimension = 0; + for(int i = 0; i < sz; i++){ + complex.insert_simplex_and_subfaces(cliques[i]); + if(dimension < cliques[i].size()-1) dimension = cliques[i].size()-1; + } + complex.set_dimension(dimension); } public: - void find_all_simplices(std::vector > & cliques, const std::vector > & cover_elts, int & token, std::vector & simplex_tmp){ + void find_all_simplices(std::vector > & cliques, const std::vector > & cover_elts,\ + int & token, std::vector & simplex_tmp){ int num_nodes = cover_elts.size(); if(token == num_nodes-1){ int num_clus = cover_elts[token].size(); for(int i = 0; i < num_clus; i++){ std::vector simplex = simplex_tmp; simplex.push_back(cover_elts[token][i]); + std::vector::iterator it; + std::sort(simplex.begin(),simplex.end()); it = std::unique(simplex.begin(),simplex.end()); + simplex.resize(std::distance(simplex.begin(),it)); cliques.push_back(simplex); } } @@ -89,34 +147,49 @@ class Graph_induced_complex { } public: - /** \brief Graph_induced_complex constructor from a graph and a cover. - * - * @param[in] graph built on point cloud. - * @param[in] cover of points. - * - * \tparam Cover must be a range for which `std::begin` and `std::end` return input iterators on a - * `Cover_value`. - * - */ - template - Graph_induced_complex(Simplex_tree & st, const Cover& C, const int& max_dim) { - - // Construct the Simplex Tree corresponding to the graph - st.expansion(max_dim); - - // Find complexes of GIC - cliques.clear(); + void find_simplices() { + + // Find IDs of edges to remove + std::vector simplex_to_remove; int simplex_id = 0; for (auto simplex : st.complex_simplex_range()) { - std::vector > cover_elts; - for (auto vertex : st.simplex_vertex_range(simplex)) { - cover_elts.push_back(C[vertex]); - find_all_simplices(cliques,cover_elts); + if(st.dimension(simplex) == 1){ + std::vector > comp; + for(auto vertex : st.simplex_vertex_range(simplex)) comp.push_back(Cov[vertex]); + if(comp[0].size() == 1 && comp[1].size() == 1 && comp[0][0] == comp[1][0]) simplex_to_remove.push_back(simplex_id); + } + simplex_id++; + } + + // Remove edges + int current_id = 0; auto simplex_tmp = st.complex_simplex_range().begin(); + if(simplex_to_remove[current_id] == 0){st.remove_maximal_simplex(*simplex_tmp); current_id++;} + auto simplex = st.complex_simplex_range().begin(); + for(int i = 1; i < --simplex_id; i++){ + int j = i+1; auto simplex_tmp = simplex; simplex_tmp++; + if(j == simplex_to_remove[current_id]){st.remove_maximal_simplex(*simplex_tmp); current_id++; i++;} + simplex++; + } + + // Build the Simplex Tree corresponding to the graph + st.expansion(maximal_dim); + + // Find simplices of GIC + cliques.clear(); + for (auto simplex : st.complex_simplex_range()) { + std::vector > cover_elts; int token = 0; std::vector sim; + for (auto vertex : st.simplex_vertex_range(simplex)) cover_elts.push_back(Cov[vertex]); + find_all_simplices(cliques,cover_elts,token,sim); } + std::vector >::iterator it; + std::sort(cliques.begin(),cliques.end()); it = std::unique(cliques.begin(),cliques.end()); + cliques.resize(std::distance(cliques.begin(),it)); } }; -} +} // namespace graph_induced_complex -} +} // namespace Gudhi + +#endif // GIC_H_ -- cgit v1.2.3