-
Notifications
You must be signed in to change notification settings - Fork 0
/
tournser_documentation.tex
195 lines (161 loc) · 8.38 KB
/
tournser_documentation.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
\documentclass{amsart}
\usepackage[utf8]{inputenc}
\usepackage[margin=.9in]{geometry}
\usepackage[]{amsmath}
\usepackage{amsthm}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{exscale}
\usepackage{textcomp}
\usepackage[all,ps,tips,tpic]{xy}
\usepackage{upgreek}
\usepackage{url}
\usepackage{booktabs}
\usepackage[final,pdftex,colorlinks=false,pdfborder={0 0 0}]{hyperref}
\usepackage{microtype}
\usepackage{verbatim}
\usepackage{soul}
\usepackage{tikz}
\pagenumbering{gobble}
\theoremstyle{definition}
\newtheorem*{example*}{Example}
\newcommand{\sd}{\operatorname{\mathrm{sd}}}
%spacing around left-right brackets
\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}
\begin{document}
\title{Documentation: tournser}
\author{Jason P. Smith}
\address{University of Aberdeen, Aberdeen, United Kingdom}
\email{jason.smith@abdn.ac.uk}
\maketitle
\noindent
The software \textsc{tournser} is designed for the computation of persistent
homology for tournaplexes with different filtrations, see for \href{https://arxiv.org/abs/2003.00324}{here} for the background.
\textsc{Tournser} is an adaptation of \href{https://github.com/luetge/flagser}{\textsc{flagser}}
which in turn is an adaptation of Ulrich Bauer's
\href{https://github.com/Ripser/ripser}{\textsc{ripser}}.
An online version of tournser is available \href{https://homepages.abdn.ac.uk/neurotopology/tournser.html}{here}.
\section{Compiling the source code}
\noindent
\textsc{Tournser} requires a C++14 compiler.
For Linux or Mac (Windows is currently not supported) open the terminal, change into the \textsc{tournser} main directory and execute
\vspace{1em}
\begin{verbatim}c++ tournser.cpp -o tournser -std=c++14 -pthread -O3\end{verbatim}
\vspace{1em}
\section{Usage}
\noindent
After building \textsc{tournser}, you can compute persistent homology as follows:
\vspace{1em}
\begin{verbatim}./tournser in_file_address out_file_address [options]\end{verbatim}
\vspace{1em}
For example:
\vspace{1em}
\begin{verbatim}./tournser ./Examples/test.trn ./Examples/test.homology --filtration relative\end{verbatim}
\vspace{1em}
\noindent
The following \texttt{[options]} exist:
\enlargethispage{\baselineskip}
\begin{description}
\item [-{}-filtration] One of the following which gives filtration value $F(\sigma)$ to simplex $\sigma$:
\begin{itemize}
\item \emph{local}: $F(\sigma)=2\binom{n}{3}+\sum_{v\in \sigma}(\sd_\sigma(v))^2$
\item \emph{global}: $F(\sigma)=\sum_{v\in \sigma}(\sd_\mathcal{G}(v))^2$
\item \emph{3cycle}: $F(\sigma)=$ Number of directed 3-cycles in $\sigma$
\item \emph{vertexMax}: $F(\sigma)=\max_{v\in\sigma}(F(v))$
\item \emph{vertexSum}: $F(\sigma)=\sum_{v\in\sigma}F(v)$
\item \emph{edgeMax}: $F(\sigma)=\max_{e\in K_1(\sigma)}(F(e))$
\item \emph{natural}: $F(\sigma)=\sum_{v\in \sigma}(\sd_\sigma(v))^2+\max_{b\in bdry(\sigma)}F(b)$
\item \emph{natural-max}: $F(\sigma)=\max(\sum_{v\in \sigma}(\sd_\sigma(v))^2,\max_{b\in bdry(\sigma)}F(b))$
\end{itemize}
where $sd_X(v)=indeg_X(v)-outdeg_X(v)$ and $indeg_X(v)$ is the indegree of vertex $v$ in the digraph $X$.
\item [-{}-max-dim \textit{dim}] the maximal homology dimension to be computed
\item [-{}-min-dim \textit{dim}] the minimal homology dimension to be computed
\item [-{}-print\_dist true] Prints the distribution of the filtration values
\item [-{}-count\_only true] Computes only the simplex counts and skips all homology computations
\item [-{}-print print\_address] Prints the whole tournaplex to a file, see below for format.
\item [-{}-approximate \textit{n}] skip all cells creating columns in the reduction matrix with
more than $n$ entries. Use this for hard problems, a good value is often 100000. Increase for
higher precision, decrease for faster computation. This function is taken from \textsc{flagser}, see for \href{https://www.mdpi.com/1999-4893/13/1/19}{this article} more information.
\end{description}
\vspace{1em}
\newpage
\subsection{Input Format}
\noindent
The input file defines the directed graph and must have the following shape:
\vspace{.5em}
\begin{verbatim}
dim 0:
weight_vertex_0 weight_vertex_1 ... weight_vertex_n
dim 1:
first_vertex_id_of_edge_0 second_vertex_id_of_edge_0 [weight_edge_0]
first_vertex_id_of_edge_1 second_vertex_id_of_edge_1 [weight_edge_1]
...
first_vertex_id_of_edge_m second_vertex_id_of_edge_m [weight_edge_m]
\end{verbatim}
\vspace{.5em}
\noindent
The edges are oriented to point from the first vertex to the second vertex, the weights of the edges
are optional.
The weights should be rational numbers.
Important: the input graphs can not contain self-loops, i.e.\ edges that start and end in the same vertex.
\begin{example*}
The full directed graph on three vertices without explicit edge weights is described by the
following input file:
\vspace{.5em}
\begin{verbatim}
dim 0:
0.2 0.522 4.9
dim 1:
0 1
1 0
0 2
2 0
1 2
2 1
\end{verbatim}
\end{example*}
\subsection{Print Tournaplex}
Using the option \textbf{-{}-print print\_address} will print the whole tournaplex to a file, where each simplex is written as a line with the following information:
\begin{itemize}
\item \emph{Vrts}: This is the vertices of the simplex
\item \emph{bdry}: This is the boundary of the simplex, where each number corresponds to the simplex in the dimension below which has that ``loc" value
\item \emph{cbdry}: This is the coboundary of the simplex, where each number corresponds to the simplex in the dimension above which has that ``loc" value
\item \emph{filt}: The filtration value of the simplex
\item \emph{ort}: The orientation of the edges of the tournament represented as a lower triangular matrix $M$, where the first entry is $M_{1,0}$ and each row is separated by :,
where $$M_{i,j}=\begin{cases}0,&\mbox{ if }i\rightarrow j\\1,&\mbox{ if }i\leftarrow j\end{cases}$$
\item \emph{loc}: The location (or index) of the simplex, i.e all simplices in dimension $k$ are numbered $0$ to $n_k$.
\end{itemize}
For example:
\begin{verbatim}
Vrts = 0 1 3 | bdry = 5 2 3 | cbdry = 1 3 | ort = 0 : 1 1 : | filt = 4 | loc = 5
\end{verbatim}
Corresponds to the simplex in dimension 2 which is given by the tournament $$\begin{tikzpicture}[scale=.75]
\node[circle, draw=black,inner sep=1pt] (0) at (0,0){$0$};
\node[circle, draw=black,inner sep=1pt] (1) at (1,0){$1$};
\node[circle, draw=black,inner sep=1pt] (3) at (.5,1){$3$};
\draw[->] (1) -- (0);
\draw[->] (0) -- (3);
\draw[->] (1) -- (3);
\end{tikzpicture}$$
and this simplex has three faces in its boundary and two in its coboundary, has filtration value $4$ and is the $5$'th face of dimension 2
\pagebreak
\subsection{pytournser}
Also included here is a python wrapper for tournser. To use \textit{pytournser}, first ensure it is installed (see README), then open python and load the package with:
\begin{verbatim}from pytournser import *\end{verbatim}
Then simply call:
\begin{verbatim}X=tournser(V,M)\end{verbatim}
Where $M$ is the adjacency matrix of the graph to consider as a numpy array (with entries the filtration values of the edges, which cannot be $0$), and V is a vector of the vertex filtration values. The optional entries are:
\begin{verbatim}tournser(vertex_values, adjacency_matrix, filtration='vertexMax', approx=False,\end{verbatim}
\begin{verbatim}approx_val=100000, count_only=False)\end{verbatim}
where filtration, approx\_val and count\_only are the same as the C++ version of tournser, and approx indicates whether or not to use the approx value. The output of the tournser function is a dictionary with entries: `cell\_counts', `finite\_pairs', `infinte\_pairs' and `bettis'. Where the i'th entry of each corresponds to the i'th dimension. And an entry of infinite pairs is a single number denoting the birth time of the pair.
Also available is tournser\_file and tournser\_edge which have the arguments:
\begin{verbatim}tournser_file(in_file, filtration='vertexMax', approx=False, approx_val=100000, count_only=False)\end{verbatim}
\begin{verbatim}tournser_edges(vertex_values, edge_list, filtration='vertexMax', approx=False,\end{verbatim}
\begin{verbatim}approx_val=100000, count_only=False)\end{verbatim}
where edge list is a $m\times2$ or $m\times 3$ numpy array, where the third entry of each row is the optional filtration value. And in\_file is the address of a .trn file.
\vfill
\end{document}