From 9e1a4e80bc3f2cffc965dc3f5194ea308ca9afab Mon Sep 17 00:00:00 2001 From: mcarrier Date: Wed, 10 May 2017 15:32:55 +0000 Subject: git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Nerve_GIC@2411 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 92552c44d0a2369735bd29495c3504f53010a06c --- src/Nerve_GIC/doc/COPYRIGHT | 19 ++++++ src/Nerve_GIC/doc/Intro_graph_induced_complex.h | 25 ++++++-- src/Nerve_GIC/doc/gic_complex.png | Bin 0 -> 56761 bytes src/Nerve_GIC/doc/nerve.png | Bin 0 -> 45129 bytes src/Nerve_GIC/include/gudhi/GIC.h | 70 +++++++++++++++------ src/Nerve_GIC/test/data/cloud | 5 ++ src/Nerve_GIC/test/data/cover | 3 + src/Nerve_GIC/test/data/graph | 3 + src/Nerve_GIC/test/test.cpp | 79 ++++++++++++++++++++++++ 9 files changed, 181 insertions(+), 23 deletions(-) create mode 100644 src/Nerve_GIC/doc/COPYRIGHT create mode 100644 src/Nerve_GIC/doc/gic_complex.png create mode 100644 src/Nerve_GIC/doc/nerve.png create mode 100644 src/Nerve_GIC/test/data/cloud create mode 100644 src/Nerve_GIC/test/data/cover create mode 100644 src/Nerve_GIC/test/data/graph create mode 100644 src/Nerve_GIC/test/test.cpp (limited to 'src/Nerve_GIC') diff --git a/src/Nerve_GIC/doc/COPYRIGHT b/src/Nerve_GIC/doc/COPYRIGHT new file mode 100644 index 00000000..0c36a526 --- /dev/null +++ b/src/Nerve_GIC/doc/COPYRIGHT @@ -0,0 +1,19 @@ +The files of this directory are part of the Gudhi Library. The Gudhi library +(Geometric Understanding in Higher Dimensions) is a generic C++ library for +computational topology. + +Author(s): Mathieu Carrière + +Copyright (C) 2017 INRIA + +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 . diff --git a/src/Nerve_GIC/doc/Intro_graph_induced_complex.h b/src/Nerve_GIC/doc/Intro_graph_induced_complex.h index 8c31b262..f30d51a4 100644 --- a/src/Nerve_GIC/doc/Intro_graph_induced_complex.h +++ b/src/Nerve_GIC/doc/Intro_graph_induced_complex.h @@ -33,23 +33,31 @@ namespace graph_induced_complex { * * @{ * + * \section covers Covers + * + * Nerves and Graph Induced Complexes require a cover C of the input point cloud P, + * that is a set of subsets of P whose union is P itself. + * Very often, this cover is obtained from the preimage of a family of intervals covering + * the image of some scalar-valued function f defined on P. This family is parameterized + * by its resolution, which can be either the number or the length of the intervals, + * and its gain, which is the overlap percentage between consecutive intervals (ordered by their first values). + * * \section nerves Nerves * * \subsection nervedefinition Nerve definition * - * Assume you are given a cover C of your point cloud P, that is a set of subsets of P - * whose union is P itself. Then, the Nerve of this cover + * Assume you are given a cover C of your point cloud P. Then, the Nerve of this cover * is the simplicial complex that has one k-simplex per k-fold intersection of cover elements. * See also Wikipedia . * + * \image html "nerve.png" "Nerve of a double torus" + * * \subsection nerveexample Example * * This example builds the Nerve of a point cloud sampled on a 3D human shape (human.off). * The cover C comes from the preimages of intervals (10 intervals with gain 0.3) * covering the height function (coordinate 2), * which are then refined into their connected components using the triangulation of the .OFF file. - * All intervals have the resolution (either the length or the number of the intervals) - * and gain (overlap percentage). * * \include Nerve_GIC/Nerve.cpp * @@ -62,6 +70,13 @@ namespace graph_induced_complex { * * \include Nerve_GIC/Nerve.txt * + * The first three lines are requirements for visualization with Kepler-Mapper. + * The fourth line contains the number of vertices nv and edges ne of the Nerve. + * The next nv lines represent the vertices. Each line contains the vertex ID, + * the number of data points it contains, and their average color function value. + * Finally, the next ne lines represent the edges, characterized by the ID of their vertices. + * + * * \section gic Graph Induced Complexes (GIC) * * \subsection gicdefinition GIC definition @@ -73,6 +88,8 @@ namespace graph_induced_complex { * See this article * for more details. * + * \image html "gic_complex.png" "GIC of a point cloud." + * * \subsection gicexample Example * * This example builds the GIC of a point cloud sampled on a 3D human shape (human.off). diff --git a/src/Nerve_GIC/doc/gic_complex.png b/src/Nerve_GIC/doc/gic_complex.png new file mode 100644 index 00000000..fb4b20ad Binary files /dev/null and b/src/Nerve_GIC/doc/gic_complex.png differ diff --git a/src/Nerve_GIC/doc/nerve.png b/src/Nerve_GIC/doc/nerve.png new file mode 100644 index 00000000..b66da4a4 Binary files /dev/null and b/src/Nerve_GIC/doc/nerve.png differ diff --git a/src/Nerve_GIC/include/gudhi/GIC.h b/src/Nerve_GIC/include/gudhi/GIC.h index c373b25c..e9b7a1f1 100644 --- a/src/Nerve_GIC/include/gudhi/GIC.h +++ b/src/Nerve_GIC/include/gudhi/GIC.h @@ -162,10 +162,21 @@ class Graph_induced_complex { * */ void set_graph_from_file(const std::string& graph_file_name){ - int neighb; int vid; std::ifstream input(graph_file_name); std::string line; std::vector edge(2); + int neighb; int vid; std::ifstream input(graph_file_name); std::string line; std::vector edge(2); int n = 0; while(std::getline(input,line)){ std::stringstream stream(line); stream >> vid; edge[0] = vid; while(stream >> neighb){edge[1] = neighb; st.insert_simplex_and_subfaces(edge);} + n++; + } + + std::vector empty; + for(int i = 0; i < n; i++) adjacency_matrix.insert(std::pair >(i,empty)); + for (auto simplex : st.complex_simplex_range()) { + if(st.dimension(simplex) == 1){ + std::vector vertices; + for(auto vertex : st.simplex_vertex_range(simplex)) vertices.push_back(vertex); + adjacency_matrix[vertices[0]].push_back(vertices[1]); adjacency_matrix[vertices[1]].push_back(vertices[0]); + } } } @@ -191,6 +202,16 @@ class Graph_induced_complex { } i++; } + + std::vector empty; + for(int i = 0; i < numpts; i++) adjacency_matrix.insert(std::pair >(i,empty)); + for (auto simplex : st.complex_simplex_range()) { + if(st.dimension(simplex) == 1){ + std::vector vertices; + for(auto vertex : st.simplex_vertex_range(simplex)) vertices.push_back(vertex); + adjacency_matrix[vertices[0]].push_back(vertices[1]); adjacency_matrix[vertices[1]].push_back(vertices[0]); + } + } } public: // Set graph from Rips complex. @@ -204,6 +225,17 @@ class Graph_induced_complex { 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); data_dimension = off_reader.get_point_cloud()[0].size(); + + std::vector empty; int n = off_reader.get_point_cloud().size(); + for(int i = 0; i < n; i++) adjacency_matrix.insert(std::pair >(i,empty)); + for (auto simplex : st.complex_simplex_range()) { + if(st.dimension(simplex) == 1){ + std::vector vertices; + for(auto vertex : st.simplex_vertex_range(simplex)) vertices.push_back(vertex); + adjacency_matrix[vertices[0]].push_back(vertices[1]); adjacency_matrix[vertices[1]].push_back(vertices[0]); + } + } + } public: // Automatic tuning of Rips complex. @@ -277,6 +309,16 @@ class Graph_induced_complex { Rips_complex rips_complex_from_points(off_reader.get_point_cloud(), delta, Euclidean_distance()); rips_complex_from_points.create_complex(st, 1); + std::vector empty; + for(int i = 0; i < n; i++) adjacency_matrix.insert(std::pair >(i,empty)); + for (auto simplex : st.complex_simplex_range()) { + if(st.dimension(simplex) == 1){ + std::vector vertices; + for(auto vertex : st.simplex_vertex_range(simplex)) vertices.push_back(vertex); + adjacency_matrix[vertices[0]].push_back(vertices[1]); adjacency_matrix[vertices[1]].push_back(vertices[0]); + } + } + } @@ -337,7 +379,7 @@ class Graph_induced_complex { 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);} + while(stream >> cov){cov_elts.push_back(cov); cov_number.push_back(cov); cover_fct.insert(std::pair(cov,cov));} cover.insert(std::pair >(vertex_id, cov_elts)); vertex_id++; } std::vector::iterator it; @@ -442,17 +484,6 @@ class Graph_induced_complex { std::vector points(num_pts); for(int i = 0; i < num_pts; i++) points[i] = i; std::sort(points.begin(),points.end(),functional_comp); - // Build adjacency matrix - std::vector empty; - for(int i = 0; i < num_pts; i++) adjacency_matrix.insert(std::pair >(points[i],empty)); - for (auto simplex : st.complex_simplex_range()) { - if(st.dimension(simplex) == 1){ - std::vector vertices; - for(auto vertex : st.simplex_vertex_range(simplex)) vertices.push_back(vertex); - adjacency_matrix[vertices[0]].push_back(vertices[1]); adjacency_matrix[vertices[1]].push_back(vertices[0]); - } - } - int id = 0; int pos = 0; double min_prop_int; double max_prop_int; for(int i = 0; i < res; i++){ @@ -627,7 +658,6 @@ class Graph_induced_complex { public: /** \brief Creates the simplicial complex. * - * \tparam SimplicialComplexForGIC must meet `SimplicialComplexForRips` concept. * @param[in] complex SimplicialComplexForGIC to be created. * */ @@ -685,14 +715,16 @@ class Graph_induced_complex { } // Remove edges - int current_id = 1; - auto simplex = st.complex_simplex_range().begin(); int num_rem = 0; - for(int i = 0; i < simplex_id-1; i++){ + if(simplex_to_remove.size() > 1){ + int current_id = 1; + auto simplex = st.complex_simplex_range().begin(); int num_rem = 0; + for(int i = 0; i < simplex_id-1; 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++; num_rem++;} else simplex++; - } simplex = st.complex_simplex_range().begin(); - for(int i = 0; i < simplex_to_remove[0]; i++) simplex++; st.remove_maximal_simplex(*simplex); + } simplex = st.complex_simplex_range().begin(); + for(int i = 0; i < simplex_to_remove[0]; i++) simplex++; st.remove_maximal_simplex(*simplex); + } // Build the Simplex Tree corresponding to the graph st.expansion(maximal_dim); diff --git a/src/Nerve_GIC/test/data/cloud b/src/Nerve_GIC/test/data/cloud new file mode 100644 index 00000000..82fc5c79 --- /dev/null +++ b/src/Nerve_GIC/test/data/cloud @@ -0,0 +1,5 @@ +OFF +3 0 0 +0 0 0 +2 1 0 +4 0 0 \ No newline at end of file diff --git a/src/Nerve_GIC/test/data/cover b/src/Nerve_GIC/test/data/cover new file mode 100644 index 00000000..5f5fbe75 --- /dev/null +++ b/src/Nerve_GIC/test/data/cover @@ -0,0 +1,3 @@ +1 +2 +3 \ No newline at end of file diff --git a/src/Nerve_GIC/test/data/graph b/src/Nerve_GIC/test/data/graph new file mode 100644 index 00000000..37142800 --- /dev/null +++ b/src/Nerve_GIC/test/data/graph @@ -0,0 +1,3 @@ +0 1 +0 2 +1 2 \ No newline at end of file diff --git a/src/Nerve_GIC/test/test.cpp b/src/Nerve_GIC/test/test.cpp new file mode 100644 index 00000000..20e5ee4d --- /dev/null +++ b/src/Nerve_GIC/test/test.cpp @@ -0,0 +1,79 @@ +/* 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): Mathieu Carrière + * + * Copyright (C) 2017 INRIA Saclay (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 . + */ + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "graph_induced_complex" + +#include +#include // float comparison +#include +#include +#include +#include // std::max +#include +#include +#include + +bool are_almost_the_same(float a, float b) { + return std::fabs(a - b) < std::numeric_limits::epsilon(); +} + +BOOST_AUTO_TEST_CASE(check_nerve) { + + Gudhi::graph_induced_complex::Graph_induced_complex GIC; + std::string graph_file_name("data/graph"); GIC.set_graph_from_file(graph_file_name); + std::string cover_file_name("data/cover"); GIC.set_cover_from_file(cover_file_name); + std::string cloud_file_name("data/cloud"); GIC.set_color_from_file(cloud_file_name); + GIC.find_Nerve_simplices(); Simplex_tree stree; GIC.create_complex(stree); + + BOOST_CHECK(stree.num_vertices() == 3); + BOOST_CHECK((stree.num_simplices()-stree.num_vertices()) == 0); + BOOST_CHECK(stree.dimension() == 0); +} + +BOOST_AUTO_TEST_CASE(check_GICMAP) { + + Gudhi::graph_induced_complex::Graph_induced_complex GIC; GIC.set_verbose(1); + std::string graph_file_name("data/graph"); GIC.set_graph_from_file(graph_file_name); + std::string cover_file_name("data/cover"); GIC.set_cover_from_file(cover_file_name); + std::string cloud_file_name("data/cloud"); GIC.set_color_from_file(cloud_file_name); + GIC.find_GICMAP_simplices_with_functional_minimal_cover(); Simplex_tree stree; GIC.create_complex(stree); + + BOOST_CHECK(stree.num_vertices() == 3); + BOOST_CHECK((stree.num_simplices()-stree.num_vertices()) == 2); + BOOST_CHECK(stree.dimension() == 1); +} + +BOOST_AUTO_TEST_CASE(check_GIC) { + + Gudhi::graph_induced_complex::Graph_induced_complex GIC; + std::string graph_file_name("data/graph"); GIC.set_graph_from_file(graph_file_name); + std::string cover_file_name("data/cover"); GIC.set_cover_from_file(cover_file_name); + std::string cloud_file_name("data/cloud"); GIC.set_color_from_file(cloud_file_name); + GIC.find_GIC_simplices(); Simplex_tree stree; GIC.create_complex(stree); + + BOOST_CHECK(stree.num_vertices() == 3); + BOOST_CHECK((stree.num_simplices()-stree.num_vertices()) == 4); + BOOST_CHECK(stree.dimension() == 2); +} + + -- cgit v1.2.3