Metadata-Version: 2.2
Name: networkx_algo_common_subtree
Version: 0.2.2
Summary: A networkx implemention of algorithms to find common ordered subtree minors and isomorphisms
Home-page: https://github.com/Erotemic/networkx_algo_common_subtree
Author: Jon Crall
Author-email: erotemic@gmail.com
License: Apache 2
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: Utilities
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Requires-Python: >=3.8
Description-Content-Type: text/x-rst
Requires-Dist: networkx>=2.7; python_version < "4.0" and python_version >= "3.11"
Requires-Dist: networkx>=2.7; python_version < "3.11" and python_version >= "3.10"
Requires-Dist: networkx<3.0,>=2.7; python_version < "3.10" and python_version >= "3.9"
Requires-Dist: networkx<3.0,>=2.7; python_version < "3.9" and python_version >= "3.8"
Requires-Dist: networkx<3.0,>=2.6.2; python_version < "3.8" and python_version >= "3.7"
Requires-Dist: networkx<3.0,>=2.5.1; python_version < "3.7" and python_version >= "3.6"
Provides-Extra: all
Requires-Dist: networkx>=2.7; (python_version < "4.0" and python_version >= "3.11") and extra == "all"
Requires-Dist: networkx>=2.7; (python_version < "3.11" and python_version >= "3.10") and extra == "all"
Requires-Dist: networkx<3.0,>=2.7; (python_version < "3.10" and python_version >= "3.9") and extra == "all"
Requires-Dist: networkx<3.0,>=2.7; (python_version < "3.9" and python_version >= "3.8") and extra == "all"
Requires-Dist: networkx<3.0,>=2.6.2; (python_version < "3.8" and python_version >= "3.7") and extra == "all"
Requires-Dist: networkx<3.0,>=2.5.1; (python_version < "3.7" and python_version >= "3.6") and extra == "all"
Requires-Dist: xdoctest>=1.1.3; extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "4.0" and python_version >= "3.13") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.13" and python_version >= "3.12") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.12" and python_version >= "3.11") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.11" and python_version >= "3.10") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.10" and python_version >= "3.9") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.9" and python_version >= "3.8") and extra == "all"
Requires-Dist: pytest>=7.4.4; (python_version < "3.8" and python_version >= "3.7") and extra == "all"
Requires-Dist: pytest>=6.2.5; (python_version < "3.7" and python_version >= "3.6") and extra == "all"
Requires-Dist: pytest-cov>=3.0.0; python_version >= "3.6.0" and extra == "all"
Requires-Dist: coverage[toml]>=7.3.0; (python_version < "4.0" and python_version >= "3.12") and extra == "all"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.12" and python_version >= "3.10") and extra == "all"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.10" and python_version >= "3.9") and extra == "all"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.9" and python_version >= "3.8") and extra == "all"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.8" and python_version >= "3.7") and extra == "all"
Requires-Dist: coverage[toml]>=6.1.1; (python_version < "3.7" and python_version >= "3.6") and extra == "all"
Requires-Dist: ubelt>=1.3.4; extra == "all"
Requires-Dist: scikit-build>=0.11.1; extra == "all"
Requires-Dist: ninja>=1.10.2; extra == "all"
Requires-Dist: cmake>=3.21.2; extra == "all"
Requires-Dist: cython>=0.29.24; extra == "all"
Provides-Extra: runtime
Requires-Dist: networkx>=2.7; (python_version < "4.0" and python_version >= "3.11") and extra == "runtime"
Requires-Dist: networkx>=2.7; (python_version < "3.11" and python_version >= "3.10") and extra == "runtime"
Requires-Dist: networkx<3.0,>=2.7; (python_version < "3.10" and python_version >= "3.9") and extra == "runtime"
Requires-Dist: networkx<3.0,>=2.7; (python_version < "3.9" and python_version >= "3.8") and extra == "runtime"
Requires-Dist: networkx<3.0,>=2.6.2; (python_version < "3.8" and python_version >= "3.7") and extra == "runtime"
Requires-Dist: networkx<3.0,>=2.5.1; (python_version < "3.7" and python_version >= "3.6") and extra == "runtime"
Provides-Extra: tests
Requires-Dist: xdoctest>=1.1.3; extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "4.0" and python_version >= "3.13") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.13" and python_version >= "3.12") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.12" and python_version >= "3.11") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.11" and python_version >= "3.10") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.10" and python_version >= "3.9") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.9" and python_version >= "3.8") and extra == "tests"
Requires-Dist: pytest>=7.4.4; (python_version < "3.8" and python_version >= "3.7") and extra == "tests"
Requires-Dist: pytest>=6.2.5; (python_version < "3.7" and python_version >= "3.6") and extra == "tests"
Requires-Dist: pytest-cov>=3.0.0; python_version >= "3.6.0" and extra == "tests"
Requires-Dist: coverage[toml]>=7.3.0; (python_version < "4.0" and python_version >= "3.12") and extra == "tests"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.12" and python_version >= "3.10") and extra == "tests"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.10" and python_version >= "3.9") and extra == "tests"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.9" and python_version >= "3.8") and extra == "tests"
Requires-Dist: coverage[toml]>=6.5.0; (python_version < "3.8" and python_version >= "3.7") and extra == "tests"
Requires-Dist: coverage[toml]>=6.1.1; (python_version < "3.7" and python_version >= "3.6") and extra == "tests"
Requires-Dist: ubelt>=1.3.4; extra == "tests"
Provides-Extra: optional
Provides-Extra: build
Requires-Dist: scikit-build>=0.11.1; extra == "build"
Requires-Dist: ninja>=1.10.2; extra == "build"
Requires-Dist: cmake>=3.21.2; extra == "build"
Requires-Dist: cython>=0.29.24; extra == "build"
Provides-Extra: docs
Requires-Dist: sphinx>=5.0.1; extra == "docs"
Requires-Dist: sphinx-autobuild>=2021.3.14; extra == "docs"
Requires-Dist: sphinx_rtd_theme>=1.0.0; extra == "docs"
Requires-Dist: sphinxcontrib-napoleon>=0.7; extra == "docs"
Requires-Dist: sphinx-autoapi>=1.8.4; extra == "docs"
Requires-Dist: Pygments>=2.9.0; extra == "docs"
Requires-Dist: myst_parser>=0.18.0; extra == "docs"
Requires-Dist: sphinx-reredirects>=0.0.1; extra == "docs"
Provides-Extra: all-strict
Requires-Dist: networkx==2.7; (python_version < "4.0" and python_version >= "3.11") and extra == "all-strict"
Requires-Dist: networkx==2.7; (python_version < "3.11" and python_version >= "3.10") and extra == "all-strict"
Requires-Dist: networkx<3.0,==2.7; (python_version < "3.10" and python_version >= "3.9") and extra == "all-strict"
Requires-Dist: networkx<3.0,==2.7; (python_version < "3.9" and python_version >= "3.8") and extra == "all-strict"
Requires-Dist: networkx<3.0,==2.6.2; (python_version < "3.8" and python_version >= "3.7") and extra == "all-strict"
Requires-Dist: networkx<3.0,==2.5.1; (python_version < "3.7" and python_version >= "3.6") and extra == "all-strict"
Requires-Dist: xdoctest==1.1.3; extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "4.0" and python_version >= "3.13") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.13" and python_version >= "3.12") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.12" and python_version >= "3.11") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.11" and python_version >= "3.10") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.10" and python_version >= "3.9") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.9" and python_version >= "3.8") and extra == "all-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.8" and python_version >= "3.7") and extra == "all-strict"
Requires-Dist: pytest==6.2.5; (python_version < "3.7" and python_version >= "3.6") and extra == "all-strict"
Requires-Dist: pytest-cov==3.0.0; python_version >= "3.6.0" and extra == "all-strict"
Requires-Dist: coverage[toml]==7.3.0; (python_version < "4.0" and python_version >= "3.12") and extra == "all-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.12" and python_version >= "3.10") and extra == "all-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.10" and python_version >= "3.9") and extra == "all-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.9" and python_version >= "3.8") and extra == "all-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.8" and python_version >= "3.7") and extra == "all-strict"
Requires-Dist: coverage[toml]==6.1.1; (python_version < "3.7" and python_version >= "3.6") and extra == "all-strict"
Requires-Dist: ubelt==1.3.4; extra == "all-strict"
Requires-Dist: scikit-build==0.11.1; extra == "all-strict"
Requires-Dist: ninja==1.10.2; extra == "all-strict"
Requires-Dist: cmake==3.21.2; extra == "all-strict"
Requires-Dist: cython==0.29.24; extra == "all-strict"
Provides-Extra: runtime-strict
Requires-Dist: networkx==2.7; (python_version < "4.0" and python_version >= "3.11") and extra == "runtime-strict"
Requires-Dist: networkx==2.7; (python_version < "3.11" and python_version >= "3.10") and extra == "runtime-strict"
Requires-Dist: networkx<3.0,==2.7; (python_version < "3.10" and python_version >= "3.9") and extra == "runtime-strict"
Requires-Dist: networkx<3.0,==2.7; (python_version < "3.9" and python_version >= "3.8") and extra == "runtime-strict"
Requires-Dist: networkx<3.0,==2.6.2; (python_version < "3.8" and python_version >= "3.7") and extra == "runtime-strict"
Requires-Dist: networkx<3.0,==2.5.1; (python_version < "3.7" and python_version >= "3.6") and extra == "runtime-strict"
Provides-Extra: tests-strict
Requires-Dist: xdoctest==1.1.3; extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "4.0" and python_version >= "3.13") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.13" and python_version >= "3.12") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.12" and python_version >= "3.11") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.11" and python_version >= "3.10") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.10" and python_version >= "3.9") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.9" and python_version >= "3.8") and extra == "tests-strict"
Requires-Dist: pytest==7.4.4; (python_version < "3.8" and python_version >= "3.7") and extra == "tests-strict"
Requires-Dist: pytest==6.2.5; (python_version < "3.7" and python_version >= "3.6") and extra == "tests-strict"
Requires-Dist: pytest-cov==3.0.0; python_version >= "3.6.0" and extra == "tests-strict"
Requires-Dist: coverage[toml]==7.3.0; (python_version < "4.0" and python_version >= "3.12") and extra == "tests-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.12" and python_version >= "3.10") and extra == "tests-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.10" and python_version >= "3.9") and extra == "tests-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.9" and python_version >= "3.8") and extra == "tests-strict"
Requires-Dist: coverage[toml]==6.5.0; (python_version < "3.8" and python_version >= "3.7") and extra == "tests-strict"
Requires-Dist: coverage[toml]==6.1.1; (python_version < "3.7" and python_version >= "3.6") and extra == "tests-strict"
Requires-Dist: ubelt==1.3.4; extra == "tests-strict"
Provides-Extra: optional-strict
Provides-Extra: build-strict
Requires-Dist: scikit-build==0.11.1; extra == "build-strict"
Requires-Dist: ninja==1.10.2; extra == "build-strict"
Requires-Dist: cmake==3.21.2; extra == "build-strict"
Requires-Dist: cython==0.29.24; extra == "build-strict"
Provides-Extra: docs-strict
Requires-Dist: sphinx==5.0.1; extra == "docs-strict"
Requires-Dist: sphinx-autobuild==2021.3.14; extra == "docs-strict"
Requires-Dist: sphinx_rtd_theme==1.0.0; extra == "docs-strict"
Requires-Dist: sphinxcontrib-napoleon==0.7; extra == "docs-strict"
Requires-Dist: sphinx-autoapi==1.8.4; extra == "docs-strict"
Requires-Dist: Pygments==2.9.0; extra == "docs-strict"
Requires-Dist: myst_parser==0.18.0; extra == "docs-strict"
Requires-Dist: sphinx-reredirects==0.0.1; extra == "docs-strict"
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: license
Dynamic: provides-extra
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

