src/componenttree.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2006 by Michael Andreen                                 *
   3  *   andreen@student.chalmers.se                                           *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA          *
  19  ***************************************************************************/
  20
  21 #include "componenttree.h"
  22
  23 using namespace std;
  24
  25 ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
  26         if (_parent){
  27                 _parent->_children.push_back(this);
  28         }
  29 }
  30
  31 ComponentTree::Node::~Node(){
  32         for (vector<Node*>::iterator c = _children.begin();
  33                         c != _children.end(); ++c){
  34                 delete *c;
  35         }
  36 }
  37
  38 /**
  39  * Implemented as O(n*log n), should be possible in O(n), but this is pretty clean, and should
  40  * be fast enough
  41  */
  42 ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(new Node(0,Component())){
  43         map<size_t,Component> starting;
  44         map<size_t,Component> ending;
  45         size_t max = 0;
  46         for (vector<Component>::const_iterator c = components.begin(); c != components.end(); ++c){
  47                 starting.insert(pair<size_t,Component>(c->i1,*c));
  48                 ending.insert(pair<size_t,Component>(c->i2,*c));
  49                 max = (c->i2 > max ? c->i2 : max);
  50         }
  51
  52         Node* q = _root;
  53         Node* p = new Node(q,starting[0]);
  54
  55         for (size_t i = 1; i < max; ++i){
  56                 map<size_t,Component>::iterator c = starting.find(i);
  57                 if (c != starting.end()){
  58                         if (ending.find(i) == ending.end()){
  59                                 q = new Node(p,Component());
  60                         }
  61                         p = new Node(q,c->second);
  62
  63                 }else if (ending.find(i) != ending.end()){
  64                         p = q->_parent;
  65                         q = p->_parent;
  66                 }
  67         }
  68
  69 }
  70
  71 ComponentTree::~ComponentTree(){
  72         delete _root;
  73 }
  74
  75 void ComponentTree::makeUnoriented(){
  76         removeOriented(_root);
  77         while (_root->_children.size() == 1 && _root->_comp.sign == 0){
  78                 Node* n = _root->_children[0];
  79                 _root->_children.clear();
  80                 delete _root;
  81                 _root = n;
  82         }
  83 }
  84
  85 void ComponentTree::removeOriented(Node* n){
  86         for (vector<Node*>::iterator c = n->_children.begin();
  87                         c != n->_children.end(); /*empty*/){
  88                 removeOriented(*c);
  89                 if ((*c)->_children.empty() && (*c)->_comp.sign == 0){
  90                         delete *c;
  91                         n->_children.erase(c);
  92                 }else{
  93                         ++c;
  94                 }
  95         }
  96 }
  97
  98 size_t ComponentTree::countLeaves(){
  99         size_t leaves = countLeaves(_root);
 100         if (_root->_children.size() < 2 && _root->_comp.sign != 0){
 101                 ++leaves;
 102         }
 103         return leaves;
 104 }
 105
 106 size_t ComponentTree::countLeaves(Node* n){
 107         if (n != _root && n->_children.empty()){
 108                 return 1;
 109         }
 110         size_t leaves = 0;
 111         for (vector<Node*>::iterator c = n->_children.begin();
 112                         c != n->_children.end(); ++c){
 113                 leaves += countLeaves(*c);
 114         }
 115         return leaves;
 116 }
 117
 118 void ComponentTree::branches (Node* n, map<Node*,size_t> & b){
 119         if (n->_children.empty() && n->_parent != 0){
 120                 Node* p = n;
 121                 while (p->_parent != 0 && p->_children.size() < 2)
 122                         p = p->_parent;
 123                 ++b[p];
 124                 return;
 125         }
 126         for (vector<Node*>::iterator c = n->_children.begin();
 127                         c != n->_children.end(); ++c){
 128                 branches(*c,b);
 129         }
 130 }
 131
 132 size_t ComponentTree::shortBranches(){
 133         map<Node*,size_t> br;
 134         branches(_root,br);
 135         if (_root->_children.size() < 2 && _root->_comp.sign != 0){
 136                 br[_root]++;
 137         }
 138         size_t sb = 0;
 139         for (map<Node*,size_t>::iterator b = br.begin(); b != br.end(); ++b){
 140                 if (b->second == 1)
 141                         ++sb;
 142         }
 143         return sb;
 144 }
 145