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