#include "genealgorithms.h"
#include "geneorder.h"
+#include "componenttree.h"
#include <algorithm>
#include <set>
}
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){
s = Sdir.top();
}
if (go[i] > 0 && dir[i] == dir[s] && static_cast<Gene>(i - s) == p[i] - p[s])
- components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s])));
+ components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s]),s,i));
//Reverse
if (p[i-1] < p[i])
s = Srev.top();
}
if (go[i] < 0 && rev[i] == rev[s] && static_cast<Gene>(i - s) == p[s] - p[i])
- components.push_back(Component(-p[s],-p[i],(s+1 == i ? 0 : os[s])));
+ components.push_back(Component(-p[s],-p[i],(s+1 == i ? 0 : os[s]),s,i));
//Update stacks
if (go[i] > 0)