New revision of witness and its documentation

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST_cythonize@2181 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 5f002c1a58b2daff6c6826a2552d1c101f6810e1

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.