1 #ifndef __WEIGHTED_DFA_H__ 2 #define __WEIGHTED_DFA_H__ 3 #include <chuffed/mdd/MurmurHash3.h> 4 #include <chuffed/support/vec.h> 5 #include <unordered_map> 6 #include <memory> 7 #include <vector> 8 9 #include <chuffed/mdd/opcache.h> 10 11 // Code for manipulating a weighted DFA. 12 // Converts a weighted DFA to a structurally hashed 13 // layered graph. 14 15 // Caveats: 16 // Does nothing to ensure that there are no long edges. 17 // Similarly, it does not ensure that the levels are 18 // increasing. 19 20 // TODO: Add a normalization step, so that: 21 // x1: [0, 3 -> y] 22 // x2: [0, 2 -> y] 23 // are mapped to the same node. 24 class EVLayerGraph; 25 26 class EVEdge; 27 28 class EVNode { 29 public: EVNode(EVLayerGraph * _g,int _idx)30 EVNode(EVLayerGraph* _g, int _idx) 31 : g(_g), idx(_idx) 32 { } 33 EVEdge operator[](int idx); 34 35 int var(void); 36 int id(void); 37 int size(void); 38 39 EVLayerGraph* g; 40 int idx; 41 }; 42 43 inline bool operator==(const EVNode& x, const EVNode& y) 44 { 45 return x.g == y.g && x.idx == y.idx; 46 } 47 inline bool operator!=(const EVNode& x, const EVNode& y) 48 { 49 return !(x == y); 50 } 51 52 EVNode& operator++(EVNode& x); 53 54 class EVEdge { 55 public: EVEdge(int _val,int _weight,const EVNode & _dest)56 EVEdge(int _val, int _weight, const EVNode& _dest) 57 : val(_val), weight(_weight), dest(_dest) 58 { } 59 60 61 int val; 62 int weight; 63 EVNode dest; 64 }; 65 66 67 class EVLayerGraph { 68 // Local structs 69 //============== 70 typedef struct { 71 int id; 72 int next; 73 int flag; 74 } TravInfo; 75 76 // Globally visible structs 77 //========================= 78 public: 79 typedef struct { 80 int val; 81 int weight; 82 int dest; 83 } EInfo; 84 85 typedef struct { 86 unsigned int var; 87 unsigned int sz; 88 89 EInfo edges[1]; 90 } NodeInfo; 91 92 typedef NodeInfo* NodeRef; 93 typedef int NodeID; 94 95 // Need to set up a nice interface for traversal. 96 class IterNode { 97 public: IterNode(EVLayerGraph * _graph,int _idx)98 IterNode(EVLayerGraph* _graph, int _idx) 99 : graph(_graph), idx(_idx) 100 { } 101 102 EVLayerGraph* graph; 103 int idx; 104 }; 105 106 // Local structs 107 //============== 108 protected: 109 struct eqnode 110 { operatoreqnode111 bool operator()(const NodeRef a1, const NodeRef a2) const 112 { 113 if( a1->var != a2->var ) 114 return false; 115 if( a1->sz != a2->sz ) 116 return false; 117 118 for( unsigned int ii = 0; ii < a1->sz; ii++ ) 119 { 120 if( a1->edges[ii].val != a2->edges[ii].val 121 || a1->edges[ii].dest != a2->edges[ii].dest 122 || a1->edges[ii].weight != a2->edges[ii].weight ) 123 return false; 124 } 125 return true; 126 } 127 }; 128 129 struct hashnode 130 { operatorhashnode131 unsigned int operator()(const NodeRef a1) const 132 { 133 unsigned int hash = 5381; 134 135 hash = ((hash << 5) + hash) + a1->var; 136 hash = ((hash << 5) + hash) + a1->sz; 137 #if 0 138 for(unsigned int ii = 0; ii < a1->sz; ii++) 139 { 140 hash = ((hash << 5) + hash) + a1->edges[ii].val; 141 hash = ((hash << 5) + hash) + a1->edges[ii].weight; 142 hash = ((hash << 5) + hash) + a1->edges[ii].dest; 143 } 144 return (hash & 0x7FFFFFFF); 145 #else 146 uint32_t ret; 147 MurmurHash3_x86_32(&(a1->edges), sizeof(EInfo)*a1->sz, hash, &ret); 148 return ret; 149 #endif 150 } 151 }; 152 153 typedef std::unordered_map<const NodeRef, NodeID, hashnode, eqnode> NodeCache; 154 155 // Public Methods 156 public: 157 EVLayerGraph(void); // Do we need the number of variables as a parameter? 158 ~EVLayerGraph(void); 159 160 NodeID insert(int level, vec<EInfo>& edges); 161 162 // Initialize the traversal info stuff. 163 // Returns the size of the computed subgraph. 164 int traverse(NodeID idx); travBegin(void)165 EVNode travBegin(void) { return EVNode(this, status[0].next); } travEnd(void)166 EVNode travEnd(void) { return EVNode(this, -1); } 167 168 const static int EVFalse; 169 const static int EVTrue; 170 protected: 171 inline NodeRef allocNode(int sz); 172 inline void deallocNode(NodeRef node); 173 174 int nvars; 175 176 OpCache opcache; 177 NodeCache cache; 178 179 int intermed_maxsz; 180 NodeRef intermed; 181 182 public: 183 std::vector<NodeRef> nodes; 184 185 // Traversal information. 186 std::vector<TravInfo> status; 187 }; 188 189 // Transition for a cost-regular constraint. 190 typedef struct { 191 int weight; 192 int dest; 193 } WDFATrans; 194 195 inline void create_edges(EVLayerGraph &graph, 196 vec<EVLayerGraph::EInfo> &edges, 197 const vec<EVLayerGraph::NodeID> &previous_layer, 198 const WDFATrans *T, int dom, 199 int nstates, int soff); 200 EVLayerGraph::NodeID wdfa_to_layergraph(EVLayerGraph &graph, int nvars, int dom, WDFATrans *T, int nstates, int q0, vec<int> &accepts); 201 202 #endif 203