shortBranches

[germs.git] / src / componenttree.cpp

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