Software

Click here for links to the source code, pre-compiled executables and also a brief manual on using the software.

Persistent homology - or simply, persistence - is an algebraic topological invariant of a filtered cell complex. Perseus computes this invariant for a wide class of filtrations built around datasets arising from point samples, images, distance matrices and so forth.

---

For a quick introduction to persistent homology, see the survey papers by Carlsson and Ghrist. An elementary account of simplicial complexes, what homology actually measures, and some biological applications can be found in my introductory paper written with Sazdanovic. For a much more comprehensive (but elementary!) overview of applied topology in general, consult Rob Ghrist's book.

The standard algorithm for computing persistence intervals relies on Smith normal form and is therefore of super-cubical complexity in the total number of cells. Perseus reduces the original filtration drastically in linear time via discrete Morse theory without altering its persistent homology. The reduced complex is then passed on to the standard cubical algorithm. This Morse theoretic pre-processing results in incredible savings of both time and memory when compared to the standard approach. More details can be found in the associated paper here.

Click here for the C++ source code. Don't worry, it is just a single file.

The diamond cubic is a highly symmetric three dimensional graph structure so that all angles in sight are tetrahedral. Statistics of self-avoiding random walks on diamond cubics might provide convenient null hypotheses when analyzing corresponding structures of protein molecules, since protein molecules are also built on a backbone of tetrahedrally arranged atoms. Norris generates self-avoiding random walks on diamond cubics.

---

Usage Instructions

Open the file "rwalk.cpp" downloaded from the link above in any text editor. Change the following #define-d global variables at the top of the file to suit your requirements:

• WALKSIZE controls the number of steps in the walk,
• NUMPIVOTTRYS determines the number of pivot attempts,
• NUMWALKS defines the number (default = 1) of random walks to generate, and
• FILESTR lets you control how the output files are named the default choice is "rw_(walk number).txt".

Now compile the file using any standard C++ compiler and run the generated executable. For instance, if you are on a Unix type terminal with gcc installed on your system, you can try the following:

• g++ rwalk.cpp -O3 -o norris
• ./norris

That's it! The output will be a collection of NUMWALK files (named according to your choice of FILESTR) created in the working directory. Each file contains an ordered collection of 3 dimensional points separated by line breaks which represent the vertices on the diamond cubic traversed during a self avoiding walk.

---

How it Works

Norris utilizes the famous pivot algorithm to create self-avoiding walks. This algorithm works as follows: first, we generate a self avoiding walk of the desired length by doing something obvious. In the case of the integer lattice, an obvious initial walk of length n would just involve starting at the origin and going in the +X direction n times. The starting walk for a diamond cubic requires a subtler approach since it lacks translation-invariance, but the principle is the same. Next, we pick a random point P called the pivot on this initial walk and apply a random symmetry of the diamond cubic (which fixes P) to all the points subsequent to P on the walk. If the new walk so obtained is self-avoiding, then we keep it and apply another symmetry to another point. If this walk is not self-avoiding, then we discard the symmetry and try again. Repeating this process for a large enough number of pivot attempts guarantees the generation of a truly random self-avoiding walk.