src/libcola/cycle_detector.cpp

   1 /* Cycle detector that returns a list of
   2  * edges involved in cycles in a digraph.
   3  *
   4  * Kieran Simpson 2006
   5 */
   6 #include <iostream>
   7 #include <stack>
   8 #include <vector>
   9 #include <cassert>
  10 #include <cycle_detector.h>
  11
  12 #define RUN_DEBUG
  13
  14 using namespace std;
  15 using namespace cola;
  16
  17 // a global var representing time
  18 TimeStamp Time;
  19
  20 CycleDetector::CycleDetector(unsigned numVertices, Edges *edges)  {
  21   this->V = numVertices;
  22   this->edges = edges;
  23
  24   // make the adjacency matrix
  25   this->make_matrix();
  26   assert(nodes.size() == this->V);
  27 }
  28
  29 CycleDetector::~CycleDetector()  {
  30   if (!nodes.empty())  { for (unsigned i = 0; i < nodes.size(); i++)  { delete nodes[i]; } }
  31 }
  32
  33 void CycleDetector::make_matrix()  {
  34   Edges::iterator ei;
  35   Edge anEdge;
  36   Node *newNode;
  37
  38   if (!nodes.empty())  { for (map<unsigned, Node *>::iterator ni = nodes.begin(); ni != nodes.end(); ni++)  { delete nodes[ni->first]; } }
  39   nodes.clear();
  40   traverse.clear();
  41
  42   // we should have no nodes in the list
  43   assert(nodes.empty());
  44   assert(traverse.empty());
  45
  46   // from the edges passed, fill the adjacency matrix
  47   for (ei = edges->begin(); ei != edges->end(); ei++)  {
  48     anEdge = *ei;
  49     // the matrix is indexed by the first vertex of the edge
  50     // the second vertex of the edge is pushed onto another
  51     // vector of all vertices connected to the first vertex
  52     // with a directed edge
  53     #ifdef ADJMAKE_DEBUG
  54       cout << "vertex1: " << anEdge.first << ", vertex2: " << anEdge.second << endl;
  55     #endif
  56     if (nodes.find(anEdge.first) == nodes.end())  {
  57       #ifdef ADJMAKE_DEBUG
  58         cout << "Making a new vector indexed at: " << anEdge.first << endl;
  59       #endif
  60
  61       newNode = new Node(anEdge.first);
  62       newNode->dests.push_back(anEdge.second);
  63       nodes[anEdge.first] = newNode;
  64     }
  65     else  {
  66       nodes[anEdge.first]->dests.push_back(anEdge.second);
  67     }
  68
  69     // check if the destination vertex exists in the nodes map
  70     if (nodes.find(anEdge.second) == nodes.end())  {
  71       #ifdef ADJMAKE_DEBUG
  72         cerr << "Making a new vector indexed at: " << anEdge.second << endl;
  73       #endif
  74
  75       newNode = new Node(anEdge.second);
  76       nodes[anEdge.second] = newNode;
  77     }
  78   }
  79
  80   assert(!nodes.empty());
  81
  82   // the following block is code to print out
  83   // the adjacency matrix.
  84   #ifdef ADJMAKE_DEBUG
  85     for (map<unsigned, Node *>::iterator ni = nodes.begin(); ni != nodes.end(); ni++)  {
  86       Node *node = ni->second;
  87       cout << "nodes[" << node->id << "]: ";
  88
  89       if (isSink(node))  { cout << "SINK"; }
  90       else  {
  91         for (unsigned j = 0; j < node->dests.size(); j++)  { cout << node->dests[j] << " "; }
  92       }
  93       cout << endl;
  94     }
  95   #endif
  96 }
  97
  98 vector<bool> *CycleDetector::detect_cycles()  {
  99   vector<bool> *cyclicEdgesMapping = NULL;
 100
 101   assert(!nodes.empty());
 102   assert(!edges->empty());
 103
 104   // make a copy of the graph to ensure that we have visited all
 105   // vertices
 106   traverse.clear(); assert(traverse.empty());
 107   for (unsigned i = 0; i < V; i++)  { traverse[i] = false; }
 108   #ifdef SETUP_DEBUG
 109     for (map<unsigned, bool>::iterator ivi = traverse.begin(); ivi != traverse.end(); ivi++)  {
 110       cout << "traverse{" << ivi->first << "}: " << ivi->second << endl;
 111     }
 112   #endif
 113
 114   // set up the mapping between the edges and their cyclic truth
 115   for(unsigned i = 0; i < edges->size(); i++)  { cyclicEdges[(*edges)[i]] = false; }
 116
 117   // find the cycles
 118   assert(nodes.size() > 1);
 119
 120   // while we still have vertices to visit, visit.
 121   while (!traverse.empty())  {
 122     // mark any vertices seen in a previous run as closed
 123     while (!seenInRun.empty())  {
 124       unsigned v = seenInRun.top();
 125       seenInRun.pop();
 126       #ifdef RUN_DEBUG
 127         cout << "Marking vertex(" << v << ") as CLOSED" << endl;
 128       #endif
 129       nodes[v]->status = Node::DoneVisiting;
 130     }
 131
 132     assert(seenInRun.empty());
 133
 134     #ifdef VISIT_DEBUG
 135       cout << "begining search at vertex(" << traverse.begin()->first << ")" << endl;
 136     #endif
 137
 138     Time = 0;
 139
 140     // go go go
 141     visit(traverse.begin()->first);
 142   }
 143
 144   // clean up
 145   while (!seenInRun.empty())  { seenInRun.pop(); }
 146   assert(seenInRun.empty());
 147   assert(traverse.empty());
 148
 149   cyclicEdgesMapping = new vector<bool>(edges->size(), false);
 150
 151   for (unsigned i = 0; i < edges->size(); i++)  {
 152     if (cyclicEdges[(*edges)[i]])  {
 153       (*cyclicEdgesMapping)[i] = true;
 154       #ifdef OUTPUT_DEBUG
 155         cout << "Setting cyclicEdgesMapping[" << i << "] to true" << endl;
 156       #endif
 157     }
 158   }
 159
 160   return cyclicEdgesMapping;
 161 }
 162
 163 void CycleDetector::mod_graph(unsigned numVertices, Edges *edges)  {
 164   this->V = numVertices;
 165   this->edges = edges;
 166   // remake the adjaceny matrix
 167   this->make_matrix();
 168   assert(nodes.size() == this->V);
 169 }
 170
 171 void CycleDetector::visit(unsigned k)  {
 172   unsigned cycleOpen;
 173
 174   // state that we have seen this vertex
 175   if (traverse.find(k) != traverse.end())  {
 176     #ifdef VISIT_DEBUG
 177       cout << "Visiting vertex(" << k << ") for the first time" << endl;
 178     #endif
 179     traverse.erase(k);
 180   }
 181
 182   seenInRun.push(k);
 183
 184   // set up this node as being visited.
 185   nodes[k]->stamp = ++Time;
 186   nodes[k]->status = Node::BeingVisited;
 187
 188   // traverse to all the vertices adjacent to this vertex.
 189   for (unsigned n = 0; n < nodes[k]->dests.size(); n++)  {
 190     unsigned v = nodes[k]->dests[n];
 191
 192     if (nodes[v]->status != Node::DoneVisiting)  {
 193       if (nodes[v]->status == Node::NotVisited)  {
 194         // visit this node
 195         #ifdef VISIT_DEBUG
 196           cout << "traversing from vertex(" << k << ") to vertex(" << v << ")" << endl;
 197         #endif
 198         visit(v);
 199       }
 200
 201       // if we are part of a cycle get the timestamp of the ancestor
 202       if (nodes[v]->cyclicAncestor != NULL)  { cycleOpen = nodes[v]->cyclicAncestor->stamp; }
 203       // else just get the timestamp of the node we just visited
 204       else  { cycleOpen = nodes[v]->stamp; }
 205
 206       // compare the stamp of the traversal with our stamp
 207       if (cycleOpen <= nodes[k]->stamp)  {
 208         if (nodes[v]->cyclicAncestor == NULL)  { nodes[v]->cyclicAncestor = nodes[v]; }
 209         // store the cycle
 210         cyclicEdges[Edge(k,v)] = true;
 211         // this node is part of a cycle
 212         if (nodes[k]->cyclicAncestor == NULL)  { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
 213
 214         // see if we are part of a cycle with a cyclicAncestor that possesses a lower timestamp
 215         if (nodes[v]->cyclicAncestor->stamp < nodes[k]->cyclicAncestor->stamp)  { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
 216       }
 217     }
 218   }
 219 }
 220
 221
 222 // determines whether or not a vertex is a sink
 223 bool CycleDetector::isSink(Node *node)  {
 224   // a vertex is a sink if it has no outgoing edges,
 225   // or that the adj entry is empty
 226   if (node->dests.empty())  { return true; }
 227   else  { return false; }
 228 }