1 #include "orderencoder.h"
5 #include "ordergraph.h"
10 NodeInfo* allocNodeInfo() {
11 NodeInfo* This = (NodeInfo*) ourmalloc(sizeof(NodeInfo));
13 This->status = NOTVISITED;
17 void deleteNodeInfo(NodeInfo* info){
21 OrderEncoder* allocOrderEncoder(){
22 OrderEncoder* This = (OrderEncoder*) ourmalloc(sizeof(OrderEncoder));
23 initDefVectorOrderGraph( &This->graphs );
27 void deleteOrderEncoder(OrderEncoder* This){
28 uint size = getSizeVectorOrderGraph(&This->graphs);
29 for(uint i=0; i<size; i++){
30 deleteOrderGraph(getVectorOrderGraph(&This->graphs, i));
35 OrderEncoder* buildOrderGraphs(CSolver* This) {
36 uint size = getSizeVectorOrder(This->allOrders);
37 OrderEncoder* oEncoder = allocOrderEncoder();
38 for(uint i=0; i<size; i++){
39 Order* order = getVectorOrder(This->allOrders, i);
40 OrderGraph *orderGraph=buildOrderGraph(order);
41 pushVectorOrderGraph(&oEncoder->graphs, orderGraph);
46 OrderGraph* buildOrderGraph(Order *order) {
47 OrderGraph* orderGraph = allocOrderGraph();
48 uint constrSize = getSizeVectorBoolean(&order->constraints);
49 for(uint j=0; j<constrSize; j++){
50 addOrderConstraintToOrderGraph(orderGraph, getVectorBoolean(&order->constraints, j));
55 void DFS(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNodeInfo* nodeToInfo){
57 HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
58 while(hasNextOrderNode(iterator)){
59 OrderNode* node = nextOrderNode(iterator);
60 NodeInfo* info= getNodeInfo(nodeToInfo, node);
61 if(info->status == NOTVISITED){
62 info->status = VISITED;
63 DFSNodeVisit(node, finishNodes, nodeToInfo, &timer, false);
64 info->status = FINISHED;
65 info->finishTime = timer;
66 pushVectorOrderNode(finishNodes, node);
69 deleteIterOrderNode(iterator);
72 void DFSReverse(OrderGraph* graph, VectorOrderNode* finishNodes, HashTableNodeInfo* nodeToInfo){
74 uint size = getSizeVectorOrderNode(finishNodes);
75 for(int i=size-1; i>=0; i--){
76 OrderNode* node = getVectorOrderNode(finishNodes, i);
77 NodeInfo* info= getNodeInfo(nodeToInfo, node);
78 if(info->status == NOTVISITED){
79 info->status = VISITED;
80 DFSNodeVisit(node, NULL, nodeToInfo, &timer, true);
81 info->status = FINISHED;
82 info->finishTime = timer;
83 pushVectorOrderNode(&graph->scc, node);
88 void DFSNodeVisit(OrderNode* node, VectorOrderNode* finishNodes,
89 HashTableNodeInfo* nodeToInfo, uint* timer, bool isReverse){
91 model_print("Timer in DFSNodeVisit:%u\n", *timer);
92 HSIteratorOrderEdge* iterator = isReverse?iteratorOrderEdge(node->inEdges):iteratorOrderEdge(node->outEdges);
93 while(hasNextOrderEdge(iterator)){
94 OrderEdge* edge = nextOrderEdge(iterator);
95 OrderNode* child = isReverse? edge->source: edge->sink;
96 NodeInfo* childInfo = getNodeInfo(nodeToInfo, child);
97 if(childInfo->status == NOTVISITED){
98 childInfo->status = VISITED;
99 DFSNodeVisit(child, finishNodes, nodeToInfo, timer, isReverse);
100 childInfo->status = FINISHED;
101 childInfo->finishTime = *timer;
103 pushVectorOrderNode(finishNodes, child);
106 deleteIterOrderEdge(iterator);
109 void initializeNodeInfoSCC(OrderGraph* graph, HashTableNodeInfo* nodeToInfo){
110 HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
111 while(hasNextOrderNode(iterator)){
112 putNodeInfo(nodeToInfo, nextOrderNode(iterator), allocNodeInfo());
114 deleteIterOrderNode(iterator);
117 void resetNodeInfoStatusSCC(OrderGraph* graph, HashTableNodeInfo* nodeToInfo){
118 HSIteratorOrderNode* iterator = iteratorOrderNode(graph->nodes);
119 while(hasNextOrderNode(iterator)){
120 NodeInfo* info= getNodeInfo(nodeToInfo, nextOrderNode(iterator));
121 info->status = NOTVISITED;
123 deleteIterOrderNode(iterator);
126 void computeStronglyConnectedComponentGraph(OrderGraph* graph){
127 VectorOrderNode finishNodes;
128 initDefVectorOrderNode(& finishNodes);
129 HashTableNodeInfo* nodeToInfo = allocHashTableNodeInfo(HT_INITIAL_CAPACITY, HT_DEFAULT_FACTOR);
130 initializeNodeInfoSCC(graph, nodeToInfo);
131 DFS(graph, &finishNodes, nodeToInfo);
132 resetNodeInfoStatusSCC(graph, nodeToInfo);
133 DFSReverse(graph, &finishNodes, nodeToInfo);
134 deleteHashTableNodeInfo(nodeToInfo);
137 void removeMustBeTrueNodes(OrderGraph* graph){
138 //TODO: Nodes that all the incoming/outgoing edges are MUST_BE_TRUE
141 void orderAnalysis(CSolver* solver){
142 OrderEncoder* oEncoder = buildOrderGraphs(solver);
143 uint size = getSizeVectorOrderGraph(&oEncoder->graphs);
144 for(uint i=0; i<size; i++){
145 OrderGraph* graph = getVectorOrderGraph(&oEncoder->graphs, i);
146 removeMustBeTrueNodes(graph);
147 computeStronglyConnectedComponentGraph(graph);