author Dmitriy Morozov <>
Mon, 31 Aug 2009 10:51:56 -0700
changeset 167 5a5f3e1c466b
parent 149 3d15aca95dfb
child 169 c0bf4675697c
permissions -rw-r--r--
Removed Qt4 requirement + added link to download and tutorial to the front page of the documentation

.. _tutorial:

Brief Tutorial

It suffices to import only the necessary commands from module :mod:`dionysus`,
but for the purposes of the tutorial, we import everything::

    from dionysus import *

Read in a points file (for :func:`points_file` the points should appear one per
line with coordinates separated with spaces; of course, one can read in the
points however one wants)::

    points = [p for p in points_file('points_filename')]
    print "Number of points:", len(points)


If the points are in :math:`\mathbb{R}^2` or :math:`\mathbb{R}^3`, one can
construct an alphashape filtration::

    simplices = []
    fill_alpha2D_complex(points, simplices)     # for 2D, or
    fill_alpha3D_complex(points, simplices)     # for 3D

Functions :ref:`fill_alpha*_complex <alphashapes>` fill the ``simplices`` list
with all the :class:`simplices <Simplex>` of the Delaunay triangulation. Each one has attributes
``data`` and ``attached`` set to its respective value in the alpha shape (the
smallest value of the squared distance function on the dual Voronoi cell) and
whether the simplex is attached or not (i.e. whether its dual cell does not or
does contain a critical point of the distance function). See :ref:`alphashapes`
for more details, and :ref:`alpha-shape-example` for a full example.

As a result, if one wanted only those simplices whose alpha shape value did not
exceed 10, one could obtain them as follows::

    simplices10 = [s for s in simplices if <= 10]

If the point set lies in higher dimensions, one may construct a Rips complex on
it. This complex requires only pairwise distances, which makes it very
versatile. One must first construct an instance of a class providing such
distances (e.g. :class:`PairwiseDistances` for explicit points, see
:ref:`distances` for more details), and then pass it to the :class:`Rips`
complex class::

    distances = PairwiseDistances(points)
    rips = Rips(distances)

Usually, because of space restrictions, generation of a Rips complex has to be
restricted to a :math:`k`-skeleton of the complex and some maximal parameter
:math:`max`. In the following example :math:`k = 3` and :math:`max = 50`::

    simplices = []
    rips.generate(3, 50, simplices.append)

