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:
networkx/networkx#4350 networkx/networkx#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 |