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