Changeset 3b02b04 for src/dgp/sgraph.hh

Timestamp:

01/17/13 20:50:41 (11 years ago)

Author:

Tomasz Obrebski <to@…>

Branches:

master

Children:

d2f119e

Parents:

555c7f8

git-author:

Tomasz Obrebski <to@…> (01/17/13 20:50:41)

git-committer:

Tomasz Obrebski <to@…> (01/17/13 20:50:41)

Message:

prawie ca�kiem nowe dgc, du�e zmiany w dgp, pomniejsze poprawki

File:

• src/dgp/sgraph.hh (modified) (5 diffs)

src/dgp/sgraph.hh

@@ -7 +7 @@
 #include <vector>
 #include <bitset>
+#include <stack>
 
 #include "const.hh"
@@ -71 +72 @@
   if(init_attached != p.init_attached) return false;
   if(fin_attached != p.fin_attached) return false;
-  
-  list<Boubble*>::const_iterator b1 = p.boubbles.begin();
-  for(list<Boubble*>::const_iterator b = boubbles.begin(); b != boubbles.end(); b++)
-    {
-      if(b1 == p.boubbles.end())
-        return false;
-      if(!(**b == **b1))
-        return false;
-    }
-  if(b1 != p.boubbles.end())
+
+  list<Boubble*>::const_iterator b,b1;
+  for(b=boubbles.begin(), b1=p.boubbles.begin(); b != boubbles.end() && b1 != p.boubbles.end(); b++,b1++)
+    if(!(**b == **b1))
+      return false;
+  if(b != boubbles.end() || b1 != p.boubbles.end())
     return false;
-  
+
   return true;
 }
@@ -172 +169 @@
 {
   
+  SNode() { visible_as_neighbour = true; }
+
   int mnode;
 
   NodeProp prop;
+
+  vector<int> edge;
+  bool        edge_contains_self;
+  bool visible_as_neighbour;
 
   bitset<MAXNODES> LV;
@@ -231 +234 @@
   int size()              {return nodes.size(); }
 
+  friend class LViterator;
+  friend class LHiterator;
+  friend class LDiterator;
+  friend class LNiterator;
+
 private:
 
@@ -259 +267 @@
 
 //----------------------------------------------------------------------------------------------------
+//----------------------------------------------------------------------------------------------------
+
+class XXiterator
+{
+protected:
+
+  bool checked(int i) { return _checked[i]; }
+  void check(int i)   { _checked.set(i); }
+
+  void push(stack<int>& s, int i)
+  {
+    if(!checked(i))
+      {
+        s.push(i);
+        check(i);
+      }
+  }
+
+  bitset<MAXNODES> _checked;
+};
+
+//----------------------------------------------------------------------------------------------------
+//----------------------------------------------------------------------------------------------------
+
+class LViterator : public XXiterator
+{
+public:
+  LViterator(SGraph& sg, int n, bool s);
+  int next();
+
+private:
+
+  SGraph& sgraph;
+  MGraph& mgraph;
+  stack<int> waydown;
+  stack<int> wayup;
+  bool strict;
+
+  void push_ld(int i);
+  void push_lh(int i);
+  void push_ln(int i);
+};
+
+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
+    {
+      push_ld(n);
+      push_ln(n);
+    }
+
+  for(vector<int>::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i)
+    {
+      if(*i != n)
+        {
+          push_ld(*i);
+          push_ln(*i);
+        }
+      
+    }
+  // if(!strict)
+  //   {
+  //     push_ld(n);
+  //              push_ln(n);
+  //   }
+}
+
+inline int LViterator::next()
+{
+  if(wayup.empty())
+    {
+      if(waydown.empty())
+        return -1; // 
+      else
+        {
+          int k = waydown.top();
+          waydown.pop();
+          push_ld(k);
+          push_ln(k);
+          if(wayup.empty())
+            return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW
+          else
+            {
+              int i = wayup.top();
+              wayup.pop();
+              push_lh(i);
+              return i;
+            }
+        }
+      
+    }
+  else
+    {
+      int i = wayup.top();
+      wayup.pop();
+      push_lh(i);
+      return i;
+    };
+}
+
+inline void LViterator::push_ld(int i)
+{
+  vector<Arc>& arcs = sgraph[i].deps;
+  for(vector<Arc>::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)
+{
+  vector<Arc>& arcs = sgraph[i].heads;
+  for(vector<Arc>::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<int>& mpredecessors = mgraph[sgraph[i].mnode].pred;
+  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph
+    {
+      vector<int>& spredecessors = mgraph[*mp].snodes;
+      for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp )
+        if(sgraph[*sp].visible_as_neighbour || !strict)
+          push(wayup,*sp);
+    }
+}
+
+
+//----------------------------------------------------------------------------------------------------
+//----------------------------------------------------------------------------------------------------
+
+class LNiterator
+{
+public:
+  LNiterator(SGraph& sg, int n);
+
+  int next();
+
+private:
+
+  SGraph& sgraph;
+  MGraph& mgraph;
+  int thenode;
+  stack<int> 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<int>& mpredecessors = mgraph[sgraph[i].mnode].pred;
+  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph
+    {
+      vector<int>& spredecessors = mgraph[*mp].snodes;
+      for(vector<int>::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<int> 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<Arc>& arcs = sgraph[i].heads;
+  for(vector<Arc>::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<int> waydown;
+
+  void push_ld(int i);
+};
+
+inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n)
+{
+  push_ld(n);
+}
+
+inline int LDiterator::next()
+{
+  if(waydown.empty())
+    return -1;
+  else
+    {
+      int k = waydown.top();
+      waydown.pop();
+      push_ld(k);
+      return k;
+    }
+}
+
+inline void LDiterator::push_ld(int i)
+{
+  vector<Arc>& arcs = sgraph[i].deps;
+  for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a)
+    if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[thenode].mnode].pos)
+      waydown.push(a->dst);
+}
+
+
 
 #endif