amnh / PCG

𝙋𝙝𝙮𝙡𝙤𝙜𝙚𝙣𝙚𝙩𝙞𝙘 𝘾𝙤𝙢𝙥𝙤𝙣𝙚𝙣𝙩 𝙂𝙧𝙖𝙥𝙝 ⸺ Haskell program and libraries for general phylogenetic graph search
28 stars 1 forks source link

Improve Wagner build performace by adding virtual node data to edges labels #82

Closed recursion-ninja closed 5 years ago

recursion-ninja commented 5 years ago

The Wagner build is currently very slow because all information from the previous tree is discarded when build the new candidate trees. We can improve this by adding a virtual node datum on each edge and compare adding a new node on that edge by using the postorder logic between the virtual node datum and the new leaf node datum to get the cost of adding that leaf node on that edge without rebuilding the whole tree. This will improve performance by an order of magnitude.

recursion-ninja commented 5 years ago

The Wagner build implementation has been improved to reduce the asymptotic runtime from O(n^3) to O(n^2). See 59c4f2d52d88f23c0338db2a7acafb5a2f474c37.