# HG changeset patch
# User marci
# Date 1095855950 0
# Node ID 309d81806228088bfb8f07fcd58c2c101c723e7a
# Parent  69a8e672acb1ef88010a00bc67059cc4b7369d9e
correction to 0.2

diff -r 69a8e672acb1 -r 309d81806228 src/work/marci/bipartite_graph_wrapper.h
--- a/src/work/marci/bipartite_graph_wrapper.h	Wed Sep 22 10:47:59 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper.h	Wed Sep 22 12:25:50 2004 +0000
@@ -71,19 +71,24 @@
     friend class OutEdgeIt;
     class InEdgeIt;
     friend class InEdgeIt;
-    class ClassNodeIt {
+    class ClassNodeIt : public Node {
       friend class BipartiteGraphWrapper<Graph>;
     protected:
-      Node n;
+      const BipartiteGraphWrapper<Graph>* gw;
     public:
       ClassNodeIt() { }
-      ClassNodeIt(const Invalid& i) : n(i) { }
-      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
-	_G.s_false_t_true_map->first(n, _class); 
+      ClassNodeIt(Invalid i) : Node(i) { }
+      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) : 
+	Node(), gw(&_gw) { 
+	_gw.s_false_t_true_map->first(*this, _class); 
       }
       //FIXME needed in new concept, important here
-      ClassNodeIt(const Node& _n) : n(_n) { }
-      operator Node() const { return n; }
+      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) : 
+	Node(n), gw(&_gw) { }
+      ClassNodeIt& operator++() { 
+	gw->s_false_t_true_map->next(*this);
+	return *this; 
+      }
     };
 //     class SNodeIt {
 //       Node n;
@@ -105,87 +110,88 @@
 //       }
 //       operator Node() const { return n; }
 //     };
-    class OutEdgeIt { 
-      friend class BipartiteGraphWrapper<Graph>;
-    protected:
-      typename Graph::OutEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
-	if (!(*(_G.s_false_t_true_map))[_n]) 
-	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
-	else 
-	  e=INVALID;
-      }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
-      friend class BipartiteGraphWrapper<Graph>;
-    protected:
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
-	if ((*(_G.s_false_t_true_map))[_n]) 
-	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
-	else 
-	  e=INVALID;
-      }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
+//     class OutEdgeIt { 
+//       friend class BipartiteGraphWrapper<Graph>;
+//     protected:
+//       typename Graph::OutEdgeIt e;
+//     public:
+//       OutEdgeIt() { }
+//       OutEdgeIt(const Invalid& i) : e(i) { }
+//       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+// 	if (!(*(_G.s_false_t_true_map))[_n]) 
+// 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
+// 	else 
+// 	  e=INVALID;
+//       }
+//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
+//     };
+//     class InEdgeIt { 
+//       friend class BipartiteGraphWrapper<Graph>;
+//     protected:
+//       typename Graph::InEdgeIt e;
+//     public:
+//       InEdgeIt() { }
+//       InEdgeIt(const Invalid& i) : e(i) { }
+//       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+// 	if ((*(_G.s_false_t_true_map))[_n]) 
+// 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
+// 	else 
+// 	  e=INVALID;
+//       }
+//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
+//     };
 
     using GraphWrapper<Graph>::first;
     ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
-      n=ClassNodeIt(*this, _class) ; return n; }
+      n=ClassNodeIt(*this, _class); return n;
+    }
 //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
 //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
-    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
-      i=OutEdgeIt(*this, p); return i;
-    }
-    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
-      i=InEdgeIt(*this, p); return i;
-    }
+//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
+//       i=OutEdgeIt(*this, p); return i;
+//     }
+//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
+//       i=InEdgeIt(*this, p); return i;
+//     }
 
