Package jazzparser :: Package misc :: Package tree :: Module lces
[hide private]
[frames] | no frames]

Module lces

source code

Largest Common Embeddable Subtree.

Implementation of the algorithm from On the Maximum Common Embedded Subtree Problem for Ordered Trees by Loxano and Valiente. This is for unlabeled, ordered trees.


Author: Mark Granroth-Wilding <mark.granroth-wilding@ed.ac.uk>

Functions [hide private]
 
lces_size(tree1, tree2)
Computes the size of the largest common embedded subtree for two unlabeled trees.
source code
 
lces(tree1, tree2)
Computes the largest common embedded subtree for two unlabeled trees.
source code
Variables [hide private]
  __package__ = 'jazzparser.misc.tree'
Function Details [hide private]

lces_size(tree1, tree2)

source code 

Computes the size of the largest common embedded subtree for two unlabeled trees. It is quicker to compute the size than to compute the common tree itself, so this function doesn't actually compute what the tree is.

lces(tree1, tree2)

source code 

Computes the largest common embedded subtree for two unlabeled trees. Even you only need to know the size, use lces_size, since it's a slightly simpler problem.