The networkx_algo_common_subtree Module
=======================================

|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:

.. code::

    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.


Demo
----

Consider two directed ordered trees (the algorithm also works on undirected
ordered trees):

.. code:: python

    >>> import networkx as nx
    >>> tree1 = nx.DiGraph()
    >>> tree2 = nx.DiGraph()
    >>> tree1.add_edges_from([(0, 2), (5, 7), (5, 4), (5, 3), (2, 5), (2, 6), (3, 1)])
    >>> tree2.add_edges_from([(0, 6), (0, 1), (1, 5), (6, 2), (5, 4), (5, 3), (5, 7)])
    >>> print('Tree 1:')
    >>> nx.write_network_text(tree1)
    >>> print('Tree 2:')
    >>> nx.write_network_text(tree2)
    Tree 1:
    ╙── 0
        └─╼ 2
            ├─╼ 5
            │   ├─╼ 7
            │   ├─╼ 4
            │   └─╼ 3
            │       └─╼ 1
            └─╼ 6
    Tree 2:
    ╙── 0
        ├─╼ 6
        │   └─╼ 2
        └─╼ 1
            └─╼ 5
                ├─╼ 4
                ├─╼ 3
                └─╼ 7


The maximum common ordered isomorphism (a strict common subtree structure) is:

.. code:: python

    >>> import networkx_algo_common_subtree
    >>> subtree1, subtree2, score = networkx_algo_common_subtree.maximum_common_ordered_subtree_isomorphism(tree1, tree2)
    >>> print(f'{score=}')
    >>> print('Isomorphic Subtree 1:')
    >>> nx.write_network_text(subtree1)
    >>> print('Isomorphic Subtree 2:')
    >>> nx.write_network_text(subtree2)
    score=3
    Isomorphic Subtree 1:
    ╙── 5
        ├─╼ 4
        └─╼ 3
    Isomorphic Subtree 2:
    ╙── 5
        ├─╼ 4
        └─╼ 3

