diff options
7 files changed, 116 insertions, 44 deletions
diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 9fc01a5d..a994ebef 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -954,3 +954,10 @@ pages={91-106}, language={English} } +@article{de2004topological, + title={Topological estimation using witness complexes}, + author={De Silva, Vin and Carlsson, Gunnar}, + journal={Proc. Sympos. Point-Based Graphics}, + pages={157--166}, + year={2004} +}
\ No newline at end of file diff --git a/src/Witness_complex/concept/Simplicial_complex_for_witness.h b/src/Witness_complex/concept/Simplicial_complex_for_witness.h index caaf0db6..b47de809 100644 --- a/src/Witness_complex/concept/Simplicial_complex_for_witness.h +++ b/src/Witness_complex/concept/Simplicial_complex_for_witness.h @@ -29,7 +29,7 @@ namespace witness_complex { /** \brief The concept Simplicial_Complex describes the requirements * for a type to implement a simplicial complex, - * used for example to build a 'Witness_complex'. + * used for example to build a Witness_complex. */ struct SimplicialComplexForWitness { /** Handle to specify a simplex. */ diff --git a/src/Witness_complex/doc/Witness_complex_doc.h b/src/Witness_complex/doc/Witness_complex_doc.h index 60dfd27b..1d6e9da2 100644 --- a/src/Witness_complex/doc/Witness_complex_doc.h +++ b/src/Witness_complex/doc/Witness_complex_doc.h @@ -6,33 +6,55 @@ \author Siargey Kachanovich - \image html "Witness_complex_representation.png" "Witness complex representation" + \image html "Witness_complex_representation.png" "Witness complex representation in a Simplex tree (from \cite boissonnatmariasimplextreealgorithmica)" \section Definitions - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: + Witness complex is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: \li \f$W\f$ set of **witnesses** and - \li \f$L \subseteq W\f$ set of **landmarks**. + \li \f$L\f$ set of **landmarks**. + + Even though often the set of landmarks \f$L\f$ is a subset of the set of witnesses \f$ W\f$, it is not a requirement for the current implementation. The simplices are based on landmarks - and a simplex belongs to the witness complex if and only if it is witnessed, that is: + and witnesses help to decide on which simplices are inserted via a predicate "is witnessed". + + De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**: + + - *weak*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in L \setminus \sigma,\ d(w,l) \leq d(w,l') \f$ + - *strong*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in L,\ d(w,l) \leq d(w,l') \f$ + + where \f$ d(.,.) \f$ is a distance function. + + Both definitions can be relaxed by a real value \f$\alpha\f$: + + - *weak*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in L \setminus \sigma,\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + - *strong*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in L,\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ - \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that - w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. - - The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively. \section Implementation + + The two complexes described above are implemented in the corresponding classes + - Gudhi::witness_complex::Witness_complex + - Gudhi::witness_complex::Strong_witness_complex + + The construction of both of them follow the same scheme: + 1. Construct a search tree on landmarks (for that Gudhi::spatial_searching::Kd_tree_search is used internally). + 2. Construct lists of nearest landmarks for each witness (special internal structure Gudhi::spatial_searching::Active_witness is used internally). + 3. Construct the witness complex for nearest landmark lists. + + The constructors take on the step 1, while the function 'create_complex' executes the steps 2 and 3. - The principal class of this module is Gudhi::Witness_complex. + \section Examples - In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness. - This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module. + Here is an example of constructing a strong witness complex filtration and computing persistence on it: + + \include Witness_complex/example_strong_witness_persistence.cpp *\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. diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h index e52410e4..2ca76767 100644 --- a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h @@ -31,9 +31,10 @@ namespace Gudhi { namespace witness_complex { - /** \brief Class representing a list of nearest neighbors to a given witness. - * \detail Every element is a pair of a landmark identifier and the squared distance to it. - */ + // /** \class Active_witness + // * \brief Class representing a list of nearest neighbors to a given witness. + // * \details Every element is a pair of a landmark identifier and the squared distance to it. + // */ template< typename Id_distance_pair, typename INS_range > class Active_witness { diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h index 9c96f7e8..38c7adb2 100644 --- a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h @@ -31,12 +31,12 @@ namespace Gudhi { namespace witness_complex { - /** \brief Iterator in the nearest landmark list. - * \detail After the iterator reaches the end of the list, - * the list is augmented by a (nearest landmark, distance) pair if possible. - * If all the landmarks are present in the list, iterator returns the specific end value - * of the corresponding 'Active_witness' object. - */ + // /** \brief Iterator in the nearest landmark list. + // * \details After the iterator reaches the end of the list, + // * the list is augmented by a (nearest landmark, distance) pair if possible. + // * If all the landmarks are present in the list, iterator returns the specific end value + // * of the corresponding 'Active_witness' object. + // */ template< typename Active_witness, typename Id_distance_pair, diff --git a/src/Witness_complex/include/gudhi/Strong_witness_complex.h b/src/Witness_complex/include/gudhi/Strong_witness_complex.h index 1ce050ad..e64f8f20 100644 --- a/src/Witness_complex/include/gudhi/Strong_witness_complex.h +++ b/src/Witness_complex/include/gudhi/Strong_witness_complex.h @@ -37,6 +37,22 @@ namespace Gudhi { namespace witness_complex { +/** + * \private + * \class Strong_witness_complex + * \brief Constructs strong witness complex for the given sets of witnesses and landmarks. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which + * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. + * \tparam DimensionTag can be either <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dimension__tag.html">Dimension_tag<d></a> + * if you know the intrinsic dimension at compile-time, + * or <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dynamic__dimension__tag.html">CGAL::Dynamic_dimension_tag</a> + * if you don't. + */ template< class Kernel_ > class Strong_witness_complex { private: @@ -55,7 +71,7 @@ private: typedef FT Filtration_value; - typedef std::ptrdiff_t Witness_id; + typedef std::size_t Witness_id; typedef typename Nearest_landmark_range::Point_with_transformed_distance Id_distance_pair; typedef typename Id_distance_pair::first_type Landmark_id; typedef Active_witness<Id_distance_pair, Nearest_landmark_range> ActiveWitness; @@ -63,6 +79,8 @@ private: typedef std::vector< Landmark_id > typeVectorVertex; typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; + typedef Landmark_id Vertex_handle; + private: Point_range witnesses_, landmarks_; Kd_tree landmark_tree_; @@ -74,9 +92,13 @@ private: //@{ - /* + /** * \brief Initializes member variables before constructing simplicial complex. - * \details The parameters should satisfy InputIterator C++ concepts. + * \details Records landmarks from the range [landmarks_first, landmarks_last) into a + * table internally, as well as witnesses from the range [witnesses_first, witnesses_last). + * All iterator parameters should satisfy <a target="_blank" + * href="http://en.cppreference.com/w/cpp/concept/InputIterator">InputIterator</a> + * C++ concept. */ template< typename InputIteratorLandmarks, typename InputIteratorWitnesses > @@ -90,15 +112,17 @@ private: /** \brief Returns the point corresponding to the given vertex. */ - Point_d get_point( std::size_t vertex ) const + template <typename Vertex_handle> + Point_d get_point( Vertex_handle vertex ) const { return landmarks_[vertex]; } - /** \brief Outputs the (strong) witness complex with - * squared relaxation parameter 'max_alpha_square' - * to simplicial complex 'complex'. - * The parameter 'limit_dimension' represents the maximal dimension of the simplicial complex + /** \brief Outputs the strong witness complex in a simplicial complex data structure. + * @param[out] complex Simplicial complex data structure compatible with 'find' and 'insert' operations. + * (Cf SimplicialComplexForWitness) + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex * (default value = no limit). */ template < typename SimplicialComplexForWitness > diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 7b46e1c0..6a944c43 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -37,12 +37,22 @@ namespace Gudhi { namespace witness_complex { -// /* -// * \private -// \class Witness_complex -// \brief Constructs the witness complex for the given set of witnesses and landmarks. -// \ingroup witness_complex -// */ +/** + * \private + * \class Witness_complex + * \brief Constructs (weak) witness complex for the given sets of witnesses and landmarks. + * \ingroup witness_complex + * + * \tparam Kernel_ requires a <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which + * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. + * \tparam DimensionTag can be either <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dimension__tag.html">Dimension_tag<d></a> + * if you know the intrinsic dimension at compile-time, + * or <a target="_blank" + * href="http://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Dynamic__dimension__tag.html">CGAL::Dynamic_dimension_tag</a> + * if you don't. +*/ template< class Kernel_ > class Witness_complex { private: @@ -69,6 +79,8 @@ private: typedef std::vector< Landmark_id > typeVectorVertex; typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; + typedef Landmark_id Vertex_handle; + private: Point_range witnesses_, landmarks_; Kd_tree landmark_tree_; @@ -80,9 +92,13 @@ private: //@{ - /* + /** * \brief Initializes member variables before constructing simplicial complex. - * \details The parameters should satisfy InputIterator C++ concepts. + * \details Records landmarks from the range [landmarks_first, landmarks_last) into a + * table internally, as well as witnesses from the range [witnesses_first, witnesses_last). + * All iterator parameters should satisfy <a target="_blank" + * href="http://en.cppreference.com/w/cpp/concept/InputIterator">InputIterator</a> + * C++ concept. */ template< typename InputIteratorLandmarks, typename InputIteratorWitnesses > @@ -95,16 +111,18 @@ private: } /** \brief Returns the point corresponding to the given vertex. + * @param[in] vertex Vertex handle of the point to retrieve. */ - Point_d get_point( std::size_t vertex ) const + Point_d get_point( Vertex_handle vertex ) const { return landmarks_[vertex]; } - /** \brief Outputs the (weak) witness complex with - * squared relaxation parameter 'max_alpha_square' - * to simplicial complex 'complex'. - * The parameter 'limit_dimension' represents the maximal dimension of the simplicial complex + /** \brief Outputs the (weak) witness complex in a simplicial complex data structure. + * @param[out] complex Simplicial complex data structure compatible with 'find' and 'insert' operations. + * (Cf SimplicialComplexForWitness) + * @param[in] max_alpha_square Maximal squared relaxation parameter. + * @param[in] limit_dimension Represents the maximal dimension of the simplicial complex * (default value = no limit). */ template < typename SimplicialComplexForWitness > @@ -229,7 +247,7 @@ private: return will_be_active; } - /** \brief Check if the facets of the k-dimensional simplex witnessed + /* \brief Check if the facets of the k-dimensional simplex witnessed * by witness witness_id are already in the complex. * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id */ |