Performance of Zhang Tree Edit Distance

[stefanhahmann]

The computation of the Zhang Edit Distance of the trees 2aba and 1bab between timepoints 30 and 350 takes:

• with the BranchSpotTree implementation ~60.000ms
• with the SimpleTree implementation ~25.000ms
  both is too long.
  The purpose of this ticket is to improve this performance.

Mastodon file containing the two trees (amongst other):

• flatSim2_be_2.zip

• The SimpleTree implementation is contained in this code example:
  https://github.com/mastodon-sc/mastodon-deep-lineage/blob/master/src/test/java/org/mastodon/mamut/treesimilarity/tree/DenseSimpleTreeExamples.java

Tasks

• Add the optimization for building the flow network in case of binary trees
• Do further profiling
• Add further optimization if possible
• Find reason, why BranchSpotTree so much slower than SimpleTree implementation

[stefanhahmann]

Many of the trees used with the tree edit distance implementation inside Mastodon are binary trees. For these trees the max flow min cost algorithm can be simplified.