source: src/dgp/dgp1.cc @ 3b02b04

Last change on this file since 3b02b04 was 3b02b04, checked in by Tomasz Obrebski <to@…>, 11 years ago

prawie ca�kiem nowe dgc, du�e zmiany w dgp, pomniejsze poprawki
  • Property mode set to 100644
File size: 17.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
14void print_sets(int n);
15
16
17//====================================================================================================
18
19void set_initial_constraints(int node)
20{
21  sgraph[node].prop.forbidden.reset();
22  sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node));
23  sgraph[node].prop.attached.reset();
24  sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node));
25}
26
27//----------------------------------------------------------------------------------------------------
28
29bool changing_constraints(int head, Role role)
30{
31  return grammar.is_sgl(role) || sgraph[head].prop.required[role];
32}
33
34//====================================================================================================
35
36NodeProp compute_head_prop(NodeProp headprop, const Link& link, list<Boubble*> bs, FlagSet& depflags)
37{
38  NodeProp ret=headprop;
39
40  if(grammar.is_sgl(link.role))
41    {
42      ret.forbidden.set(link.role);
43      ret.attached.set(link.role);
44    }
45  ret.required.reset(link.role);
46
47  ret.required |= (grammar.constr_include(link.role) & ~ret.attached);
48  ret.forbidden |= grammar.constr_exclude(link.role);
49
50  ret.boubbles.merge(bs); //DOBRZE
51  ret.flags |= ( depflags & grammar.pass_flags(link.role) );
52
53  if(link.props[Prop("INIT")]) ret.init_attached=true;
54  if(link.props[Prop("FIN")]) ret.fin_attached=true;
55
56  return ret;
57}
58
59//----------------------------------------------------------------------------------------------------
60
61NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs)
62{
63  NodeProp ret=depprop;
64  ret.boubbles.merge(bs); //DOBRZE
65  return ret;
66}
67
68//====================================================================================================
69
70int find_existing_node(int mnodeind, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV)
71{
72  MNode& mnode = mgraph[mnodeind];
73  int ret=-1;
74  for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps)
75    {
76      if(debug) fprintf(stderr,"#find existing node: checking %d ... \n", *ps);
77      if(sgraph[*ps].prop==p)
78        if(sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV)
79          {
80            ret = *ps;
81            // fprintf(stderr,"FIND EXISTING NODE SUCCEEDED BEACAUSE OF LH/LV equality ()\n");
82          }
83        else
84          {
85            // fprintf(stderr,"FIND EXISTING NODE FAILED BEACAUSE OF LH/LV inequality\n");
86          }
87    }
88
89  if(debug) fprintf(stderr,"\n");
90  return ret;
91}
92
93//====================================================================================================
94
95list<Boubble*> receive_boubbles(int node, Role role, Dir dir)
96{
97  list<Boubble*> ret;
98  for(list<Boubble*>::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++)
99    {
100      Boubble* new_boubble = (*b)->step(role,dir);
101      if(new_boubble)
102        ret.push_back(new_boubble);
103    }
104
105  return ret;
106}
107
108//----------------------------------------------------------------------------------------------------
109
110list<Boubble*> collect_head_boubbles(int head, int dep, Role role)
111{
112  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP);
113 
114  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
115    (*b)->src(dep);
116
117  list<Boubble*> received_boubbles = receive_boubbles(dep,role,UP);
118
119  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
120
121  return new_boubbles;
122}
123
124//----------------------------------------------------------------------------------------------------
125
126list<Boubble*> collect_dep_boubbles(int head, int dep, Role role)
127{
128  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN);
129 
130  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
131    (*b)->src(head);
132
133  list<Boubble*> received_boubbles = receive_boubbles(head,role,DOWN);
134
135  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
136
137  return new_boubbles;
138}
139
140//====================================================================================================
141
142void copy_links(int i, int j)
143{
144  sgraph[j].heads = sgraph[i].heads;
145  sgraph[j].deps = sgraph[i].deps;
146}
147
148
149void create_reverse_links(int n)
150{
151  for(vector<Arc>::iterator a=sgraph[n].heads.begin(); a != sgraph[n].heads.end(); a++)
152    sgraph[a->dst].deps.push_back(Arc(n,a->role,a->headanc,a->depanc));
153
154  for(vector<Arc>::iterator a=sgraph[n].deps.begin(); a != sgraph[n].deps.end(); a++)
155    sgraph[a->dst].heads.push_back(Arc(n,a->role,a->headanc,a->depanc));
156}
157
158//====================================================================================================
159
160int create_new_head_node_left(int h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
161{
162  int newheadind = sgraph.clone(h,newheadprop);
163  // list<int>::iterator nextit=h; ++nextit;
164  // nodelist.insert(nextit,newheadind);
165  nodelist.push_back(newheadind);
166  sgraph[newheadind].LH=newheadLH;
167  sgraph[newheadind].LD = newheadLD;
168  sgraph[newheadind].in_LH=true;
169  sgraph[newheadind].LV.reset();
170
171  copy_links(h,newheadind);
172  create_reverse_links(newheadind);
173 
174  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h);
175  if(debug) print_sets(newheadind);
176  return newheadind;
177}
178
179int create_new_dep_node_left(int d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
180{
181  int newind = sgraph.clone(d,prop);
182  // list<int>::iterator nextit=d; ++nextit;
183  // nodelist.insert(nextit,newind);
184  nodelist.push_back(newind);
185  sgraph[newind].LH.reset();
186  sgraph[newind].LD=LD;
187  sgraph[newind].in_LH=false; //???????
188  sgraph[newind].LV.reset();
189
190  copy_links(d,newind);
191  create_reverse_links(newind);
192 
193  if(debug) sgraph.print_node_debug(stderr,"C ",newind,d);
194  if(debug) print_sets(newind);
195 
196  return newind;
197}
198
199int create_new_head_node_right(int h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
200{
201  int newheadind = sgraph.clone(h,newheadprop);
202  // list<int>::iterator nextit=h; ++nextit;
203  // nodelist.insert(nextit,newheadind);
204  nodelist.push_back(newheadind);
205  sgraph[newheadind].LH=newheadLH;
206  sgraph[newheadind].LD=newheadLD;
207  sgraph[newheadind].in_LH=false;
208  sgraph[newheadind].LV=newheadLV;
209 
210  copy_links(h,newheadind);
211  create_reverse_links(newheadind);
212
213  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h);
214  if(debug) print_sets(newheadind);
215 
216  return newheadind;
217}
218
219int create_new_dep_node_right(int d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
220{
221  int newind = sgraph.clone(d,prop);
222  nodelist.push_back(newind);
223  sgraph[newind].LH=LH;
224  sgraph[newind].LD=LD;
225  sgraph[newind].in_LH=true; //???????
226  sgraph[newind].LV.reset();
227 
228  copy_links(d,newind);
229  create_reverse_links(newind);
230
231  if(debug) sgraph.print_node_debug(stderr,"C ",newind,d);
232  if(debug) print_sets(newind);
233 
234  return newind;
235}
236
237//====================================================================================================
238
239void connect_left(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
240{
241
242  NodeProp &oldheadprop = sgraph[h].prop;
243  NodeProp &olddepprop = sgraph[d].prop;
244
245  NodeProp newheadprop  = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags);
246 
247  int newheadind;
248  if(oldheadprop==newheadprop)
249    newheadind = h;
250  else
251  {
252    bitset<MAXNODES> newheadLH = sgraph[h].LH;
253    bitset<MAXNODES> newheadLV = sgraph[d].LV;
254    bitset<MAXNODES> newheadLD = sgraph[h].LD;
255
256    //    vector<int> newedge;
257
258    newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV);
259    if( newheadind >= 0) // W£¡CZONE
260      sgraph[newheadind].LD |= newheadLD;
261    else
262      {
263        newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV);
264        sgraph[newheadind].edge.clear();
265        sgraph[newheadind].edge_contains_self = false;
266      }
267   
268  }
269
270  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);
271
272  int newdepind;
273 
274  if(olddepprop==newdepprop)
275    newdepind = d;
276  else
277  {
278    bitset<MAXNODES> newdepLH = sgraph[d].LH;
279    bitset<MAXNODES> newdepLV = sgraph[d].LV;
280    bitset<MAXNODES> newdepLD = sgraph[d].LD;
281
282    newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV);
283    if( newdepind >= 0) // W£¡CZONE
284      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
285    else
286      {
287        newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV);
288        sgraph[newdepind].edge.clear();
289        //sgraph[newdepind].edge.push_back(newdepind); // TO
290        sgraph[newdepind].edge_contains_self = true; // LUB TO
291      }
292  }
293 
294
295  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d));
296  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d));
297  sgraph[newheadind].edge.push_back(newdepind);
298 
299  if(sgraph[d].saturated()) sgraph[newheadind].LV |= sgraph[d].LV;
300
301  sgraph[newheadind].LD.set(d);
302  if(sgraph[d].saturated()) sgraph[newheadind].LD |= sgraph[d].LD;
303 
304  if(debug) sgraph.print_arc(stderr,newheadind,d,l.role,0);
305  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h);
306  if(debug) print_sets(newheadind);
307  if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d);
308  if(debug) print_sets(newdepind);
309}
310
311//----------------------------------------------------------------------------------------------------
312
313void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
314{
315  NodeProp &oldheadprop = sgraph[h].prop;
316
317  NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[d].prop.flags);
318
319  int newheadind;
320 
321  if(oldheadprop==newheadprop)
322    newheadind = h;
323  else
324  {
325    bitset<MAXNODES> newheadLH = sgraph[h].LH;
326    bitset<MAXNODES> newheadLV = sgraph[h].LV;
327    bitset<MAXNODES> newheadLD = sgraph[h].LD;
328
329    newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV);
330
331    if(debug) fprintf(stderr,"#HEAD EXISTS %d\n",newheadind);
332
333    if( newheadind >= 0) // W£¡CZONE
334      sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD
335    else
336      {
337        newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV);
338        //if(!sgraph[h].edge.empty()) sgraph[newheadind].edge.push_back(newheadind); // TO
339        sgraph[newheadind].edge_contains_self = sgraph[h].edge_contains_self;      // LUB TO
340        sgraph[newheadind].visible_as_neighbour = false;
341      }
342  }
343
344  NodeProp &olddepprop = sgraph[d].prop;
345  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);
346
347  int newdepind;
348 
349  if(olddepprop==newdepprop)
350    newdepind = d;
351  else
352  {
353    bitset<MAXNODES> newdepLH = sgraph[d].LH;
354    bitset<MAXNODES> newdepLV = sgraph[d].LV;
355    bitset<MAXNODES> newdepLD = sgraph[d].LD;
356
357    newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV);
358
359    if(debug) fprintf(stderr,"#DEP EXISTS %d\n",newdepind);
360
361    if( newdepind >= 0) // W£¡CZONE
362      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
363    else
364      {
365        newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV);
366        sgraph[newdepind].edge.clear();
367        sgraph[newdepind].edge_contains_self = false;
368      }
369  }
370
371
372  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d));
373  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d));
374  //sgraph[newdepind].edge.push_back(newheadind);
375
376  sgraph[newdepind].LH.set(newheadind);
377
378  //  sgraph[*d].prop.merge_boubbles(new_dep_boubbles);
379 
380  if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH;
381
382  if(debug) sgraph.print_arc(stderr,newheadind,newdepind,l.role,1);
383  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h);
384  if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d);
385 
386}
387
388//====================================================================================================
389
390// sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node
391// daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles
392
393bool check_boubbles_at_target(list<Boubble*>& boubbles, int node)
394{
395  list<Boubble*>::iterator last; // ostatnio sprawdzany b±bel
396  bool remove=false;             // czy usun±æ ostatnio sprawdzany b±bel
397
398  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b )
399    if( (*b)->is_at_target() )
400      if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
401        remove=true;
402      else
403        return false;
404    else
405      remove=false;
406     
407  return true;
408}
409
410//====================================================================================================
411
412void try_connect_dependents(int j)
413{
414  // for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
415  //   if(sgraph.visible(*i,*j) && sgraph.saturated(*i))
416  LViterator lvi(sgraph,j);
417  int i;
418  while((i=lvi.next()) >= 0)
419    if(sgraph.saturated(i))
420      {
421      if(debug) {fprintf(stderr,"## %d <-- %d ... ",i,j); }
422
423      list<const Link*> ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!!
424      list<const Link*>::iterator ri = ji_links.begin();
425      if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
426      else
427        {
428          for(; ri != ji_links.end(); ++ri )
429            if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri ))
430              { if(debug) fprintf(stderr,"constraints failed\n"); }
431            else
432              {
433                list<Boubble*> new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role);
434                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role);
435               
436                if( !(check_boubbles_at_target(new_head_boubbles,j) && check_boubbles_at_target(new_dep_boubbles,i)) )
437                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
438                else
439                  {
440                    if(debug) fprintf(stderr,"success\n");
441                    connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
442                  }
443              }
444        }
445    }
446}
447
448
449//----------------------------------------------------------------------------------------------------
450
451void try_connect_heads(int j)
452{
453  // for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
454  //   if(sgraph.visible(*i,*j) && sgraph.saturated(*j))
455
456  LViterator lvi(sgraph,j);
457  int i;
458  while((i=lvi.next()) >= 0)
459    if(sgraph.saturated(j))
460    {
461      if(debug) fprintf(stderr, "## %d --> %d ... ",i,j);
462
463      list<const Link*> ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags );
464      list<const Link*>::iterator ri = ij_links.begin();
465      if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
466      else
467        {
468          for(; ri != ij_links.end(); ++ri )
469            if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) )
470              { if(debug) fprintf(stderr,"constraints failed\n"); }
471            else
472              {
473                list<Boubble*> new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role);
474                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role);
475               
476                if( !(check_boubbles_at_target(new_head_boubbles,i) && check_boubbles_at_target(new_dep_boubbles,j)) )
477                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
478                else
479                  {
480                    if(debug) fprintf(stderr,"success\n");
481                    connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
482                  }
483              }
484        }
485    }
486}
487
488//====================================================================================================
489
490void update_sets()
491{
492  for(int n=0; n<sgraph.size(); ++n)
493    {
494      LViterator lvi(sgraph,n,false);
495      LHiterator lhi(sgraph,n);
496      LDiterator ldi(sgraph,n);
497      int i;
498
499      // printf("UPDATING LV[%d]:",n);
500      while((i=lvi.next())>=0)
501        {
502          // printf(" %d",i);
503          sgraph[n].LV.set(i);
504        }
505      // printf("\n");
506
507      while((i=lhi.next())>=0) sgraph[n].LH.set(i);
508      while((i=ldi.next())>=0) sgraph[n].LD.set(i);
509    }
510}
511
512//====================================================================================================
513
514void print_sets(int n)
515{
516  LViterator lvi(sgraph,n);
517  LHiterator lhi(sgraph,n);
518  LDiterator ldi(sgraph,n);
519 
520  int i; 
521  printf("LV[%d]: ",n);
522  while((i=lvi.next())>=0)
523        {
524          printf("%d ",i);
525          sgraph[n].LV.set(i);
526        }
527
528  printf("LH[%d]: ",n);
529  while((i=lhi.next())>=0)
530    {
531      printf("%d ",i);
532      sgraph[n].LH.set(i);
533    }
534  printf("LD[%d]: ",n);
535  while((i=ldi.next())>=0)
536    {
537      printf("%d ",i);
538      sgraph[n].LD.set(i);
539    }
540  printf("\n");
541}
542
543//====================================================================================================
544
545void reverse_links()
546{
547  list<int>::iterator i = nodelist.begin();
548  for(++i; i!=nodelist.end(); ++i)
549    {
550      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
551        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
552      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
553        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
554    }
555}
556
557//====================================================================================================
558
559void dgp1()
560{
561
562  nodelist.clear();
563  nodelist.push_back(0); // BOS
564  processed=nodelist.begin();
565
566  for(int m=0; m<mgraph.size() ; ++m)
567  {
568    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*
569
570    set_initial_constraints(basenode);
571    nodelist.push_back(basenode);
572
573    if(debug) sgraph.print_node_debug(stderr,"B ",basenode,-1); // STDOUT!!!
574    if(debug) print_sets(basenode);
575
576    list<int>::iterator cursor=processed;
577    while(++cursor != nodelist.end())
578    {
579      if(debug) sgraph.print_node_debug(stderr,"> ",*cursor,-1);
580      try_connect_dependents(*cursor);
581      try_connect_heads(*cursor);
582      processed=cursor;
583    }
584
585  }
586   // reverse_links();
587  update_sets();
588}
Note: See TracBrowser for help on using the repository browser.