source: src/dgp/dgp1.cc @ acbabee

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

many changes, mainly dgp1 algorithm
  • Property mode set to 100644
File size: 14.5 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    newd = create_new_node(d,new_dep_prop,new_dep_edge);
176 
177  Edge new_head_edge(sgraph[newd].edge,newd);
178  int newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge);
179  if( newh < 0 )
180    newh = create_new_node(h,new_head_prop,new_head_edge);
181   
182  sgraph[newh].deps.push_back(Arc(newd,l.role,h,d));
183  sgraph[newd].heads.push_back(Arc(newh,l.role,h,d));
184
185  if(debug)
186    {
187      sgraph.print_arc(stderr,"link",newh,d,l.role,0);
188      sgraph.print_node_debug(stderr,"",newh,h);
189      sgraph.print_node_debug(stderr,"",newd,d);
190    }
191}
192
193//----------------------------------------------------------------------------------------------------
194
195void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
196{
197  NodeProp &old_head_prop = sgraph[h].prop;
198  NodeProp &old_dep_prop = sgraph[d].prop;
199  NodeProp new_head_prop = compute_head_prop(old_head_prop,l,new_head_boubbles,old_dep_prop.flags);
200  NodeProp new_dep_prop = compute_dep_prop(old_dep_prop,l,new_dep_boubbles);
201
202  Edge new_head_edge(sgraph[h].edge);
203  int newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge);
204  if( newh < 0 )
205      {
206        newh = create_new_node(h,new_head_prop,new_head_edge);
207        sgraph[newh].visible_as_neighbour = false;
208      }
209
210  Edge new_dep_edge;
211  int newd = find_existing_node(sgraph[d].mnode, new_dep_prop, new_dep_edge);
212  if( newd < 0)
213    newd = create_new_node(d,new_dep_prop,new_dep_edge);
214
215
216  sgraph[newd].heads.push_back(Arc(newh,l.role,h,d));
217  sgraph[newh].deps.push_back(Arc(newd,l.role,h,d));
218
219  if(debug)
220    {
221      sgraph.print_arc(stderr,"link",newh,newd,l.role,1);
222      sgraph.print_node_debug(stderr,"",newh,h);
223      sgraph.print_node_debug(stderr,"",newd,d);
224    }
225 
226}
227
228//====================================================================================================
229
230bool check_meeting_boubles(list<Boubble*>& boubbles)
231{
232  bool hremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
233  bool dremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
234
235  // cerr << "CHECKING MEETING BUBBLES" << endl;
236
237  for(list<Boubble*>::iterator hb = boubbles.begin(); hb != boubbles.end(); hb = hremove ? boubbles.erase(hb) : ++hb )
238    {
239      hremove=false;
240      for(list<Boubble*>::iterator db = hb; db != boubbles.end(); db = dremove ? boubbles.erase(db) : ++db )
241        {
242          // cerr << " db:" << **db;
243          dremove=false;
244          if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() )
245            {
246              // cerr << "Z";
247              int srcnode,dstnode;
248              if( (*hb)->reverse()==false )
249                srcnode = (*hb)->src(), dstnode = (*db)->src();
250              else
251                srcnode = (*db)->src(), dstnode = (*hb)->src();
252              if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) )
253                {
254                  // cerr << " REMOVE ";
255                  hremove=dremove=true;
256                  if(debug) fprintf(stderr,"BOUBBLES MET!!!\n");
257                }
258              else
259                {
260                  // cerr << " FAIL ";
261                  if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n");
262                  return false;
263                }
264            }
265        }
266    }
267  return true;
268}
269
270//====================================================================================================
271
272// sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node
273// daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles
274
275bool check_boubbles_at_target(list<Boubble*>& boubbles, int node)
276{
277  bool remove=false;             // czy usun±æ ostatnio sprawdzany b±bel
278
279  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b )
280    if( (*b)->is_at_target() )
281      if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
282        {
283          // cerr << endl << "REMOVE ChBatT " << **b << endl;
284          remove=true;
285        }
286      else
287        return false;
288    else
289      remove=false;
290     
291  return true;
292}
293
294//====================================================================================================
295
296void try_connect_dependents(int j)
297{
298  LViterator lvi(sgraph,j);
299  int i;
300  while((i=lvi.next()) >= 0)
301      if(sgraph.saturated(i))
302        {
303          if(debug) {fprintf(stderr,"\t%d <-- %d",i,j); }
304         
305          list<const Link*> ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!!
306          list<const Link*>::iterator ri = ji_links.begin();
307          if(ri == ji_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
308          else
309            {
310              for(; ri != ji_links.end(); ++ri )
311                {
312                  if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
313                  if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri ))
314                    { if(debug) fprintf(stderr," ...constraints failed\n"); }
315                  else
316                    {
317                      list<Boubble*> new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role);
318                      list<Boubble*> new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role);
319                      if( check_meeting_boubles(new_head_boubbles) &&
320                          check_meeting_boubles(new_dep_boubbles) &&
321                          check_boubbles_at_target(new_head_boubbles,j) &&
322                          check_boubbles_at_target(new_dep_boubbles,i) )
323                        {
324                          if(debug) fprintf(stderr," ...SUCCESS!\n");
325                          connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
326                          // lvi.update_edge(sgraph,i);
327                        }
328                      else
329                        { if(debug) fprintf(stderr," ...boubbles failed\n"); }
330                    }
331                }
332            }
333        }
334      else
335        if(debug) {fprintf(stderr,"\t%d <-- %d\t%d unsaturated\n",i,j,i); } 
336}
337//----------------------------------------------------------------------------------------------------
338
339void try_connect_heads(int j)
340{
341  LViterator lvi(sgraph,j);
342  int i;
343  while((i=lvi.next()) >= 0)
344    if(sgraph.saturated(j))
345      {
346        if(debug) fprintf(stderr, "\t%d --> %d",i,j);
347       
348        list<const Link*> ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags );
349        list<const Link*>::iterator ri = ij_links.begin();
350        if(ri == ij_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
351        else
352          {
353            for(; ri != ij_links.end(); ++ri )
354              {
355                if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
356                if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) )
357                  { if(debug) fprintf(stderr," ...constraints failed\n"); }
358                else
359                  {
360                    list<Boubble*> new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role);
361                    list<Boubble*> new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role);
362                   
363                    if( check_meeting_boubles(new_head_boubbles) &&
364                        check_meeting_boubles(new_dep_boubbles) &&
365                        check_boubbles_at_target(new_head_boubbles,i) &&
366                        check_boubbles_at_target(new_dep_boubbles,j) )
367                      {
368                        if(debug) fprintf(stderr," ...SUCCESS!\n");
369                        connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
370                      }
371                    else
372                      { if(debug) fprintf(stderr," ...bubbles failed\n",i); }
373                  }
374              }
375          }
376      }
377    else
378      if(debug) {fprintf(stderr,"\t* <-- %d    unsaturated\n",j); }
379}
380
381//====================================================================================================
382
383void update_sets()
384{
385  for(int n=0; n<sgraph.size(); ++n)
386    {
387      LViterator lvi(sgraph,n,false);
388      LHiterator lhi(sgraph,n);
389      LDiterator ldi(sgraph,n);
390      int i;
391
392      // printf("UPDATING LV[%d]:",n);
393      while((i=lvi.next())>=0)
394        {
395          // printf(" %d",i);
396          sgraph[n].LV.set(i);
397        }
398      // printf("\n");
399
400      while((i=lhi.next())>=0) sgraph[n].LH.set(i);
401      while((i=ldi.next())>=0) sgraph[n].LD.set(i);
402    }
403}
404
405//====================================================================================================
406
407void print_sets(int n)
408{
409  LViterator lvi(sgraph,n);
410  LHiterator lhi(sgraph,n);
411  LDiterator ldi(sgraph,n);
412 
413  int i; 
414  printf("LV[%d]: ",n);
415  while((i=lvi.next())>=0)
416        {
417          printf("%d ",i);
418          sgraph[n].LV.set(i);
419        }
420
421  printf("LH[%d]: ",n);
422  while((i=lhi.next())>=0)
423    {
424      printf("%d ",i);
425      sgraph[n].LH.set(i);
426    }
427  printf("LD[%d]: ",n);
428  while((i=ldi.next())>=0)
429    {
430      printf("%d ",i);
431      sgraph[n].LD.set(i);
432    }
433  printf("\n");
434}
435
436//====================================================================================================
437
438void reverse_links()
439{
440  list<int>::iterator i = nodelist.begin();
441  for(++i; i!=nodelist.end(); ++i)
442    {
443      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
444        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
445      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
446        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
447    }
448}
449
450//====================================================================================================
451
452void dgp1()
453{
454
455  nodelist.clear();
456  nodelist.push_back(0); // BOS
457  processed=nodelist.begin();
458
459  for(int m=0; m<mgraph.size() ; ++m)
460  {
461    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*
462
463    set_initial_constraints(basenode);
464    nodelist.push_back(basenode);
465
466    if(debug) sgraph.print_node_debug(stderr,"node",basenode,-1); // STDOUT!!!
467    // if(debug) print_sets(basenode);
468
469    list<int>::iterator cursor=processed;
470    while(++cursor != nodelist.end())
471    {
472      if(debug) sgraph.print_node_debug(stderr,"CUR>",*cursor,-1);
473      try_connect_dependents(*cursor);
474      try_connect_heads(*cursor);
475      processed=cursor;
476    }
477
478  }
479   // reverse_links();
480  update_sets();
481}
Note: See TracBrowser for help on using the repository browser.