src/Encoders/orderencoder.c

   1
   2 #include "orderencoder.h"
   3 #include "structs.h"
   4 #include "csolver.h"
   5 #include "boolean.h"
   6 #include "ordergraph.h"
   7 #include "order.h"
   8 #include "ordernode.h"
   9
  10
  11 NodeInfo* allocNodeInfo(){
  12         NodeInfo* This = (NodeInfo*) ourmalloc(sizeof(NodeInfo));
  13         This->finishTime = 0;
  14         This->status = NOTVISITED;
  15         return This;
  16 }
  17
  18 void deleteNodeInfo(NodeInfo* info){
  19         ourfree(info);
  20 }
  21
  22 OrderEncoder* allocOrderEncoder(){
  23         OrderEncoder* This = (OrderEncoder*) ourmalloc(sizeof(OrderEncoder));
  24         initDefVectorOrderGraph( &This->graphs );
  25         return This;
  26 }
  27
  28 void deleteOrderEncoder(OrderEncoder* This){
  29         uint size = getSizeVectorOrderGraph(&This->graphs);
  30         for(uint i=0; i<size; i++){
  31                 deleteOrderGraph(getVectorOrderGraph(&This->graphs, i));
  32         }
  33         ourfree(This);
  34 }
  35
  36 OrderEncoder* buildOrderGraphs(CSolver* This){
  37         uint size = getSizeVectorOrder(This->allOrders);
  38         OrderEncoder* oEncoder = allocOrderEncoder();
  39         for(uint i=0; i<size; i++){
  40                 OrderGraph* orderGraph = allocOrderGraph();
  41                 Order* order = getVectorOrder(This->allOrders, i);
  42                 uint constrSize = getSizeVectorBoolean(&order->constraints);
  43                 for(uint j=0; j<constrSize; j++){
  44                         addOrderConstraintToOrderGraph(orderGraph, getVectorBoolean(&order->constraints, j));
  45                 }
  46                 pushVectorOrderGraph(&oEncoder->graphs, orderGraph);
  47         }
  48         return oEncoder;
  49 }
  50
  51 void DFS(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNodeInfo* nodeToInfo){
  52         uint timer=0;
  53         HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
  54         while(hasNextOrderNode(iterator)){
  55                 OrderNode* node = nextOrderNode(iterator);
  56                 NodeInfo* info= getNodeInfo(nodeToInfo, node);
  57                 if(info->status == NOTVISITED){
  58                         info->status = VISITED;
  59                         DFSNodeVisit(node, finishNodes, nodeToInfo, &timer, false);
  60                         info->status = FINISHED;
  61                         info->finishTime = timer;
  62                         pushVectorOrderNode(finishNodes, node);
  63                 }
  64         }
  65         deleteIterOrderNode(iterator);
  66 }
  67
  68 void DFSReverse(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNodeInfo* nodeToInfo){
  69         uint timer=0;
  70         uint size = getSizeVectorOrderNode(finishNodes);
  71         for(int i=size-1; i>=0; i--){
  72                 OrderNode* node = getVectorOrderNode(finishNodes, i);
  73                 NodeInfo* info= getNodeInfo(nodeToInfo, node);
  74                 if(info->status == NOTVISITED){
  75                         info->status = VISITED;
  76                         DFSNodeVisit(node, NULL, nodeToInfo, &timer, true);
  77                         info->status = FINISHED;
  78                         info->finishTime = timer;
  79                         pushVectorOrderNode(&graph->scc, node);
  80                 }
  81         }
  82 }
  83
  84 void DFSNodeVisit(OrderNode* node, VectorOrderNode* finishNodes,
  85         HashTableNodeInfo* nodeToInfo, uint* timer, bool isReverse){
  86         (*timer)++;
  87         model_print("Timer in DFSNodeVisit:%u\n", *timer);
  88         HSIteratorOrderEdge* iterator = isReverse?iteratorOrderEdge(node->inEdges):iteratorOrderEdge(node->outEdges);
  89         while(hasNextOrderEdge(iterator)){
  90                 OrderEdge* edge = nextOrderEdge(iterator);
  91                 OrderNode* child = isReverse? edge->source: edge->sink;
  92                 NodeInfo* childInfo = getNodeInfo(nodeToInfo, child);
  93                 if(childInfo->status == NOTVISITED){
  94                         childInfo->status = VISITED;
  95                         DFSNodeVisit(child, finishNodes, nodeToInfo, timer, isReverse);
  96                         childInfo->status = FINISHED;
  97                         childInfo->finishTime = *timer;
  98                         if(!isReverse)
  99                                 pushVectorOrderNode(finishNodes, child);
 100                 }
 101         }
 102         deleteIterOrderEdge(iterator);
 103 }
 104
 105 void initializeNodeInfoSCC(OrderGraph* graph, HashTableNodeInfo* nodeToInfo){
 106         HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
 107         while(hasNextOrderNode(iterator)){
 108                 putNodeInfo(nodeToInfo, nextOrderNode(iterator), allocNodeInfo());
 109         }
 110         deleteIterOrderNode(iterator);
 111 }
 112
 113 void resetNodeInfoStatusSCC(OrderGraph* graph, HashTableNodeInfo* nodeToInfo){
 114         HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
 115         while(hasNextOrderNode(iterator)){
 116                 NodeInfo* info= getNodeInfo(nodeToInfo, nextOrderNode(iterator));
 117                 info->status = NOTVISITED;
 118         }
 119         deleteIterOrderNode(iterator);
 120 }
 121
 122 void computeStronglyConnectedComponentGraph(OrderGraph* graph){
 123         VectorOrderNode finishNodes;
 124         initDefVectorOrderNode(& finishNodes);
 125         HashTableNodeInfo* nodeToInfo = allocHashTableNodeInfo(HT_INITIAL_CAPACITY, HT_DEFAULT_FACTOR);
 126         initializeNodeInfoSCC(graph, nodeToInfo);
 127         DFS(graph, &finishNodes, nodeToInfo);
 128         resetNodeInfoStatusSCC(graph, nodeToInfo);
 129         DFSReverse(graph, &finishNodes, nodeToInfo);
 130         deleteHashTableNodeInfo(nodeToInfo);
 131 }
 132
 133 void removeMustBeTrueNodes(OrderGraph* graph){
 134         //TODO: Nodes that all the incoming/outgoing edges are MUST_BE_TRUE
 135 }
 136
 137 void orderAnalysis(CSolver* solver){
 138         OrderEncoder* oEncoder = buildOrderGraphs(solver);
 139         uint size = getSizeVectorOrderGraph(&oEncoder->graphs);
 140         for(uint i=0; i<size; i++){
 141                 OrderGraph* graph = getVectorOrderGraph(&oEncoder->graphs, i);
 142                 removeMustBeTrueNodes(graph);
 143                 computeStronglyConnectedComponentGraph(graph);
 144         }
 145 }
 146