source: src/dgp/dgp1.cc @ f4bf33e

Last change on this file since f4bf33e was a15e59b, checked in by Tomasz Obrebski <to@…>, 13 years ago

dodana opcja --time w dgp, poprawione przesy�anie b�belk�w, obsluga &LEFT, &RIGHT
  • Property mode set to 100644
File size: 14.3 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
305// sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node
306// daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles
307
308bool check_boubbles_at_target(list<Boubble*>& boubbles, int node)
309{
310  list<Boubble*>::iterator last; // ostatnio sprawdzany b±bel
311  bool remove=false;             // czy usun±æ ostatnio sprawdzany b±bel
312
313  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b )
314    if( (*b)->is_at_target() )
315      if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
316        remove=true;
317      else
318        return false;
319    else
320      remove=false;
321     
322  return true;
323}
324
325// bool check_boubbles_at_target(list<Boubble*> boubbles, int node)
326// {
327//   for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); ++b )
328//     if( (*b)->is_at_target() && !grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
329//       return false;
330//   return true;
331// }
332
333//====================================================================================================
334
335void try_connect_dependents(list<int>::iterator j)
336{
337  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
338    if(sgraph.visible(*i,*j) && sgraph.saturated(*i))
339    {
340      if(debug) {fprintf(stderr,"## %d <-- %d ... ",*i,*j); }
341
342      list<const Link*> ji_links = grammar.connectable2( sgraph.cat(*j), sgraph.cat(*i), sgraph[*j].prop.flags, sgraph[*i].prop.flags); // ref do Roles!!!
343      list<const Link*>::iterator ri = ji_links.begin();
344      if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
345      else
346        {
347          for(; ri != ji_links.end(); ++ri )
348            if(!grammar.check_constr2(sgraph[*j].prop,sgraph[*i].prop,0,**ri ))
349              { if(debug) fprintf(stderr,"constraints failed\n"); }
350            else
351              {
352                list<Boubble*> new_head_boubbles = collect_head_boubbles(*j,*i,(*ri)->role);
353                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(*j,*i,(*ri)->role);
354               
355                if( !(check_boubbles_at_target(new_head_boubbles,*j) && check_boubbles_at_target(new_dep_boubbles,*i)) )
356                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
357                else
358                  {
359                    if(debug) fprintf(stderr,"success\n");
360                    connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
361                  }
362              }
363        }
364    }
365}
366
367
368//----------------------------------------------------------------------------------------------------
369
370void try_connect_heads(list<int>::iterator j)
371{
372  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
373    if(sgraph.visible(*i,*j))
374    {
375      if(debug) fprintf(stderr, "## %d --> %d ... ",*i,*j);
376
377      list<const Link*> ij_links = grammar.connectable2( sgraph.cat(*i), sgraph.cat(*j), sgraph[*i].prop.flags, sgraph[*j].prop.flags );
378      list<const Link*>::iterator ri = ij_links.begin();
379      if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); }
380      else
381        {
382          for(; ri != ij_links.end(); ++ri )
383            if( !grammar.check_constr2( sgraph[*i].prop, sgraph[*j].prop, 1, **ri ) )
384              { if(debug) fprintf(stderr,"constraints failed\n"); }
385            else
386              {
387                list<Boubble*> new_head_boubbles = collect_head_boubbles(*i,*j,(*ri)->role);
388                list<Boubble*> new_dep_boubbles = collect_dep_boubbles(*i,*j,(*ri)->role);
389               
390                if( !(check_boubbles_at_target(new_head_boubbles,*i) && check_boubbles_at_target(new_dep_boubbles,*j)) )
391                  { if(debug) fprintf(stderr,"boubbles failed\n"); }
392                else
393                  {
394                    if(debug) fprintf(stderr,"success\n");
395                    connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
396                  }
397              }
398        }
399    }
400}
401 
402//====================================================================================================
403
404void reverse_links()
405{
406  list<int>::iterator i = nodelist.begin();
407  for(++i; i!=nodelist.end(); ++i)
408    {
409      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
410        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
411      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
412        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
413    }
414}
415
416//====================================================================================================
417
418void dgp1()
419{
420
421  nodelist.clear();
422  nodelist.push_back(0); // BOS
423  processed=nodelist.begin();
424
425  for(int m=0; m<mgraph.size() ; ++m)
426  {
427    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*
428
429    set_initial_constraints(basenode);
430    nodelist.push_back(basenode);
431
432    if(debug) {sgraph.print_node_debug(stderr,"B ",basenode,-1);} // STDOUT!!!
433
434    list<int>::iterator cursor=processed;
435    while(++cursor != nodelist.end())
436    {
437      try_connect_dependents(cursor);
438      try_connect_heads(cursor);
439      processed=cursor;
440    }
441
442  }
443  reverse_links();
444}
Note: See TracBrowser for help on using the repository browser.