diff options
| -rw-r--r-- | src/Nerve_GIC/example/CoordGIC.cpp | 4 | ||||
| -rw-r--r-- | src/cython/CMakeLists.txt | 29 | ||||
| -rw-r--r-- | src/cython/cython/nerve_gic.pyx | 401 | ||||
| -rw-r--r-- | src/cython/doc/examples.rst | 4 | ||||
| -rw-r--r-- | src/cython/doc/index.rst | 5 | ||||
| -rw-r--r-- | src/cython/doc/nerve_gic_complex_ref.rst | 10 | ||||
| -rw-r--r-- | src/cython/doc/nerve_gic_complex_sum.rst | 15 | ||||
| -rw-r--r-- | src/cython/doc/nerve_gic_complex_user.rst | 312 | ||||
| -rwxr-xr-x | src/cython/example/coordinate_graph_induced_complex.py | 68 | ||||
| -rwxr-xr-x | src/cython/example/functional_graph_induced_complex.py | 69 | ||||
| -rwxr-xr-x | src/cython/example/nerve_of_a_covering.py | 70 | ||||
| -rwxr-xr-x | src/cython/example/voronoi_graph_induced_complex.py | 65 | ||||
| -rw-r--r-- | src/cython/gudhi.pyx.in | 1 | ||||
| -rw-r--r-- | src/cython/include/Nerve_gic_interface.h | 61 | ||||
| -rwxr-xr-x | src/cython/test/test_cover_complex.py | 89 |
15 files changed, 1201 insertions, 2 deletions
diff --git a/src/Nerve_GIC/example/CoordGIC.cpp b/src/Nerve_GIC/example/CoordGIC.cpp index 73edae18..9889b198 100644 --- a/src/Nerve_GIC/example/CoordGIC.cpp +++ b/src/Nerve_GIC/example/CoordGIC.cpp @@ -79,10 +79,10 @@ int main(int argc, char **argv) { // -------------------------------------------- if (verb) { - std::cout << "Functional GIC is of dimension " << stree.dimension() << " - " << stree.num_simplices() + std::cout << "Coordinate GIC is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - " << stree.num_vertices() << " vertices." << std::endl; - std::cout << "Iterator on functional GIC simplices" << std::endl; + std::cout << "Iterator on coordinate GIC simplices" << std::endl; for (auto f_simplex : stree.filtration_simplex_range()) { for (auto vertex : stree.simplex_vertex_range(f_simplex)) { std::cout << vertex << " "; diff --git a/src/cython/CMakeLists.txt b/src/cython/CMakeLists.txt index 17d440ee..92eb6c94 100644 --- a/src/cython/CMakeLists.txt +++ b/src/cython/CMakeLists.txt @@ -55,6 +55,7 @@ if(CYTHON_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.8.1) set(GUDHI_CYTHON_BOTTLENECK_DISTANCE "include '${CMAKE_CURRENT_SOURCE_DIR}/cython/bottleneck_distance.pyx'") + set(GUDHI_CYTHON_NERVE_GIC "include '${CMAKE_CURRENT_SOURCE_DIR}/cython/nerve_gic.pyx'") endif (NOT CGAL_VERSION VERSION_LESS 4.8.1) if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.8.1) set(GUDHI_CYTHON_SUBSAMPLING "include '${CMAKE_CURRENT_SOURCE_DIR}/cython/subsampling.pyx'") @@ -185,6 +186,34 @@ if(CYTHON_FOUND) ${PYTHON_EXECUTABLE} "${CMAKE_CURRENT_SOURCE_DIR}/example/bottleneck_basic_example.py") add_gudhi_py_test(test_bottleneck_distance) + + # Cover complex + add_test(NAME cover_complex_nerve_example_py_test + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + COMMAND ${CMAKE_COMMAND} -E env "PYTHONPATH=${CMAKE_CURRENT_BINARY_DIR}" + ${PYTHON_EXECUTABLE} "${CMAKE_CURRENT_SOURCE_DIR}/example/nerve_of_a_covering.py" + -f ${CMAKE_SOURCE_DIR}/data/points/human.off -c 2 -r 10 -g 0.3) + + add_test(NAME cover_complex_coordinate_gic_example_py_test + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + COMMAND ${CMAKE_COMMAND} -E env "PYTHONPATH=${CMAKE_CURRENT_BINARY_DIR}" + ${PYTHON_EXECUTABLE} "${CMAKE_CURRENT_SOURCE_DIR}/example/coordinate_graph_induced_complex.py" + -f ${CMAKE_SOURCE_DIR}/data/points/human.off -c 0 -v) + + add_test(NAME cover_complex_functional_gic_example_py_test + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + COMMAND ${CMAKE_COMMAND} -E env "PYTHONPATH=${CMAKE_CURRENT_BINARY_DIR}" + ${PYTHON_EXECUTABLE} "${CMAKE_CURRENT_SOURCE_DIR}/example/functional_graph_induced_complex.py" + -o ${CMAKE_SOURCE_DIR}/data/points/COIL_database/lucky_cat.off + -f ${CMAKE_SOURCE_DIR}/data/points/COIL_database/lucky_cat_PCA1 -v) + + add_test(NAME cover_complex_voronoi_gic_example_py_test + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + COMMAND ${CMAKE_COMMAND} -E env "PYTHONPATH=${CMAKE_CURRENT_BINARY_DIR}" + ${PYTHON_EXECUTABLE} "${CMAKE_CURRENT_SOURCE_DIR}/example/voronoi_graph_induced_complex.py" + -f ${CMAKE_SOURCE_DIR}/data/points/human.off -n 700 -v) + + add_gudhi_py_test(test_cover_complex) endif (NOT CGAL_VERSION VERSION_LESS 4.8.1) if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.7.0) diff --git a/src/cython/cython/nerve_gic.pyx b/src/cython/cython/nerve_gic.pyx new file mode 100644 index 00000000..30a14d3b --- /dev/null +++ b/src/cython/cython/nerve_gic.pyx @@ -0,0 +1,401 @@ +from cython cimport numeric +from libcpp.vector cimport vector +from libcpp.utility cimport pair +from libcpp.string cimport string +from libcpp cimport bool +import os + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + +cdef extern from "Nerve_gic_interface.h" namespace "Gudhi": + cdef cppclass Nerve_gic_interface "Gudhi::cover_complex::Nerve_gic_interface": + Nerve_gic_interface() + double compute_confidence_level_from_distance(double distance) + double compute_distance_from_confidence_level(double alpha) + void compute_distribution(int N) + double compute_p_value() + void compute_PD() + void find_simplices() + void create_simplex_tree(Simplex_tree_interface_full_featured* simplex_tree) + bool read_point_cloud(string off_file_name) + double set_automatic_resolution() + void set_color_from_coordinate(int k) + void set_color_from_file(string color_file_name) + void set_color_from_vector(vector[double] color) + void set_cover_from_file(string cover_file_name) + void set_cover_from_function() + void set_cover_from_Euclidean_Voronoi(int m) + void set_function_from_coordinate(int k) + void set_function_from_file(string func_file_name) + void set_function_from_range(vector[double] function) + void set_gain(double g) + double set_graph_from_automatic_euclidean_rips(int N) + void set_graph_from_file(string graph_file_name) + void set_graph_from_OFF() + void set_graph_from_euclidean_rips(double threshold) + void set_mask(int nodemask) + void set_resolution_with_interval_length(double resolution) + void set_resolution_with_interval_number(int resolution) + void set_subsampling(double constant, double power) + void set_type(string type) + void set_verbose(bool verbose) + vector[int] subpopulation(int c) + void write_info() + void plot_DOT() + void plot_OFF() + +# CoverComplex python interface +cdef class CoverComplex: + """Cover complex data structure. + + The data structure is a simplicial complex, representing a Graph Induced + simplicial Complex (GIC) or a Nerve, and whose simplices are computed with + a cover C of a point cloud P, which often comes from the preimages of + intervals covering the image of a function f defined on P. These intervals + are parameterized by their resolution (either their length or their number) + and their gain (percentage of overlap). To compute a GIC, one also needs a + graph G built on top of P, whose cliques with vertices belonging to + different elements of C correspond to the simplices of the GIC. + """ + + cdef Nerve_gic_interface * thisptr + + # Fake constructor that does nothing but documenting the constructor + def __init__(self): + """CoverComplex constructor. + """ + + # The real cython constructor + def __cinit__(self): + self.thisptr = new Nerve_gic_interface() + + def __dealloc__(self): + if self.thisptr != NULL: + del self.thisptr + + def __is_defined(self): + """Returns true if CoverComplex pointer is not NULL. + """ + return self.thisptr != NULL + + def compute_confidence_level_from_distance(self, distance): + """Computes the confidence level of a specific bottleneck distance + threshold. + + :param distance: Bottleneck distance. + :type distance: double + :rtype: double + :returns: Confidence level. + """ + return self.thisptr.compute_confidence_level_from_distance(distance) + + def compute_distance_from_confidence_level(self, alpha): + """Computes the bottleneck distance threshold corresponding to a + specific confidence level. + + :param alpha: Confidence level. + :type alpha: double + :rtype: double + :returns: Bottleneck distance. + """ + return self.thisptr.compute_distance_from_confidence_level(alpha) + + def compute_distribution(self, N=100): + """Computes bootstrapped distances distribution. + + :param N: Loop number (default value is 100). + :type alpha: int + """ + self.thisptr.compute_distribution(N) + + def compute_p_value(self): + """Computes the p-value, i.e. the opposite of the confidence level of + the largest bottleneck distance preserving the points in the + persistence diagram of the output simplicial complex. + + :rtype: double + :returns: p-value. + """ + return self.thisptr.compute_p_value() + + def compute_PD(self): + """Computes the extended persistence diagram of the complex. + """ + self.thisptr.compute_PD() + + def create_simplex_tree(self): + """ + :returns: A simplex tree created from the Cover complex. + :rtype: SimplexTree + """ + simplex_tree = SimplexTree() + self.thisptr.create_simplex_tree(simplex_tree.thisptr) + return simplex_tree + + def find_simplices(self): + """Computes the simplices of the simplicial complex. + """ + self.thisptr.find_simplices() + + def read_point_cloud(self, off_file): + """Reads and stores the input point cloud. + + :param off_file: Name of the input .OFF or .nOFF file. + :type off_file: string + :rtype: bool + :returns: Read file status. + """ + if os.path.isfile(off_file): + return self.thisptr.read_point_cloud(str.encode(off_file)) + else: + print("file " + off_file + " not found.") + return False + + def set_automatic_resolution(self): + """Computes the optimal length of intervals (i.e. the smallest interval + length avoiding discretization artifacts—see :cite:`Carriere17c`) for a + functional cover. + + :rtype: double + :returns: reso interval length used to compute the cover. + """ + return self.thisptr.set_automatic_resolution() + + def set_color_from_coordinate(self, k=0): + """Computes the function used to color the nodes of the simplicial + complex from the k-th coordinate. + + :param k: Coordinate to use (start at 0). Default value is 0. + :type k: int + """ + return self.thisptr.set_color_from_coordinate(k) + + def set_color_from_file(self, color_file_name): + """Computes the function used to color the nodes of the simplicial + complex from a file containing the function values. + + :param color_file_name: Name of the input color file. + :type color_file_name: string + """ + if os.path.isfile(color_file_name): + self.thisptr.set_color_from_file(str.encode(color_file_name)) + else: + print("file " + color_file_name + " not found.") + + def set_color_from_vector(self, color): + """Computes the function used to color the nodes of the simplicial + complex from a vector stored in memory. + + :param color: Input vector of values. + :type color: vector[double] + """ + self.thisptr.set_color_from_vector(color) + + def set_cover_from_file(self, cover_file_name): + """Creates the cover C from a file containing the cover elements of + each point (the order has to be the same as in the input file!). + + :param cover_file_name: Name of the input cover file. + :type cover_file_name: string + """ + if os.path.isfile(cover_file_name): + self.thisptr.set_cover_from_file(str.encode(cover_file_name)) + else: + print("file " + cover_file_name + " not found.") + + def set_cover_from_function(self): + """Creates a cover C from the preimages of the function f. + """ + self.thisptr.set_cover_from_function() + + def set_cover_from_Voronoi(self, m=100): + """Creates the cover C from the Voronoï cells of a subsampling of the + point cloud. + + :param m: Number of points in the subsample. Default value is 100. + :type m: int + """ + self.thisptr.set_cover_from_Euclidean_Voronoi(m) + + def set_function_from_coordinate(self, k): + """Creates the function f from the k-th coordinate of the point cloud. + + :param k: Coordinate to use (start at 0). + :type k: int + """ + self.thisptr.set_function_from_coordinate(k) + + def set_function_from_file(self, func_file_name): + """Creates the function f from a file containing the function values. + + :param func_file_name: Name of the input function file. + :type func_file_name: string + """ + if os.path.isfile(func_file_name): + self.thisptr.set_function_from_file(str.encode(func_file_name)) + else: + print("file " + func_file_name + " not found.") + + def set_function_from_range(self, function): + """Creates the function f from a vector stored in memory. + + :param function: Input vector of values. + :type function: vector[double] + """ + self.thisptr.set_function_from_range(function) + + def set_gain(self, g = 0.3): + """Sets a gain from a value stored in memory. + + :param g: Gain (default value is 0.3). + :type g: double + """ + self.thisptr.set_gain(g) + + def set_graph_from_automatic_rips(self, N=100): + """Creates a graph G from a Rips complex whose threshold value is + automatically tuned with subsampling—see. + + :param N: Number of subsampling iteration (the default reasonable value + is 100, but there is no guarantee on how to choose it). + :type N: int + :rtype: double + :returns: Delta threshold used for computing the Rips complex. + """ + return self.thisptr.set_graph_from_automatic_euclidean_rips(N) + + def set_graph_from_file(self, graph_file_name): + """Creates a graph G from a file containing the edges. + + :param graph_file_name: Name of the input graph file. The graph file + contains one edge per line, each edge being represented by the IDs of + its two nodes. + :type graph_file_name: string + """ + if os.path.isfile(graph_file_name): + self.thisptr.set_graph_from_file(str.encode(graph_file_name)) + else: + print("file " + graph_file_name + " not found.") + + def set_graph_from_OFF(self): + """Creates a graph G from the triangulation given by the input OFF + file. + """ + self.thisptr.set_graph_from_OFF() + + def set_graph_from_rips(self, threshold): + """Creates a graph G from a Rips complex. + + :param threshold: Threshold value for the Rips complex. + :type threshold: double + """ + self.thisptr.set_graph_from_euclidean_rips(threshold) + + def set_mask(self, nodemask): + """Sets the mask, which is a threshold integer such that nodes in the + complex that contain a number of data points which is less than or + equal to this threshold are not displayed. + + :param nodemask: Threshold. + :type nodemask: int + """ + self.thisptr.set_mask(nodemask) + + def set_resolution_with_interval_length(self, resolution): + """Sets a length of intervals from a value stored in memory. + + :param resolution: Length of intervals. + :type resolution: double + """ + self.thisptr.set_resolution_with_interval_length(resolution) + + def set_resolution_with_interval_number(self, resolution): + """Sets a number of intervals from a value stored in memory. + + :param resolution: Number of intervals. + :type resolution: int + """ + self.thisptr.set_resolution_with_interval_number(resolution) + + def set_subsampling(self, constant, power): + """Sets the constants used to subsample the data set. These constants + are explained in :cite:`Carriere17c`. + + :param constant: Constant. + :type constant: double + :param power: Power. + :type resolution: double + """ + self.thisptr.set_subsampling(constant, power) + + def set_type(self, type): + """Specifies whether the type of the output simplicial complex. + + :param type: either "GIC" or "Nerve". + :type type: string + """ + self.thisptr.set_type(str.encode(type)) + + def set_verbose(self, verbose): + """Specifies whether the program should display information or not. + + :param verbose: true = display info, false = do not display info. + :type verbose: boolean + """ + self.thisptr.set_verbose(verbose) + + def subpopulation(self, c): + """Returns the data subset corresponding to a specific node of the + created complex. + + :param c: ID of the node. + :type c: int + :rtype: vector[int] + :returns: Vector of IDs of data points. + """ + return self.thisptr.subpopulation(c) + + def write_info(self): + """Creates a .txt file called SC.txt describing the 1-skeleton, which can + then be plotted with e.g. KeplerMapper. + """ + return self.thisptr.write_info() + + def plot_dot(self): + """Creates a .dot file called SC.dot for neato (part of the graphviz + package) once the simplicial complex is computed to get a visualization of + its 1-skeleton in a .pdf file. + """ + return self.thisptr.plot_DOT() + + def plot_off(self): + """Creates a .off file called SC.off for 3D visualization, which contains + the 2-skeleton of the GIC. This function assumes that the cover has been + computed with Voronoi. If data points are in 1D or 2D, the remaining + coordinates of the points embedded in 3D are set to 0. + """ + return self.thisptr.plot_OFF() diff --git a/src/cython/doc/examples.rst b/src/cython/doc/examples.rst index d42f5a92..1f02f8a2 100644 --- a/src/cython/doc/examples.rst +++ b/src/cython/doc/examples.rst @@ -23,3 +23,7 @@ Examples * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>` * :download:`random_cubical_complex_persistence_example.py <../example/random_cubical_complex_persistence_example.py>` + * :download:`coordinate_graph_induced_complex.py <../example/coordinate_graph_induced_complex.py>` + * :download:`functional_graph_induced_complex.py <../example/functional_graph_induced_complex.py>` + * :download:`voronoi_graph_induced_complex.py <../example/voronoi_graph_induced_complex.py>` + * :download:`nerve_of_a_covering.py <../example/nerve_of_a_covering.py>` diff --git a/src/cython/doc/index.rst b/src/cython/doc/index.rst index 4e444fb0..15cbe267 100644 --- a/src/cython/doc/index.rst +++ b/src/cython/doc/index.rst @@ -36,6 +36,11 @@ Alpha complex .. include:: alpha_complex_sum.inc +Cover complexes +=============== + +.. include:: nerve_gic_complex_sum.rst + Cubical complex =============== diff --git a/src/cython/doc/nerve_gic_complex_ref.rst b/src/cython/doc/nerve_gic_complex_ref.rst new file mode 100644 index 00000000..e24e01fc --- /dev/null +++ b/src/cython/doc/nerve_gic_complex_ref.rst @@ -0,0 +1,10 @@ +================================ +Cover complexes reference manual +================================ + +.. autoclass:: gudhi.CoverComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.CoverComplex.__init__ diff --git a/src/cython/doc/nerve_gic_complex_sum.rst b/src/cython/doc/nerve_gic_complex_sum.rst new file mode 100644 index 00000000..72782c7a --- /dev/null +++ b/src/cython/doc/nerve_gic_complex_sum.rst @@ -0,0 +1,15 @@ +================================================================= =================================== =================================== +:Author: Mathieu Carrière :Introduced in: GUDHI 2.1.0 :Copyright: GPL v3 +:Requires: CGAL :math:`\geq` 4.8.1 +================================================================= =================================== =================================== + ++----------------------------------------------------------------+------------------------------------------------------------------------+ +| .. figure:: | Nerves and Graph Induced Complexes are cover complexes, i.e. | +| ../../doc/Nerve_GIC/gicvisu.jpg | simplicial complexes that provably contain topological information | +| :alt: Graph Induced Complex of a point cloud. | about the input data. They can be computed with a cover of the data, | +| :figclass: align-center | that comes i.e. from the preimage of a family of intervals covering | +| | the image of a scalar-valued function defined on the data. | +| Graph Induced Complex of a point cloud. | | ++----------------------------------------------------------------+------------------------------------------------------------------------+ +| :doc:`nerve_gic_complex_user` | :doc:`nerve_gic_complex_ref` | ++----------------------------------------------------------------+------------------------------------------------------------------------+ diff --git a/src/cython/doc/nerve_gic_complex_user.rst b/src/cython/doc/nerve_gic_complex_user.rst new file mode 100644 index 00000000..b2669303 --- /dev/null +++ b/src/cython/doc/nerve_gic_complex_user.rst @@ -0,0 +1,312 @@ +Cover complexes user manual +=========================== +Definition +---------- + +.. include:: nerve_gic_complex_sum.rst + +Visualizations of the simplicial complexes can be done with either +neato (from `graphviz <http://www.graphviz.org/>`_), +`geomview <http://www.geomview.org/>`_, +`KeplerMapper <https://github.com/MLWave/kepler-mapper>`_. +Input point clouds are assumed to be +`OFF files <http://www.geomview.org/docs/html/OFF.html>`_. + +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). + +Nerves +------ + +Nerve definition +^^^^^^^^^^^^^^^^ + +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 <https://en.wikipedia.org/wiki/Nerve_of_a_covering>`_. + +.. figure:: + ../../doc/Nerve_GIC/nerve.png + :figclass: align-center + :alt: Nerve of a double torus + + Nerve of a double torus + +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. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + nerve_complex.set_verbose(True) + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/human.off')): + nerve_complex.set_type('Nerve') + nerve_complex.set_color_from_coordinate(2) + nerve_complex.set_function_from_coordinate(2) + nerve_complex.set_graph_from_OFF() + nerve_complex.set_resolution_with_interval_number(10) + nerve_complex.set_gain(0.3) + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.write_info() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + result_str = 'Nerve is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) + +the program output is: + +.. code-block:: none + + Min function value = -0.979672 and Max function value = 0.816414 + Interval 0 = [-0.979672, -0.761576] + Interval 1 = [-0.838551, -0.581967] + Interval 2 = [-0.658942, -0.402359] + Interval 3 = [-0.479334, -0.22275] + Interval 4 = [-0.299725, -0.0431414] + Interval 5 = [-0.120117, 0.136467] + Interval 6 = [0.059492, 0.316076] + Interval 7 = [0.239101, 0.495684] + Interval 8 = [0.418709, 0.675293] + Interval 9 = [0.598318, 0.816414] + Computing preimages... + Computing connected components... + 5 interval(s) in dimension 0: + [-0.909111, 0.0081753] + [-0.171433, 0.367393] + [-0.171433, 0.367393] + [-0.909111, 0.745853] + 0 interval(s) in dimension 1: + +.. testoutput:: + + Nerve is of dimension 1 - 41 simplices - 21 vertices. + [1] + [0] + [4] + [0, 4] + [2] + [1, 2] + [8] + [2, 8] + [5] + [4, 5] + [9] + [8, 9] + [13] + [5, 13] + [14] + [9, 14] + [19] + [13, 19] + [25] + [32] + [20] + [20, 32] + [33] + [25, 33] + [26] + [14, 26] + [19, 26] + [42] + [26, 42] + [34] + [33, 34] + [27] + [20, 27] + [35] + [27, 35] + [34, 35] + [35, 42] + [44] + [35, 44] + [54] + [44, 54] + + +The program also writes a file ../../data/points/human.off_sc.txt. The first +three lines in this file are the location of the input point cloud and the +function used to compute the cover. +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. + +Using KeplerMapper, one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/nervevisu.jpg + :figclass: align-center + :alt: Visualization with KeplerMapper + + Visualization with KeplerMapper + +Graph Induced Complexes (GIC) +----------------------------- + +GIC definition +^^^^^^^^^^^^^^ + +Again, assume you are given a cover C of your point cloud P. Moreover, assume +you are also given a graph G built on top of P. Then, for any clique in G +whose nodes all belong to different elements of C, the GIC includes a +corresponding simplex, whose dimension is the number of nodes in the clique +minus one. +See :cite:`Dey13` for more details. + +.. figure:: + ../../doc/Nerve_GIC/GIC.jpg + :figclass: align-center + :alt: GIC of a point cloud + + GIC of a point cloud + +Example with cover from Voronoï +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This example builds the GIC of a point cloud sampled on a 3D human shape +(human.off). +We randomly subsampled 100 points in the point cloud, which act as seeds of +a geodesic Voronoï diagram. Each cell of the diagram is then an element of C. +The graph G (used to compute both the geodesics for Voronoï and the GIC) +comes from the triangulation of the human shape. Note that the resulting +simplicial complex is in dimension 3 in this example. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/human.off')): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate() + nerve_complex.set_graph_from_OFF() + nerve_complex.set_cover_from_Voronoi(700) + nerve_complex.find_simplices() + nerve_complex.plot_off() + +the program outputs SC.off. Using e.g. + +.. code-block:: none + + geomview ../../data/points/human.off_sc.off + +one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/gicvoronoivisu.jpg + :figclass: align-center + :alt: Visualization with Geomview + + Visualization with Geomview + +Functional GIC +^^^^^^^^^^^^^^ + +If one restricts to the cliques in G whose nodes all belong to preimages of +consecutive intervals (assuming the cover of the height function is minimal, +i.e. no more than two intervals can intersect at a time), the GIC is of +dimension one, i.e. a graph. +We call this graph the functional GIC. See :cite:`Carriere16` for more details. + +Example +^^^^^^^ + +Functional GIC comes with automatic selection of the Rips threshold, +the resolution and the gain of the function cover. See :cite:`Carriere17c` for +more details. In this example, we compute the functional GIC of a Klein bottle +embedded in R^5, where the graph G comes from a Rips complex with automatic +threshold, and the cover C comes from the preimages of intervals covering the +first coordinate, with automatic resolution and gain. Note that automatic +threshold, resolution and gain can be computed as well for the Nerve. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/KleinBottle5D.off')): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate(0) + nerve_complex.set_function_from_coordinate(0) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + +the program outputs SC.dot. Using e.g. + +.. code-block:: none + + neato ../../data/points/KleinBottle5D.off_sc.dot -Tpdf -o ../../data/points/KleinBottle5D.off_sc.pdf + +one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/coordGICvisu2.jpg + :figclass: align-center + :alt: Visualization with neato + + Visualization with neato + +where nodes are colored by the filter function values and, for each node, the +first number is its ID and the second is the number of data points that its +contain. + +We also provide an example on a set of 72 pictures taken around the same object +(lucky_cat.off). +The function is now the first eigenfunction given by PCA, whose values are +written in a file (lucky_cat_PCA1). Threshold, resolution and gain are +automatically selected as before. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/COIL_database/lucky_cat.off')): + nerve_complex.set_type('GIC') + pca_file = gudhi.__root_source_dir__ + \ + '/data/points/COIL_database/lucky_cat_PCA1' + nerve_complex.set_color_from_file(pca_file) + nerve_complex.set_function_from_file(pca_file) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + +the program outputs again SC.dot which gives the following visualization after using neato: + +.. figure:: + ../../doc/Nerve_GIC/funcGICvisu.jpg + :figclass: align-center + :alt: Visualization with neato + + Visualization with neato diff --git a/src/cython/example/coordinate_graph_induced_complex.py b/src/cython/example/coordinate_graph_induced_complex.py new file mode 100755 index 00000000..9e93109a --- /dev/null +++ b/src/cython/example/coordinate_graph_induced_complex.py @@ -0,0 +1,68 @@ +#!/usr/bin/env python + +import gudhi +import argparse + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + +parser = argparse.ArgumentParser(description='Coordinate GIC ' + 'from points read in a OFF file.', + epilog='Example: ' + 'example/coordinate_graph_induced_complex.py ' + '-f ../data/points/KleinBottle5D.off -c 0 -v' + '- Constructs the coordinate GIC with the ' + 'points from the given OFF file.') +parser.add_argument("-f", "--file", type=str, required=True) +parser.add_argument("-c", "--coordinate", type=int, default=0) +parser.add_argument("-v", "--verbose", default=False, action='store_true' , help='Flag for program verbosity') + +args = parser.parse_args() + +nerve_complex = gudhi.CoverComplex() +nerve_complex.set_verbose(args.verbose) + +if (nerve_complex.read_point_cloud(args.file)): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate(args.coordinate) + nerve_complex.set_function_from_coordinate(args.coordinate) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + if (args.verbose): + print('Iterator on coordinate GIC simplices') + result_str = 'Coordinate GIC is of dimension ' + \ + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) diff --git a/src/cython/example/functional_graph_induced_complex.py b/src/cython/example/functional_graph_induced_complex.py new file mode 100755 index 00000000..6ad7c2ec --- /dev/null +++ b/src/cython/example/functional_graph_induced_complex.py @@ -0,0 +1,69 @@ +#!/usr/bin/env python + +import gudhi +import argparse + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + +parser = argparse.ArgumentParser(description='Functional GIC ' + 'from points read in a OFF file.', + epilog='Example: ' + 'example/functional_graph_induced_complex.py ' + '-o ../data/points/COIL_database/lucky_cat.off ' + '-f ../data/points/COIL_database/lucky_cat_PCA1' + '- Constructs the functional GIC with the ' + 'points from the given OFF and function files.') +parser.add_argument("-o", "--off-file", type=str, required=True) +parser.add_argument("-f", "--function-file", type=str, required=True) +parser.add_argument("-v", "--verbose", default=False, action='store_true' , help='Flag for program verbosity') + +args = parser.parse_args() + +nerve_complex = gudhi.CoverComplex() +nerve_complex.set_verbose(args.verbose) + +if (nerve_complex.read_point_cloud(args.off_file)): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_file(args.function_file) + nerve_complex.set_function_from_file(args.function_file) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + if (args.verbose): + print('Iterator on functional GIC simplices') + result_str = 'Functional GIC is of dimension ' + \ + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) diff --git a/src/cython/example/nerve_of_a_covering.py b/src/cython/example/nerve_of_a_covering.py new file mode 100755 index 00000000..c5577cb1 --- /dev/null +++ b/src/cython/example/nerve_of_a_covering.py @@ -0,0 +1,70 @@ +#!/usr/bin/env python + +import gudhi +import argparse + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + +parser = argparse.ArgumentParser(description='Nerve of a covering creation ' + 'from points read in a OFF file.', + epilog='Example: ' + 'example/nerve_of_a_covering.py ' + '-f ../data/points/human.off -c 2 -r 10 -g 0.3' + '- Constructs Nerve of a covering with the ' + 'points from the given OFF file.') +parser.add_argument("-f", "--file", type=str, required=True) +parser.add_argument("-c", "--coordinate", type=int, default=0) +parser.add_argument("-r", "--resolution", type=int, default=10) +parser.add_argument("-g", "--gain", type=float, default=0.3) +parser.add_argument("-v", "--verbose", default=False, action='store_true' , help='Flag for program verbosity') + +args = parser.parse_args() + +nerve_complex = gudhi.CoverComplex() +nerve_complex.set_verbose(args.verbose) + +if (nerve_complex.read_point_cloud(args.file)): + nerve_complex.set_type('Nerve') + nerve_complex.set_color_from_coordinate(args.coordinate) + nerve_complex.set_function_from_coordinate(args.coordinate) + nerve_complex.set_graph_from_OFF() + nerve_complex.set_resolution_with_interval_number(args.resolution) + nerve_complex.set_gain(args.gain) + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.write_info() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + if (args.verbose): + print('Iterator on graph induced complex simplices') + result_str = 'Nerve is of dimension ' + \ + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) diff --git a/src/cython/example/voronoi_graph_induced_complex.py b/src/cython/example/voronoi_graph_induced_complex.py new file mode 100755 index 00000000..8266a0e4 --- /dev/null +++ b/src/cython/example/voronoi_graph_induced_complex.py @@ -0,0 +1,65 @@ +#!/usr/bin/env python + +import gudhi +import argparse + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + +parser = argparse.ArgumentParser(description='Voronoi GIC ' + 'from points read in a OFF file.', + epilog='Example: ' + 'example/voronoi_graph_induced_complex.py ' + '-f ../data/points/human.off -n 700 -v' + '- Constructs the Voronoi GIC with the ' + 'points from the given OFF file.') +parser.add_argument("-f", "--file", type=str, required=True) +parser.add_argument("-n", "--subsample-nb-points", type=int, default=100) +parser.add_argument("-v", "--verbose", default=False, action='store_true' , help='Flag for program verbosity') + +args = parser.parse_args() + +nerve_complex = gudhi.CoverComplex() +nerve_complex.set_verbose(args.verbose) + +if (nerve_complex.read_point_cloud(args.file)): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate() + nerve_complex.set_graph_from_OFF() + nerve_complex.set_cover_from_Voronoi(args.subsample_nb_points) + nerve_complex.find_simplices() + nerve_complex.plot_off() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + if (args.verbose): + print('Iterator on graph induced complex simplices') + result_str = 'Graph induced complex is of dimension ' + \ + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) diff --git a/src/cython/gudhi.pyx.in b/src/cython/gudhi.pyx.in index b94f2251..56a72b04 100644 --- a/src/cython/gudhi.pyx.in +++ b/src/cython/gudhi.pyx.in @@ -41,3 +41,4 @@ include '@CMAKE_CURRENT_SOURCE_DIR@/cython/strong_witness_complex.pyx' @GUDHI_CYTHON_SUBSAMPLING@ @GUDHI_CYTHON_TANGENTIAL_COMPLEX@ @GUDHI_CYTHON_BOTTLENECK_DISTANCE@ +@GUDHI_CYTHON_NERVE_GIC@ diff --git a/src/cython/include/Nerve_gic_interface.h b/src/cython/include/Nerve_gic_interface.h new file mode 100644 index 00000000..90edd544 --- /dev/null +++ b/src/cython/include/Nerve_gic_interface.h @@ -0,0 +1,61 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef INCLUDE_NERVE_GIC_INTERFACE_H_ +#define INCLUDE_NERVE_GIC_INTERFACE_H_ + +#include <gudhi/Simplex_tree.h> +#include <gudhi/distance_functions.h> +#include <gudhi/GIC.h> + +#include "Simplex_tree_interface.h" + +#include <iostream> +#include <vector> +#include <string> + +namespace Gudhi { + +namespace cover_complex { + +class Nerve_gic_interface : public Cover_complex<std::vector<double>> { + public: + void create_simplex_tree(Simplex_tree_interface<>* simplex_tree) { + create_complex(*simplex_tree); + simplex_tree->initialize_filtration(); + } + void set_cover_from_Euclidean_Voronoi(int m) { + set_cover_from_Voronoi(Gudhi::Euclidean_distance(), m); + } + double set_graph_from_automatic_euclidean_rips(int N) { + set_graph_from_automatic_rips(Gudhi::Euclidean_distance(), N); + } + void set_graph_from_euclidean_rips(double threshold) { + set_graph_from_rips(threshold, Gudhi::Euclidean_distance()); + } +}; + +} // namespace cover_complex + +} // namespace Gudhi + +#endif // INCLUDE_NERVE_GIC_INTERFACE_H_ diff --git a/src/cython/test/test_cover_complex.py b/src/cython/test/test_cover_complex.py new file mode 100755 index 00000000..39bf20a3 --- /dev/null +++ b/src/cython/test/test_cover_complex.py @@ -0,0 +1,89 @@ +from gudhi import CoverComplex + +"""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): Vincent Rouvreau + + Copyright (C) 2018 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 <http://www.gnu.org/licenses/>. +""" + +__author__ = "Vincent Rouvreau" +__copyright__ = "Copyright (C) 2018 Inria" +__license__ = "GPL v3" + + +def test_empty_constructor(): + # Try to create an empty CoverComplex + cover = CoverComplex() + assert cover.__is_defined() == True + +def test_non_existing_file_read(): + # Try to open a non existing file + cover = CoverComplex() + assert (cover.read_point_cloud('pouetpouettralala.toubiloubabdou') == False) + +def test_files_creation(): + # Create test file + cloud_file = open('cloud', 'w') + cloud_file.write('nOFF\n3\n3 0 0\n0 0 0\n2 1 0\n4 0 0') + cloud_file.close() + cover_file = open('cover', 'w') + cover_file.write('1\n2\n3') + cover_file.close() + graph_file = open('graph', 'w') + graph_file.write('0 1\n0 2\n1 2') + graph_file.close() + +def test_nerve(): + nerve = CoverComplex() + assert (nerve.read_point_cloud('cloud') == True) + nerve.set_type('Nerve') + nerve.set_graph_from_file('graph') + nerve.set_cover_from_file('cover') + nerve.find_simplices() + stree = nerve.create_simplex_tree() + + assert (stree.num_vertices() == 3) + assert ((stree.num_simplices() - stree.num_vertices()) == 0) + assert (stree.dimension() == 0) + +def test_graph_induced_complex(): + gic = CoverComplex() + gic.set_type('GIC') + assert (gic.read_point_cloud('cloud') == True) + gic.set_graph_from_file('graph') + gic.set_cover_from_file('cover') + gic.find_simplices() + stree = gic.create_simplex_tree() + + assert (stree.num_vertices() == 3) + assert ((stree.num_simplices() - stree.num_vertices()) == 4) + assert (stree.dimension() == 2) + +def test_voronoi_graph_induced_complex(): + gic = CoverComplex() + gic.set_type('GIC') + assert (gic.read_point_cloud('cloud') == True) + gic.set_graph_from_file('graph') + gic.set_cover_from_Voronoi(2) + gic.find_simplices() + stree = gic.create_simplex_tree() + + assert (stree.num_vertices() == 2) + assert ((stree.num_simplices() - stree.num_vertices()) == 1) + assert (stree.dimension() == 1) |