source: src/dgp/dgp1.cc

Last change on this file was 854bece, checked in by Tomasz Obrebski <obrebski@…>, 10 years ago

has_head prop added, visible_as_neighbour moved to prop
  • Property mode set to 100644
File size: 14.6 KB
Line 
1#include <iostream>
2using namespace std;
3
4#include "dgp1.hh"
5#include "global.hh"
6
7extern Grammar grammar;
8extern MGraph mgraph;
9extern SGraph sgraph;
10
11extern bool debug;
12
13list<int> nodelist;
14list<int>::iterator processed;
15
16
17void print_sets(int n);
18
19
20//====================================================================================================
21
22void set_initial_constraints(int node)
23{
24  sgraph[node].prop.forbidden.reset();
25  sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node));
26  sgraph[node].prop.attached.reset();
27  sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node));
28}
29
30//----------------------------------------------------------------------------------------------------
31
32bool changing_constraints(int head, Role role)
33{
34  return grammar.is_sgl(role) || sgraph[head].prop.required[role];
35}
36
37//====================================================================================================
38
39NodeProp compute_head_prop(NodeProp headprop, const Link& link, list<Boubble*> bs, FlagSet& depflags)
40{
41  NodeProp ret=headprop;
42
43  if(grammar.is_sgl(link.role))
44    {
45      ret.forbidden.set(link.role);
46      ret.attached.set(link.role);
47    }
48  ret.required.reset(link.role);
49
50  ret.required |= (grammar.constr_include(link.role) & ~ret.attached);
51  ret.forbidden |= grammar.constr_exclude(link.role);
52
53  ret.boubbles.merge(bs); //DOBRZE
54  ret.flags |= ( depflags & grammar.pass_flags(link.role) );
55
56  if(link.props[Prop("INIT")]) ret.init_attached=true;
57  if(link.props[Prop("FIN")]) ret.fin_attached=true;
58
59  return ret;
60}
61
62//----------------------------------------------------------------------------------------------------
63
64NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs)
65{
66  NodeProp ret=depprop;
67  ret.boubbles.merge(bs); //DOBRZE
68  return ret;
69}
70
71//====================================================================================================
72
73int find_existing_node(int mnode, NodeProp p, Edge e)
74{
75  for(vector<int>::iterator i = mgraph[mnode].snodes.begin(); i!=mgraph[mnode].snodes.end(); ++i)
76    if(sgraph[*i].prop==p && sgraph[*i].edge==e)
77      { 
78        if(debug) fprintf(stderr,"\t\treusing %d\n",*i);
79        return *i;
80      }
81  return -1;
82}
83
84//====================================================================================================
85
86list<Boubble*> receive_boubbles(int node, Role role, Dir dir)
87{
88  list<Boubble*> ret;
89  for(list<Boubble*>::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++)
90    {
91      Boubble* new_boubble = (*b)->step(role,dir);
92      if(new_boubble)
93        ret.push_back(new_boubble);
94    }
95
96  return ret;
97}
98
99//----------------------------------------------------------------------------------------------------
100
101list<Boubble*> collect_head_boubbles(int head, int dep, Role role)
102{
103  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP);
104 
105  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
106    (*b)->src(dep);
107
108  list<Boubble*> received_boubbles = receive_boubbles(dep,role,UP);
109
110  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
111
112  return new_boubbles;
113}
114
115//----------------------------------------------------------------------------------------------------
116
117list<Boubble*> collect_dep_boubbles(int head, int dep, Role role)
118{
119  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN);
120 
121  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
122    (*b)->src(head);
123
124  list<Boubble*> received_boubbles = receive_boubbles(head,role,DOWN);
125
126  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());
127
128  return new_boubbles;
129}
130
131//====================================================================================================
132
133void copy_links(int i, int j)
134{
135  sgraph[j].heads = sgraph[i].heads;
136  sgraph[j].deps = sgraph[i].deps;
137}
138
139
140void create_reverse_links(int n)
141{
142  for(vector<Arc>::iterator a=sgraph[n].heads.begin(); a != sgraph[n].heads.end(); a++)
143    sgraph[a->dst].deps.push_back(Arc(n,a->role,a->headanc,a->depanc));
144
145  for(vector<Arc>::iterator a=sgraph[n].deps.begin(); a != sgraph[n].deps.end(); a++)
146    sgraph[a->dst].heads.push_back(Arc(n,a->role,a->headanc,a->depanc));
147}
148
149//====================================================================================================
150
151int create_new_node(int anc, NodeProp& prop, Edge edge)
152{
153  int newheadind = sgraph.clone(anc,prop,edge);
154  nodelist.push_back(newheadind);
155  copy_links(anc,newheadind);
156  create_reverse_links(newheadind);
157  if(debug) sgraph.print_node_debug(stderr,"clone",newheadind,anc);
158  // if(debug) print_sets(newheadind);
159  return newheadind;
160}
161
162//====================================================================================================
163
164void connect_left(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
165{
166
167  NodeProp &old_head_prop = sgraph[h].prop;
168  NodeProp &old_dep_prop = sgraph[d].prop;
169  NodeProp new_head_prop  = compute_head_prop(old_head_prop,l,new_head_boubbles,old_dep_prop.flags);
170  NodeProp new_dep_prop = compute_dep_prop(old_dep_prop,l,new_dep_boubbles);
171 
172  Edge new_dep_edge(sgraph[d].edge);
173  int newd = find_existing_node(sgraph[d].mnode, new_dep_prop, new_dep_edge);
174  if( newd < 0  )
175    {
176      newd = create_new_node(d,new_dep_prop,new_dep_edge);
177      sgraph[newd].prop.has_head = true;
178    }
179 
180  Edge new_head_edge(sgraph[newd].edge,newd);
181  int newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge);
182  if( newh < 0 )
183    newh = create_new_node(h,new_head_prop,new_head_edge);
184   
185  sgraph[newh].deps.push_back(Arc(newd,l.role,h,d));
186  sgraph[newd].heads.push_back(Arc(newh,l.role,h,d));
187
188  if(debug)
189    {
190      sgraph.print_arc(stderr,"link",newh,d,l.role,0);
191      sgraph.print_node_debug(stderr,"",newh,h);
192      sgraph.print_node_debug(stderr,"",newd,d);
193    }
194}
195
196//----------------------------------------------------------------------------------------------------
197
198void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
199{
200  NodeProp &old_head_prop = sgraph[h].prop;
201  NodeProp &old_dep_prop = sgraph[d].prop;
202  NodeProp new_head_prop = compute_head_prop(old_head_prop,l,new_head_boubbles,old_dep_prop.flags);
203  NodeProp new_dep_prop = compute_dep_prop(old_dep_prop,l,new_dep_boubbles);
204
205  Edge new_head_edge(sgraph[h].edge);
206  int newh = -1;
207  if(!new_head_prop.forbidden[l.role]) newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge);
208  if( newh < 0 )
209      {
210        newh = create_new_node(h,new_head_prop,new_head_edge);
211        sgraph[newh].prop.visible_as_neighbour = false;
212      }
213
214  Edge new_dep_edge;
215  int newd = d;
216  if( ! (new_dep_edge == sgraph[d].edge) || ! (old_dep_prop == new_dep_prop) )
217    {
218      newd = create_new_node(d,new_dep_prop,new_dep_edge);
219      sgraph[newd].prop.has_head = true;
220    }
221
222
223  sgraph[newd].heads.push_back(Arc(newh,l.role,h,d));
224  sgraph[newh].deps.push_back(Arc(newd,l.role,h,d));
225
226  if(debug)
227    {
228      sgraph.print_arc(stderr,"link",newh,newd,l.role,1);
229      sgraph.print_node_debug(stderr,"",newh,h);
230      sgraph.print_node_debug(stderr,"",newd,d);
231    }
232 
233}
234
235//====================================================================================================
236
237bool check_meeting_boubles(list<Boubble*>& boubbles)
238{
239  bool hremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
240  bool dremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
241
242  // cerr << "CHECKING MEETING BUBBLES" << endl;
243
244  for(list<Boubble*>::iterator hb = boubbles.begin(); hb != boubbles.end(); hb = hremove ? boubbles.erase(hb) : ++hb )
245    {
246      hremove=false;
247      for(list<Boubble*>::iterator db = hb; db != boubbles.end(); db = dremove ? boubbles.erase(db) : ++db )
248        {
249          // cerr << " db:" << **db;
250          dremove=false;
251          if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() )
252            {
253              // cerr << "Z";
254              int srcnode,dstnode;
255              if( (*hb)->reverse()==false )
256                srcnode = (*hb)->src(), dstnode = (*db)->src();
257              else
258                srcnode = (*db)->src(), dstnode = (*hb)->src();
259              if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) )
260                {
261                  // cerr << " REMOVE ";
262                  hremove=dremove=true;
263                  if(debug) fprintf(stderr,"BOUBBLES MET!!!\n");
264                }
265              else
266                {
267                  // cerr << " FAIL ";
268                  if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n");
269                  return false;
270                }
271            }
272        }
273    }
274  return true;
275}
276
277//====================================================================================================
278
279// sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node
280// daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles
281
282bool check_boubbles_at_target(list<Boubble*>& boubbles, int node)
283{
284  bool remove=false;             // czy usun±æ ostatnio sprawdzany b±bel
285
286  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b )
287    if( (*b)->is_at_target() )
288      if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
289        {
290          // cerr << endl << "REMOVE ChBatT " << **b << endl;
291          remove=true;
292        }
293      else
294        return false;
295    else
296      remove=false;
297     
298  return true;
299}
300
301//====================================================================================================
302
303void try_connect_dependents(int j)
304{
305  LViterator lvi(sgraph,j);
306  int i;
307  while((i=lvi.next()) >= 0)
308    if(sgraph.saturated(i) && ! sgraph.has_head(i))
309        {
310          if(debug) {fprintf(stderr,"\t%d <-- %d",i,j); }
311         
312          list<const Link*> ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!!
313          list<const Link*>::iterator ri = ji_links.begin();
314          if(ri == ji_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
315          else
316            {
317              for(; ri != ji_links.end(); ++ri )
318                {
319                  if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
320                  if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri ))
321                    { if(debug) fprintf(stderr," ...constraints failed\n"); }
322                  else
323                    {
324                      list<Boubble*> new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role);
325                      list<Boubble*> new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role);
326                      if( check_meeting_boubles(new_head_boubbles) &&
327                          check_meeting_boubles(new_dep_boubbles) &&
328                          check_boubbles_at_target(new_head_boubbles,j) &&
329                          check_boubbles_at_target(new_dep_boubbles,i) )
330                        {
331                          if(debug) fprintf(stderr," ...SUCCESS!\n");
332                          connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
333                          // lvi.update_edge(sgraph,i);
334                        }
335                      else
336                        { if(debug) fprintf(stderr," ...boubbles failed\n"); }
337                    }
338                }
339            }
340        }
341      else
342        if(debug) {fprintf(stderr,"\t%d <-- %d\t%d unsaturated\n",i,j,i); } 
343}
344//----------------------------------------------------------------------------------------------------
345
346void try_connect_heads(int j)
347{
348  LViterator lvi(sgraph,j);
349  int i;
350  while((i=lvi.next()) >= 0)
351    if(sgraph.saturated(j))
352      {
353        if(debug) fprintf(stderr, "\t%d --> %d",i,j);
354       
355        list<const Link*> ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags );
356        list<const Link*>::iterator ri = ij_links.begin();
357        if(ri == ij_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
358        else
359          {
360            for(; ri != ij_links.end(); ++ri )
361              {
362                if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
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_meeting_boubles(new_head_boubbles) &&
371                        check_meeting_boubles(new_dep_boubbles) &&
372                        check_boubbles_at_target(new_head_boubbles,i) &&
373                        check_boubbles_at_target(new_dep_boubbles,j) )
374                      {
375                        if(debug) fprintf(stderr," ...SUCCESS!\n");
376                        connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
377                      }
378                    else
379                      { if(debug) fprintf(stderr," ...bubbles failed\n",i); }
380                  }
381              }
382          }
383      }
384    else
385      if(debug) {fprintf(stderr,"\t* <-- %d    unsaturated\n",j); }
386}
387
388//====================================================================================================
389
390void update_sets()
391{
392  for(int n=0; n<sgraph.size(); ++n)
393    {
394      LViterator lvi(sgraph,n,false);
395      LHiterator lhi(sgraph,n);
396      LDiterator ldi(sgraph,n);
397      int i;
398
399      // printf("UPDATING LV[%d]:",n);
400      while((i=lvi.next())>=0)
401        {
402          // printf(" %d",i);
403          sgraph[n].LV.set(i);
404        }
405      // printf("\n");
406
407      while((i=lhi.next())>=0) sgraph[n].LH.set(i);
408      while((i=ldi.next())>=0) sgraph[n].LD.set(i);
409    }
410}
411
412//====================================================================================================
413
414void print_sets(int n)
415{
416  LViterator lvi(sgraph,n);
417  LHiterator lhi(sgraph,n);
418  LDiterator ldi(sgraph,n);
419 
420  int i; 
421  printf("LV[%d]: ",n);
422  while((i=lvi.next())>=0)
423        {
424          printf("%d ",i);
425          sgraph[n].LV.set(i);
426        }
427
428  printf("LH[%d]: ",n);
429  while((i=lhi.next())>=0)
430    {
431      printf("%d ",i);
432      sgraph[n].LH.set(i);
433    }
434  printf("LD[%d]: ",n);
435  while((i=ldi.next())>=0)
436    {
437      printf("%d ",i);
438      sgraph[n].LD.set(i);
439    }
440  printf("\n");
441}
442
443//====================================================================================================
444
445void reverse_links()
446{
447  list<int>::iterator i = nodelist.begin();
448  for(++i; i!=nodelist.end(); ++i)
449    {
450      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
451        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
452      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
453        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
454    }
455}
456
457//====================================================================================================
458
459void dgp1()
460{
461
462  nodelist.clear();
463  nodelist.push_back(0); // BOS
464  processed=nodelist.begin();
465
466  for(int m=0; m<mgraph.size() ; ++m)
467  {
468    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*
469
470    set_initial_constraints(basenode);
471    nodelist.push_back(basenode);
472
473    if(debug) sgraph.print_node_debug(stderr,"node",basenode,-1); // STDOUT!!!
474    // if(debug) print_sets(basenode);
475
476    list<int>::iterator cursor=processed;
477    while(++cursor != nodelist.end())
478    {
479      if(debug) sgraph.print_node_debug(stderr,"CUR>",*cursor,-1);
480      try_connect_dependents(*cursor);
481      try_connect_heads(*cursor);
482      processed=cursor;
483    }
484
485  }
486   // reverse_links();
487  update_sets();
488}
Note: See TracBrowser for help on using the repository browser.