From a16f3a90b540c9adf29050f8041baf0c0781c20a Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Thu, 16 Aug 2007 09:17:35 +0000
Subject: [PATCH] shortBranches

---
 src/componenttree.cpp          | 30 +++++++++++++++++++++++++++++-
 src/componenttree.h            |  4 ++++
 src/test/componenttreetest.cpp | 14 ++++++++++++++
 3 files changed, 47 insertions(+), 1 deletion(-)

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 5832c36..fac5639 100644
--- 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 aad4ddb..816059c 100644
--- 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 b916bf4..61e9322 100644
--- 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());
+	}
 
 };
 
-- 
2.39.2