cyclegraph.cc

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