Merge https://gitlab.com/inkscape/inkscape into selectable-knots

1 files changed, 0 insertions, 249 deletions

diff --git a/src/libcola/cycle_detector.cpp b/src/libcola/cycle_detector.cpp
deleted file mode 100644
index 11e24a0ba..000000000
--- a/src/libcola/cycle_detector.cpp
+++ /dev/null
@@ -1,249 +0,0 @@
-/* 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 VISIT_DEBUG
-#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;
-  nodes = NULL;
-
-  // make the adjacency matrix
-  this->make_matrix();
-  assert(nodes->size() == this->V);
-}
-
-CycleDetector::~CycleDetector()  {
-  if (nodes != NULL)  {
-    for (unsigned i = 0; i < nodes->size(); i++)  { if ((*nodes)[i] != NULL)  { delete (*nodes)[i]; } }
-    delete nodes;
-  }
-}
-
-void CycleDetector::make_matrix()  {
-  Edges::iterator ei;
-  Edge anEdge;
-  Node *newNode;
-
-  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 not have an empty array
-  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 (!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;
-    }
-    else  {
-      (*nodes)[anEdge.first]->dests.push_back(anEdge.second);
-    }
-
-    // check if the destination vertex exists in the nodes map
-    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;
-    }
-  }
-
-  assert(!nodes->empty());
-
-  // the following block is code to print out
-  // the adjacency matrix.
-  #ifdef ADJMAKE_DEBUG
-    for (unsigned i = 0; i < nodes->size(); i++)  {
-      Node *node = (*nodes)[i];
-      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()  {
-  cyclicEdgesMapping = new vector<bool>(edges->size(), false);
-
-  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.push_back(i); }
-  #ifdef SETUP_DEBUG
-    for (unsigned i = 0; i < traverse.size(); i++)  {
-      cout << "traverse{" << i << "}: " << traverse[i] << endl;
-    }
-  #endif
-
-  // 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[0] << ")" << endl;
-    #endif
-
-    Time = 0;
-
-    // go go go
-    visit(traverse[0]);
-  }
-
-  // clean up
-  while (!seenInRun.empty())  { seenInRun.pop(); }
-  assert(seenInRun.empty());
-  assert(traverse.empty());
-
-  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;
-  Node *thisNode = (*nodes)[k];
-
-  // state that we have seen this vertex
-  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(haveSeen.second);
-  }
-
-  seenInRun.push(k);
-
-  // set up this node as being visited.
-  thisNode->stamp = ++Time;
-  thisNode->status = Node::BeingVisited;
-
-  // traverse to all the vertices adjacent to this vertex.
-  for (unsigned n = 0; n < thisNode->dests.size(); n++)  {
-    Node *otherNode = (*nodes)[thisNode->dests[n]];
-
-    if (otherNode->status != Node::DoneVisiting)  {
-      if (otherNode->status == Node::NotVisited)  {  
-        // visit this node
-	#ifdef VISIT_DEBUG
-          cout << "traversing from vertex(" << k << ") to vertex(" << otherNode->id << ")" << endl;
-	#endif
-        visit(otherNode->id);
-      }
-
-      // if we are part of a cycle get the timestamp of the ancestor
-      if (otherNode->cyclicAncestor != NULL)  { cycleOpen = otherNode->cyclicAncestor->stamp; }
-      // else just get the timestamp of the node we just visited
-      else  { cycleOpen = otherNode->stamp; }
-
-      // compare the stamp of the traversal with our stamp
-      if (cycleOpen <= thisNode->stamp)  {
-	if (otherNode->cyclicAncestor == NULL)  { otherNode->cyclicAncestor = otherNode; }
-
-	// store the cycle
-	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 (thisNode->cyclicAncestor == NULL)  { thisNode->cyclicAncestor = otherNode->cyclicAncestor; }
-
-	// see if we are part of a cycle with a cyclicAncestor that possesses a lower timestamp
-	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,
-  // or that the adj entry is empty
-  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()); 
-}