diff options
Diffstat (limited to 'src/cython/doc')
-rw-r--r-- | src/cython/doc/euclidean_strong_witness_complex_ref.rst | 10 | ||||
-rw-r--r-- | src/cython/doc/euclidean_witness_complex_ref.rst | 10 | ||||
-rw-r--r-- | src/cython/doc/strong_witness_complex_ref.rst | 10 | ||||
-rw-r--r-- | src/cython/doc/witness_complex_sum.rst | 20 | ||||
-rw-r--r-- | src/cython/doc/witness_complex_user.rst | 86 |
5 files changed, 106 insertions, 30 deletions
diff --git a/src/cython/doc/euclidean_strong_witness_complex_ref.rst b/src/cython/doc/euclidean_strong_witness_complex_ref.rst new file mode 100644 index 00000000..bebf0f9a --- /dev/null +++ b/src/cython/doc/euclidean_strong_witness_complex_ref.rst @@ -0,0 +1,10 @@ +================================================= +Euclidean strong witness complex reference manual +================================================= + +.. autoclass:: gudhi.EuclideanStrongWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.EuclideanStrongWitnessComplex.__init__ diff --git a/src/cython/doc/euclidean_witness_complex_ref.rst b/src/cython/doc/euclidean_witness_complex_ref.rst new file mode 100644 index 00000000..29b8806f --- /dev/null +++ b/src/cython/doc/euclidean_witness_complex_ref.rst @@ -0,0 +1,10 @@ +========================================== +Euclidean witness complex reference manual +========================================== + +.. autoclass:: gudhi.EuclideanWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.EuclideanWitnessComplex.__init__ diff --git a/src/cython/doc/strong_witness_complex_ref.rst b/src/cython/doc/strong_witness_complex_ref.rst new file mode 100644 index 00000000..4ed4fe46 --- /dev/null +++ b/src/cython/doc/strong_witness_complex_ref.rst @@ -0,0 +1,10 @@ +======================================= +Strong witness complex reference manual +======================================= + +.. autoclass:: gudhi.StrongWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.StrongWitnessComplex.__init__ diff --git a/src/cython/doc/witness_complex_sum.rst b/src/cython/doc/witness_complex_sum.rst index 1b20d4bc..b65522ba 100644 --- a/src/cython/doc/witness_complex_sum.rst +++ b/src/cython/doc/witness_complex_sum.rst @@ -1,25 +1,17 @@ ================================================================= =================================== =================================== :Author: Siargey Kachanovich :Introduced in: GUDHI 2.0.0 :Copyright: GPL v3 +:Euclidean version requires: CGAL :math:`\geq` 4.6.0 Eigen3 ================================================================= =================================== =================================== +-----------------------------------------------------------------+----------------------------------------------------------------------+ | .. image:: | Witness complex :math:`Wit(W,L)` is a simplicial complex defined on | -| img/Witness_complex_representation.png | two sets of points in :math:`\mathbb{R}^D`:Wit(W,L)` is a simplicial | -| | complex defined on two sets of points in :math:`\mathbb{R}^D`: | -| | | -| | * :math:`W` set of **witnesses** and | -| | * :math:`L \subseteq W` set of **landmarks**. | -| | | -| | The simplices are based on landmarks and a simplex belongs to the | -| | witness complex if and only if it is witnessed, that is: | -| | | -| | :math:`\sigma \subset L` is witnessed if there exists a point | -| | :math:`w \in W` such that w is closer to the vertices of | -| | :math:`\sigma` than other points in :math:`L` and all of its faces | -| | are witnessed as well. | +| img/Witness_complex_representation.png | two sets of points in :math:`\mathbb{R}^D`. | | | | | | The data structure is described in | | | :cite:`boissonnatmariasimplextreealgorithmica`. | +-----------------------------------------------------------------+----------------------------------------------------------------------+ -| :doc:`witness_complex_user` | :doc:`witness_complex_ref` | +| :doc:`witness_complex_user` | * :doc:`witness_complex_ref` | +| | * :doc:`strong_witness_complex_ref` | +| | * :doc:`euclidean_witness_complex_ref` | +| | * :doc:`euclidean_strong_witness_complex_ref` | +-----------------------------------------------------------------+----------------------------------------------------------------------+ diff --git a/src/cython/doc/witness_complex_user.rst b/src/cython/doc/witness_complex_user.rst index 604c7357..071d8ef5 100644 --- a/src/cython/doc/witness_complex_user.rst +++ b/src/cython/doc/witness_complex_user.rst @@ -6,26 +6,80 @@ Definition .. include:: witness_complex_sum.rst + +Definitions +----------- + +Witness complex is a simplicial complex defined on two sets of points in :math:`\mathbb{R}^D`: + +- :math:`W` set of **witnesses** and +- :math:`L` set of **landmarks**. + +Even though often the set of landmarks :math:`L` is a subset of the set of witnesses :math:`W`, it is not a requirement +for the current implementation. + +Landmarks are the vertices of the simplicial complex 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*: :math:`\sigma \subset L` is witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l')` +- *strong*: :math:`\sigma \subset L` is witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l')` + +where :math:`d(.,.)` is a distance function. + +Both definitions can be relaxed by a real value :math:`\alpha`: + +- *weak*: :math:`\sigma \subset L` is :math:`\alpha`-witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2` +- *strong*: :math:`\sigma \subset L` is :math:`\alpha`-witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2` + +which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and +**strong relaxed witness complex** respectively. + +.. figure:: img/swit.svg + :alt: Strongly witnessed simplex + :figclass: align-center + + Strongly witnessed simplex + + +In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in +:cite:`de2004topological`, whereas 0-relaxed strong witness complex consists of just vertices and is not very +interesting. Hence for small relaxation weak version is preferable. +However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is +often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute +and offers similar results. + Implementation -------------- -The principal class of this module is Gudhi::Witness_complex. +The two complexes described above are implemented in the corresponding classes + +- :doc:`witness_complex_ref` +- :doc:`strong_witness_complex_ref` +- :doc:`euclidean_witness_complex_ref` +- :doc:`euclidean_strong_witness_complex_ref` + +The construction of the Euclidean versions of complexes follow the same scheme: + +1. Construct a search tree on landmarks. +2. Construct lists of nearest landmarks for each witness. +3. Construct the witness complex for nearest landmark lists. + +In the non-Euclidean classes, the lists of nearest landmarks are supposed to be given as input. + +The constructors take on the steps 1 and 2, while the function 'create_complex' executes the step 3. + +Constructing weak relaxed witness complex from an off file +---------------------------------------------------------- + +Let's start with a simple example, which reads an off point file and computes a weak witness complex. -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. +Example2: Computing persistence using strong relaxed witness complex +-------------------------------------------------------------------- -.. todo:: - 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: -.. figure:: - img/bench_Cy8.png - :align: center - - Running time as function on number of landmarks. +.. include:: biblio.rst -.. figure:: - img/bench_sphere.png - :align: center - - Running time as function on number of witnesses for |L|=300. |