1 #ifndef CYCLE_DETECTOR_H
2 #define CYCLE_DETECTOR_H
4 #include <map>
5 #include <vector>
6 #include <stack>
7 #include <cola.h>
9 typedef unsigned TimeStamp;
10 typedef std::vector<cola::Edge> Edges;
11 typedef std::vector<bool> CyclicEdges;
13 class Node {
14 public:
15 enum StatusType { NotVisited, BeingVisited, DoneVisiting };
17 unsigned id;
18 TimeStamp stamp;
19 Node *cyclicAncestor;
20 std::vector<unsigned> dests;
21 StatusType status;
23 Node(unsigned id) { this->id = id; cyclicAncestor = NULL; status = NotVisited; }
24 ~Node() {}
25 };
27 class CycleDetector {
28 public:
29 CycleDetector(unsigned numVertices, Edges *edges);
30 ~CycleDetector();
31 std::vector<bool> *detect_cycles();
32 void mod_graph(unsigned numVertices, Edges *edges);
33 unsigned getV() { return this->V; }
34 Edges *getEdges() { return this->edges; }
36 private:
37 // attributes
38 unsigned V;
39 Edges *edges;
41 // internally used variables.
42 std::vector<Node *> *nodes; // the nodes in the graph
43 std::vector<bool> *cyclicEdgesMapping; // the cyclic edges in the graph.
44 std::vector<unsigned> traverse; // nodes still left to visit in the graph
45 std::stack<unsigned> seenInRun; // nodes visited in a single pass.
47 // internally used methods
48 void make_matrix();
49 void visit(unsigned k);
50 bool isSink(Node *node);
51 bool find_node(std::vector<Node *> *& list, unsigned k);
52 std::pair< bool, std::vector<unsigned>::iterator > find_node(std::vector<unsigned>& list, unsigned k);
53 };
55 #endif