sorting without hurdles seems to work

diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp
index 67c504e77b3f9bdfad9589236e8f65f8e2b2cd5d..ed68b67ab4b798483da9003dbb37478165ef760c 100644 (file)
--- a/src/genealgorithms.cpp
+++ b/src/genealgorithms.cpp
@@ -173,18 +173,37 @@ std::vector<Component> findComponents(const GeneOrder& go){
        return components;
 }
 
        return components;
 }
 

+int sign2(Gene g){
+       if (g < 0)
+               return -1;
+       return 1;
+}

 /**
  * 
  */
 std::vector<Interval> findIntervals(const GeneOrder& go){
 /**
  * 
  */
 std::vector<Interval> findIntervals(const GeneOrder& go){

-       vector<Interval> intervals(go.size()-1,Interval(go.size(),go.size()));
+       size_t max = go.size();
+       vector<Interval> intervals(go.size()-1,Interval(max,max,false));

        size_t n = 0;
        for (GeneOrder::iterator g = go.begin(); g != go.end(); ++g, ++n){
                        size_t i = abs(*g);
        size_t n = 0;
        for (GeneOrder::iterator g = go.begin(); g != go.end(); ++g, ++n){
                        size_t i = abs(*g);

-                       if (i < go.size() - 1)
+                       if (i < go.size() - 1){

                                intervals[i].first = n + (*g >= 0 ? 1 : 0);
                                intervals[i].first = n + (*g >= 0 ? 1 : 0);

-                       if (i > 0)
+
+                               if (intervals[i].second == max)
+                                       intervals[i].oriented = *g < 0;
+                               else
+                                       intervals[i].oriented ^=  *g < 0;
+                       }
+                       if (i > 0){

                                intervals[i-1].second = n + (*g < 0 ? 1 : 0);
                                intervals[i-1].second = n + (*g < 0 ? 1 : 0);

+
+                               if (intervals[i-1].first == max)
+                                       intervals[i-1].oriented = *g < 0;
+                               else
+                                       intervals[i-1].oriented ^=  *g < 0;
+                       }
+

        }
        return intervals;
 }
        }
        return intervals;
 }


