![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
index ddc056e4d50c3e2fdd20b4d815f7aa966bee240e..89a2ccaae2771b1abd31abc8f067fcab8f67459e 100644 (file)
#include <cassert>
#include <cycle_detector.h>
+#define VISIT_DEBUG
#define RUN_DEBUG
using namespace std;
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);
+ assert(nodes->size() == this->V);
}
CycleDetector::~CycleDetector() {
- if (!nodes.empty()) { for (unsigned i = 0; i < nodes.size(); i++) { delete nodes[i]; } }
+ if (nodes != NULL) {
+ for (unsigned i = 0; i < nodes->size(); i++) { if ((*nodes)[i] != NULL) { delete (*nodes)[i]; } }
+ delete nodes;
+ }
}
void CycleDetector::make_matrix() {
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();
+ 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 have no nodes in the list
- assert(nodes.empty());
+ // we should not have an empty array
+ assert(!nodes->empty());
assert(traverse.empty());
// from the edges passed, fill the adjacency matrix
#ifdef ADJMAKE_DEBUG
cout << "vertex1: " << anEdge.first << ", vertex2: " << anEdge.second << endl;
#endif
- if (nodes.find(anEdge.first) == nodes.end()) {
+ 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;
+ (*nodes)[anEdge.first] = newNode;
}
else {
- nodes[anEdge.first]->dests.push_back(anEdge.second);
+ (*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()) {
+ 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;
+ (*nodes)[anEdge.second] = newNode;
}
}
- assert(!nodes.empty());
+ 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;
+ for (unsigned i = 0; i < nodes->size(); i++) {
+ Node *node = (*nodes)[i];
cout << "nodes[" << node->id << "]: ";
if (isSink(node)) { cout << "SINK"; }
}
vector<bool> *CycleDetector::detect_cycles() {
- vector<bool> *cyclicEdgesMapping = NULL;
+ cyclicEdgesMapping = new vector<bool>(edges->size(), false);
- assert(!nodes.empty());
+ 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; }
+ for (unsigned i = 0; i < V; i++) { traverse.push_back(i); }
#ifdef SETUP_DEBUG
- for (map<unsigned, bool>::iterator ivi = traverse.begin(); ivi != traverse.end(); ivi++) {
- cout << "traverse{" << ivi->first << "}: " << ivi->second << endl;
+ for (unsigned i = 0; i < traverse.size(); i++) {
+ cout << "traverse{" << i << "}: " << traverse[i] << 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);
+ assert(nodes->size() > 1);
// while we still have vertices to visit, visit.
while (!traverse.empty()) {
#ifdef RUN_DEBUG
cout << "Marking vertex(" << v << ") as CLOSED" << endl;
#endif
- nodes[v]->status = Node::DoneVisiting;
+ (*nodes)[v]->status = Node::DoneVisiting;
}
assert(seenInRun.empty());
#ifdef VISIT_DEBUG
- cout << "begining search at vertex(" << traverse.begin()->first << ")" << endl;
+ cout << "begining search at vertex(" << traverse[0] << ")" << endl;
#endif
Time = 0;
// go go go
- visit(traverse.begin()->first);
+ visit(traverse[0]);
}
// clean up
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;
}
this->edges = edges;
// remake the adjaceny matrix
this->make_matrix();
- assert(nodes.size() == this->V);
+ assert(nodes->size() == this->V);
}
void CycleDetector::visit(unsigned k) {
unsigned cycleOpen;
+ Node *thisNode = (*nodes)[k];
// state that we have seen this vertex
- if (traverse.find(k) != traverse.end()) {
+ 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(k);
+ traverse.erase(haveSeen.second);
}
seenInRun.push(k);
// set up this node as being visited.
- nodes[k]->stamp = ++Time;
- nodes[k]->status = Node::BeingVisited;
+ thisNode->stamp = ++Time;
+ thisNode->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];
+ for (unsigned n = 0; n < thisNode->dests.size(); n++) {
+ Node *otherNode = (*nodes)[thisNode->dests[n]];
- if (nodes[v]->status != Node::DoneVisiting) {
- if (nodes[v]->status == Node::NotVisited) {
+ if (otherNode->status != Node::DoneVisiting) {
+ if (otherNode->status == Node::NotVisited) {
// visit this node
#ifdef VISIT_DEBUG
- cout << "traversing from vertex(" << k << ") to vertex(" << v << ")" << endl;
+ cout << "traversing from vertex(" << k << ") to vertex(" << otherNode->id << ")" << endl;
#endif
- visit(v);
+ visit(otherNode->id);
}
// if we are part of a cycle get the timestamp of the ancestor
- if (nodes[v]->cyclicAncestor != NULL) { cycleOpen = nodes[v]->cyclicAncestor->stamp; }
+ if (otherNode->cyclicAncestor != NULL) { cycleOpen = otherNode->cyclicAncestor->stamp; }
// else just get the timestamp of the node we just visited
- else { cycleOpen = nodes[v]->stamp; }
+ else { cycleOpen = otherNode->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]; }
+ if (cycleOpen <= thisNode->stamp) {
+ if (otherNode->cyclicAncestor == NULL) { otherNode->cyclicAncestor = otherNode; }
+
// store the cycle
- cyclicEdges[Edge(k,v)] = true;
+ 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 (nodes[k]->cyclicAncestor == NULL) { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
+ 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 (nodes[v]->cyclicAncestor->stamp < nodes[k]->cyclicAncestor->stamp) { nodes[k]->cyclicAncestor = nodes[v]->cyclicAncestor; }
+ 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,
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());
+}