From c5cda419f16ce7d9d58a09852d5af83c7c25b9d1 Mon Sep 17 00:00:00 2001
From: tgdwyer <tgdwyer@users.sourceforge.net>
Date: Mon, 17 Jul 2006 04:23:39 +0000
Subject: [PATCH] remove overlaps between connected components

---
 src/graphlayout/graphlayout.cpp      |  1 +
 src/libcola/cola.h                   | 34 +++++++++++----------
 src/libcola/connected_components.cpp | 44 ++++++++++++++++++++++++++++
 3 files changed, 64 insertions(+), 15 deletions(-)

diff --git a/src/graphlayout/graphlayout.cpp b/src/graphlayout/graphlayout.cpp
index ec5c780c7..1b77b5afa 100644
--- a/src/graphlayout/graphlayout.cpp
+++ b/src/graphlayout/graphlayout.cpp
@@ -169,6 +169,7 @@ void graphlayout(GSList const *const items) {
                 NULL,NULL,&c->scx,&c->scy,NULL,NULL);
         alg.run();
     }
+    separateComponents(cs);
 	
 	for (list<SPItem *>::iterator it(selected.begin());
 		it != selected.end();
diff --git a/src/libcola/cola.h b/src/libcola/cola.h
index d3c1624db..c3cdb03c0 100644
--- a/src/libcola/cola.h
+++ b/src/libcola/cola.h
@@ -24,19 +24,15 @@ namespace cola {
 
     // a graph component with a list of node_ids giving indices for some larger list of nodes
     // for the nodes in this component, and a list of edges - node indices relative to this component
-    struct Component {
+    class Component {
+    public:
         vector<unsigned> node_ids;
         vector<Rectangle*> rects;
         vector<Edge> edges;
         SimpleConstraints scx, scy;
-        ~Component() {
-            for(unsigned i=0;i<scx.size();i++) {
-                delete scx[i];
-            }
-            for(unsigned i=0;i<scy.size();i++) {
-                delete scy[i];
-            }
-        }
+        ~Component();
+        void moveRectangles(double x, double y);
+        Rectangle* getBoundingBox();
     };
     // for a graph of n nodes, return connected components
     void connectedComponents(
@@ -46,6 +42,10 @@ namespace cola {
             const SimpleConstraints &scy, 
             vector<Component*> &components);
 
+    // move the contents of each component so that the components do not
+    // overlap.
+    void separateComponents(const vector<Component*> &components);
+
     // defines references to three variables for which the goal function
     // will be altered to prefer points u-b-v are in a linear arrangement
     // such that b is placed at u+t(v-u).
@@ -116,10 +116,8 @@ namespace cola {
     public:
         double old_stress;
 		TestConvergence(const double& tolerance = 0.001, const unsigned maxiterations = 1000)
-			: old_stress(DBL_MAX),
-              tolerance(tolerance),
-              maxiterations(maxiterations),
-              iterations(0) { }
+			: tolerance(tolerance),
+              maxiterations(maxiterations) { reset(); }
         virtual ~TestConvergence() {}
 
 		virtual bool operator()(double new_stress, double* X, double* Y) {
@@ -138,9 +136,13 @@ namespace cola {
             old_stress = new_stress;
 			return converged;
 		}
+        void reset() {
+            old_stress = DBL_MAX;
+            iterations = 0;
+        }
   	private:
-        double tolerance;
-        unsigned maxiterations;
+        const double tolerance;
+        const unsigned maxiterations;
         unsigned iterations;
   	};
     static TestConvergence defaultTest(0.0001,100);
@@ -170,6 +172,8 @@ namespace cola {
             boundingBoxes = new Rectangle*[rs.size()];
             copy(rs.begin(),rs.end(),boundingBoxes);
 
+            done.reset();
+
             double** D=new double*[n];
             for(unsigned i=0;i<n;i++) {
                 D[i]=new double[n];
diff --git a/src/libcola/connected_components.cpp b/src/libcola/connected_components.cpp
index 5eb9d07ab..f626649cd 100644
--- a/src/libcola/connected_components.cpp
+++ b/src/libcola/connected_components.cpp
@@ -1,8 +1,35 @@
 #include <map>
 #include "cola.h"
+#include <libvpsc/remove_rectangle_overlap.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());
+        }
+        printf("Bounding Box=(%f,%f,%f,%f)\n",llx,urx,lly,ury);
+        return new Rectangle(llx,urx,lly,ury);
+    }
+
     namespace ccomponents {
         struct Node {
             unsigned id;
@@ -81,5 +108,22 @@ namespace cola {
                     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
-- 
2.30.2