connected_components.cpp

#include <map>
#include <list>
#include <libvpsc/remove_rectangle_overlap.h>
#include "cola.h"
using namespace std;

namespace cola {
    Component::~Component() {
        for(unsigned i=0;i<scx.size();i++) {
            delete scx[i];
        }
        for(unsigned i=0;i<scy.size();i++) {
            delete scy[i];
        }
    }
    void Component::moveRectangles(double x, double y) {
        for(unsigned i=0;i<rects.size();i++) {
            rects[i]->moveCentreX(rects[i]->getCentreX()+x);
            rects[i]->moveCentreY(rects[i]->getCentreY()+y);
        }
    }
    Rectangle* Component::getBoundingBox() {
        double llx=DBL_MAX, lly=DBL_MAX, urx=-DBL_MAX, ury=-DBL_MAX;
        for(unsigned i=0;i<rects.size();i++) {
            llx=min(llx,rects[i]->getMinX());
            lly=min(lly,rects[i]->getMinY());
            urx=max(urx,rects[i]->getMaxX());
            ury=max(ury,rects[i]->getMaxY());
        }
        return new Rectangle(llx,urx,lly,ury);
    }

    namespace ccomponents {
        struct Node {
            unsigned id;
            bool visited;
            vector<Node*> neighbours;
            list<Node*>::iterator listPos;
            Rectangle* r;
        };
        // Depth first search traversal of graph to find connected component
        void dfs(Node* v,
                list<Node*>& remaining,
                Component* component,
                map<unsigned,pair<Component*,unsigned> > &cmap) {
            v->visited=true;
            remaining.erase(v->listPos);
            cmap[v->id]=make_pair(component,component->node_ids.size());
            component->node_ids.push_back(v->id);
            component->rects.push_back(v->r);
            for(unsigned i=0;i<v->neighbours.size();i++) {
                Node* u=v->neighbours[i];
                if(!u->visited) {
                    dfs(u,remaining,component,cmap);
                }
            }
        }
    }

    using namespace ccomponents;

    // for a graph of n nodes, return connected components
    void connectedComponents(
            const vector<Rectangle*> &rs,
            const vector<Edge> &es, 
            const SimpleConstraints &scx,
            const SimpleConstraints &scy,
            vector<Component*> &components) {
        unsigned n=rs.size();
        vector<Node> vs(n);
        list<Node*> remaining;
        for(unsigned i=0;i<n;i++) {
            vs[i].id=i;
            vs[i].visited=false;
            vs[i].r=rs[i];
            vs[i].listPos = remaining.insert(remaining.end(),&vs[i]);
        }
        vector<Edge>::const_iterator ei;
        SimpleConstraints::const_iterator ci;
        for(ei=es.begin();ei!=es.end();ei++) {
            vs[ei->first].neighbours.push_back(&vs[ei->second]);
            vs[ei->second].neighbours.push_back(&vs[ei->first]);
        }
        map<unsigned,pair<Component*,unsigned> > cmap;
        while(!remaining.empty()) {
            Component* component=new Component;
            Node* v=*remaining.begin();
            dfs(v,remaining,component,cmap);
            components.push_back(component);
        }
        for(ei=es.begin();ei!=es.end();ei++) {
            pair<Component*,unsigned> u=cmap[ei->first],
                                      v=cmap[ei->second];
            assert(u.first==v.first);
            u.first->edges.push_back(make_pair(u.second,v.second));
        }
        for(ci=scx.begin();ci!=scx.end();ci++) {
            SimpleConstraint *c=*ci;
            pair<Component*,unsigned> u=cmap[c->left],
                                      v=cmap[c->right];
            assert(u.first==v.first);
            u.first->scx.push_back(
                    new SimpleConstraint(u.second,v.second,c->gap));
        }
        for(ci=scy.begin();ci!=scy.end();ci++) {
            SimpleConstraint *c=*ci;
            pair<Component*,unsigned> u=cmap[c->left],
                                      v=cmap[c->right];
            assert(u.first==v.first);
            u.first->scy.push_back(
                    new SimpleConstraint(u.second,v.second,c->gap));
        }
    }
    void separateComponents(const vector<Component*> &components) {
        unsigned n=components.size();
        Rectangle* bbs[n];
        double origX[n], origY[n];
        for(unsigned i=0;i<n;i++) {
            bbs[i]=components[i]->getBoundingBox();
            origX[i]=bbs[i]->getCentreX();
            origY[i]=bbs[i]->getCentreY();
        }
        removeRectangleOverlap(n,bbs,0,0);
        for(unsigned i=0;i<n;i++) {
            components[i]->moveRectangles(
                    bbs[i]->getCentreX()-origX[i],
                    bbs[i]->getCentreY()-origY[i]);
            delete bbs[i];
        }
    }
}
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4