From 1fb658ea3ad9dc286e95ec515d7c90f5ad2d4a1f Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Thu, 16 Aug 2007 09:17:46 +0000 Subject: [PATCH] calculate the proper distance, with hurdles --- src/genealgorithms.cpp | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp index 174c6f7..3fb2aaa 100644 --- a/src/genealgorithms.cpp +++ b/src/genealgorithms.cpp @@ -94,9 +94,20 @@ size_t countCycles(const GeneOrder& go){ } size_t inversionDistance(const GeneOrder& go){ - size_t cycles = countCycles(go); + size_t distance = go.size() - 1; + distance -= countCycles(go); + + ComponentTree t(findComponents(go)); + t.makeUnoriented(); + size_t leaves = t.countLeaves(); + distance += leaves; + if (leaves % 2 != 0){ + size_t sb = t.shortBranches(); + if (sb == 0) + distance += 1; + } - return go.size() - 1 - cycles; + return distance; } int sign(Gene g){ -- 2.39.2