source: src/dgp/dgp1.cc @ abd28d1

Last change on this file since abd28d1 was e7de6cc, checked in by Tomasz Obrebski <to@…>, 12 years ago

new version of dgp
added dgc, tre and compdic components
compiledic renamed to compdic_utf8
./configure updated
  • Property mode set to 100644
File size: 13.6 KB
Line 
1#include "dgp0.hh"
2#include "global.hh"
3
4extern Grammar grammar;
5extern MGraph mgraph;
6extern SGraph sgraph;
7
8extern bool debug;
9
10list<int> nodelist;
11list<int>::iterator processed;
12
13//====================================================================================================
14
15void set_initial_constraints(int node)
16{
17  sgraph[node].prop.forbidden.reset();
18  sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node));
19  sgraph[node].prop.attached.reset();
20  sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node));
21}
22
23//----------------------------------------------------------------------------------------------------
24
25bool changing_constraints(int head, Role role)
26{
27  return grammar.is_sgl(role) || sgraph[head].prop.required[role];
28}
29
30//====================================================================================================
31
32NodeProp compute_head_prop(NodeProp headprop, const Link& link, list<Boubble*> bs, FlagSet& depflags)
33{
34  NodeProp ret=headprop;
35
36  if(grammar.is_sgl(link.role))
37    {
38      ret.forbidden.set(link.role);
39      ret.attached.set(link.role);
40    }
41  ret.required.reset(link.role);
42
43  ret.required |= (grammar.constr_include(link.role) & ~ret.attached);
44  ret.forbidden |= grammar.constr_exclude(link.role);
45
46  ret.boubbles=bs;
47  ret.flags |= ( depflags & grammar.pass_flags(link.role) );
48
49  if(link.props[Prop("INIT")]) ret.init_attached=true;
50  if(link.props[Prop("FIN")]) ret.fin_attached=true;
51
52  return ret;
53}
54
55//----------------------------------------------------------------------------------------------------
56
57NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs)
58{
59  NodeProp ret=depprop;
60  ret.boubbles=bs;
61  return ret;
62}
63
64//====================================================================================================
65
66int find_existing_node(int mnodeind, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV)
67{
68  MNode& mnode = mgraph[mnodeind];
69  for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps)
70    if(sgraph[*ps].prop==p && sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV)      return *ps;
71  return -1;
72}
73
74//====================================================================================================
75
76list<Boubble*> receive_boubbles(int node, Role role, Dir dir)
77{
78  list<Boubble*> ret;
79  for(list<Boubble*>::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++)
80    {
81      Boubble* new_boubble = (*b)->step(role,dir);
82      if(new_boubble)
83        ret.push_back(new_boubble);
84    }
85  return ret;
86}
87
88//----------------------------------------------------------------------------------------------------
89
90list<Boubble*> collect_head_boubbles(int head, int dep, Role role)
91{
92  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP);
93 
94  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
95    (*b)->src(dep);
96
97  list<Boubble*> received_boubbles = receive_boubbles(dep,role,UP);
98
99  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
100
101  return new_boubbles;
102}
103
104//----------------------------------------------------------------------------------------------------
105
106list<Boubble*> collect_dep_boubbles(int head, int dep, Role role)
107{
108  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN);
109 
110  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
111    (*b)->src(head);
112
113  list<Boubble*> received_boubbles = receive_boubbles(head,role,DOWN);
114
115  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
116
117  return new_boubbles;
118}
119
120//====================================================================================================
121
122int create_new_head_node_left(list<int>::iterator h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
123{
124  int newheadind = sgraph.clone(*h,newheadprop);
125  list<int>::iterator nextit=h; ++nextit;
126  nodelist.insert(nextit,newheadind);
127  sgraph[newheadind].LH=newheadLH;
128  sgraph[newheadind].LD = newheadLD;
129  sgraph[newheadind].in_LH=true;
130  sgraph[newheadind].LV.reset();
131 
132  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h);
133 
134  return newheadind;
135}
136
137int create_new_dep_node_left(list<int>::iterator d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
138{
139  int newind = sgraph.clone(*d,prop);
140  list<int>::iterator nextit=d; ++nextit;
141  nodelist.insert(nextit,newind);
142  sgraph[newind].LH.reset();
143  sgraph[newind].LD=LD;
144  sgraph[newind].in_LH=false; //???????
145  sgraph[newind].LV.reset();
146 
147  if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d);
148 
149  return newind;
150}
151
152int create_new_head_node_right(list<int>::iterator h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
153{
154  int newheadind = sgraph.clone(*h,newheadprop);
155  list<int>::iterator nextit=h; ++nextit;
156  nodelist.insert(nextit,newheadind);
157  sgraph[newheadind].LH=newheadLH;
158  sgraph[newheadind].LD=newheadLD;
159  sgraph[newheadind].in_LH=false;
160  sgraph[newheadind].LV=newheadLV;
161 
162  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h);
163 
164  return newheadind;
165}
166
167int create_new_dep_node_right(list<int>::iterator d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
168{
169  int newind = sgraph.clone(*d,prop);
170  list<int>::iterator nextit=d; ++nextit;
171  nodelist.insert(nextit,newind);
172  sgraph[newind].LH=LH;
173  sgraph[newind].LD=LD;
174  sgraph[newind].in_LH=true; //???????
175  sgraph[newind].LV.reset();
176 
177  if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d);
178 
179  return newind;
180}
181
182//====================================================================================================
183
184void connect_left(list<int>::iterator h, list<int>::iterator d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
185{
186
187  NodeProp &oldheadprop = sgraph[*h].prop;
188  NodeProp &olddepprop = sgraph[*d].prop;
189
190  NodeProp newheadprop  = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags);
191 
192  int newheadind;
193  if(oldheadprop==newheadprop)
194    newheadind = *h;
195  else
196  {
197    bitset<MAXNODES> newheadLH = sgraph[*h].LH;
198    bitset<MAXNODES> newheadLV = sgraph[*d].LV;
199    bitset<MAXNODES> newheadLD = sgraph[*h].LD;
200
201    newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV);
202    if( newheadind >= 0 )
203      sgraph[newheadind].LD |= newheadLD;
204    else
205      newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV);
206  }
207
208
209
210  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);
211
212  int newdepind;
213 
214  if(olddepprop==newdepprop)
215    newdepind = *d;
216  else
217  {
218    bitset<MAXNODES> newdepLH = sgraph[*d].LH;
219    bitset<MAXNODES> newdepLV = sgraph[*d].LV;
220    bitset<MAXNODES> newdepLD = sgraph[*d].LD;
221
222    newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV);
223    if( newdepind >= 0 )
224      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
225    else
226      newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV);
227  }
228
229  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,*h,*d));
230 
231  if(sgraph[*d].saturated()) sgraph[newheadind].LV |= sgraph[*d].LV;
232
233  sgraph[newheadind].LD.set(*d);
234  if(sgraph[*d].saturated()) sgraph[newheadind].LD |= sgraph[*d].LD;
235 
236  if(debug) sgraph.print_arc(stderr,newheadind,*d,l.role,0);
237  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h);
238  if(debug) sgraph.print_node_debug(stderr,"U ",*d,*d);
239}
240
241//----------------------------------------------------------------------------------------------------
242
243void connect_right(list<int>::iterator h, list<int>::iterator d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
244{
245  NodeProp &oldheadprop = sgraph[*h].prop;
246
247  NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[*d].prop.flags);
248
249  int newheadind;
250 
251  if(oldheadprop==newheadprop)
252    newheadind = *h;
253  else
254  {
255    bitset<MAXNODES> newheadLH = sgraph[*h].LH;
256    bitset<MAXNODES> newheadLV = sgraph[*h].LV;
257    bitset<MAXNODES> newheadLD = sgraph[*h].LD;
258
259    newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV);
260    if( newheadind >= 0 )
261      sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD
262    else
263      newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV);
264  }
265
266  NodeProp &olddepprop = sgraph[*d].prop;
267  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);
268
269  int newdepind;
270 
271  if(olddepprop==newdepprop)
272    newdepind = *d;
273  else
274  {
275    bitset<MAXNODES> newdepLH = sgraph[*d].LH;
276    bitset<MAXNODES> newdepLV = sgraph[*d].LV;
277    bitset<MAXNODES> newdepLD = sgraph[*d].LD;
278
279    newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV);
280    if( newdepind >= 0 )
281      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
282    else
283      newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV);
284  }
285
286
287
288 
289  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,*h,*d));
290
291  sgraph[newdepind].LH.set(newheadind);
292
293  //  sgraph[*d].prop.merge_boubbles(new_dep_boubbles);
294 
295  if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH;
296
297  if(debug) sgraph.print_arc(stderr,newheadind,newdepind,l.role,1);
298  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h);
299  if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,*d);
300 
301}
302
303//====================================================================================================
304
305bool check_boubbles_at_target(list<Boubble*> boubbles, int node)
306{
307  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b++)
308    if( (*b)->is_at_target() && !grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()))
309      return false;
310  return true;
311}
312
313//====================================================================================================
314
315void try_connect_dependents(list<int>::iterator j)
316{
317  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
318    if(sgraph.visible(*i,*j) && sgraph.saturated(*i))
319    {
320      if(debug) {fprintf(stderr,"## %d <-- %d ... ",*i,*j); }
321
322      list<const Link*> ji_links = grammar.connectable2( sgraph.cat(*j), sgraph.cat(*i), sgraph[*j].prop.flags, sgraph[*i].prop.flags); // ref do Roles!!!
323      list<const Link*>::iterator ri = ji_links.begin();
324      if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
325      else
326        {
327          for(; ri != ji_links.end(); ++ri )
328            if(!grammar.check_constr2(sgraph[*j].prop,sgraph[*i].prop,0,**ri ))
329              { if(debug) fprintf(stderr,"constraints failed\n"); }
330            else
331              {
332                list<Boubble*> new_head_boubbles = collect_head_boubbles(*j,*i,(*ri)->role);
333                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(*j,*i,(*ri)->role);
334               
335                if( !(check_boubbles_at_target(new_head_boubbles,*j) && check_boubbles_at_target(new_dep_boubbles,*i)) )
336                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
337                else
338                  {
339                    if(debug) fprintf(stderr,"success\n");
340                    connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
341                  }
342              }
343        }
344    }
345}
346
347
348//----------------------------------------------------------------------------------------------------
349
350void try_connect_heads(list<int>::iterator j)
351{
352  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
353    if(sgraph.visible(*i,*j))
354    {
355      if(debug) fprintf(stderr, "## %d --> %d ... ",*i,*j);
356
357      list<const Link*> ij_links = grammar.connectable2( sgraph.cat(*i), sgraph.cat(*j), sgraph[*i].prop.flags, sgraph[*j].prop.flags );
358      list<const Link*>::iterator ri = ij_links.begin();
359      if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
360      else
361        {
362          for(; ri != ij_links.end(); ++ri )
363            if( !grammar.check_constr2( sgraph[*i].prop, sgraph[*j].prop, 1, **ri ) )
364              { if(debug) fprintf(stderr,"constraints failed\n"); }
365            else
366              {
367                list<Boubble*> new_head_boubbles = collect_head_boubbles(*i,*j,(*ri)->role);
368                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(*i,*j,(*ri)->role);
369               
370                if( !(check_boubbles_at_target(new_head_boubbles,*i) && check_boubbles_at_target(new_dep_boubbles,*j)) )
371                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
372                else
373                  {
374                    if(debug) fprintf(stderr,"success\n");
375                    connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
376                  }
377              }
378        }
379    }
380}
381 
382//====================================================================================================
383
384void reverse_links()
385{
386  list<int>::iterator i = nodelist.begin();
387  for(++i; i!=nodelist.end(); ++i)
388    {
389      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
390        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
391      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
392        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
393    }
394}
395
396//====================================================================================================
397
398void dgp1()
399{
400
401  nodelist.clear();
402  nodelist.push_back(0); // BOS
403  processed=nodelist.begin();
404
405  for(int m=0; m<mgraph.size() ; ++m)
406  {
407    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*
408
409    set_initial_constraints(basenode);
410    nodelist.push_back(basenode);
411
412    if(debug) {sgraph.print_node_debug(stderr,"B ",basenode,-1);} // STDOUT!!!
413
414    list<int>::iterator cursor=processed;
415    while(++cursor != nodelist.end())
416    {
417      try_connect_dependents(cursor);
418      try_connect_heads(cursor);
419      processed=cursor;
420    }
421
422  }
423  reverse_links();
424}
Note: See TracBrowser for help on using the repository browser.