@@ -194,7 +213,7 @@ std::vector<Interval> findIntervals(const GeneOrder& go){
  */
 std::vector<Interval> findIntervalsAtPoints(const vector<Interval>& intervals){
        size_t max = intervals.size()+1;
  */
 std::vector<Interval> findIntervalsAtPoints(const vector<Interval>& intervals){
        size_t max = intervals.size()+1;

-       vector<Interval> points(max,Interval(max,max));
+       vector<Interval> points(max,Interval(max,max,false));

        size_t n = 0;
        for (vector<Interval>::const_iterator i = intervals.begin(); i != intervals.end(); ++i, ++n){
                if (points[i->first].first == max){
        size_t n = 0;
        for (vector<Interval>::const_iterator i = intervals.begin(); i != intervals.end(); ++i, ++n){
                if (points[i->first].first == max){

diff --git a/src/genealgorithms.h b/src/genealgorithms.h
index 7f07d17f47476f617018e62494b7cb0ed9e738c6..6bc133fa96174478746cd828659a476e02ea52ec 100644 (file)
--- a/src/genealgorithms.h
+++ b/src/genealgorithms.h
@@ -34,7 +34,16 @@ struct Component{
        int end;
        int sign;
 };
        int end;
        int sign;
 };

-typedef std::pair<size_t,size_t> Interval;
+
+struct Interval{
+       Interval(size_t f,size_t s,bool o = false):first(f),second(s),oriented(o){}
+       bool operator==(const Interval& i){
+               return first == i.first && second == i.second && oriented == i.oriented;
+       }
+       size_t first;
+       size_t second;
+       bool oriented;
+};

 
 /**
  * Returns the length of the longest increasing sequence and the longest
 
 /**
  * Returns the length of the longest increasing sequence and the longest

diff --git a/src/genesorter.cpp b/src/genesorter.cpp
index 8126d6aaa5781336ab03ba3a822f4d72f4c8820d..03f19db1d8949ced3f18cb229671b590cb19acc0 100644 (file)
--- a/src/genesorter.cpp
+++ b/src/genesorter.cpp
@@ -27,26 +27,69 @@
 #include "genealgorithms.h"
 
 #include <queue>
 #include "genealgorithms.h"
 
 #include <queue>

+#include <iostream>
+#include <iterator>

 using namespace std;
 
 GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
        ActionList al;
        GeneOrder temp(go);
 using namespace std;
 
 GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
        ActionList al;
        GeneOrder temp(go);

-       while(inversionDistance(go) > 0){
-               ActionList safe = safeActions(go);
+       while(inversionDistance(temp) > 0){
+               cout << "AL: " << al.size() << " : ";
+               cout << "Distance: " << inversionDistance(temp) << " : ";
+               copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
+               cout << endl;
+               ActionList safe = safeActions(temp);

                if (safe.size() > 0){
                        safe[0](temp);
                        al.push_back(safe[0]);
                if (safe.size() > 0){
                        safe[0](temp);
                        al.push_back(safe[0]);

+                       cout << "AL: " << al.size() << " : ";

                }else
                        return ActionList(); //TODO: Need to handle hurdles.
        }
                }else
                        return ActionList(); //TODO: Need to handle hurdles.
        }

+       cout << "Distance: " << inversionDistance(temp) << " : ";
+       copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
+       cout << endl;

        return al;
 }
 
        return al;
 }
 

+struct ScoreCmp {
+       template<typename T>
+       bool operator()(T s1, T s2){
+               return s1.first < s2.first;
+       }
+};
+

 GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
        if (countCycles(go) == go.size() - 1)
                return ActionList();
        ActionList al;
 GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
        if (countCycles(go) == go.size() - 1)
                return ActionList();
        ActionList al;

-       //al.push_back(SortAction(new ReverseAction(2,3)));
+       vector<Interval> intervals = findIntervals(go);
+       priority_queue<pair<size_t,SortAction>,vector<pair<size_t,SortAction> >, ScoreCmp > pq;
+       for (size_t i = 0; i < intervals.size(); ++i){
+               if (intervals[i].oriented && intervals[i].first != intervals[i].second){
+                       SortAction sa(new ReverseAction(intervals[i]));
+                       size_t score = scoreActions(go,sa);
+                       cout << "Inversion: " << min(intervals[i].first,intervals[i].second) << ":" << max(intervals[i].first,intervals[i].second)-1 << " Score: " << score <<  endl;
+                       pq.push(pair<size_t,SortAction>(score,sa));
+               }                               
+       }
+       while (pq.size() > 0){
+               al.push_back(pq.top().second);
+               pq.pop();
+       }

        return al;
 }
        return al;
 }

+
+size_t GeneSorter::scoreActions(const GeneOrder& go, SortAction& sa){
+       GeneOrder temp(go);
+       sa(temp);
+       vector<Interval> intervals = findIntervals(temp);
+       int o = 0;
+       for (vector<Interval>::iterator in = intervals.begin(); in != intervals.end(); ++in){
+               if (in->oriented)
+                       ++o;
+       }
+       return o;
+}
+

diff --git a/src/genesorter.h b/src/genesorter.h
index 384261196060dfaa19522a7deadc68e28784e6d1..4380e9957479625140f95c858f3245e54942731f 100644 (file)
--- a/src/genesorter.h
+++ b/src/genesorter.h
@@ -46,6 +46,8 @@ class GeneSorter{
                 */
                ActionList safeActions(const GeneOrder& go1);
 
                 */
                ActionList safeActions(const GeneOrder& go1);
 

+               size_t scoreActions(const GeneOrder& go, SortAction& sa);
+

                ~GeneSorter(){};
 };
 
                ~GeneSorter(){};
 };
 

diff --git a/src/reverseaction.h b/src/reverseaction.h
index 0330597a90b775c7da1ed89fb118ee59482e1241..76ab6660da377187420f268ce6dda84825ef3361 100644 (file)
--- a/src/reverseaction.h
+++ b/src/reverseaction.h
@@ -22,6 +22,10 @@
 #define __REVERSEACTION_H__
 
 #include "sortaction.h"
 #define __REVERSEACTION_H__
 
 #include "sortaction.h"

+#include "genealgorithms.h"
+
+#include <algorithm>
+

 /**
  * Reverses an interval
  *
 /**
  * Reverses an interval
  *


@@ -35,6 +39,10 @@ class ReverseAction : public SortAction{
                 */
                ReverseAction(size_t i, size_t j): SortAction(0),_i(i),_j(j){
                }
                 */
                ReverseAction(size_t i, size_t j): SortAction(0),_i(i),_j(j){
                }

+               ReverseAction(Interval i): SortAction(0){
+                       _i = std::min(i.first,i.second);
+                       _j = std::max(i.first,i.second)-1;
+               }

 
                /**
                 * Applies the sort action on the gene order
 
                /**
                 * Applies the sort action on the gene order

diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp
index b7dd4e16862e9452751ff509c41b1347f1052536..35f3bf8bca3010d8d3c73254e5c86e0b5f32d7a5 100644 (file)
--- a/src/test/genealgorithmstest.cpp
+++ b/src/test/genealgorithmstest.cpp
@@ -84,22 +84,40 @@ protected:
        }
        void testFindIntervals (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());
        }
        void testFindIntervals (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());

-               vector<pair<size_t,size_t> > v = findIntervals(go);
+               vector<Interval> v = findIntervals(go);

                CPPUNIT_ASSERT_EQUAL(4ul,v.size());
                Interval go10(1,1);
                Interval go12(3,3);
                CPPUNIT_ASSERT(go10 == v[0]);
                CPPUNIT_ASSERT(go12 == v[2]);
                
                CPPUNIT_ASSERT_EQUAL(4ul,v.size());
                Interval go10(1,1);
                Interval go12(3,3);
                CPPUNIT_ASSERT(go10 == v[0]);
                CPPUNIT_ASSERT(go12 == v[2]);
                

-               GeneOrder go2(_validPerm3.begin(),_validPerm3.end());
+               GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
+               v = findIntervals(go2);
+               CPPUNIT_ASSERT_EQUAL(9ul,v.size());
+               Interval go20(1,3,true);
+               Interval go21(2,2);
+               Interval go22(1,4,true);
+               Interval go23(5,3);
+               Interval go25(6,7);
+               Interval go26(8,8);
+               Interval go27(9,7,true);
+               CPPUNIT_ASSERT(go20 == v[0]);
+               CPPUNIT_ASSERT(go21 == v[1]);
+               CPPUNIT_ASSERT(go22 == v[2]);
+               CPPUNIT_ASSERT(go23 == v[3]);
+               CPPUNIT_ASSERT(go25 == v[5]);
+               CPPUNIT_ASSERT(go26 == v[6]);
+               CPPUNIT_ASSERT(go27 == v[7]);
+
+               /*GeneOrder go2(_validPerm3.begin(),_validPerm3.end());

                v = findIntervals(go2);
                CPPUNIT_ASSERT_EQUAL(16ul,v.size());
                v = findIntervals(go2);
                CPPUNIT_ASSERT_EQUAL(16ul,v.size());

-               Interval go20(1,2);
+               Interval go20(1,2,true);

                Interval go22(4,2);
                Interval go215(8,16);
                CPPUNIT_ASSERT(go20 == v[0]);
                CPPUNIT_ASSERT(go22 == v[2]);
                Interval go22(4,2);
                Interval go215(8,16);
                CPPUNIT_ASSERT(go20 == v[0]);
                CPPUNIT_ASSERT(go22 == v[2]);

-               CPPUNIT_ASSERT(go215 == v[15]);
+               CPPUNIT_ASSERT(go215 == v[15]);*/

        }
        void testFindIntervalsAtPoints (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());
        }
        void testFindIntervalsAtPoints (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());

diff --git a/src/test/genesortertest.cpp b/src/test/genesortertest.cpp
index 6a58ce2b8fb6e8fa0ecace92a3542d2823545c83..157e3c40be6c8764476a10b829babc58545766cf 100644 (file)
--- a/src/test/genesortertest.cpp
+++ b/src/test/genesortertest.cpp
@@ -83,16 +83,20 @@ protected:
 
                GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
                al = so.safeActions(go2);
 
                GeneOrder go2(_validPerm2.begin(),_validPerm2.end());
                al = so.safeActions(go2);

-               CPPUNIT_ASSERT_EQUAL(1ul,al.size());
+               CPPUNIT_ASSERT_EQUAL(2ul,al.size());

                CPPUNIT_ASSERT(al[0] == ReverseAction(2,3));
                CPPUNIT_ASSERT(al[0] == ReverseAction(2,3));

+               CPPUNIT_ASSERT(al[1] == ReverseAction(2,3));

                CPPUNIT_ASSERT(!(al[0] == ReverseAction(2,5)));
 
                GeneOrder go3(_validPerm3.begin(),_validPerm3.end());
                al = so.safeActions(go3);
                CPPUNIT_ASSERT(al.size() > 0);
                CPPUNIT_ASSERT(!(al[0] == ReverseAction(2,5)));
 
                GeneOrder go3(_validPerm3.begin(),_validPerm3.end());
                al = so.safeActions(go3);
                CPPUNIT_ASSERT(al.size() > 0);

-               size_t cycles = countCycles(go3);
-               al[0](go3);
-               CPPUNIT_ASSERT(cycles < countCycles(go3));
+               size_t dist = inversionDistance(go3);
+               for (size_t i = 0; i < al.size(); ++i){
+                       GeneOrder go(go3);
+                       al[0](go);
+                       CPPUNIT_ASSERT(dist > inversionDistance(go));
+               }

        }
 
 };
        }
 
 };