Index: src/dgp/dgp1.cc =================================================================== --- src/dgp/dgp1.cc (revision d484a3254b584fb1c97577bdc58ee2ae3796028c) +++ src/dgp/dgp1.cc (revision acbabee74272f626d34fbc8e42126d06c76c7903) @@ -2,5 +2,5 @@ using namespace std; -#include "dgp0.hh" +#include "dgp1.hh" #include "global.hh" @@ -71,25 +71,13 @@ //==================================================================================================== -int find_existing_node(int mnodeind, NodeProp p, bitset& newheadLH, bitset& newheadLV) -{ - MNode& mnode = mgraph[mnodeind]; - int ret=-1; - for(vector::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps) - { - if(debug) fprintf(stderr,"#find existing node: checking %d ... \n", *ps); - if(sgraph[*ps].prop==p) - if(sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV) - { - ret = *ps; - if(debug) fprintf(stderr,"#\tsucceeded because of LH/LV equality ()\n"); - } - else - { - if(debug) fprintf(stderr,"#\tfailed beacause of LH/LV inequality\n"); - } - } - - if(debug) fprintf(stderr,"\n"); - return ret; +int find_existing_node(int mnode, NodeProp p, Edge e) +{ + for(vector::iterator i = mgraph[mnode].snodes.begin(); i!=mgraph[mnode].snodes.end(); ++i) + if(sgraph[*i].prop==p && sgraph[*i].edge==e) + { + if(debug) fprintf(stderr,"\t\treusing %d\n",*i); + return *i; + } + return -1; } @@ -161,75 +149,15 @@ //==================================================================================================== -int create_new_head_node_left(int anc, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newheadind = sgraph.clone(anc,prop); +int create_new_node(int anc, NodeProp& prop, Edge edge) +{ + int newheadind = sgraph.clone(anc,prop,edge); nodelist.push_back(newheadind); - sgraph[newheadind].LH = LH; - sgraph[newheadind].LD = LD; - sgraph[newheadind].in_LH = true; - sgraph[newheadind].LV.reset(); - copy_links(anc,newheadind); create_reverse_links(newheadind); - - if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc); + if(debug) sgraph.print_node_debug(stderr,"clone",newheadind,anc); // if(debug) print_sets(newheadind); return newheadind; } -int create_new_dep_node_left(int anc, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(anc,prop); - nodelist.push_back(newind); - sgraph[newind].LH.reset(); - sgraph[newind].LD=LD; - sgraph[newind].in_LH=false; //??????? - sgraph[newind].LV.reset(); - - copy_links(anc,newind); - create_reverse_links(newind); - - if(debug) sgraph.print_node_debug(stderr,"add new",newind,anc); - // if(debug) print_sets(newind); - - return newind; -} - -int create_new_head_node_right(int anc, NodeProp& prop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) -{ - int newheadind = sgraph.clone(anc,prop); - nodelist.push_back(newheadind); - sgraph[newheadind].LH=newheadLH; - sgraph[newheadind].LD=newheadLD; - sgraph[newheadind].in_LH=false; - sgraph[newheadind].LV=newheadLV; - - copy_links(anc,newheadind); - create_reverse_links(newheadind); - - if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc); - // if(debug) print_sets(newheadind); - - return newheadind; -} - -int create_new_dep_node_right(int anc, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(anc,prop); - nodelist.push_back(newind); - sgraph[newind].LH=LH; - sgraph[newind].LD=LD; - sgraph[newind].in_LH=true; //??????? - sgraph[newind].LV.reset(); - - copy_links(anc,newind); - create_reverse_links(newind); - - if(debug) sgraph.print_node_debug(stderr,"ADD NEW",newind,anc); - // if(debug) print_sets(newind); - - return newind; -} - //==================================================================================================== @@ -237,183 +165,64 @@ { - NodeProp &oldheadprop = sgraph[h].prop; - NodeProp &olddepprop = sgraph[d].prop; - - NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags); - - int newheadind; - if(oldheadprop==newheadprop) - newheadind = h; - else - { - bitset newheadLH = sgraph[h].LH; - bitset newheadLV = sgraph[d].LV; - bitset newheadLD = sgraph[h].LD; - - newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); - if( newheadind >= 0) // W£¡CZONE - sgraph[newheadind].LD |= newheadLD; - else + NodeProp &old_head_prop = sgraph[h].prop; + NodeProp &old_dep_prop = sgraph[d].prop; + NodeProp new_head_prop = compute_head_prop(old_head_prop,l,new_head_boubbles,old_dep_prop.flags); + NodeProp new_dep_prop = compute_dep_prop(old_dep_prop,l,new_dep_boubbles); + + Edge new_dep_edge(sgraph[d].edge); + int newd = find_existing_node(sgraph[d].mnode, new_dep_prop, new_dep_edge); + if( newd < 0 ) + newd = create_new_node(d,new_dep_prop,new_dep_edge); + + Edge new_head_edge(sgraph[newd].edge,newd); + int newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge); + if( newh < 0 ) + newh = create_new_node(h,new_head_prop,new_head_edge); + + sgraph[newh].deps.push_back(Arc(newd,l.role,h,d)); + sgraph[newd].heads.push_back(Arc(newh,l.role,h,d)); + + if(debug) + { + sgraph.print_arc(stderr,"link",newh,d,l.role,0); + sgraph.print_node_debug(stderr,"",newh,h); + sgraph.print_node_debug(stderr,"",newd,d); + } +} + +//---------------------------------------------------------------------------------------------------- + +void connect_right(int h, int d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) +{ + NodeProp &old_head_prop = sgraph[h].prop; + NodeProp &old_dep_prop = sgraph[d].prop; + NodeProp new_head_prop = compute_head_prop(old_head_prop,l,new_head_boubbles,old_dep_prop.flags); + NodeProp new_dep_prop = compute_dep_prop(old_dep_prop,l,new_dep_boubbles); + + Edge new_head_edge(sgraph[h].edge); + int newh = find_existing_node(sgraph[h].mnode, new_head_prop, new_head_edge); + if( newh < 0 ) { - newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV); - sgraph[newheadind].edge.clear(); - sgraph[newheadind].edge_contains_self = false; + newh = create_new_node(h,new_head_prop,new_head_edge); + sgraph[newh].visible_as_neighbour = false; } - - } - - NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); - - int newdepind; - - if(olddepprop==newdepprop) - newdepind = d; - else - { - bitset newdepLH = sgraph[d].LH; - bitset newdepLV = sgraph[d].LV; - bitset newdepLD = sgraph[d].LD; - - newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); - if( newdepind >= 0) // W£¡CZONE - sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD - else - { - newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV); - sgraph[newdepind].edge.clear(); - //sgraph[newdepind].edge.push_back(newdepind); // TO - sgraph[newdepind].edge_contains_self = true; // LUB TO - } - } - - - sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); - sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); - sgraph[newheadind].edge.push_back(newdepind); - - if(sgraph[d].saturated()) sgraph[newheadind].LV |= sgraph[d].LV; - - sgraph[newheadind].LD.set(d); - if(sgraph[d].saturated()) sgraph[newheadind].LD |= sgraph[d].LD; - - if(debug) sgraph.print_arc(stderr,"new link",newheadind,d,l.role,0); - if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h); - // if(debug) print_sets(newheadind); - if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d); - // if(debug) print_sets(newdepind); -} - -//---------------------------------------------------------------------------------------------------- - -void connect_right(int h, int d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) -{ - NodeProp &oldheadprop = sgraph[h].prop; - - NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[d].prop.flags); - - int newheadind; - - if(oldheadprop==newheadprop) - newheadind = h; - else - { - bitset newheadLH = sgraph[h].LH; - bitset newheadLV = sgraph[h].LV; - bitset newheadLD = sgraph[h].LD; - - newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); - - if(debug) fprintf(stderr,"#HEAD EXISTS %d\n",newheadind); - - if( newheadind >= 0) // W£¡CZONE - sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD - else - { - newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV); - //if(!sgraph[h].edge.empty()) sgraph[newheadind].edge.push_back(newheadind); // TO - sgraph[newheadind].edge_contains_self = sgraph[h].edge_contains_self; // LUB TO - sgraph[newheadind].visible_as_neighbour = false; - } - } - - NodeProp &olddepprop = sgraph[d].prop; - NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); - - int newdepind; - - if(olddepprop==newdepprop) - newdepind = d; - else - { - bitset newdepLH = sgraph[d].LH; - bitset newdepLV = sgraph[d].LV; - bitset newdepLD = sgraph[d].LD; - - newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); - - if(debug) fprintf(stderr,"#DEP EXISTS %d\n",newdepind); - - if( newdepind >= 0) // W£¡CZONE - sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD - else - { - newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV); - sgraph[newdepind].edge.clear(); - sgraph[newdepind].edge_contains_self = false; - } - } - - - sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); - sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); - //sgraph[newdepind].edge.push_back(newheadind); - - sgraph[newdepind].LH.set(newheadind); - - // sgraph[*d].prop.merge_boubbles(new_dep_boubbles); - - if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH; - - if(debug) sgraph.print_arc(stderr,"new link",newheadind,newdepind,l.role,1); - if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h); - if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d); - -} - -//==================================================================================================== - -// bool check_meeting_boubles(list& hboubbles, list& dboubbles) -// { -// bool hremove=false; // czy usun±æ ostatnio sprawdzany b±bel -// bool dremove=false; // czy usun±æ ostatnio sprawdzany b±bel - -// for(list::iterator hb = hboubbles.begin(); hb != hboubbles.end(); hb = hremove ? hboubbles.erase(hb) : ++hb ) -// { -// hremove=false; -// for(list::iterator db = dboubbles.begin(); db != dboubbles.end(); db = dremove ? dboubbles.erase(db) : ++db ) -// { -// dremove=false; -// if( (*hb)->rel()==(*db)->rel() && (*hb)->dir()==DOWN && (*db)->dir()==UP && (*hb)->reverse()!=(*db)->reverse() ) -// { -// int srcnode,dstnode; -// if( (*hb)->reverse()==false ) -// srcnode = (*hb)->src(), dstnode = (*db)->src(); -// else -// srcnode = (*db)->src(), dstnode = (*hb)->src(); -// if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) ) -// { -// hremove=dremove=true; -// if(debug) fprintf(stderr,"BOUBBLES MET!!!\n"); -// } -// else -// { -// if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n"); -// return false; -// } -// } -// } -// } -// return true; -// } + + Edge new_dep_edge; + int newd = find_existing_node(sgraph[d].mnode, new_dep_prop, new_dep_edge); + if( newd < 0) + newd = create_new_node(d,new_dep_prop,new_dep_edge); + + + sgraph[newd].heads.push_back(Arc(newh,l.role,h,d)); + sgraph[newh].deps.push_back(Arc(newd,l.role,h,d)); + + if(debug) + { + sgraph.print_arc(stderr,"link",newh,newd,l.role,1); + sgraph.print_node_debug(stderr,"",newh,h); + sgraph.print_node_debug(stderr,"",newd,d); + } + +} //==================================================================================================== @@ -424,15 +233,16 @@ bool dremove=false; // czy usun±æ ostatnio sprawdzany b±bel + // cerr << "CHECKING MEETING BUBBLES" << endl; + for(list::iterator hb = boubbles.begin(); hb != boubbles.end(); hb = hremove ? boubbles.erase(hb) : ++hb ) { - cout << endl << "hb:" << **hb ; hremove=false; for(list::iterator db = hb; db != boubbles.end(); db = dremove ? boubbles.erase(db) : ++db ) { - cout << " db:" << **db; + // cerr << " db:" << **db; dremove=false; if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() ) { - cout << "Z"; + // cerr << "Z"; int srcnode,dstnode; if( (*hb)->reverse()==false ) @@ -442,5 +252,5 @@ if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) ) { - cout << " REMOVE "; + // cerr << " REMOVE "; hremove=dremove=true; if(debug) fprintf(stderr,"BOUBBLES MET!!!\n"); @@ -448,5 +258,5 @@ else { - cout << " FAIL "; + // cerr << " FAIL "; if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n"); return false; @@ -471,5 +281,5 @@ if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) ) { - cout << endl << "REMOVE ChBatT " << **b << endl; + // cerr << endl << "REMOVE ChBatT " << **b << endl; remove=true; } @@ -489,10 +299,7 @@ int i; while((i=lvi.next()) >= 0) - { - //if(debug) sgraph.print_node_debug(stderr,"D-CUR>",i,-1); - if(sgraph.saturated(i)) { - if(debug) {fprintf(stderr,"%d <--",i); } + if(debug) {fprintf(stderr,"\t%d <-- %d",i,j); } list ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!! @@ -517,5 +324,5 @@ if(debug) fprintf(stderr," ...SUCCESS!\n"); connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles); - lvi.update_edge(sgraph,i); + // lvi.update_edge(sgraph,i); } else @@ -526,7 +333,5 @@ } else - if(debug) {fprintf(stderr,"%d <-- unsaturated\n",i); } - } - + if(debug) {fprintf(stderr,"\t%d <-- %d\t%d unsaturated\n",i,j,i); } } //---------------------------------------------------------------------------------------------------- @@ -537,42 +342,39 @@ int i; while((i=lvi.next()) >= 0) - { - // if(debug) sgraph.print_node_debug(stderr,"H-CUR> ",i,-1); - if(sgraph.saturated(j)) - { - if(debug) fprintf(stderr, "%d -->",i); - - list ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags ); - list::iterator ri = ij_links.begin(); - if(ri == ij_links.end()) { if(debug) fprintf(stderr," no roles\n"); } - else - { - for(; ri != ij_links.end(); ++ri ) - { - if(debug) fprintf(stderr," %s",(*ri)->role.str()); - if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) ) - { if(debug) fprintf(stderr," ...constraints failed\n"); } - else - { - list new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role); - list new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role); - - if( check_meeting_boubles(new_head_boubbles) && - check_meeting_boubles(new_dep_boubbles) && - check_boubbles_at_target(new_head_boubbles,i) && - check_boubbles_at_target(new_dep_boubbles,j) ) - { - if(debug) fprintf(stderr," ...SUCCESS!\n"); - connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles ); - } - else - { if(debug) fprintf(stderr," ...bubbles failed\n",i); } - } - } - } - } - else - if(debug) {fprintf(stderr,"%d <-- unsaturated\n",j); } - } + if(sgraph.saturated(j)) + { + if(debug) fprintf(stderr, "\t%d --> %d",i,j); + + list ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags ); + list::iterator ri = ij_links.begin(); + if(ri == ij_links.end()) { if(debug) fprintf(stderr," no roles\n"); } + else + { + for(; ri != ij_links.end(); ++ri ) + { + if(debug) fprintf(stderr," %s",(*ri)->role.str()); + if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) ) + { if(debug) fprintf(stderr," ...constraints failed\n"); } + else + { + list new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role); + list new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role); + + if( check_meeting_boubles(new_head_boubbles) && + check_meeting_boubles(new_dep_boubbles) && + check_boubbles_at_target(new_head_boubbles,i) && + check_boubbles_at_target(new_dep_boubbles,j) ) + { + if(debug) fprintf(stderr," ...SUCCESS!\n"); + connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles ); + } + else + { if(debug) fprintf(stderr," ...bubbles failed\n",i); } + } + } + } + } + else + if(debug) {fprintf(stderr,"\t* <-- %d unsaturated\n",j); } } @@ -662,5 +464,5 @@ nodelist.push_back(basenode); - if(debug) sgraph.print_node_debug(stderr,"add base",basenode,-1); // STDOUT!!! + if(debug) sgraph.print_node_debug(stderr,"node",basenode,-1); // STDOUT!!! // if(debug) print_sets(basenode); @@ -668,5 +470,5 @@ while(++cursor != nodelist.end()) { - if(debug) sgraph.print_node_debug(stderr,"MAIN-CUR> ",*cursor,-1); + if(debug) sgraph.print_node_debug(stderr,"CUR>",*cursor,-1); try_connect_dependents(*cursor); try_connect_heads(*cursor); Index: src/dgp/dgp1.hh =================================================================== --- src/dgp/dgp1.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/dgp1.hh (revision acbabee74272f626d34fbc8e42126d06c76c7903) @@ -1,4 +1,4 @@ -#ifndef _DGP0_HH -#define _DGP0_HH +#ifndef _DGP1_HH +#define _DGP1_HH #include "grammar.hh" Index: src/dgp/sgraph.cc =================================================================== --- src/dgp/sgraph.cc (revision d484a3254b584fb1c97577bdc58ee2ae3796028c) +++ src/dgp/sgraph.cc (revision acbabee74272f626d34fbc8e42126d06c76c7903) @@ -1,3 +1,2 @@ -#include "global.hh" #include "sgraph.hh" #include "grammar.hh" @@ -16,19 +15,19 @@ newnode.mnode=mnodeind; - for(vector::iterator pm=mgraph[newnode.mnode].pred.begin(); pm!=mgraph[newnode.mnode].pred.end(); ++pm) - for(vector::iterator ps=mgraph[*pm].snodes.begin(); ps!=mgraph[*pm].snodes.end(); ++ps) - if(nodes[*ps].in_LH) - { - newnode.LV.set(*ps); - if(nodes[*ps].saturated()) newnode.LV |= nodes[*ps].LH; - } + // for(vector::iterator pm=mgraph[newnode.mnode].pred.begin(); pm!=mgraph[newnode.mnode].pred.end(); ++pm) + // for(vector::iterator ps=mgraph[*pm].snodes.begin(); ps!=mgraph[*pm].snodes.end(); ++ps) + // if(nodes[*ps].in_LH) + // { + // newnode.LV.set(*ps); + // if(nodes[*ps].saturated()) newnode.LV |= nodes[*ps].LH; + // } mgraph[newnode.mnode].snodes.push_back(lastnodeind()); - newnode.in_LH=true; + // newnode.in_LH=true; - newnode.edge.push_back(lastnodeind()); + // newnode.edge.push_back(lastnodeind()); - newnode.edge_contains_self = true ; + newnode.edge.insert_self(); return lastnodeind(); @@ -55,11 +54,12 @@ //==================================================================================================== -int SGraph::clone(int ancind, NodeProp newprop) +int SGraph::clone(int ancind, NodeProp newprop, Edge edge) { SNode &newnode=makenewnode(); SNode &ancnode = nodes[ancind]; - newnode.prop=newprop; - newnode.mnode=ancnode.mnode; + newnode.prop = newprop; + newnode.edge = edge; + newnode.mnode = ancnode.mnode; mgraph[newnode.mnode].snodes.push_back(lastnodeind()); @@ -90,7 +90,7 @@ { if(dir==0) - fprintf(f,"%s %s:%d <-- %d\n", msg, role.str(), dep, head); + fprintf(f,"%s\t%d <-- %d\t%s\n", msg, dep, head, role.str()); else - fprintf(f,"%s %s:%d --> %d\n", msg, role.str(), head, dep); + fprintf(f,"%s\t%d --> %d\t%s\n", msg, head, dep, role.str()); } @@ -172,13 +172,15 @@ { char *buf0 = buf; - buf+=sprintf(buf,"%-10s",pref); + buf+=sprintf(buf,"%-8s",pref); buf+=sprintf(buf,"%d.%s",n,form(n)); buf+=sprintf(buf,";"); buf+=sprintf(buf,"%s ",cat(n).str()); while(buf-buf0<40) buf+=sprintf(buf," "); - buf+=sprint_node(buf,n,anc,HEADS|DEPS|SETS|CONSTRAINTS); + buf+=sprint_node(buf,n,anc,HEADS|DEPS|CONSTRAINTS); buf+=sprintf(buf,"/"); - for(vector::iterator e = nodes[n].edge.begin(); e != nodes[n].edge.end(); e++ ) + if(nodes[n].edge.self()) + buf += sprintf(buf,"* "); + for(list::iterator e = nodes[n].edge.others().begin(); e != nodes[n].edge.others().end(); e++ ) buf += sprintf(buf,"%d ", *e); Index: src/dgp/sgraph.hh =================================================================== --- src/dgp/sgraph.hh (revision d484a3254b584fb1c97577bdc58ee2ae3796028c) +++ src/dgp/sgraph.hh (revision acbabee74272f626d34fbc8e42126d06c76c7903) @@ -13,5 +13,5 @@ #include "thesymbols.hh" #include "boubble.hh" - +#include "global.hh" using namespace std; @@ -116,41 +116,9 @@ } -//---------------------------------------------------------------------------------------------------- - -inline -NodeProp::~NodeProp() -{ - clear_boubbles(); -} -//---------------------------------------------------------------------------------------------------- - -inline -NodeProp::NodeProp() -{ - clear(); -} - -//---------------------------------------------------------------------------------------------------- - -inline -NodeProp::NodeProp(const NodeProp& p) -{ - copy(p); -} - -//---------------------------------------------------------------------------------------------------- - -inline -NodeProp& NodeProp::operator=(const NodeProp& p) -{ - clear(); - copy(p); - return *this; -} - -//---------------------------------------------------------------------------------------------------- - -inline -void NodeProp::clear() +inline NodeProp::~NodeProp() { clear_boubbles(); } +inline NodeProp::NodeProp() { clear(); } +inline NodeProp::NodeProp(const NodeProp& p) { copy(p); } +inline NodeProp& NodeProp::operator=(const NodeProp& p) { clear(); copy(p); return *this; } +inline void NodeProp::clear() { required.reset(); @@ -163,4 +131,29 @@ //==================================================================================================== +// CLASS Edge +//==================================================================================================== + +class Edge +{ +public: + Edge() : _self(false) { } + Edge(const Edge& e, int map_self) { assign(e,map_self); } + + bool self() const { return _self; } + list& others() { return _others; } + + void insert_self(bool b=true) { _self=b; } + void insert(int n) { list::iterator i=others().begin(); while(i!=others().end() && *i l) { for(list::const_iterator i=l.begin(); i!=l.end(); i++) insert(*i); } + + void assign(const Edge& e, int map_self=-1) { _others = e._others; if(e.self()) { _self = false; insert(map_self); } } + const bool operator==(const Edge& e) const { return _self == e._self && _others == e._others; } + +private: + bool _self; + list _others; +}; + +//==================================================================================================== // CLASS SNode //==================================================================================================== @@ -175,6 +168,5 @@ NodeProp prop; - vector edge; - bool edge_contains_self; + Edge edge; bool visible_as_neighbour; @@ -189,4 +181,12 @@ void clear(); bool saturated(); + + // void edge_clear() { edge.clear(); edge_contains_self=false;} + // void edge_set(int i) { edge.clear(); edge_contains_self=false; edge.push_back(i); } + // void edge_set(vector& v) { edge.assign(v.begin(),v.end()); edge_contains_self=false; } + // void edge_set_self(bool b=true) { edge.clear(); edge_contains_self=b; } + // void edge_add(int i) { edge.push_back(i); } + // void edge_add(vector& v) { edge.insert(edge.end(),v.begin(),v.end()); } + // void edge_add_self(bool b=true) { edge_contains_self=b; } }; @@ -216,5 +216,5 @@ void clear() { nodes.clear(); } int add_base_snode(int mnodeind); - int clone(int ancind, NodeProp newprop); + int clone(int ancind, NodeProp newprop, Edge edge); void update_left(int headind, int depind); void update_right(int headind, int depind); @@ -299,5 +299,5 @@ private: - + int snode; SGraph& sgraph; MGraph& mgraph; @@ -312,7 +312,7 @@ }; -inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : sgraph(sg), mgraph(sg.mgraph), strict(s) -{ - if(sg[n].edge_contains_self) // TO DODAÆ PO PRZEJŠCIU NA EDGE_CONTAINS_SELF +inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : snode(n), sgraph(sg), mgraph(sg.mgraph), strict(s) +{ + if(sg[n].edge.self()) { push_ld(n); @@ -320,21 +320,24 @@ } - for(vector::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) - { - if(*i != n) - { - push_ld(*i); - push_ln(*i); - } - - } -} - -inline void LViterator::update_edge(SGraph& sg, int n) -{ - for(vector::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) + for(list::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) { push_ld(*i); push_ln(*i); + + } +} + +inline void LViterator::update_edge(SGraph& sg, int n) +{ + if(sg[n].edge.self()) + { + push_ld(n); + push_ln(n); + } + + for(list::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) + { + push_ld(*i); + push_ln(*i); } } @@ -345,5 +348,8 @@ { if(waydown.empty()) - return -1; // + { + if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); + return -1; // + } else { @@ -353,5 +359,8 @@ push_ln(k); if(wayup.empty()) - return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW + { + if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); + return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW + } else { @@ -359,4 +368,5 @@ wayup.pop(); push_lh(i); + if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); return i; } @@ -364,4 +374,135 @@ } + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); + return i; + }; +} + +inline void LViterator::push_ld(int i) +{ + vector& arcs = sgraph[i].deps; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + { + push(waydown,a->dst); + if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LD waydown %d\n",snode,a->dst); + } +} + +inline void LViterator::push_lh(int i) +{ + vector& arcs = sgraph[i].heads; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + { + push(wayup,a->dst); + if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LH wayup %d\n",snode,a->dst); + } +} + +inline void LViterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + if(sgraph[*sp].visible_as_neighbour || !strict) + { + push(wayup,*sp); + if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LN wayup %d\n",snode, *sp); + } + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LNiterator +{ +public: + LNiterator(SGraph& sg, int n); + + int next(); + +private: + int snode; + SGraph& sgraph; + MGraph& mgraph; + stack wayup; + + void push_ln(int i); +}; + +inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) +{ + push_ln(n); +} + +inline int LNiterator::next() +{ + if(wayup.empty()) + { + if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,-1); + return -1; + } + else + { + int i = wayup.top(); + wayup.pop(); + if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,i); + return i; + }; +} + +inline void LNiterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + { + wayup.push(*sp); + if(debug) fprintf(stderr,"\t\tLNiterator(%d)\tPUSH %d\n",snode,-1); + } + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LHiterator +{ +public: + LHiterator(SGraph& sg, int n); + + int next(); + +private: + int snode; + SGraph& sgraph; + MGraph& mgraph; + stack wayup; + + void push_lh(int i); +}; + +inline LHiterator::LHiterator(SGraph& sg, int n) : snode(n), sgraph(sg), mgraph(sg.mgraph) +{ + push_lh(n); +} + +inline int LHiterator::next() +{ + if(wayup.empty()) + return -1; else { @@ -373,142 +514,29 @@ } -inline void LViterator::push_ld(int i) -{ - vector& arcs = sgraph[i].deps; - for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) - if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) - push(waydown,a->dst); -} - -inline void LViterator::push_lh(int i) +inline void LHiterator::push_lh(int i) { vector& arcs = sgraph[i].heads; for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) - push(wayup,a->dst); -} - -inline void LViterator::push_ln(int i) -{ - vector& mpredecessors = mgraph[sgraph[i].mnode].pred; - for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph - { - vector& spredecessors = mgraph[*mp].snodes; - for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) - if(sgraph[*sp].visible_as_neighbour || !strict) - push(wayup,*sp); - } -} - - -//---------------------------------------------------------------------------------------------------- -//---------------------------------------------------------------------------------------------------- - -class LNiterator + { + wayup.push(a->dst); + if(debug) fprintf(stderr,"\t\tLHiterator(%d)\tPUSH %d\n",snode,-1); + } +} + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LDiterator { public: - LNiterator(SGraph& sg, int n); + LDiterator(SGraph& sg, int n); int next(); private: - + int snode; SGraph& sgraph; MGraph& mgraph; - int thenode; - stack wayup; - - void push_ln(int i); -}; - -inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) -{ - push_ln(n); -} - -inline int LNiterator::next() -{ - if(wayup.empty()) - return -1; - else - { - int i = wayup.top(); - wayup.pop(); - return i; - }; -} - -inline void LNiterator::push_ln(int i) -{ - vector& mpredecessors = mgraph[sgraph[i].mnode].pred; - for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph - { - vector& spredecessors = mgraph[*mp].snodes; - for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) - wayup.push(*sp); - } -} - - -//---------------------------------------------------------------------------------------------------- -//---------------------------------------------------------------------------------------------------- - -class LHiterator -{ -public: - LHiterator(SGraph& sg, int n); - - int next(); - -private: - - SGraph& sgraph; - MGraph& mgraph; - stack wayup; - - void push_lh(int i); -}; - -inline LHiterator::LHiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph) -{ - push_lh(n); -} - -inline int LHiterator::next() -{ - if(wayup.empty()) - return -1; - else - { - int i = wayup.top(); - wayup.pop(); - push_lh(i); - return i; - }; -} - -inline void LHiterator::push_lh(int i) -{ - vector& arcs = sgraph[i].heads; - for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) - if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) - wayup.push(a->dst); -} - -//---------------------------------------------------------------------------------------------------- -//---------------------------------------------------------------------------------------------------- - -class LDiterator -{ -public: - LDiterator(SGraph& sg, int n); - - int next(); - -private: - - SGraph& sgraph; - MGraph& mgraph; - int thenode; stack waydown; @@ -516,5 +544,5 @@ }; -inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) +inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) { push_ld(n); @@ -538,9 +566,10 @@ vector& arcs = sgraph[i].deps; for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) - if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[thenode].mnode].pos) - waydown.push(a->dst); -} - - + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[snode].mnode].pos) + { + waydown.push(a->dst); + if(debug) fprintf(stderr,"\t\tLDiterator(%d)\tPUSH %d\n",snode,-1); + } +} #endif