Changeset acbabee for src/dgp/sgraph.hh


Ignore:
Timestamp:
12/17/14 12:13:11 (9 years ago)
Author:
Tomasz Obrebski <obrebski@…>
Branches:
master
Children:
854bece
Parents:
d484a32
git-author:
Tomasz Obrebski <obrebski@…> (12/17/14 12:10:45)
git-committer:
Tomasz Obrebski <obrebski@…> (12/17/14 12:13:11)
Message:

many changes, mainly dgp1 algorithm

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/dgp/sgraph.hh

    rd484a32 racbabee  
    1313#include "thesymbols.hh" 
    1414#include "boubble.hh" 
    15  
     15#include "global.hh" 
    1616 
    1717using namespace std; 
    … …  
    116116} 
    117117 
    118 //---------------------------------------------------------------------------------------------------- 
    119  
    120 inline 
    121 NodeProp::~NodeProp() 
    122 { 
    123   clear_boubbles(); 
    124 } 
    125 //---------------------------------------------------------------------------------------------------- 
    126  
    127 inline 
    128 NodeProp::NodeProp() 
    129 { 
    130   clear(); 
    131 } 
    132  
    133 //---------------------------------------------------------------------------------------------------- 
    134  
    135 inline 
    136 NodeProp::NodeProp(const NodeProp& p) 
    137 { 
    138   copy(p); 
    139 } 
    140  
    141 //---------------------------------------------------------------------------------------------------- 
    142  
    143 inline 
    144 NodeProp& NodeProp::operator=(const NodeProp& p) 
    145 { 
    146   clear(); 
    147   copy(p); 
    148   return *this; 
    149 } 
    150  
    151 //---------------------------------------------------------------------------------------------------- 
    152  
    153 inline 
    154 void NodeProp::clear() 
     118inline NodeProp::~NodeProp() { clear_boubbles(); } 
     119inline NodeProp::NodeProp() { clear(); } 
     120inline NodeProp::NodeProp(const NodeProp& p) { copy(p); } 
     121inline NodeProp& NodeProp::operator=(const NodeProp& p) { clear(); copy(p); return *this; } 
     122inline void NodeProp::clear() 
    155123{ 
    156124  required.reset(); 
    … …  
    163131 
    164132//==================================================================================================== 
     133// CLASS Edge 
     134//==================================================================================================== 
     135 
     136class Edge 
     137{ 
     138public: 
     139  Edge() : _self(false) { } 
     140  Edge(const Edge& e, int map_self) { assign(e,map_self); } 
     141 
     142  bool self() const { return _self; } 
     143  list<int>& others() { return _others; } 
     144 
     145  void insert_self(bool b=true) { _self=b; } 
     146  void insert(int n) { list<int>::iterator i=others().begin(); while(i!=others().end() && *i<n) ++i; others().insert(i,n);} 
     147  void insert(list<int> l) { for(list<int>::const_iterator i=l.begin(); i!=l.end(); i++) insert(*i); } 
     148 
     149  void assign(const Edge& e, int map_self=-1) { _others = e._others; if(e.self()) { _self = false; insert(map_self); } } 
     150  const bool operator==(const Edge& e) const { return _self == e._self && _others == e._others; } 
     151   
     152private: 
     153  bool _self; 
     154  list<int> _others; 
     155}; 
     156 
     157//==================================================================================================== 
    165158// CLASS SNode 
    166159//==================================================================================================== 
    … …  
    175168  NodeProp prop; 
    176169 
    177   vector<int> edge; 
    178   bool        edge_contains_self; 
     170  Edge edge; 
    179171  bool visible_as_neighbour; 
    180172 
    … …  
    189181  void clear(); 
    190182  bool saturated(); 
     183 
     184  // void edge_clear()               { edge.clear(); edge_contains_self=false;} 
     185  // void edge_set(int i)            { edge.clear(); edge_contains_self=false; edge.push_back(i); } 
     186  // void edge_set(vector<int>& v)   { edge.assign(v.begin(),v.end()); edge_contains_self=false; } 
     187  // void edge_set_self(bool b=true) { edge.clear(); edge_contains_self=b; } 
     188  // void edge_add(int i)            { edge.push_back(i); } 
     189  // void edge_add(vector<int>& v)   { edge.insert(edge.end(),v.begin(),v.end()); } 
     190  // void edge_add_self(bool b=true) { edge_contains_self=b; } 
    191191}; 
    192192 
    … …  
    216216  void clear()                                  { nodes.clear(); } 
    217217  int  add_base_snode(int mnodeind); 
    218   int  clone(int ancind, NodeProp newprop); 
     218  int  clone(int ancind, NodeProp newprop, Edge edge); 
    219219  void update_left(int headind, int depind); 
    220220  void update_right(int headind, int depind); 
    … …  
    299299 
    300300private: 
    301  
     301  int snode; 
    302302  SGraph& sgraph; 
    303303  MGraph& mgraph; 
    … …  
    312312}; 
    313313 
    314 inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : sgraph(sg), mgraph(sg.mgraph), strict(s) 
    315 { 
    316   if(sg[n].edge_contains_self) // TO DODAÆ PO PRZEJŠCIU NA EDGE_CONTAINS_SELF 
     314inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : snode(n), sgraph(sg), mgraph(sg.mgraph), strict(s) 
     315{ 
     316  if(sg[n].edge.self()) 
    317317    { 
    318318      push_ld(n); 
    … …  
    320320    } 
    321321 
    322   for(vector<int>::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) 
    323     { 
    324       if(*i != n) 
    325         { 
    326           push_ld(*i); 
    327           push_ln(*i); 
    328         } 
    329        
    330     } 
    331 } 
    332  
    333 inline void LViterator::update_edge(SGraph& sg, int n) 
    334 { 
    335   for(vector<int>::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) 
     322  for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) 
    336323    { 
    337324      push_ld(*i); 
    338325      push_ln(*i); 
     326       
     327    } 
     328} 
     329 
     330inline void LViterator::update_edge(SGraph& sg, int n) 
     331{ 
     332  if(sg[n].edge.self())  
     333    { 
     334      push_ld(n); 
     335      push_ln(n); 
     336    } 
     337 
     338  for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) 
     339    { 
     340      push_ld(*i); 
     341      push_ln(*i); 
    339342    } 
    340343} 
    … …  
    345348    { 
    346349      if(waydown.empty()) 
    347         return -1; //  
     350        { 
     351          if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); 
     352          return -1; //  
     353        } 
    348354      else 
    349355        { 
    … …  
    353359          push_ln(k); 
    354360          if(wayup.empty()) 
    355             return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW 
     361            { 
     362              if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); 
     363              return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW 
     364            } 
    356365          else 
    357366            { 
    … …  
    359368              wayup.pop(); 
    360369              push_lh(i); 
     370              if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); 
    361371              return i; 
    362372            } 
    … …  
    364374       
    365375    } 
     376  else 
     377    { 
     378      int i = wayup.top(); 
     379      wayup.pop(); 
     380      push_lh(i); 
     381      if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); 
     382      return i; 
     383    }; 
     384} 
     385 
     386inline void LViterator::push_ld(int i) 
     387{ 
     388  vector<Arc>& arcs = sgraph[i].deps; 
     389  for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
     390    if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) 
     391      { 
     392        push(waydown,a->dst); 
     393        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LD waydown %d\n",snode,a->dst); 
     394      } 
     395} 
     396 
     397inline void LViterator::push_lh(int i) 
     398{ 
     399  vector<Arc>& arcs = sgraph[i].heads; 
     400  for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
     401    if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) 
     402      { 
     403        push(wayup,a->dst); 
     404        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LH wayup %d\n",snode,a->dst); 
     405      } 
     406} 
     407 
     408inline void LViterator::push_ln(int i) 
     409{ 
     410  vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; 
     411  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph 
     412    { 
     413      vector<int>& spredecessors = mgraph[*mp].snodes; 
     414      for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) 
     415        if(sgraph[*sp].visible_as_neighbour || !strict) 
     416          { 
     417            push(wayup,*sp); 
     418            if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LN wayup %d\n",snode, *sp); 
     419          } 
     420    } 
     421} 
     422 
     423 
     424//---------------------------------------------------------------------------------------------------- 
     425//---------------------------------------------------------------------------------------------------- 
     426 
     427class LNiterator 
     428{ 
     429public: 
     430  LNiterator(SGraph& sg, int n); 
     431 
     432  int next(); 
     433 
     434private: 
     435  int snode; 
     436  SGraph& sgraph; 
     437  MGraph& mgraph; 
     438  stack<int> wayup; 
     439 
     440  void push_ln(int i); 
     441}; 
     442 
     443inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) 
     444{ 
     445  push_ln(n); 
     446} 
     447 
     448inline int LNiterator::next() 
     449{ 
     450  if(wayup.empty()) 
     451    { 
     452      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,-1); 
     453      return -1; 
     454    } 
     455  else 
     456    { 
     457      int i = wayup.top(); 
     458      wayup.pop(); 
     459      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,i); 
     460      return i; 
     461    }; 
     462} 
     463 
     464inline void LNiterator::push_ln(int i) 
     465{ 
     466  vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; 
     467  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph 
     468    { 
     469      vector<int>& spredecessors = mgraph[*mp].snodes; 
     470      for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) 
     471        { 
     472          wayup.push(*sp); 
     473          if(debug) fprintf(stderr,"\t\tLNiterator(%d)\tPUSH %d\n",snode,-1); 
     474        } 
     475    } 
     476} 
     477 
     478 
     479//---------------------------------------------------------------------------------------------------- 
     480//---------------------------------------------------------------------------------------------------- 
     481 
     482class LHiterator 
     483{ 
     484public: 
     485  LHiterator(SGraph& sg, int n); 
     486 
     487  int next(); 
     488 
     489private: 
     490  int snode; 
     491  SGraph& sgraph; 
     492  MGraph& mgraph; 
     493  stack<int> wayup; 
     494 
     495  void push_lh(int i); 
     496}; 
     497 
     498inline LHiterator::LHiterator(SGraph& sg, int n) : snode(n), sgraph(sg), mgraph(sg.mgraph) 
     499{ 
     500  push_lh(n); 
     501} 
     502 
     503inline int LHiterator::next() 
     504{ 
     505  if(wayup.empty()) 
     506        return -1;  
    366507  else 
    367508    { 
    … …  
    373514} 
    374515 
    375 inline void LViterator::push_ld(int i) 
    376 { 
    377   vector<Arc>& arcs = sgraph[i].deps; 
    378   for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
    379     if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) 
    380       push(waydown,a->dst); 
    381 } 
    382  
    383 inline void LViterator::push_lh(int i) 
     516inline void LHiterator::push_lh(int i) 
    384517{ 
    385518  vector<Arc>& arcs = sgraph[i].heads; 
    386519  for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
    387520    if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) 
    388       push(wayup,a->dst); 
    389 } 
    390  
    391 inline void LViterator::push_ln(int i) 
    392 { 
    393   vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; 
    394   for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph 
    395     { 
    396       vector<int>& spredecessors = mgraph[*mp].snodes; 
    397       for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) 
    398         if(sgraph[*sp].visible_as_neighbour || !strict) 
    399           push(wayup,*sp); 
    400     } 
    401 } 
    402  
    403  
    404 //---------------------------------------------------------------------------------------------------- 
    405 //---------------------------------------------------------------------------------------------------- 
    406  
    407 class LNiterator 
     521      { 
     522        wayup.push(a->dst); 
     523        if(debug) fprintf(stderr,"\t\tLHiterator(%d)\tPUSH %d\n",snode,-1); 
     524      } 
     525} 
     526 
     527//---------------------------------------------------------------------------------------------------- 
     528//---------------------------------------------------------------------------------------------------- 
     529 
     530class LDiterator 
    408531{ 
    409532public: 
    410   LNiterator(SGraph& sg, int n); 
     533  LDiterator(SGraph& sg, int n); 
    411534 
    412535  int next(); 
    413536 
    414537private: 
    415  
     538  int snode; 
    416539  SGraph& sgraph; 
    417540  MGraph& mgraph; 
    418   int thenode; 
    419   stack<int> wayup; 
    420  
    421   void push_ln(int i); 
    422 }; 
    423  
    424 inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) 
    425 { 
    426   push_ln(n); 
    427 } 
    428  
    429 inline int LNiterator::next() 
    430 { 
    431   if(wayup.empty()) 
    432     return -1; 
    433   else 
    434     { 
    435       int i = wayup.top(); 
    436       wayup.pop(); 
    437       return i; 
    438     }; 
    439 } 
    440  
    441 inline void LNiterator::push_ln(int i) 
    442 { 
    443   vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; 
    444   for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph 
    445     { 
    446       vector<int>& spredecessors = mgraph[*mp].snodes; 
    447       for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) 
    448           wayup.push(*sp); 
    449     } 
    450 } 
    451  
    452  
    453 //---------------------------------------------------------------------------------------------------- 
    454 //---------------------------------------------------------------------------------------------------- 
    455  
    456 class LHiterator 
    457 { 
    458 public: 
    459   LHiterator(SGraph& sg, int n); 
    460  
    461   int next(); 
    462  
    463 private: 
    464  
    465   SGraph& sgraph; 
    466   MGraph& mgraph; 
    467   stack<int> wayup; 
    468  
    469   void push_lh(int i); 
    470 }; 
    471  
    472 inline LHiterator::LHiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph) 
    473 { 
    474   push_lh(n); 
    475 } 
    476  
    477 inline int LHiterator::next() 
    478 { 
    479   if(wayup.empty()) 
    480         return -1;  
    481   else 
    482     { 
    483       int i = wayup.top(); 
    484       wayup.pop(); 
    485       push_lh(i); 
    486       return i; 
    487     }; 
    488 } 
    489  
    490 inline void LHiterator::push_lh(int i) 
    491 { 
    492   vector<Arc>& arcs = sgraph[i].heads; 
    493   for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
    494     if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) 
    495       wayup.push(a->dst); 
    496 } 
    497  
    498 //---------------------------------------------------------------------------------------------------- 
    499 //---------------------------------------------------------------------------------------------------- 
    500  
    501 class LDiterator 
    502 { 
    503 public: 
    504   LDiterator(SGraph& sg, int n); 
    505  
    506   int next(); 
    507  
    508 private: 
    509  
    510   SGraph& sgraph; 
    511   MGraph& mgraph; 
    512   int thenode; 
    513541  stack<int> waydown; 
    514542 
    … …  
    516544}; 
    517545 
    518 inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) 
     546inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) 
    519547{ 
    520548  push_ld(n); 
    … …  
    538566  vector<Arc>& arcs = sgraph[i].deps; 
    539567  for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) 
    540     if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[thenode].mnode].pos) 
    541       waydown.push(a->dst); 
    542 } 
    543  
    544  
     568    if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[snode].mnode].pos) 
     569      { 
     570        waydown.push(a->dst); 
     571        if(debug) fprintf(stderr,"\t\tLDiterator(%d)\tPUSH %d\n",snode,-1); 
     572      } 
     573} 
    545574 
    546575#endif 
Note: See TracChangeset for help on using the changeset viewer.