1 #include <map>
2 #include <list>
3 #include <libvpsc/remove_rectangle_overlap.h>
4 #include "cola.h"
5 using namespace std;
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 }
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 }
60 using namespace ccomponents;
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