[519eaf5] | 1 | #include <iostream> |
---|
| 2 | using namespace std; |
---|
| 3 | |
---|
[acbabee] | 4 | #include "dgp1.hh" |
---|
[e7de6cc] | 5 | #include "global.hh" |
---|
| 6 | |
---|
| 7 | extern Grammar grammar; |
---|
| 8 | extern MGraph mgraph; |
---|
| 9 | extern SGraph sgraph; |
---|
| 10 | |
---|
| 11 | extern bool debug; |
---|
| 12 | |
---|
| 13 | list<int> nodelist; |
---|
| 14 | list<int>::iterator processed; |
---|
| 15 | |
---|
[3b02b04] | 16 | |
---|
| 17 | void print_sets(int n); |
---|
| 18 | |
---|
| 19 | |
---|
[e7de6cc] | 20 | //==================================================================================================== |
---|
| 21 | |
---|
| 22 | void 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 | |
---|
| 32 | bool changing_constraints(int head, Role role) |
---|
| 33 | { |
---|
| 34 | return grammar.is_sgl(role) || sgraph[head].prop.required[role]; |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | //==================================================================================================== |
---|
| 38 | |
---|
| 39 | NodeProp 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 | |
---|
[3b02b04] | 53 | ret.boubbles.merge(bs); //DOBRZE |
---|
[e7de6cc] | 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 | |
---|
| 64 | NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs) |
---|
| 65 | { |
---|
| 66 | NodeProp ret=depprop; |
---|
[3b02b04] | 67 | ret.boubbles.merge(bs); //DOBRZE |
---|
[e7de6cc] | 68 | return ret; |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | //==================================================================================================== |
---|
| 72 | |
---|
[acbabee] | 73 | int find_existing_node(int mnode, NodeProp p, Edge e) |
---|
[e7de6cc] | 74 | { |
---|
[acbabee] | 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; |
---|
[e7de6cc] | 82 | } |
---|
| 83 | |
---|
| 84 | //==================================================================================================== |
---|
| 85 | |
---|
| 86 | list<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 | } |
---|
[3b02b04] | 95 | |
---|
[e7de6cc] | 96 | return ret; |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | //---------------------------------------------------------------------------------------------------- |
---|
| 100 | |
---|
| 101 | list<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 | |
---|
| 117 | list<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 | |
---|
[3b02b04] | 133 | void copy_links(int i, int j) |
---|
[e7de6cc] | 134 | { |
---|
[3b02b04] | 135 | sgraph[j].heads = sgraph[i].heads; |
---|
| 136 | sgraph[j].deps = sgraph[i].deps; |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | |
---|
| 140 | void 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 | |
---|
[acbabee] | 151 | int create_new_node(int anc, NodeProp& prop, Edge edge) |
---|
[e7de6cc] | 152 | { |
---|
[acbabee] | 153 | int newheadind = sgraph.clone(anc,prop,edge); |
---|
[3b02b04] | 154 | nodelist.push_back(newheadind); |
---|
[519eaf5] | 155 | copy_links(anc,newheadind); |
---|
[3b02b04] | 156 | create_reverse_links(newheadind); |
---|
[acbabee] | 157 | if(debug) sgraph.print_node_debug(stderr,"clone",newheadind,anc); |
---|
[b97a556] | 158 | // if(debug) print_sets(newheadind); |
---|
[e7de6cc] | 159 | return newheadind; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | //==================================================================================================== |
---|
| 163 | |
---|
[3b02b04] | 164 | void connect_left(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles) |
---|
[e7de6cc] | 165 | { |
---|
| 166 | |
---|
[acbabee] | 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); |
---|
[e7de6cc] | 171 | |
---|
[acbabee] | 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 ) |
---|
[854bece] | 175 | { |
---|
| 176 | newd = create_new_node(d,new_dep_prop,new_dep_edge); |
---|
| 177 | sgraph[newd].prop.has_head = true; |
---|
| 178 | } |
---|
[e7de6cc] | 179 | |
---|
[acbabee] | 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)); |
---|
[e7de6cc] | 187 | |
---|
[acbabee] | 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 | } |
---|
[e7de6cc] | 194 | } |
---|
| 195 | |
---|
| 196 | //---------------------------------------------------------------------------------------------------- |
---|
| 197 | |
---|
[3b02b04] | 198 | void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles) |
---|
[e7de6cc] | 199 | { |
---|
[acbabee] | 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); |
---|
[854bece] | 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); |
---|
[acbabee] | 208 | if( newh < 0 ) |
---|
[3b02b04] | 209 | { |
---|
[acbabee] | 210 | newh = create_new_node(h,new_head_prop,new_head_edge); |
---|
[854bece] | 211 | sgraph[newh].prop.visible_as_neighbour = false; |
---|
[3b02b04] | 212 | } |
---|
[e7de6cc] | 213 | |
---|
[acbabee] | 214 | Edge new_dep_edge; |
---|
[854bece] | 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 | } |
---|
[e7de6cc] | 221 | |
---|
| 222 | |
---|
[acbabee] | 223 | sgraph[newd].heads.push_back(Arc(newh,l.role,h,d)); |
---|
| 224 | sgraph[newh].deps.push_back(Arc(newd,l.role,h,d)); |
---|
[e7de6cc] | 225 | |
---|
[acbabee] | 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 | } |
---|
[e7de6cc] | 232 | |
---|
| 233 | } |
---|
| 234 | |
---|
| 235 | //==================================================================================================== |
---|
| 236 | |
---|
[519eaf5] | 237 | bool 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 | |
---|
[acbabee] | 242 | // cerr << "CHECKING MEETING BUBBLES" << endl; |
---|
| 243 | |
---|
[519eaf5] | 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 | { |
---|
[acbabee] | 249 | // cerr << " db:" << **db; |
---|
[519eaf5] | 250 | dremove=false; |
---|
| 251 | if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() ) |
---|
| 252 | { |
---|
[acbabee] | 253 | // cerr << "Z"; |
---|
[519eaf5] | 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 | { |
---|
[acbabee] | 261 | // cerr << " REMOVE "; |
---|
[519eaf5] | 262 | hremove=dremove=true; |
---|
| 263 | if(debug) fprintf(stderr,"BOUBBLES MET!!!\n"); |
---|
| 264 | } |
---|
| 265 | else |
---|
| 266 | { |
---|
[acbabee] | 267 | // cerr << " FAIL "; |
---|
[519eaf5] | 268 | if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n"); |
---|
| 269 | return false; |
---|
| 270 | } |
---|
| 271 | } |
---|
| 272 | } |
---|
| 273 | } |
---|
| 274 | return true; |
---|
| 275 | } |
---|
| 276 | |
---|
| 277 | //==================================================================================================== |
---|
| 278 | |
---|
[a15e59b] | 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 | |
---|
| 282 | bool check_boubbles_at_target(list<Boubble*>& boubbles, int node) |
---|
[e7de6cc] | 283 | { |
---|
[a15e59b] | 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()) ) |
---|
[519eaf5] | 289 | { |
---|
[acbabee] | 290 | // cerr << endl << "REMOVE ChBatT " << **b << endl; |
---|
[519eaf5] | 291 | remove=true; |
---|
| 292 | } |
---|
[a15e59b] | 293 | else |
---|
| 294 | return false; |
---|
| 295 | else |
---|
| 296 | remove=false; |
---|
| 297 | |
---|
[e7de6cc] | 298 | return true; |
---|
| 299 | } |
---|
| 300 | |
---|
| 301 | //==================================================================================================== |
---|
| 302 | |
---|
[3b02b04] | 303 | void try_connect_dependents(int j) |
---|
[e7de6cc] | 304 | { |
---|
[3b02b04] | 305 | LViterator lvi(sgraph,j); |
---|
| 306 | int i; |
---|
| 307 | while((i=lvi.next()) >= 0) |
---|
[854bece] | 308 | if(sgraph.saturated(i) && ! sgraph.has_head(i)) |
---|
[e7de6cc] | 309 | { |
---|
[acbabee] | 310 | if(debug) {fprintf(stderr,"\t%d <-- %d",i,j); } |
---|
[519eaf5] | 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); |
---|
[acbabee] | 333 | // lvi.update_edge(sgraph,i); |
---|
[519eaf5] | 334 | } |
---|
| 335 | else |
---|
| 336 | { if(debug) fprintf(stderr," ...boubbles failed\n"); } |
---|
| 337 | } |
---|
| 338 | } |
---|
| 339 | } |
---|
[e7de6cc] | 340 | } |
---|
[519eaf5] | 341 | else |
---|
[acbabee] | 342 | if(debug) {fprintf(stderr,"\t%d <-- %d\t%d unsaturated\n",i,j,i); } |
---|
[e7de6cc] | 343 | } |
---|
| 344 | //---------------------------------------------------------------------------------------------------- |
---|
| 345 | |
---|
[3b02b04] | 346 | void try_connect_heads(int j) |
---|
[e7de6cc] | 347 | { |
---|
[3b02b04] | 348 | LViterator lvi(sgraph,j); |
---|
| 349 | int i; |
---|
| 350 | while((i=lvi.next()) >= 0) |
---|
[acbabee] | 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); } |
---|
[e7de6cc] | 386 | } |
---|
[3b02b04] | 387 | |
---|
| 388 | //==================================================================================================== |
---|
| 389 | |
---|
| 390 | void 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 | |
---|
| 414 | void print_sets(int n) |
---|
| 415 | { |
---|
| 416 | LViterator lvi(sgraph,n); |
---|
| 417 | LHiterator lhi(sgraph,n); |
---|
| 418 | LDiterator ldi(sgraph,n); |
---|
[e7de6cc] | 419 | |
---|
[3b02b04] | 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 | |
---|
[e7de6cc] | 443 | //==================================================================================================== |
---|
| 444 | |
---|
| 445 | void 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 | |
---|
| 459 | void 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 | |
---|
[acbabee] | 473 | if(debug) sgraph.print_node_debug(stderr,"node",basenode,-1); // STDOUT!!! |
---|
[519eaf5] | 474 | // if(debug) print_sets(basenode); |
---|
[e7de6cc] | 475 | |
---|
| 476 | list<int>::iterator cursor=processed; |
---|
| 477 | while(++cursor != nodelist.end()) |
---|
| 478 | { |
---|
[acbabee] | 479 | if(debug) sgraph.print_node_debug(stderr,"CUR>",*cursor,-1); |
---|
[3b02b04] | 480 | try_connect_dependents(*cursor); |
---|
| 481 | try_connect_heads(*cursor); |
---|
[e7de6cc] | 482 | processed=cursor; |
---|
| 483 | } |
---|
| 484 | |
---|
| 485 | } |
---|
[3b02b04] | 486 | // reverse_links(); |
---|
| 487 | update_sets(); |
---|
[e7de6cc] | 488 | } |
---|