Previously graph layout was done using the Kamada-Kawai layout algorithm

implemented in Boost.  I am replacing this with a custom implementation of
a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

(bzr r1394)

1 files changed, 228 insertions, 0 deletions

diff --git a/src/libcola/cycle_detector.cpp b/src/libcola/cycle_detector.cpp
new file mode 100644
index 000000000..ddc056e4d
--- /dev/null
+++ b/src/libcola/cycle_detector.cpp
@@ -0,0 +1,228 @@
+/* Cycle detector that returns a list of 
+ * edges involved in cycles in a digraph.
+ *
+ * Kieran Simpson 2006
+*/
+#include <iostream>
+#include <stack>
+#include <vector>
+#include <cassert>
+#include <cycle_detector.h>
+
+#define RUN_DEBUG
+
+using namespace std;
+using namespace cola;
+
+// a global var representing time
+TimeStamp Time;
+
+CycleDetector::CycleDetector(unsigned numVertices, Edges *edges)  {
+  this->V = numVertices; 
+  this->edges = edges;
+
+  // make the adjacency matrix
+  this->make_matrix();
+  assert(nodes.size() == this->V);
+}
+
+CycleDetector::~CycleDetector()  {
+  if (!nodes.empty())  { for (unsigned i = 0; i < nodes.size(); i++)  { delete nodes[i]; } }
+}
+
+void CycleDetector::make_matrix()  {
+  Edges::iterator ei;
+  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();
+  traverse.clear();
+
+  // we should have no nodes in the list
+  assert(nodes.empty());
+  assert(traverse.empty());
+
+  // from the edges passed, fill the adjacency matrix
+  for (ei = edges->begin(); ei != edges->end(); ei++)  {
+    anEdge = *ei;
+    // the matrix is indexed by the first vertex of the edge
+    // the second vertex of the edge is pushed onto another
+    // vector of all vertices connected to the first vertex
+    // with a directed edge
+    #ifdef ADJMAKE_DEBUG
+      cout << "vertex1: " << anEdge.first << ", vertex2: " << anEdge.second << endl;
+    #endif
+    if (nodes.find(anEdge.first) == nodes.end())  {
+      #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;
+    }
+    else  {
+      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())  {
+      #ifdef ADJMAKE_DEBUG
+        cerr << "Making a new vector indexed at: " << anEdge.second << endl;
+      #endif
+
+      newNode = new Node(anEdge.second);
+      nodes[anEdge.second] = newNode;
+    }
+  }
+
+  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;
+      cout << "nodes[" << node->id << "]: ";
+      
+      if (isSink(node))  { cout << "SINK"; }
+      else  {
+        for (unsigned j = 0; j < node->dests.size(); j++)  { cout << node->dests[j] << " "; }
+      }
+      cout << endl;
+    }
+  #endif
+}
+
+vector<bool> *CycleDetector::detect_cycles()  {
+  vector<bool> *cyclicEdgesMapping = NULL;
+
+  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; }
+  #ifdef SETUP_DEBUG
+    for (map<unsigned, bool>::iterator ivi = traverse.begin(); ivi != traverse.end(); ivi++)  {
+      cout << "traverse{" << ivi->first << "}: " << ivi->second << 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);
+
+  // while we still have vertices to visit, visit.
+  while (!traverse.empty())  {
+    // mark any vertices seen in a previous run as closed
+    while (!seenInRun.empty())  {
+      unsigned v = seenInRun.top();
+      seenInRun.pop();
+      #ifdef RUN_DEBUG
+        cout << "Marking vertex(" << v << ") as CLOSED" << endl;
+      #endif
+      nodes[v]->status = Node::DoneVisiting;
+    }
+
+    assert(seenInRun.empty());
+
+    #ifdef VISIT_DEBUG
+      cout << "begining search at vertex(" << traverse.begin()->first << ")" << endl;
+    #endif
+
+    Time = 0;
+
+    // go go go
+    visit(traverse.begin()->first);
+  }
+
+  // clean up
+  while (!seenInRun.empty())  { seenInRun.pop(); }
+  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;
+}
+
+void CycleDetector::mod_graph(unsigned numVertices, Edges *edges)  {
+  this->V = numVertices;
+  this->edges = edges;
+  // remake the adjaceny matrix
+  this->make_matrix();
+  assert(nodes.size() == this->V);
+}
+
+void CycleDetector::visit(unsigned k)  {
+  unsigned cycleOpen;
+
+  // state that we have seen this vertex
+  if (traverse.find(k) != traverse.end())  {
+    #ifdef VISIT_DEBUG
+      cout << "Visiting vertex(" << k << ") for the first time" << endl;
+    #endif
+    traverse.erase(k);
+  }
+
+  seenInRun.push(k);
+
+  // set up this node as being visited.
+  nodes[k]->stamp = ++Time;
+  nodes[k]->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];
+
+    if (nodes[v]->status != Node::DoneVisiting)  {
+      if (nodes[v]->status == Node::NotVisited)  {  
+        // visit this node
+	#ifdef VISIT_DEBUG
+          cout << "traversing from vertex(" << k << ") to vertex(" << v << ")" << endl;
+	#endif
+        visit(v);
+      }
+
+      // if we are part of a cycle get the timestamp of the ancestor
+      if (nodes[v]->cyclicAncestor != NULL)  { cycleOpen = nodes[v]->cyclicAncestor->stamp; }
+      // else just get the timestamp of the node we just visited
+      else  { cycleOpen = nodes[v]->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]; }
+	// store the cycle
+	cyclicEdges[Edge(k,v)] = true;
+        // this node is part of a cycle
+        if (nodes[k]->cyclicAncestor == NULL)  { nodes[k]->cyclicAncestor = nodes[v]->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; }
+      }
+    }
+  }
+}
+
+
+// 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,
+  // or that the adj entry is empty
+  if (node->dests.empty())  { return true; }
+  else  { return false; }
+}