From: Michael Andreen <harv@ruin.nu>
Date: Sun, 24 Jun 2007 14:01:54 +0000 (+0000)
Subject: good to have a inversion distance function
X-Git-Tag: v0.1~47
X-Git-Url: https://ruin.nu/git/?p=germs.git;a=commitdiff_plain;h=e44303f027e957d05c9e9418fbd68171f3707599

good to have a inversion distance function
---

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 7f54109..67c504e 100644
--- 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 b5ed95d..7f07d17 100644
--- 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 f2bd118..b7dd4e1 100644
--- 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);