Layout algorithm is now applied to each connected component in the

selection separately.  Previously, behaviour of layout on disconnected 
graphs was... undefined!

(bzr r1421)

5 files changed, 184 insertions, 79 deletions

diff --git a/src/libcola/Makefile_insert b/src/libcola/Makefile_insert
index f8f9de20c..dc032a289 100644
--- a/src/libcola/Makefile_insert
+++ b/src/libcola/Makefile_insert
@@ -14,4 +14,5 @@ libcola_libcola_a_SOURCES = libcola/cola.h\
 	libcola/shortest_paths.cpp\
 	libcola/shortest_paths.h\
 	libcola/straightener.h\
-	libcola/straightener.cpp
+	libcola/straightener.cpp\
+	libcola/connected_components.cpp
diff --git a/src/libcola/cola.h b/src/libcola/cola.h
index cc99515bf..e0cf1257c 100644
--- a/src/libcola/cola.h
+++ b/src/libcola/cola.h
@@ -17,9 +17,24 @@
 typedef vector<unsigned> Cluster;
 typedef vector<Cluster*> Clusters;
 
+using vpsc::Rectangle;
+
 namespace cola {
     typedef pair<unsigned, unsigned> Edge;
 
+    // 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 {
+        vector<unsigned> node_ids;
+        vector<Rectangle*> rects;
+        vector<Edge> edges;
+    };
+    // for a graph of n nodes, return connected components
+    void connectedComponents(
+            vector<Rectangle*> &rs,
+            vector<Edge> &es, 
+            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).
@@ -121,7 +136,7 @@ namespace cola {
 	class ConstrainedMajorizationLayout {
     public:
 		ConstrainedMajorizationLayout(
-                vector<vpsc::Rectangle*>& rs,
+                vector<Rectangle*>& rs,
                 vector<Edge>& es,
 				double* eweights,
                 double idealLength,
@@ -141,7 +156,7 @@ namespace cola {
               straightenEdges(NULL)
         {
             assert(rs.size()==n);
-            boundingBoxes = new vpsc::Rectangle*[rs.size()];
+            boundingBoxes = new Rectangle*[rs.size()];
             copy(rs.begin(),rs.end(),boundingBoxes);
 
             double** D=new double*[n];
@@ -229,7 +244,7 @@ namespace cola {
         double** Dij;
         double tol;
 		TestConvergence& done;
-        vpsc::Rectangle** boundingBoxes;
+        Rectangle** boundingBoxes;
         double *X, *Y;
         Clusters* clusters;
         double edge_length;
diff --git a/src/libcola/connected_components.cpp b/src/libcola/connected_components.cpp
new file mode 100644
index 000000000..8450e4874
--- /dev/null
+++ b/src/libcola/connected_components.cpp
@@ -0,0 +1,67 @@
+#include <map>
+#include "cola.h"
+using namespace std;
+
+namespace cola {
+    namespace ccomponents {
+        struct Node {
+            unsigned id;
+            bool visited;
+            vector<Node*> neighbours;
+            Rectangle* r;
+        };
+        // Depth first search traversal of graph to find connected component
+        void dfs(Node* v,
+                set<Node*>& remaining,
+                Component* component,
+                map<unsigned,pair<Component*,unsigned> > &cmap) {
+            v->visited=true;
+            remaining.erase(v);
+            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(
+            vector<Rectangle*> &rs,
+            vector<Edge> &es, 
+            vector<Component*> &components) {
+        unsigned n=rs.size();
+        vector<Node> vs(n);
+        set<Node*> remaining;
+        for(unsigned i=0;i<n;i++) {
+            vs[i].id=i;
+            vs[i].visited=false;
+            vs[i].r=rs[i];
+            remaining.insert(&vs[i]);
+        }
+        for(vector<Edge>::iterator e=es.begin();e!=es.end();e++) {
+            vs[e->first].neighbours.push_back(&vs[e->second]);
+            vs[e->second].neighbours.push_back(&vs[e->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(vector<Edge>::iterator e=es.begin();e!=es.end();e++) {
+            pair<Component*,unsigned> u=cmap[e->first],
+                                      v=cmap[e->second];
+            assert(u.first==v.first);
+            u.first->edges.push_back(make_pair(u.second,v.second));
+        }
+    }
+}
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
diff --git a/src/libcola/cycle_detector.cpp b/src/libcola/cycle_detector.cpp
index ddc056e4d..89a2ccaae 100644
--- a/src/libcola/cycle_detector.cpp
+++ b/src/libcola/cycle_detector.cpp
@@ -9,6 +9,7 @@
 #include <cassert>
 #include <cycle_detector.h>
 
+#define VISIT_DEBUG
 #define RUN_DEBUG
 
 using namespace std;
@@ -20,14 +21,18 @@ TimeStamp Time;
 CycleDetector::CycleDetector(unsigned numVertices, Edges *edges)  {
   this->V = numVertices; 
   this->edges = edges;
+  nodes = NULL;
 
   // make the adjacency matrix
   this->make_matrix();
-  assert(nodes.size() == this->V);
+  assert(nodes->size() == this->V);
 }
 
 CycleDetector::~CycleDetector()  {
-  if (!nodes.empty())  { for (unsigned i = 0; i < nodes.size(); i++)  { delete nodes[i]; } }
+  if (nodes != NULL)  {
+    for (unsigned i = 0; i < nodes->size(); i++)  { if ((*nodes)[i] != NULL)  { delete (*nodes)[i]; } }
+    delete nodes;
+  }
 }
 
 void CycleDetector::make_matrix()  {
@@ -35,12 +40,16 @@ void CycleDetector::make_matrix()  {
   Edge anEdge;
   Node *newNode;
 
-  if (!nodes.empty())  { for (map<unsigned, Node *>::iterator ni = nodes.begin(); ni != nodes.end(); ni++)  { delete nodes[ni->first]; } }
-  nodes.clear();
+  if (nodes != NULL)  {
+    for (unsigned i = 0; i < nodes->size(); i++)  { if ((*nodes)[i] != NULL)  { delete (*nodes)[i]; } }
+    delete nodes;
+  }
+
+  nodes = new vector<Node *>(this->V, NULL);
   traverse.clear();
 
-  // we should have no nodes in the list
-  assert(nodes.empty());
+  // we should not have an empty array
+  assert(!nodes->empty());
   assert(traverse.empty());
 
   // from the edges passed, fill the adjacency matrix
@@ -53,37 +62,37 @@ void CycleDetector::make_matrix()  {
     #ifdef ADJMAKE_DEBUG
       cout << "vertex1: " << anEdge.first << ", vertex2: " << anEdge.second << endl;
     #endif
-    if (nodes.find(anEdge.first) == nodes.end())  {
+    if (!find_node(nodes, anEdge.first))  {
       #ifdef ADJMAKE_DEBUG
         cout << "Making a new vector indexed at: " << anEdge.first << endl;
       #endif
 
       newNode = new Node(anEdge.first);
       newNode->dests.push_back(anEdge.second);
-      nodes[anEdge.first] = newNode;
+      (*nodes)[anEdge.first] = newNode;
     }
     else  {
-      nodes[anEdge.first]->dests.push_back(anEdge.second);
+      (*nodes)[anEdge.first]->dests.push_back(anEdge.second);
     }
 
     // check if the destination vertex exists in the nodes map
-    if (nodes.find(anEdge.second) == nodes.end())  {
+    if (!find_node(nodes, anEdge.second))  {
       #ifdef ADJMAKE_DEBUG
         cerr << "Making a new vector indexed at: " << anEdge.second << endl;
       #endif
 
       newNode = new Node(anEdge.second);
-      nodes[anEdge.second] = newNode;
+      (*nodes)[anEdge.second] = newNode;
     }
   }
 
-  assert(!nodes.empty());
+  assert(!nodes->empty());
 
   // the following block is code to print out
   // the adjacency matrix.
   #ifdef ADJMAKE_DEBUG
-    for (map<unsigned, Node *>::iterator ni = nodes.begin(); ni != nodes.end(); ni++)  {
-      Node *node = ni->second;
+    for (unsigned i = 0; i < nodes->size(); i++)  {
+      Node *node = (*nodes)[i];
       cout << "nodes[" << node->id << "]: ";
       
       if (isSink(node))  { cout << "SINK"; }
@@ -96,26 +105,23 @@ void CycleDetector::make_matrix()  {
 }
 
 vector<bool> *CycleDetector::detect_cycles()  {
-  vector<bool> *cyclicEdgesMapping = NULL;
+  cyclicEdgesMapping = new vector<bool>(edges->size(), false);
 
-  assert(!nodes.empty());
+  assert(!nodes->empty());
   assert(!edges->empty());
 
   // make a copy of the graph to ensure that we have visited all
   // vertices
   traverse.clear(); assert(traverse.empty());
-  for (unsigned i = 0; i < V; i++)  { traverse[i] = false; }
+  for (unsigned i = 0; i < V; i++)  { traverse.push_back(i); }
   #ifdef SETUP_DEBUG
-    for (map<unsigned, bool>::iterator ivi = traverse.begin(); ivi != traverse.end(); ivi++)  {
-      cout << "traverse{" << ivi->first << "}: " << ivi->second << endl;
+    for (unsigned i = 0; i < traverse.size(); i++)  {
+      cout << "traverse{" << i << "}: " << traverse[i] << endl;
     }
   #endif
 
-  // set up the mapping between the edges and their cyclic truth
-  for(unsigned i = 0; i < edges->size(); i++)  { cyclicEdges[(*edges)[i]] = false; }
-
   // find the cycles
-  assert(nodes.size() > 1);
+  assert(nodes->size() > 1);
 
   // while we still have vertices to visit, visit.
   while (!traverse.empty())  {
@@ -126,19 +132,19 @@ vector<bool> *CycleDetector::detect_cycles()  {
       #ifdef RUN_DEBUG
         cout << "Marking vertex(" << v << ") as CLOSED" << endl;
       #endif
-      nodes[v]->status = Node::DoneVisiting;
+      (*nodes)[v]->status = Node::DoneVisiting;
     }
 
     assert(seenInRun.empty());
 
     #ifdef VISIT_DEBUG
-      cout << "begining search at vertex(" << traverse.begin()->first << ")" << endl;
+      cout << "begining search at vertex(" << traverse[0] << ")" << endl;
     #endif
 
     Time = 0;
 
     // go go go
-    visit(traverse.begin()->first);
+    visit(traverse[0]);
   }
 
   // clean up
@@ -146,17 +152,6 @@ vector<bool> *CycleDetector::detect_cycles()  {
   assert(seenInRun.empty());
   assert(traverse.empty());
 
-  cyclicEdgesMapping = new vector<bool>(edges->size(), false);
-
-  for (unsigned i = 0; i < edges->size(); i++)  {
-    if (cyclicEdges[(*edges)[i]])  { 
-      (*cyclicEdgesMapping)[i] = true;
-      #ifdef OUTPUT_DEBUG
-        cout << "Setting cyclicEdgesMapping[" << i << "] to true" << endl;
-      #endif
-    }
-  }
-
   return cyclicEdgesMapping;
 }
 
@@ -165,60 +160,68 @@ void CycleDetector::mod_graph(unsigned numVertices, Edges *edges)  {
   this->edges = edges;
   // remake the adjaceny matrix
   this->make_matrix();
-  assert(nodes.size() == this->V);
+  assert(nodes->size() == this->V);
 }
 
 void CycleDetector::visit(unsigned k)  {
   unsigned cycleOpen;
+  Node *thisNode = (*nodes)[k];
 
   // state that we have seen this vertex
-  if (traverse.find(k) != traverse.end())  {
+  pair< bool, vector<unsigned>::iterator > haveSeen = find_node(traverse, k);
+  if (haveSeen.first)  {
     #ifdef VISIT_DEBUG
       cout << "Visiting vertex(" << k << ") for the first time" << endl;
     #endif
-    traverse.erase(k);
+    traverse.erase(haveSeen.second);
   }
 
   seenInRun.push(k);
 
   // set up this node as being visited.
-  nodes[k]->stamp = ++Time;
-  nodes[k]->status = Node::BeingVisited;
+  thisNode->stamp = ++Time;
+  thisNode->status = Node::BeingVisited;
 
   // traverse to all the vertices adjacent to this vertex.
-  for (unsigned n = 0; n < nodes[k]->dests.size(); n++)  {
-    unsigned v = nodes[k]->dests[n];
+  for (unsigned n = 0; n < thisNode->dests.size(); n++)  {
+    Node *otherNode = (*nodes)[thisNode->dests[n]];
 
-    if (nodes[v]->status != Node::DoneVisiting)  {
-      if (nodes[v]->status == Node::NotVisited)  {  
+    if (otherNode->status != Node::DoneVisiting)  {
+      if (otherNode->status == Node::NotVisited)  {  
         // visit this node
 	#ifdef VISIT_DEBUG
-          cout << "traversing from vertex(" << k << ") to vertex(" << v << ")" << endl;
+          cout << "traversing from vertex(" << k << ") to vertex(" << otherNode->id << ")" << endl;
 	#endif
-        visit(v);
+        visit(otherNode->id);
       }
 
       // if we are part of a cycle get the timestamp of the ancestor
-      if (nodes[v]->cyclicAncestor != NULL)  { cycleOpen = nodes[v]->cyclicAncestor->stamp; }
+      if (otherNode->cyclicAncestor != NULL)  { cycleOpen = otherNode->cyclicAncestor->stamp; }
       // else just get the timestamp of the node we just visited
-      else  { cycleOpen = nodes[v]->stamp; }
+      else  { cycleOpen = otherNode->stamp; }
 
       // compare the stamp of the traversal with our stamp
-      if (cycleOpen <= nodes[k]->stamp)  {
-	if (nodes[v]->cyclicAncestor == NULL)  { nodes[v]->cyclicAncestor = nodes[v]; }
+      if (cycleOpen <= thisNode->stamp)  {
+	if (otherNode->cyclicAncestor == NULL)  { otherNode->cyclicAncestor = otherNode; }
+
 	// store the cycle
-	cyclicEdges[Edge(k,v)] = true;
+	for (unsigned i = 0; i < edges->size(); i++)  {
+	  if ((*edges)[i] == Edge(k, otherNode->id))  { (*cyclicEdgesMapping)[i] = true; }
+          #ifdef OUTPUT_DEBUG
+            cout << "Setting cyclicEdgesMapping[" << i << "] to true" << endl;
+          #endif
+	}
+
         // this node is part of a cycle
-        if (nodes[k]->cyclicAncestor == NULL)  { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
+        if (thisNode->cyclicAncestor == NULL)  { thisNode->cyclicAncestor = otherNode->cyclicAncestor; }
 
 	// see if we are part of a cycle with a cyclicAncestor that possesses a lower timestamp
-	if (nodes[v]->cyclicAncestor->stamp < nodes[k]->cyclicAncestor->stamp)  { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
+	if (otherNode->cyclicAncestor->stamp < thisNode->cyclicAncestor->stamp)  { thisNode->cyclicAncestor = otherNode->cyclicAncestor; }
       }
     }
   }
 }
 
-
 // determines whether or not a vertex is a sink
 bool CycleDetector::isSink(Node *node)  {
   // a vertex is a sink if it has no outgoing edges,
@@ -226,3 +229,21 @@ bool CycleDetector::isSink(Node *node)  {
   if (node->dests.empty())  { return true; }
   else  { return false; }
 }
+
+bool CycleDetector::find_node(std::vector<Node *> *& list, unsigned k)  {
+  for (unsigned i = 0; i < this->V; i++)  {
+    if ((*list)[i] != NULL)  {
+      if ((*list)[i]->id == k)  { return true; }
+    }
+  }
+
+  return false;
+}
+
+pair< bool, vector<unsigned>::iterator > CycleDetector::find_node(std::vector<unsigned>& list, unsigned k)  {
+  for (vector<unsigned>::iterator ti = traverse.begin(); ti != traverse.end(); ti++)  {
+    if (*ti == k)  { return pair< bool, vector<unsigned>::iterator >(true, ti); }
+  }
+
+  return pair< bool, vector<unsigned>::iterator >(false, traverse.end()); 
+}
diff --git a/src/libcola/cycle_detector.h b/src/libcola/cycle_detector.h
index 5cd52e324..fcb8722fe 100644
--- a/src/libcola/cycle_detector.h
+++ b/src/libcola/cycle_detector.h
@@ -4,12 +4,25 @@
 #include <map>
 #include <vector>
 #include <stack>
-#include "cola.h"
+#include <cola.h>
 
 typedef unsigned TimeStamp;
 typedef std::vector<cola::Edge> Edges;
 typedef std::vector<bool> CyclicEdges;
-class Node;
+
+class Node  {
+  public:
+    enum StatusType { NotVisited, BeingVisited, DoneVisiting };
+
+    unsigned id;
+    TimeStamp stamp;
+    Node *cyclicAncestor;
+    std::vector<unsigned> dests;
+    StatusType status;
+
+    Node(unsigned id)  { this->id = id; cyclicAncestor = NULL; status = NotVisited; }
+    ~Node()  {}
+};
 
 class CycleDetector  {
   public:
@@ -26,29 +39,17 @@ class CycleDetector  {
     Edges *edges;
 
     // internally used variables.
-    std::map<unsigned, Node *> nodes; // the nodes in the graph
-    std::map<cola::Edge, bool> cyclicEdges; // the cyclic edges in the graph.
-    std::map<unsigned, bool> traverse; // nodes still left to visit in the graph
+    std::vector<Node *> *nodes; // the nodes in the graph
+    std::vector<bool> *cyclicEdgesMapping; // the cyclic edges in the graph.
+    std::vector<unsigned> traverse; // nodes still left to visit in the graph
     std::stack<unsigned> seenInRun; // nodes visited in a single pass.
 
     // internally used methods
     void make_matrix();
     void visit(unsigned k);
     bool isSink(Node *node);
-};
-
-class Node  {
-  public:
-    enum StatusType { NotVisited, BeingVisited, DoneVisiting };
-
-    unsigned id;
-    TimeStamp stamp;
-    Node *cyclicAncestor;
-    vector<unsigned> dests;
-    StatusType status;
-
-    Node(unsigned id)  { this->id = id; cyclicAncestor = NULL; status = NotVisited; }
-    ~Node()  {}
+    bool find_node(std::vector<Node *> *& list, unsigned k);
+    std::pair< bool, std::vector<unsigned>::iterator > find_node(std::vector<unsigned>& list, unsigned k);
 };
 
 #endif