X-Git-Url: https://ruin.nu/git/?p=germs.git;a=blobdiff_plain;f=src%2Fcomponenttree.cpp;fp=src%2Fcomponenttree.cpp;h=fac5639df9d8f357832e0d6a6d1b65bccc78f866;hp=5832c3683bcda2ebee8970220a6b60a7906e5ccc;hb=a16f3a90b540c9adf29050f8041baf0c0781c20a;hpb=e3b0df677271c6cf14e00e2344802bfd0a66ebd5

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;
+}
+