Overview
Atlassian Sourcetree is a free Git and Mercurial client for Windows.
Atlassian Sourcetree is a free Git and Mercurial client for Mac.
DESCRIPTION
A tower is a sequence of simplicial complexes connected by simplicial maps. A simplicial map can be decomposed in a composition of two different elementary operations: the inclusion of a simplex and the contraction of two vertices. Sophia computes the persistent diagram of a tower by converting it first into an equivalent filtration, which is a sequence of simplicial complexes connected by inclusions. From there, it uses classical algorithms (see [1] and [2]) to compute the persistence pairs.
The convertion is a variation of the coning strategy by Dey et al. [3], yielding a filtration that is asymptotically only marginally larger than the tower. For more details about the construction, we refer to [4]. It is implemented as a streaming algorithm.
To be able to compute the persistence of really long towers, when they have relatively small complexes, the persistence algorithm was also implemented as a streaming algorithm. The previous converting algorithm, which can be used simultaneously, signals simplices as "inactive", which allows us to clean out the boundary matrix. This way, the space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower.
Sophia is published under the GNU Lesser General Public License.
Author: Hannah Schreiber (hschreiber@tugraz.at)
Contributor: Michael Kerber
References
[1] C. Chen and M. Kerber. Persistent homology computation with a twist. In European Workshop on Computational Geometry (EuroCG), pages 197200, 2011.
[2] U. Bauer, M. Kerber, and J. Reininghaus. Clear and compress: Computing persistent homology in chunks. In Topological Methods in Data Analysis and Visualization III, Mathematics and Visualization, pages 103117. Springer, 2014.
[3] T. Dey, F. Fan, and Y. Wang. Computing Topological Persistence for Simplicial Maps. In ACM Symposium on Computational Geometry (SoCG), pages 345354, 2014.
[4] M. Kerber, H. Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. https://arxiv.org/abs/1701.02208, TU Graz, 2016
INSTALLATION
To compile Sophia easily, we recommand to use CMake (https://cmake.org/).
Sophia has two options related to two external libraries: PHAT (https://bitbucket.org/phatcode/phat) and Gudhi (http://gudhi.gforge.inria.fr/), see USAGE section for more details. They also require to have installed the libraries OpenMP and Boost (version 1.48.0 or more recent) respectively. To activate these options, please specify the path to the include directory of PHAT and/or Gudhi in the "CMakeLists.txt" file at line 8 and 9:
#set(PHAT /pathtoPHATincludedirectory/)
#set(GUDHI /pathtoGudhiincludedirectory/)
and decomment them by removing the '#' symbol.
To compile, run in a terminal:
$ cd /pathtosoftware/
$ mkdir build
$ cd build
$ cmake ..
$ make
And then to use the software:
$ ./sophia [args]
USAGE
For Information about the different file formats mentionned in this section, refer to the section FILE FORMATS.
To each of the following options can be added the argument "silent" to avoid output in the terminal.
By default, there are 4 options:

./sophia cv inputfilename outputfilename
Builds the equivalent filtration of the tower, whose description is in inputfilename. Stores the filtration in outputfilename with a VERTICES Format. 
./sophia cf inputfilename outputfilename
Builds the equivalent filtration of the tower, whose description is in inputfilename. Stores the filtration in outputfilename with a FACES Format. 
./sophia cp inputfilename outputfilename chunksize
Builds the equivalent filtration of the tower, whose description is in inputfilename and simultaneously computes its persistence diagram, using a chunk of size chunksize. Stores the persistence pairs in outputfilename. 
./sophia p inputfilename outputfilename chunksize
Computes the persistence diagram of the filtration, whose description is in inputfilename, using a chunk of size chunksize. The format of inputfilename needs to be the FACES Format. Stores the persistence pairs in outputfilename.
Two additional options can be activated (see section INSTALLATION). Note that they are thought to be more convenient and not efficient; they are often slower than using PHAT or Gudhi separately because the filtration is kept in memory:

./sophia cphat inputfilename outputfilename
Builds the equivalent filtration of the tower, whose description is in inputfilename. Then uses the PHAT library, with its default parameters, to compute its persistent diagram. Stores the persistence pairs in outputfilename, in the same output format PHAT uses, but without the first line. 
./sophia cgudhi inputfilename outputfilename
Builds the equivalent filtration of the tower, whose description is in inputfilename. Then uses the Gudhi library, with its default parameters, to compute its persistent diagram. Stores the persistence pairs in outputfilename, in the same output format Gudhi uses.
FILE FORMATS
For each file format, every simplex has an unique integer identifier. The identifiers are assigned to the simplices in increasing order by appearence, starting with 0.
In this section, "f^i" will always correspond to an identifier of a simplex and "v^i" more specifically to the identifier of a vertex.
The example files are in the "example" directory.
Tower Format
Options 1 to 3 and 5 to 6 use the same format to describe the input Tower: one line corresponds to one action. In a case of an inclusion of a dsimplex s:
[ts] i v^1 ... v^{d+1}
where v^i in s and for each i < j in {1,...,d+1}, v^i < v^j, and ts is an optional time indicator. If there is no time indication, time will start at 0 and increase by one at each insertion or contraction. In a case of a contraction:
[ts] c v^d v^k
where v^d and v^k are the vertices to be contracted. From here on, the remaining vertex needs to be refered by v^k and NOT v^d,
and ts is the optional time indicator.
It is possible to insert comments in the file by letting the comment line begin with '#'.
An example is file "example_tower.txt".
VERTICES Format
Each line corresponds to an inclusion of a dsimplex s:
d v^1 ... v^{d+1} ts
where v^i in s and for each i < j in {1,...,d+1}, v^i < v^j,
and ts corresponds to the time s was included.
It corresponds to the input format of Gudhi.
An example is file "example_vertices_filtration.txt".
FACES Format
Each line corresponds to either an inclusion of a dsimplex s:
ts i f^1 ... f^{d+1} f^s
where f^i is a face of s and for each i < j in {1,...,d+1}, f^i < f^j,
f^s is the identifier of s,
and ts corresponds to the time s was included.
Or signals the inactivity of a simplex s:
a f^s
where f^s is the identifier of s.
An example is file "example_faces_filtration.txt".
Persistence Pairs Format
Each line corresponds to one pair:
dim b d
where b is the birth time, d the death time and dim the dimension of the homology class.
An example is file "example_res.txt".