good to have a inversion distance function

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 7f54109dc6c0103251cafff77bef93d92fa9f1e4..67c504e77b3f9bdfad9589236e8f65f8e2b2cd5d 100644 (file)
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -92,6 +92,12 @@ size_t countCycles(const GeneOrder& go){
        return cycles;
 }
 
+size_t inversionDistance(const GeneOrder& go){
+       size_t cycles = countCycles(go);
+
+       return go.size() - 1 - cycles;
+}
+
 int sign(Gene g){
        if (g > 0)
                return 1;

diff --git a/src/genealgorithms.h b/src/genealgorithms.h
index b5ed95d01ccb69af8797ec51aa820305e99db376..7f07d17f47476f617018e62494b7cb0ed9e738c6 100644 (file)
--- a/src/genealgorithms.h
+++ b/src/genealgorithms.h
@@ -51,6 +51,11 @@ std::vector<std::vector<int> > robinsonSchensted(const GeneOrder& go);
  */
 size_t countCycles(const GeneOrder& go);
 
+/**
+ * Calculates the inversion distance for this gene order
+ */
+size_t inversionDistance(const GeneOrder& go);
+
 /**
  * Finds the components in the gene order.
  */

diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
index f2bd11898b5a5a846d4364bc6073d903265d103c..b7dd4e16862e9452751ff509c41b1347f1052536 100644 (file)
--- a/src/test/genealgorithmstest.cpp
+++ b/src/test/genealgorithmstest.cpp
@@ -26,6 +26,7 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
   CPPUNIT_TEST( testFindIntervalsAtPoints );
   CPPUNIT_TEST( testCountCycles );
   CPPUNIT_TEST( testFindComponents );
+  CPPUNIT_TEST( testInversionDistance );
   CPPUNIT_TEST_SUITE_END();
 
 protected:
@@ -129,6 +130,20 @@ protected:
                CPPUNIT_ASSERT_EQUAL(6,c);
        }
 
+       void testInversionDistance (){
+               GeneOrder go(_validPerm.begin(),_validPerm.end());
+               size_t d = inversionDistance(go);
+               CPPUNIT_ASSERT_EQUAL(0ul,d);
+               
+               GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
+               d = inversionDistance(go2);
+               CPPUNIT_ASSERT_EQUAL(5ul,d);
+
+               GeneOrder go3(_validPerm3.begin(),_validPerm3.end());
+               d = inversionDistance(go3);
+               CPPUNIT_ASSERT_EQUAL(13ul,d);
+       }
+
        void testFindComponents (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());
                vector<Component> v = findComponents(go);