:meth:`Rips.generate` takes a skeleton and a maximum distance cutoffs, and a
function which is called with each of the simplices in the complex (in this
case, Python list `simplices`' ``append`` method).


There are two ways of computing persistence in Dionysus. The first *offline*
way, required by :class:`StaticPersistence` (and its derivatives), is to set up
the entire filtration at once, compute its persistence in one operation, and
then examine the pairings. The second way is to feed simplices one by one in an
*online* manner and manually keep track of the pairs that are created.
:class:`ZigzagPersistence` and :class:`CohomologyPersistence` accept their
input this way,


For the first approach, i.e. to use :class:`StaticPersistence`, one must put the
simplices into lexicographic ordering (sort them with respect to
:func:`vertex_cmp`), and construct a filtration with respect to some ordering
(for example, :func:`data_dim_cmp` for alpha shapes or :meth:`Rips.cmp` for the
Rips complex)::

    f = Filtration(simplices, data_dim_cmp)     # for the alpha shapes
    f = Filtration(simplices, rips.cmp)         # for the rips complex

Creating an instance of :class:`StaticPersistence` initialized with the
filtration really initializes a boundary matrix. The subsequent call to
:meth:`~StaticPersistence.pair_simplices` reduces the matrix to compute the
persistence of the filtration::

    p = StaticPersistence(f)

Once the simplices are paired, one may examine the pairings by iterating over
the instance of :class:`StaticPersistence`::

    for i in p:
        if i.sign():
            birth = simplices[f[p(i)]]
            if i == i.pair:
                print birth.dimension(),, "inf"
            death = simplices[f[p(i.pair)]]
            print birth.dimension(),,

The iterator ``i`` over the instance ``p`` of :class:`StaticPersistence` is of type
:class:`SPNode`, and represents individual simplices taken in the filtration
order. It knows about its own :meth:`~SPNode.sign` and :attr:`~SPNode.pair`
(``i.pair == i`` if the simplex is unpaired).  Calling ``p`` with the iterator
``i`` (``p(i)``) gives its integer index in the filtration, which can then be
used with the instance ``f`` of :class:`Filtration` to get the integer index in
the lexicographically sorted list `simplices`: ``simplices[f[p(i)]]``.  The
previous code snippet prints out the persistence diagrams of the given


Class :class:`ZigzagPersistence` accepts additions and removals of the simplices
one by one, and returns an internal representation of the simplices.
(:class:`CohomologyPersistence` works in the same way, but accepts only
additions of the simplices.) 
When one
adds a simplex via :meth:`ZigzagPersistence.add`, one must provide its boundary
in this internal representation together with a *birth value* which
:class:`ZigzagPersistence` will store in case a class is born as a result of the
addition. :meth:`~ZigzagPersistence.add` returns a pair ``(i,d)``. ``i`` is the
internal representation of the newly added simplex, which one must record for
future use in the boundaries of its cofaces (below it is recorded in the
dictionary ``complex``). ``d`` is `None` in case of the birth, otherwise, it is the
previously recorded birth value of the class that dies as a result of the
addition. The following code adds all the ``simplices`` to a zigzag::

    complex = {}
    zz = ZigzagPersistence()
    for s in simplices:
        i,d = zz.add([complex[sb] for sb in s.boundary, (s.dimension(),
        complex[s] = i
        if d is not None:                   # we have a death
            dimension, birth = d            # we previously stored the (dimension, data) pair
            print dimension, birth,       

Similarly, one can remove simplices by calling :meth:`ZigzagPersistence.remove`
with the internal index previously returned by :meth:`~ZigzagPersistence.add`::

    for s in reversed(simplices):
        d = zz.remove(complex[s], (s.dimension() - 1,
        del complex[s]
        if d is not None:
            dimension, birth = d
            print dimension, birth,

Naturally, :meth:`~ZigzagPersistence.remove` returns only `d`. 

If one wants to add or remove an entire set of simplices "at once" (i.e.  with
all births being assigned the same value), there are two helper functions:
:func:`add_simplices` and :func:`remove_simplices`.

See the :ref:`bindings reference <python-bindings>` for more details, and
:ref:`triangle-zigzag-example` for an example of :class:`ZigzagPersistence`.
See :ref:`rips-pairwise-cohomology` for an example of

.. _speed-up-suggestions:

Speed-up suggestions

Currently, when the choice comes between efficiency and flexibility, the Python
bindings err on the side of flexibility. There is hope that in the future the
choice won't really be necessary. Meanwhile, one can use a few techniques that
speed up computation at the expense of memory. Note, however, that since the
recent switch of :class:`PairwiseDistances` to C++ rather than pure Python, it
is not clear whether these deliver a substantial speed-up:

* To avoid (possibly expensive) computation of distances during Rips complex
  generation, store :class:`ExplicitDistances` (see :ref:`distances`)::

        distances = PairwiseDistances(points)
        distances = ExplicitDistances(distances)

* To avoid the computation of simplex sizes in the Rips complex during the
  initialization of a :class:`Filtration`, store them explicitly in
  :attr:`` attribute (this is not done by default to save memory);
  then use :func:`data_dim_cmp` in the initialization of the

        rips = Rips(distances)
        simplices = []
        rips.generate(..., simplices.append)
        for s in simplices: = rips.eval(s)
        f = Filtration(simplices, data_dim_cmp)

.. include::    substitutions.aux