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>
12 #define VISIT_DEBUG
13 #define RUN_DEBUG
15 using namespace std;
16 using namespace cola;
18 // a global var representing time
19 TimeStamp Time;
21 CycleDetector::CycleDetector(unsigned numVertices, Edges *edges) {
22 this->V = numVertices;
23 this->edges = edges;
24 nodes = NULL;
26 // make the adjacency matrix
27 this->make_matrix();
28 assert(nodes->size() == this->V);
29 }
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 }
38 void CycleDetector::make_matrix() {
39 Edges::iterator ei;
40 Edge anEdge;
41 Node *newNode;
43 if (nodes != NULL) {
44 for (unsigned i = 0; i < nodes->size(); i++) { if ((*nodes)[i] != NULL) { delete (*nodes)[i]; } }
45 delete nodes;
46 }
48 nodes = new vector<Node *>(this->V, NULL);
49 traverse.clear();
51 // we should not have an empty array
52 assert(!nodes->empty());
53 assert(traverse.empty());
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
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 }
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
84 newNode = new Node(anEdge.second);
85 (*nodes)[anEdge.second] = newNode;
86 }
87 }
89 assert(!nodes->empty());
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 << "]: ";
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 }
107 vector<bool> *CycleDetector::detect_cycles() {
108 cyclicEdgesMapping = new vector<bool>(edges->size(), false);
110 assert(!nodes->empty());
111 assert(!edges->empty());
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
123 // find the cycles
124 assert(nodes->size() > 1);
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 }
138 assert(seenInRun.empty());
140 #ifdef VISIT_DEBUG
141 cout << "begining search at vertex(" << traverse[0] << ")" << endl;
142 #endif
144 Time = 0;
146 // go go go
147 visit(traverse[0]);
148 }
150 // clean up
151 while (!seenInRun.empty()) { seenInRun.pop(); }
152 assert(seenInRun.empty());
153 assert(traverse.empty());
155 return cyclicEdgesMapping;
156 }
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 }
166 void CycleDetector::visit(unsigned k) {
167 unsigned cycleOpen;
168 Node *thisNode = (*nodes)[k];
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 }
179 seenInRun.push(k);
181 // set up this node as being visited.
182 thisNode->stamp = ++Time;
183 thisNode->status = Node::BeingVisited;
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]];
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 }
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; }
203 // compare the stamp of the traversal with our stamp
204 if (cycleOpen <= thisNode->stamp) {
205 if (otherNode->cyclicAncestor == NULL) { otherNode->cyclicAncestor = otherNode; }
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 }
215 // this node is part of a cycle
216 if (thisNode->cyclicAncestor == NULL) { thisNode->cyclicAncestor = otherNode->cyclicAncestor; }
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 }
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 }
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 }
240 return false;
241 }
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 }
248 return pair< bool, vector<unsigned>::iterator >(false, traverse.end());
249 }