Layout algorithm is now applied to each connected component in the

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

(bzr r1421)

1 files changed, 77 insertions, 56 deletions

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()); 
+}