Skip to main content

A networkx implemention of algorithms to find common ordered subtree minors and isomorphisms

Project description

Pypi PypiDownloads GithubActions Codecov

Networkx algorithms for maximum common ordered subtree minors (or embedding) and maximum common subtree isomorphism. Contains pure python and cython optimized versions.

At its core the maximum_common_ordered_subtree_embedding function is an implementation of:

Lozano, Antoni, and Gabriel Valiente.
    "On the maximum common embedded subtree problem for ordered trees."
    String Algorithmics (2004): 155-170.
    https://pdfs.semanticscholar.org/0b6e/061af02353f7d9b887f9a378be70be64d165.pdf

And maximum_common_ordered_subtree_isomorphism is a variant of the above algorithm that returns common subtree ismorphism instead of subtree minors.

Standalone versions of code were originally submitted as PRs to networkx proper:

https://github.com/networkx/networkx/pull/4350 https://github.com/networkx/networkx/pull/4327

These algorithms are components of algorithms in torch_liberator, see related information:

TorchLiberator

https://gitlab.kitware.com/computer-vision/torch_liberator

Torch Hackathon 2021

Youtube Video and Google Slides

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

networkx_algo_common_subtree-0.2.1.tar.gz (85.1 kB view hashes)

Uploaded Source

Built Distributions

networkx_algo_common_subtree-0.2.1-cp312-cp312-win_amd64.whl (129.4 kB view hashes)

Uploaded CPython 3.12 Windows x86-64

networkx_algo_common_subtree-0.2.1-cp312-cp312-musllinux_1_1_x86_64.whl (173.5 kB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp312-cp312-musllinux_1_1_i686.whl (172.7 kB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (171.1 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp312-cp312-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (172.0 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp312-cp312-macosx_11_0_arm64.whl (138.5 kB view hashes)

Uploaded CPython 3.12 macOS 11.0+ ARM64

networkx_algo_common_subtree-0.2.1-cp312-cp312-macosx_10_9_x86_64.whl (145.3 kB view hashes)

Uploaded CPython 3.12 macOS 10.9+ x86-64

networkx_algo_common_subtree-0.2.1-cp311-cp311-win_amd64.whl (128.5 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

networkx_algo_common_subtree-0.2.1-cp311-cp311-musllinux_1_1_x86_64.whl (172.1 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp311-cp311-musllinux_1_1_i686.whl (174.3 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (171.9 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp311-cp311-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (173.6 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp311-cp311-macosx_11_0_arm64.whl (134.4 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

networkx_algo_common_subtree-0.2.1-cp311-cp311-macosx_10_9_x86_64.whl (143.2 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

networkx_algo_common_subtree-0.2.1-cp310-cp310-win_amd64.whl (128.3 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

networkx_algo_common_subtree-0.2.1-cp310-cp310-musllinux_1_1_x86_64.whl (172.2 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp310-cp310-musllinux_1_1_i686.whl (174.9 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (167.2 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (169.4 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp310-cp310-macosx_11_0_arm64.whl (134.9 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

networkx_algo_common_subtree-0.2.1-cp310-cp310-macosx_10_9_x86_64.whl (143.4 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

networkx_algo_common_subtree-0.2.1-cp39-cp39-win_amd64.whl (128.3 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

networkx_algo_common_subtree-0.2.1-cp39-cp39-musllinux_1_1_x86_64.whl (172.2 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp39-cp39-musllinux_1_1_i686.whl (174.9 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (167.1 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (169.3 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp39-cp39-macosx_11_0_arm64.whl (134.9 kB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

networkx_algo_common_subtree-0.2.1-cp39-cp39-macosx_10_9_x86_64.whl (143.4 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

networkx_algo_common_subtree-0.2.1-cp38-cp38-win_amd64.whl (128.7 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

networkx_algo_common_subtree-0.2.1-cp38-cp38-musllinux_1_1_x86_64.whl (166.7 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp38-cp38-musllinux_1_1_i686.whl (167.8 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (166.4 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (168.6 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp38-cp38-macosx_11_0_arm64.whl (135.3 kB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

networkx_algo_common_subtree-0.2.1-cp38-cp38-macosx_10_9_x86_64.whl (143.7 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

networkx_algo_common_subtree-0.2.1-cp37-cp37m-win_amd64.whl (130.2 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

networkx_algo_common_subtree-0.2.1-cp37-cp37m-musllinux_1_1_x86_64.whl (161.2 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

networkx_algo_common_subtree-0.2.1-cp37-cp37m-musllinux_1_1_i686.whl (162.1 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ i686

networkx_algo_common_subtree-0.2.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (160.9 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

networkx_algo_common_subtree-0.2.1-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (162.2 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

networkx_algo_common_subtree-0.2.1-cp37-cp37m-macosx_10_9_x86_64.whl (143.1 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

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