The biggest common structure between both of the original trees is the subtree
involving 5, 3, 4. Notice that the (5, 7) edge is not included because these
are **ordered** subtrees. In tree 1, the (5, 7) edge is before the (5, 4) edge
and in the second it is after it, so it is not included because the edges are
not in the same order.


This substructure can be generalized by allowing edges in the original graphs
to be collapsed, which can produce larger common substructures. This is the
maximum common ordered embedding.

.. code:: python

    >>> import networkx_algo_common_subtree
    >>> subtree1, subtree2, score = networkx_algo_common_subtree.maximum_common_ordered_subtree_embedding(tree1, tree2)
    >>> print(f'{score=}')
    >>> print('Embedded Subtree 1:')
    >>> nx.write_network_text(subtree1)
    >>> print('Embedded Subtree 2:')
    >>> nx.write_network_text(subtree2)
    score=4
    Embedded Subtree 1:
    ╙── 0
        └─╼ 5
            ├─╼ 4
            └─╼ 3
    Embedded Subtree 2:
    ╙── 0
        └─╼ 5
            ├─╼ 4
            └─╼ 3

In this example, the edges (0, 2) and (2, 5) in first tree were collapsed into
(0, 5). Similarly in the second tree the edges (0, 1) and (1, 5) were collapsed
into (0, 5), thus increasing the size of the common ordered subtree.