-    using GraphWrapper<Graph>::next;
-    ClassNodeIt& next(ClassNodeIt& n) const { 
-      this->s_false_t_true_map->next(n.n); return n; 
-    }
+//     using GraphWrapper<Graph>::next;
+//     ClassNodeIt& next(ClassNodeIt& n) const { 
+//       this->s_false_t_true_map->next(n.n); return n; 
+//     }
 //     SNodeIt& next(SNodeIt& n) const { 
 //       this->s_false_t_true_map->next(n); return n; 
 //     }
 //     TNodeIt& next(TNodeIt& n) const { 
 //       this->s_false_t_true_map->next(n); return n; 
 //     }
-    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
+//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
+//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
 
-    Node tail(const Edge& e) { 
-      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
-	return Node(this->graph->tail(e));
-      else
-	return Node(this->graph->head(e));	
-    }
-    Node head(const Edge& e) { 
-      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
-	return Node(this->graph->head(e));
-      else
-	return Node(this->graph->tail(e));	
-    }
+//     Node tail(const Edge& e) { 
+//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+// 	return Node(this->graph->tail(e));
+//       else
+// 	return Node(this->graph->head(e));	
+//     }
+//     Node head(const Edge& e) { 
+//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+// 	return Node(this->graph->head(e));
+//       else
+// 	return Node(this->graph->tail(e));	
+//     }
 
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); 
-    }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); 
-    }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); 
-    }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); 
-    }
+//     Node aNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); 
+//     }
+//     Node aNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); 
+//     }
+//     Node bNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); 
+//     }
+//     Node bNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); 
+//     }
 
     /// Returns true iff \c n is in S.
     bool inSClass(const Node& n) const {
diff -r 69a8e672acb1 -r 309d81806228 src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc	Wed Sep 22 10:47:59 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Wed Sep 22 12:25:50 2004 +0000
@@ -3,22 +3,26 @@
 #include <fstream>
 #include <vector>
 
-#include <sage_graph.h>
-//#include <smart_graph.h>
+//#include <sage_graph.h>
+#include <hugo/smart_graph.h>
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
-#include <for_each_macros.h>
+//#include <for_each_macros.h>
 #include <bfs_dfs.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
-#include <hugo/max_flow.h>
+#include <hugo/preflow.h>
 #include <augmenting_flow.h>
 
+using std::cout;
+using std::endl;
+
 using namespace hugo;
 
 int main() {
-  typedef UndirSageGraph Graph; 
+  //typedef UndirSageGraph Graph; 
+  typedef SmartGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;
   typedef Graph::Edge Edge;
@@ -52,93 +56,92 @@
   for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
 
   Graph::Node u;
-  std::cout << "These nodes will be in S:\n";
+  cout << "These nodes will be in S:" << endl;
   //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 
   //irni 1etlen FOR_EACH-csel.
-  for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 
-    std::cout << u << " ";
-  std::cout << "\n";
-  std::cout << "These nodes will be in T:\n";
-  for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 
-    std::cout << u << " ";
-  std::cout << "\n";
+  for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u)) 
+    cout << g.id(u) << " ";
+  cout << endl;
+  cout << "These nodes will be in T:" << endl;
+  for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u)) 
+    cout << g.id(u) << " ";
+  cout << endl;
 
   typedef BipartiteGraphWrapper<Graph> BGW;
   BGW bgw(g, bipartite_map);
 
-  std::cout << "Nodes by NodeIt:\n";
-  FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
-    std::cout << n << " ";
-  }
-  std::cout << "\n";
-  std::cout << "Nodes in S by ClassNodeIt:\n";
-  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
-    std::cout << n << " ";
-  }
-  std::cout << "\n";
-  std::cout << "Nodes in T by ClassNodeIt:\n";
-  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
-    std::cout << n << " ";
-  }
-  std::cout << "\n";
-  std::cout << "Edges of the bipartite graph:\n";
-  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
-    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
-  }
+  cout << "Nodes by NodeIt:" << endl;
+  for (BGW::NodeIt n(bgw); n!=INVALID; ++n)
+    cout << g.id(n) << " ";
+  cout << endl;
+
+  cout << "Nodes in S by ClassNodeIt:" << endl;
+  for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n)
+    cout << g.id(n) << " ";
+  cout << endl;
+
+  cout << "Nodes in T by ClassNodeIt:" << endl;
+  for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n)
+    cout << g.id(n) << " ";
+  cout << endl;
+
+  cout << "Edges of the bipartite graph:" << endl;
+  for (BGW::EdgeIt e(bgw); e!=INVALID; ++e)
+    cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl;
 
   BGW::NodeMap<int> dbyj(bgw);
   BGW::EdgeMap<int> dbyxcj(bgw);
 
