src/libcola/cycle_detector.h

   1 #ifndef CYCLE_DETECTOR_H
   2 #define CYCLE_DETECTOR_H
   3
   4 #include <map>
   5 #include <vector>
   6 #include <stack>
   7 #include <cola.h>
   8
   9 typedef unsigned TimeStamp;
  10 typedef std::vector<cola::Edge> Edges;
  11 typedef std::vector<bool> CyclicEdges;
  12
  13 class Node  {
  14   public:
  15     enum StatusType { NotVisited, BeingVisited, DoneVisiting };
  16
  17     unsigned id;
  18     TimeStamp stamp;
  19     Node *cyclicAncestor;
  20     std::vector<unsigned> dests;
  21     StatusType status;
  22
  23     Node(unsigned id)  { this->id = id; cyclicAncestor = NULL; status = NotVisited; }
  24     virtual ~Node()  {}
  25 };
  26
  27 class CycleDetector  {
  28   public:
  29     CycleDetector(unsigned numVertices, Edges *edges);
  30     virtual ~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; }
  35
  36   private:
  37     // attributes
  38     unsigned V;
  39     Edges *edges;
  40
  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.
  46
  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 };
  54
  55 #endif