src/libcola/connected_components.cpp

   1 #include <map>
   2 #include <list>
   3 #include <libvpsc/remove_rectangle_overlap.h>
   4 #include "cola.h"
   5 using namespace std;
   6
   7 namespace cola {
   8     Component::~Component() {
   9         for(unsigned i=0;i<scx.size();i++) {
  10             delete scx[i];
  11         }
  12         for(unsigned i=0;i<scy.size();i++) {
  13             delete scy[i];
  14         }
  15     }
  16     void Component::moveRectangles(double x, double y) {
  17         for(unsigned i=0;i<rects.size();i++) {
  18             rects[i]->moveCentreX(rects[i]->getCentreX()+x);
  19             rects[i]->moveCentreY(rects[i]->getCentreY()+y);
  20         }
  21     }
  22     Rectangle* Component::getBoundingBox() {
  23         double llx=DBL_MAX, lly=DBL_MAX, urx=-DBL_MAX, ury=-DBL_MAX;
  24         for(unsigned i=0;i<rects.size();i++) {
  25             llx=min(llx,rects[i]->getMinX());
  26             lly=min(lly,rects[i]->getMinY());
  27             urx=max(urx,rects[i]->getMaxX());
  28             ury=max(ury,rects[i]->getMaxY());
  29         }
  30         return new Rectangle(llx,urx,lly,ury);
  31     }
  32
  33     namespace ccomponents {
  34         struct Node {
  35             unsigned id;
  36             bool visited;
  37             vector<Node*> neighbours;
  38             list<Node*>::iterator listPos;
  39             Rectangle* r;
  40         };
  41         // Depth first search traversal of graph to find connected component
  42         void dfs(Node* v,
  43                 list<Node*>& remaining,
  44                 Component* component,
  45                 map<unsigned,pair<Component*,unsigned> > &cmap) {
  46             v->visited=true;
  47             remaining.erase(v->listPos);
  48             cmap[v->id]=make_pair(component,component->node_ids.size());
  49             component->node_ids.push_back(v->id);
  50             component->rects.push_back(v->r);
  51             for(unsigned i=0;i<v->neighbours.size();i++) {
  52                 Node* u=v->neighbours[i];
  53                 if(!u->visited) {
  54                     dfs(u,remaining,component,cmap);
  55                 }
  56             }
  57         }
  58     }
  59
  60     using namespace ccomponents;
  61
  62     // for a graph of n nodes, return connected components
  63     void connectedComponents(
  64             const vector<Rectangle*> &rs,
  65             const vector<Edge> &es,
  66             const SimpleConstraints &scx,
  67             const SimpleConstraints &scy,
  68             vector<Component*> &components) {
  69         unsigned n=rs.size();
  70         vector<Node> vs(n);
  71         list<Node*> remaining;
  72         for(unsigned i=0;i<n;i++) {
  73             vs[i].id=i;
  74             vs[i].visited=false;
  75             vs[i].r=rs[i];
  76             vs[i].listPos = remaining.insert(remaining.end(),&vs[i]);
  77         }
  78         vector<Edge>::const_iterator ei;
  79         SimpleConstraints::const_iterator ci;
  80         for(ei=es.begin();ei!=es.end();ei++) {
  81             vs[ei->first].neighbours.push_back(&vs[ei->second]);
  82             vs[ei->second].neighbours.push_back(&vs[ei->first]);
  83         }
  84         map<unsigned,pair<Component*,unsigned> > cmap;
  85         while(!remaining.empty()) {
  86             Component* component=new Component;
  87             Node* v=*remaining.begin();
  88             dfs(v,remaining,component,cmap);
  89             components.push_back(component);
  90         }
  91         for(ei=es.begin();ei!=es.end();ei++) {
  92             pair<Component*,unsigned> u=cmap[ei->first],
  93                                       v=cmap[ei->second];
  94             assert(u.first==v.first);
  95             u.first->edges.push_back(make_pair(u.second,v.second));
  96         }
  97         for(ci=scx.begin();ci!=scx.end();ci++) {
  98             SimpleConstraint *c=*ci;
  99             pair<Component*,unsigned> u=cmap[c->left],
 100                                       v=cmap[c->right];
 101             assert(u.first==v.first);
 102             u.first->scx.push_back(
 103                     new SimpleConstraint(u.second,v.second,c->gap));
 104         }
 105         for(ci=scy.begin();ci!=scy.end();ci++) {
 106             SimpleConstraint *c=*ci;
 107             pair<Component*,unsigned> u=cmap[c->left],
 108                                       v=cmap[c->right];
 109             assert(u.first==v.first);
 110             u.first->scy.push_back(
 111                     new SimpleConstraint(u.second,v.second,c->gap));
 112         }
 113     }
 114     void separateComponents(const vector<Component*> &components) {
 115         unsigned n=components.size();
 116         Rectangle* bbs[n];
 117         double origX[n], origY[n];
 118         for(unsigned i=0;i<n;i++) {
 119             bbs[i]=components[i]->getBoundingBox();
 120             origX[i]=bbs[i]->getCentreX();
 121             origY[i]=bbs[i]->getCentreY();
 122         }
 123         removeRectangleOverlap(n,bbs,0,0);
 124         for(unsigned i=0;i<n;i++) {
 125             components[i]->moveRectangles(
 126                     bbs[i]->getCentreX()-origX[i],
 127                     bbs[i]->getCentreY()-origY[i]);
 128             delete bbs[i];
 129         }
 130     }
 131 }
 132 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4