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