cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3
   4 CycleGraph::CycleGraph() {
   5         hasCycles=false;
   6 }
   7
   8 CycleNode * CycleGraph::getNode(ModelAction * action) {
   9         CycleNode *node=actionToNode.get(action);
  10         if (node==NULL) {
  11                 node=new CycleNode(action);
  12                 actionToNode.put(action, node);
  13         }
  14         return node;
  15 }
  16
  17 void CycleGraph::addEdge(ModelAction *from, ModelAction *to) {
  18         CycleNode *fromnode=getNode(from);
  19         CycleNode *tonode=getNode(to);
  20         if (!hasCycles) {
  21                 // Check for Cycles
  22                 hasCycles=checkReachable(fromnode, tonode);
  23         }
  24         fromnode->addEdge(tonode);
  25 }
  26
  27 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
  28         std::vector<CycleNode *> queue;
  29         HashTable<CycleNode *, CycleNode *, uintptr_t, 4> discovered;
  30
  31         queue.push_back(from);
  32         discovered.put(from, from);
  33         while(!queue.empty()) {
  34                 CycleNode * node=queue.back();
  35                 queue.pop_back();
  36                 if (node==to)
  37                         return true;
  38
  39                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
  40                         CycleNode *next=(*node->getEdges())[i];
  41                         if (!discovered.contains(next)) {
  42                                 discovered.put(next,next);
  43                                 queue.push_back(next);
  44                         }
  45                 }
  46         }
  47         return false;
  48 }
  49
  50 CycleNode::CycleNode(ModelAction *modelaction) {
  51         action=modelaction;
  52 }
  53
  54 std::vector<CycleNode *> * CycleNode::getEdges() {
  55         return &edges;
  56 }
  57
  58 void CycleNode::addEdge(CycleNode * node) {
  59         edges.push_back(node);
  60 }