INCLUDE_DIRECTORIES(.)
ADD_LIBRARY(GeneSort geneorder genealgorithms modelidentifier genesorter model
- models)
+ models componenttree)
ADD_EXECUTABLE(genesort main.cpp)
SET(GENELIBS doublefann GeneSort)
--- /dev/null
+/***************************************************************************
+ * Copyright (C) 2006 by Michael Andreen *
+ * andreen@student.chalmers.se *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU General Public License *
+ * along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
+ ***************************************************************************/
+
+#include "componenttree.h"
+
+#include <map>
+using namespace std;
+
+ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
+ if (_parent){
+ _parent->_children.push_back(this);
+ }
+}
+
+ComponentTree::Node::~Node(){
+ for (vector<Node*>::iterator c = _children.begin();
+ c != _children.end(); ++c){
+ delete *c;
+ }
+}
+
+ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0,Component()){
+ map<size_t,Component> starting;
+ map<size_t,Component> ending;
+ size_t max = 0;
+ for (vector<Component>::const_iterator c = components.begin(); c != components.end(); ++c){
+ starting.insert(pair<size_t,Component>(c->i1,*c));
+ ending.insert(pair<size_t,Component>(c->i2,*c));
+ max = (c->i2 > max ? c->i2 : max);
+ }
+
+ Node* q = &_root;
+ Node* p = new Node(q,starting[0]);
+
+ for (size_t i = 1; i < max; ++i){
+ map<size_t,Component>::iterator c = starting.find(i);
+ if (c != starting.end()){
+ if (ending.find(i) == ending.end()){
+ q = new Node(p,Component());
+ }
+ p = new Node(q,c->second);
+
+ }else if (ending.find(i) != ending.end()){
+ p = q->_parent;
+ q = p->_parent;
+ }
+ }
+
+}
+
+ComponentTree::~ComponentTree(){
+}
--- /dev/null
+/***************************************************************************
+ * Copyright (C) 2006 by Michael Andreen *
+ * andreen@student.chalmers.se *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU General Public License *
+ * along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
+ ***************************************************************************/
+
+#ifndef __COMPONENTTREE_H__
+#define __COMPONENTTREE_H__
+
+#include <vector>
+#include "misc.h"
+
+class ComponentTreeTest;
+
+class ComponentTree {
+ public:
+ struct Node {
+ Node(Node* parent, Component comp);
+ ~Node();
+
+ Node* _parent;
+ Component _comp;
+ std::vector<Node*> _children;
+ };
+ ComponentTree(const std::vector<Component>& components);
+
+ ~ComponentTree();
+
+ private:
+ //Disable these, at least for now.
+ void operator=(const ComponentTree&){};
+ ComponentTree(const ComponentTree&): _root(0,Component()){};
+
+ Node _root;
+ friend class ComponentTreeTest;
+};
+
+#endif
#include "genealgorithms.h"
#include "geneorder.h"
+#include "componenttree.h"
#include <algorithm>
#include <set>
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)
#include <vector>
class GeneOrder;
+struct Component;
-struct Component{
- Component(int b,int e,int s):begin(b),end(e),sign(s){}
- bool operator==(const Component& c){
- return begin == c.begin && end == c.end && sign == c.sign;
- }
- int begin;
- int end;
- int sign;
-};
struct Interval{
Interval(size_t f,size_t s,bool o = false):first(f),second(s),oriented(o){}
typedef int Gene;
+struct Component{
+ Component(int b = 0,int e = 0,int s = 0,size_t i1 = 0, size_t i2 = 0):begin(b),end(e),sign(s),i1(i1), i2(i2){}
+ bool operator==(const Component& c){
+ return begin == c.begin && end == c.end && sign == c.sign && i1 == c.i1 && i2 == c.i2;
+ }
+ int begin;
+ int end;
+ int sign;
+ size_t i1;
+ size_t i2;
+};
+
#endif
SET(TESTSRC geneordertest genealgorithmstest modelidentifiertest
- genesortertest)
+ genesortertest componenttreetest)
ADD_EXECUTABLE(tester main ${TESTSRC})
TARGET_LINK_LIBRARIES(tester ${GENELIBS} cppunit)
--- /dev/null
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+#include <genesorter.h>
+#include <geneorder.h>
+#include <genealgorithms.h>
+#include <componenttree.h>
+
+#include <algorithm>
+#include <iterator>
+using namespace std;
+
+/*
+ * A test case that is designed to produce
+ * example errors and failures.
+ *
+ */
+
+#define TESTNAME ComponentTreeTest
+
+
+class TESTNAME : public CPPUNIT_NS::TestFixture
+{
+ CPPUNIT_TEST_SUITE( TESTNAME );
+ CPPUNIT_TEST( testCreate );
+ CPPUNIT_TEST_SUITE_END();
+
+protected:
+ vector<int> _validPerm;
+ vector<int> _validPerm2;
+ vector<int> _validPerm3;
+ vector<int> _validPerm4;
+
+public:
+
+ void setUp (){
+ int validPerm[] = {1,2,3,4};
+ _validPerm.assign(validPerm,validPerm+4);
+ int validPerm2[] = {1,-3,-2,4};
+ _validPerm2.assign(validPerm2,validPerm2+4);
+ int validPerm3[] = {0,-2,-1,4,3,5,-8,6,7,9};
+ _validPerm3.assign(validPerm3,validPerm3+10);
+ int validPerm4[] = {-3,1,2,4,6,5,7,-15,-13,-14,-12,-10,-11,-9,8};
+ _validPerm4.assign(validPerm4,validPerm4+15);
+
+ }
+
+protected:
+
+ size_t count(ComponentTree::Node* n, bool all = false){
+ size_t num = 0;
+ if (all || n->_comp.i2 != 0)
+ num += 1;
+ for (vector<ComponentTree::Node*>::iterator c = n->_children.begin();
+ c != n->_children.end(); ++c){
+ num += count(*c,all);
+ }
+ return num;
+ }
+ void testCreate (){
+ GeneOrder go(_validPerm.begin(),_validPerm.end());
+ ComponentTree t(findComponents(go));
+ ComponentTree::Node* n = &t._root;
+
+ CPPUNIT_ASSERT_EQUAL((size_t)4u,count(n));
+ CPPUNIT_ASSERT_EQUAL((size_t)5u,count(n,true));
+ CPPUNIT_ASSERT_EQUAL((size_t)4u,n->_children.size());
+
+ Component go10(0,1,0,0,1);
+ Component go11(1,2,0,1,2);
+ Component go12(2,3,0,2,3);
+ Component go13(3,4,0,3,4);
+ CPPUNIT_ASSERT(n->_children[0]->_comp == go10);
+ CPPUNIT_ASSERT(n->_children[1]->_comp == go11);
+ CPPUNIT_ASSERT(n->_children[2]->_comp == go12);
+ CPPUNIT_ASSERT(n->_children[3]->_comp == go13);
+
+ GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
+ ComponentTree t2(findComponents(go2));
+ n = &t2._root;
+
+ CPPUNIT_ASSERT_EQUAL((size_t)6u,count(n));
+ CPPUNIT_ASSERT_EQUAL((size_t)9u,count(n,true));
+ CPPUNIT_ASSERT_EQUAL((size_t)3u,n->_children.size());
+ Component go20(1,2,0,2,3);
+ Component go21(0,4,0,0,4);
+ Component go22(4,7,1,4,7);
+ Component go23(-15,-12,-1,8,11);
+ Component go24(-12,-9,-1,11,14);
+ Component go25(7,16,0,7,16);
+ CPPUNIT_ASSERT(n->_children[0]->_comp == go21);
+ CPPUNIT_ASSERT(n->_children[1]->_comp == go22);
+ CPPUNIT_ASSERT(n->_children[2]->_comp == go25);
+
+ }
+
+};
+
+CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );
+
+#undef TESTNAME
GeneOrder go(_validPerm.begin(),_validPerm.end());
vector<Component> v = findComponents(go);
CPPUNIT_ASSERT_EQUAL((size_t)4u,v.size());
- Component go10(0,1,0);
- Component go11(1,2,0);
- Component go12(2,3,0);
- Component go13(3,4,0);
+ Component go10(0,1,0,0,1);
+ Component go11(1,2,0,1,2);
+ Component go12(2,3,0,2,3);
+ Component go13(3,4,0,3,4);
CPPUNIT_ASSERT(go10 == v[0]);
CPPUNIT_ASSERT(go11 == v[1]);
CPPUNIT_ASSERT(go12 == v[2]);
GeneOrder go2(_validPerm3.begin(),_validPerm3.end());
v = findComponents(go2);
CPPUNIT_ASSERT_EQUAL((size_t)6u,v.size());
- Component go20(1,2,0);
- Component go21(0,4,0);
- Component go22(4,7,1);
- Component go23(-15,-12,-1);
- Component go24(-12,-9,-1);
- Component go25(7,16,0);
+ Component go20(1,2,0,2,3);
+ Component go21(0,4,0,0,4);
+ Component go22(4,7,1,4,7);
+ Component go23(-15,-12,-1,8,11);
+ Component go24(-12,-9,-1,11,14);
+ Component go25(7,16,0,7,16);
CPPUNIT_ASSERT(go20 == v[0]);
CPPUNIT_ASSERT(go21 == v[1]);
CPPUNIT_ASSERT(go22 == v[2]);
projects / germs.git / commitdiff