Other Information
-----------------

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

However, these algorithms are roughly ``O(N⁴)``, they require a a fast binary
(e.g. C / cython) implementation to work on graphs of reasonable size. Thus
they are unlikely to be added to mainline networkx.


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`_                      |
+----------------------+------------------------------------------------------------+

.. _Youtube Video: https://www.youtube.com/watch?v=GQqtn61iNsc
.. _Google Slides: https://docs.google.com/presentation/d/1w9XHkPjtLRj29dw50WP0rSHRRlEfhksP_Sf8XldTSYE




.. |Pypi| image:: https://img.shields.io/pypi/v/networkx_algo_common_subtree.svg
    :target: https://pypi.python.org/pypi/networkx_algo_common_subtree

.. |PypiDownloads| image:: https://img.shields.io/pypi/dm/networkx_algo_common_subtree.svg
    :target: https://pypistats.org/packages/networkx_algo_common_subtree

.. |GithubActions| image:: https://github.com/Erotemic/networkx_algo_common_subtree/actions/workflows/tests.yml/badge.svg?branch=main
    :target: https://github.com/Erotemic/networkx_algo_common_subtree/actions?query=branch%3Amain

.. |Codecov| image:: https://codecov.io/github/Erotemic/networkx_algo_common_subtree/badge.svg?branch=main&service=github
    :target: https://codecov.io/github/Erotemic/networkx_algo_common_subtree?branch=main
