• Python Wrapper for Fast Computation of Zigzag Persistence
  • Features
  • Getting Started
    • Prerequisites
    • Installation
      • For Mac Users
      • For Linux Users (Ubuntu as an example)
      • For Windows Users
    • Verify Installation
  • Usage
    • Selecting the Algorithm
    • Within Python
    • From a Filtration File
  • Citation
  • License

Python Wrapper for Fast Computation of Zigzag Persistence

This repository provides a Python wrapper for Fast Computation of Zigzag Persistence, originally implemented in C++ based on a Fast Zigzag algorithm developed by Dey and Hou in the paper

Fast Computation of Zigzag Persistence, Proc. 30th European Symposium on Algorithms (ESA 2022), Vol. 244 of LIPIcs, pages 43:1--43:15. ArXiv preprint: arXiv:2204.11080(2022).

Please note that official Python bindings have been made available as of 2023.10.01.

Features

• Easy Usage: Seamlessly utilize the power of the C++ implementation directly within Python.
• Flexible Algorithm Selection: Choose from the five algorithms available in phat for computation.

Getting Started

Prerequisites

Software	Version	Description
CMake	>= 3.5	Build tool
Boost	>= 1.5	C++ libraries
PHAT	1.4 - 1.5	Included as a submodule in /libs/phat
OpenMP	>= 5.0 (201811 or higher)	For parallel computation
pybind11	>=2.10	C++ and Python bindings

• phat is included as a submodule.
• OpenMP will be automatically installed if installing llvm and using clang as the compiler.
• You can change the directory path of PHAT in CMakeLists.txt if you would like to use a different version of PHAT.

Installation

We use clang as the compiler and use llvm. Please follow the instructions below to install the required dependencies based on your operating system.

Clone this repository:

git clone --recursive https://github.com/CommutativeGrids/fzzpy.git

Note: The --recursive flag ensures that submodules (like PHAT) are also cloned.

Following the guidelines below to install the required dependencies based on your operating system. Then navigate to the directory and install the Python package, the installation configuration is specified in pyproject.toml:

pip install .

For Mac Users

If you encounter issues with OpenMP not being found even after installation, it might be because Apple's default Clang does not come with OpenMP support. In such cases, you can use the LLVM version of Clang provided by Homebrew which includes OpenMP.

1. First, ensure we have the LLVM package installed:

   brew install llvm

2. After installing LLVM via Homebrew, set the CC and CXX environment variables to point to the Clang binaries provided by LLVM, the location of llvm can be obtained by running brew info llvm. The the compiler binaries are located in the bin directory of the installation path. For example, if the installation path is /opt/homebrew/opt/llvm, then the compiler binaries are located in /opt/homebrew/opt/llvm/bin. Then, set the environment variables as follows:

   export CC=/opt/homebrew/opt/llvm/bin/clang
   export CXX=/opt/homebrew/opt/llvm/bin/clang++

The export commands above are only valid for the current terminal session.

For Linux Users (Ubuntu as an example)

We still use clang as the compiler and use llvm. Run the following commands to install the required dependencies:

sudo apt update
sudo apt install clang llvm
sudo apt-get install libc++-dev libc++abi-dev
export CXXFLAGS="-stdlib=libc++"
export CC=clang
export CXX=clang++

The export commands above are only valid for the current terminal session. You can also uninstall the dependencies by running sudo apt remove clang llvm libc++-dev libc++abi-dev after the installation.

For Windows Users

We encourage Windows users to use WSL to install this package.

Verify Installation

Run the codes examples/installation_verification.ipynb to verify the installation.

Usage

Selecting the Algorithm

The algorithm is specified via the algorithm parameter in the compute function. The following algorithms are available:

• chunk_reduction
• row_reduction
• spectral_sequence_reduction
• standard_reduction
• twist_reduction By default, the chunk_reduction algorithm is used. For more details about the algorithms, please refer to phat 1.5

Within Python

Please also check the example in examples/installation_verification.ipynb.

Input:

• filt_simp: A list of tuples. Each tuple at index $k$ representing a simplex to be inserted or deleted in the $k$-th step
• filt_op: A list of booleans. Each boolean at index $k$ representing whether the simplex at index $k$ in filt_simp is inserted or deleted in the $k$-th step

from fzzpy import compute

# Define your filtration simplicities and filtration operations
filt_simp = [[0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2], [0, 1, 2], [1, 2], [0, 1]]
filt_op = [True, True, True, True, True, True, True, False, False, False]

# Compute persistence
result = compute(filt_simp, filt_op)

# Print the result
print(result)
# [(0, 2, 3), (0, 3, 4), (1, 6, 6), (0, 1, 10), (0, 10, 10), (1, 8, 8)]

From a Filtration File

Can read in a filtration file in the format as specified in fzz. Please also refer to the example in examples/sample_filtration.ipynb.

With filtration.txt:

i 0
i 1
i 2
i 0 1
i 0 2
i 1 2
i 0 1 2
d 0 1 2
d 1 2
d 0 1

from fzzpy import compute, parse_filtration_file, write_persistence_intervals

# Read the filtration file
filt_simp, filt_op = parse_filtration_file("filtration.txt")

# Compute persistence
result = compute(filt_simp, filt_op)

# Write the results to another file
write_persistence_intervals(result, "output_intervals.txt")

This then generate a file following the format specified in fzz.

Citation

If you use this software in your research, please consider citing the original paper on which this implementation is based: Fast Computation of Zigzag Persistence. Please refer to the readme of the fzz repository for more details.

License

This project is a wrapper around the fzz library. We do not introduce any new licensing terms. Please refer to the original license of the fzz project for usage terms and conditions.