Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

multimatching-0.1.0.tar.gz (8.8 kB view details)

Uploaded Source

Built Distribution

multimatching-0.1.0-py3-none-any.whl (10.8 kB view details)

Uploaded Python 3

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

Hashes for multimatching-0.1.0.tar.gz
Algorithm Hash digest
SHA256 a0f903fc71ed2ccd5e6443aeb4fed9bd060f9d3ef960e048156575e7c5b6fecb
MD5 7ad68f6cf678f38584cd635b81cac041
BLAKE2b-256 25213e41bce5bd4e857135a896e7b98f0b1feacbf605e136d0369e7b9643f1a3

See more details on using hashes here.

File details

Details for the file multimatching-0.1.0-py3-none-any.whl.

File metadata

File hashes

Hashes for multimatching-0.1.0-py3-none-any.whl
Algorithm Hash digest
SHA256 c8ab21522a6fbc53650a85e58e41226189b08ba9b2d96611373cd4811aa0de78
MD5 497229c063919d48fb4a28c9399d7ba2
BLAKE2b-256 32466569306c0ba920a563028299e73b8ab1e5ded33a853d8ab238514e4b4b8e

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page