From 7e811915a713eeef44f03385a1fc1f74a5301c30 Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Sun, 24 Jun 2007 17:56:11 +0000 Subject: [PATCH] sorting without hurdles seems to work --- src/genealgorithms.cpp | 27 +++++++++++++++--- src/genealgorithms.h | 11 +++++++- src/genesorter.cpp | 49 +++++++++++++++++++++++++++++++-- src/genesorter.h | 2 ++ src/reverseaction.h | 8 ++++++ src/test/genealgorithmstest.cpp | 26 ++++++++++++++--- src/test/genesortertest.cpp | 12 +++++--- 7 files changed, 119 insertions(+), 16 deletions(-) diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp index 67c504e..ed68b67 100644 --- a/src/genealgorithms.cpp +++ b/src/genealgorithms.cpp @@ -173,18 +173,37 @@ std::vector findComponents(const GeneOrder& go){ return components; } +int sign2(Gene g){ + if (g < 0) + return -1; + return 1; +} /** * */ std::vector findIntervals(const GeneOrder& go){ - vector intervals(go.size()-1,Interval(go.size(),go.size())); + size_t max = go.size(); + vector 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); - if (i < go.size() - 1) + if (i < go.size() - 1){ 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); + + if (intervals[i-1].first == max) + intervals[i-1].oriented = *g < 0; + else + intervals[i-1].oriented ^= *g < 0; + } + } return intervals; } @@ -194,7 +213,7 @@ std::vector findIntervals(const GeneOrder& go){ */ std::vector findIntervalsAtPoints(const vector& intervals){ size_t max = intervals.size()+1; - vector points(max,Interval(max,max)); + vector points(max,Interval(max,max,false)); size_t n = 0; for (vector::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 7f07d17..6bc133f 100644 --- a/src/genealgorithms.h +++ b/src/genealgorithms.h @@ -34,7 +34,16 @@ struct Component{ int end; int sign; }; -typedef std::pair 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 diff --git a/src/genesorter.cpp b/src/genesorter.cpp index 8126d6a..03f19db 100644 --- a/src/genesorter.cpp +++ b/src/genesorter.cpp @@ -27,26 +27,69 @@ #include "genealgorithms.h" #include +#include +#include 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(cout, " ")); + cout << endl; + ActionList safe = safeActions(temp); if (safe.size() > 0){ safe[0](temp); al.push_back(safe[0]); + cout << "AL: " << al.size() << " : "; }else return ActionList(); //TODO: Need to handle hurdles. } + cout << "Distance: " << inversionDistance(temp) << " : "; + copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); + cout << endl; return al; } +struct ScoreCmp { + template + 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; - //al.push_back(SortAction(new ReverseAction(2,3))); + vector intervals = findIntervals(go); + priority_queue,vector >, 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(score,sa)); + } + } + while (pq.size() > 0){ + al.push_back(pq.top().second); + pq.pop(); + } return al; } + +size_t GeneSorter::scoreActions(const GeneOrder& go, SortAction& sa){ + GeneOrder temp(go); + sa(temp); + vector intervals = findIntervals(temp); + int o = 0; + for (vector::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 3842611..4380e99 100644 --- a/src/genesorter.h +++ b/src/genesorter.h @@ -46,6 +46,8 @@ class GeneSorter{ */ ActionList safeActions(const GeneOrder& go1); + size_t scoreActions(const GeneOrder& go, SortAction& sa); + ~GeneSorter(){}; }; diff --git a/src/reverseaction.h b/src/reverseaction.h index 0330597..76ab666 100644 --- a/src/reverseaction.h +++ b/src/reverseaction.h @@ -22,6 +22,10 @@ #define __REVERSEACTION_H__ #include "sortaction.h" +#include "genealgorithms.h" + +#include + /** * 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(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 diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp index b7dd4e1..35f3bf8 100644 --- a/src/test/genealgorithmstest.cpp +++ b/src/test/genealgorithmstest.cpp @@ -84,22 +84,40 @@ protected: } void testFindIntervals (){ GeneOrder go(_validPerm.begin(),_validPerm.end()); - vector > v = findIntervals(go); + vector 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]); - 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()); - 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]); - CPPUNIT_ASSERT(go215 == v[15]); + CPPUNIT_ASSERT(go215 == v[15]);*/ } void testFindIntervalsAtPoints (){ GeneOrder go(_validPerm.begin(),_validPerm.end()); diff --git a/src/test/genesortertest.cpp b/src/test/genesortertest.cpp index 6a58ce2..157e3c4 100644 --- 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); - CPPUNIT_ASSERT_EQUAL(1ul,al.size()); + CPPUNIT_ASSERT_EQUAL(2ul,al.size()); 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); - 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)); + } } }; -- 2.39.2