src/libcola/connected_components.cpp

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