-  typedef stBipartiteGraphWrapper<BGW> stGW;
-  stGW stgw(bgw);
-  ConstMap<stGW::Edge, int> const1map(1);
-  stGW::NodeMap<int> ize(stgw);
-  stGW::EdgeMap<int> flow(stgw);
+//   typedef stBipartiteGraphWrapper<BGW> stGW;
+//   stGW stgw(bgw);
+//   ConstMap<stGW::Edge, int> const1map(1);
+//   stGW::NodeMap<int> ize(stgw);
+//   stGW::EdgeMap<int> flow(stgw);
 
-  BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
-  Graph::NodeIt si;
-  Graph::Node s; 
-  s=g.first(si);
-  bfs.pushAndSetReached(BGW::Node(s));
-  while (!bfs.finished()) { ++bfs; }
+//   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
+//   Graph::NodeIt si;
+//   Graph::Node s; 
+//   s=g.first(si);
+//   bfs.pushAndSetReached(BGW::Node(s));
+//   while (!bfs.finished()) { ++bfs; }
 
-  FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
-    std::cout << "out-edges of " << n << ":\n"; 
-    FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 
-      std::cout << " " << e << "\n";
-      std::cout << " aNode: " << stgw.aNode(e) << "\n";
-      std::cout << " bNode: " << stgw.bNode(e) << "\n";      
-    }
-    std::cout << "in-edges of " << n << ":\n"; 
-    FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 
-      std::cout << " " << e << "\n";
-      std::cout << " aNode: " << stgw.aNode(e) << "\n";
-      std::cout << " bNode: " << stgw.bNode(e) << "\n";     
-    }
-  }
-  std::cout << "Edges of the stGraphWrapper:\n"; 
-  FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 
-    std::cout << " " << n << "\n";
-  }
+//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
+//     cout << "out-edges of " << n << ":" << endl; 
+//     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 
+//       cout << " " << e << endl;
+//       cout << " aNode: " << stgw.aNode(e) << endl;
+//       cout << " bNode: " << stgw.bNode(e) << endl;      
+//     }
+//     cout << "in-edges of " << n << ":" << endl; 
+//     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 
+//       cout << " " << e << endl;
+//       cout << " aNode: " << stgw.aNode(e) << endl;
+//       cout << " bNode: " << stgw.bNode(e) << endl;     
+//     }
+//   }
+//   cout << "Edges of the stGraphWrapper:" << endl; 
+//   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 
+//     cout << " " << n << endl;
+//   }
 
-  stGW::NodeMap<bool> b(stgw);
-  FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
-    std::cout << n << ": " << b[n] <<"\n";
-  }
+//   stGW::NodeMap<bool> b(stgw);
+//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
+//     cout << n << ": " << b[n] << endl;
+//   }
 
-  std::cout << "Bfs from s: \n";
-  BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
-  bfs_stgw.pushAndSetReached(stgw.S_NODE);
-  while (!bfs_stgw.finished()) { 
-    std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
-    ++bfs_stgw; 
-  }
+//   cout << "Bfs from s:" << endl;
+//   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
+//   bfs_stgw.pushAndSetReached(stgw.S_NODE);
+//   while (!bfs_stgw.finished()) { 
+//     cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl;
+//     ++bfs_stgw; 
+//   }
   
-  AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
-    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
-  while (max_flow_test.augmentOnShortestPath()) { }
+//   AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
+//     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
+//   while (max_flow_test.augmentOnShortestPath()) { }
 
-  std::cout << max_flow_test.flowValue() << std::endl;
+//   cout << max_flow_test.flowValue() << std::endl;
 
   return 0;
 }