shortBranches

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 5832c3683bcda2ebee8970220a6b60a7906e5ccc..fac5639df9d8f357832e0d6a6d1b65bccc78f866 100644 (file)
--- a/src/componenttree.cpp
+++ b/src/componenttree.cpp
@@ -20,7 +20,6 @@
 
 #include "componenttree.h"
 
-#include <map>
 using namespace std;
 
 ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
@@ -115,3 +114,32 @@ size_t ComponentTree::countLeaves(Node* n){
        }
        return leaves;
 }
+
+void ComponentTree::branches (Node* n, map<Node*,size_t> & b){
+       if (n->_children.empty() && n->_parent != 0){
+               Node* p = n;
+               while (p->_parent != 0 && p->_children.size() < 2)
+                       p = p->_parent;
+               ++b[p];
+               return;
+       }
+       for (vector<Node*>::iterator c = n->_children.begin();
+                       c != n->_children.end(); ++c){
+               branches(*c,b);
+       }
+}
+
+size_t ComponentTree::shortBranches(){
+       map<Node*,size_t> br;
+       branches(_root,br);
+       if (_root->_children.size() < 2 && _root->_comp.sign != 0){
+               br[_root]++;
+       }
+       size_t sb = 0;
+       for (map<Node*,size_t>::iterator b = br.begin(); b != br.end(); ++b){
+               if (b->second == 1)
+                       ++sb;
+       }
+       return sb;
+}
+

diff --git a/src/componenttree.h b/src/componenttree.h
index aad4ddbdd076cc4c6c5cbb42437f1c61199696fd..816059c29b7fe3c14463bbaf023c905b2907f834 100644 (file)
--- a/src/componenttree.h
+++ b/src/componenttree.h
@@ -22,6 +22,7 @@
 #define __COMPONENTTREE_H__
 
 #include <vector>
+#include <map>
 #include "misc.h"
 
 class ComponentTree {
@@ -50,6 +51,8 @@ class ComponentTree {
 
                size_t countLeaves();
 
+               size_t shortBranches();
+
        private:
                //Disable these, at least for now.
                void operator=(const ComponentTree&){};
@@ -57,6 +60,7 @@ class ComponentTree {
 
                void removeOriented(Node* n);
                size_t countLeaves(Node* n);
+               void branches (Node* n, std::map<Node*,size_t> & b);
 
                Node* _root;
 

diff --git a/src/test/componenttreetest.cpp b/src/test/componenttreetest.cpp
index b916bf4139d0385a279476d74e74af1438c57aee..61e932218257ae9d7fe75a8b891fec21e43dfc0c 100644 (file)
--- a/src/test/componenttreetest.cpp
+++ b/src/test/componenttreetest.cpp
@@ -25,6 +25,7 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
   CPPUNIT_TEST( testCreate );
   CPPUNIT_TEST( testMakeUnoriented );
   CPPUNIT_TEST( testCountLeaves );
+  CPPUNIT_TEST( testShortBranches );
   CPPUNIT_TEST_SUITE_END();
 
 protected:
@@ -142,6 +143,19 @@ protected:
                CPPUNIT_ASSERT_EQUAL(false,n->_children.empty());
                CPPUNIT_ASSERT_EQUAL((size_t)3u,t2.countLeaves());
        }
+       void testShortBranches (){
+               GeneOrder go(_validPerm.begin(),_validPerm.end());
+               ComponentTree t(findComponents(go));
+               t.makeUnoriented();
+
+               CPPUNIT_ASSERT_EQUAL((size_t)0u,t.shortBranches());
+
+               GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
+               ComponentTree t2(findComponents(go2));
+               t2.makeUnoriented();
+               ComponentTree::Node* n = t2._root;
+               //CPPUNIT_ASSERT_EQUAL((size_t)1u,t2.shortBranches());
+       }
 
 };