A Python package for computing bottleneck distance.
Project description
Multimatching
A Python package for computing the bottleneck distance between persistence diagrams. It is optimized for diagrams in which the points have multiplicity.
Basic explanation of algorithm
The basic pattern for the algorithm resembles the approach in the persim
package.
Instead of using the Hopcroft-Karp algorithm to check for a perfect matching at a given scale, we instead solve a maximum flow problem where the capacities are determined by the multiplicities.
Steps:
- We first compute the pairwise distances between points, adding a dummy point to each set for the diagonal.
- Then, we do a binary search for the bottleneck distance. At each scale $\delta$ , we do the following
- Construct a $\delta$-neighborhood graph.
- We create a dummy sink and source vertex
- Create edges from source to points in diagram A
- Create edges from source to points in diagram B
- Add edges with the diagonal such as: sink, source, and diagonal to diagonal
- For all edges, the capacity is the minimum multiplicity of the endpoints.
- Compute a maximum flow in the graph.
- If the total flow corresponds to the total multiplicity of the diagrams, then we search try a smaller scale. Otherwise, we try a larger scale.
Examples
Example without multiplicity:
Diagram A with points (3, 6), (1, 2), (6, 18), (1, 3)
Diagram B with points (4, 6), (7, 21)
Output of bottleneck distance: 3.0
Example with multiplicity:
Diagram A with point (0, 6), and multiplicity 1000000000
This means that there are 1000000000 copies of (0,6)
Diagram B with point (1, 6), and multiplicity 1000000000
Output of bottleneck distance: 1.0
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file multimatching-0.1.0.tar.gz
.
File metadata
- Download URL: multimatching-0.1.0.tar.gz
- Upload date:
- Size: 8.8 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.9.13
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | a0f903fc71ed2ccd5e6443aeb4fed9bd060f9d3ef960e048156575e7c5b6fecb |
|
MD5 | 7ad68f6cf678f38584cd635b81cac041 |
|
BLAKE2b-256 | 25213e41bce5bd4e857135a896e7b98f0b1feacbf605e136d0369e7b9643f1a3 |
File details
Details for the file multimatching-0.1.0-py3-none-any.whl
.
File metadata
- Download URL: multimatching-0.1.0-py3-none-any.whl
- Upload date:
- Size: 10.8 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.1 CPython/3.9.13
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8ab21522a6fbc53650a85e58e41226189b08ba9b2d96611373cd4811aa0de78 |
|
MD5 | 497229c063919d48fb4a28c9399d7ba2 |
|
BLAKE2b-256 | 32466569306c0ba920a563028299e73b8ab1e5ded33a853d8ab238514e4b4b8e |