# HG changeset patch
# User marci
# Date 1082706108 0
# Node ID a5bff2813c4daa8718fa1b423609eb2a58dea9f3
# Parent  c3f93631cd24be9e4b2138820b282a4a4f1548ef
.

diff -r c3f93631cd24 -r a5bff2813c4d src/work/marci/bipartite_graph_wrapper_test.cc
--- a/src/work/marci/bipartite_graph_wrapper_test.cc	Thu Apr 22 20:36:21 2004 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Fri Apr 23 07:41:48 2004 +0000
@@ -10,6 +10,8 @@
 #include <for_each_macros.h>
 #include <bfs_iterator.h>
 #include <graph_wrapper.h>
+#include <maps.h>
+#include <edmonds_karp.h>
 
 using namespace hugo;
 
@@ -41,44 +43,35 @@
   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
   }
-//   Graph::NodeMap<OutEdgeIt> pred(G);
-//   Timer ts;
-//   {
-//     ts.reset();
-//     Graph::NodeMap<bool> reached(G);
-//     reached.set(s, true);
-//     pred.set(s, INVALID);
-//     std::queue<Node> bfs_queue;
-//     bfs_queue.push(t);
-//     while (!bfs_queue.empty()) {
-//       Node v=bfs_queue.front();	
-//       bfs_queue.pop();
-//       OutEdgeIt e;
-//       for(G.first(e,v); G.valid(e); G.next(e)) {
-// 	Node w=G.head(e);
-// 	if (!reached[w]) {
-// 	  bfs_queue.push(w);
-// 	  reached.set(w, true);
-// 	  pred.set(w, e);
-// 	}
-//       }
-//     }
 
-//     std::cout << ts << std::endl;
-//   }
+  BGW::NodeMap<int> dbyj(bgw);
+  BGW::EdgeMap<int> dbyxcj(bgw);
 
-//   {
-//     ts.reset();      
-//     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
-//     bfs.pushAndSetReached(s);
-//     pred.set(s, INVALID);
-//     while (!bfs.finished()) { 
-//       ++bfs; 
-//       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
-// 	pred.set(bfs.bNode(), bfs);
-//     }
-//     std::cout << ts << std::endl;
-//   }
+  typedef stGraphWrapper<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;
+
+  BGW::EdgeMap<bool> cap(bgw);
+  BGW::EdgeMap<bool> flow1(bgw);
+
+  typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 
+    RBGW;
+  RBGW rbgw(bgw, cap, flow1);
+  RBGW::NodeMap<int> u(rbgw);
+  
+
+  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
+    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
+  max_flow_test.augmentOnShortestPath();
 
   return 0;
 }
diff -r c3f93631cd24 -r a5bff2813c4d src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Thu Apr 22 20:36:21 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Fri Apr 23 07:41:48 2004 +0000
@@ -156,10 +156,10 @@
     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
 
+    Node tail(const Edge& e) const { 
+      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
     Node head(const Edge& e) const { 
       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
-    Node tail(const Edge& e) const { 
-      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
 
     bool valid(const Node& n) const { 
       return graph->valid(static_cast<typename Graph::Node>(n)); }
@@ -221,10 +221,10 @@
     class OutEdgeIt { 
       friend class GraphWrapper<Graph>;
       friend class RevGraphWrapper<Graph>;
-      typename Graph::OutEdgeIt e;
+      typename Graph::InEdgeIt e;
     public:
       OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
+      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
       OutEdgeIt(const Invalid& i) : e(i) { }
       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
 	e(*(_G.graph), typename Graph::Node(_n)) { }
@@ -233,10 +233,10 @@
     class InEdgeIt { 
       friend class GraphWrapper<Graph>;
       friend class RevGraphWrapper<Graph>;
-      typename Graph::InEdgeIt e;
+      typename Graph::OutEdgeIt e;
     public:
       InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
+      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
       InEdgeIt(const Invalid& i) : e(i) { }
       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
 	e(*(_G.graph), typename Graph::Node(_n)) { }
@@ -259,6 +259,12 @@
     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
+
+    Node tail(const Edge& e) const { 
+      return GraphWrapper<Graph>::head(e); }
+    Node head(const Edge& e) const { 
+      return GraphWrapper<Graph>::tail(e); }
+
   };
 
   /// Wrapper for hiding nodes and edges from a graph.
@@ -883,6 +889,9 @@
     SFalseTTrueMap* s_false_t_true_map;
     
   public:
+    static const bool S_CLASS=false;
+    static const bool T_CLASS=true;
+    
     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
       : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
     }
@@ -890,35 +899,46 @@
     //using GraphWrapper<Graph>::NodeIt;
     typedef typename GraphWrapper<Graph>::Edge Edge;
     //using GraphWrapper<Graph>::EdgeIt;
-    class SNodeIt {
+    class ClassNodeIt {
       Node n;
     public:
-      SNodeIt() { }
-      SNodeIt(const Invalid& i) : n(i) { }
-      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
-	_G.s_false_t_true_map->first(n, false); 
+      ClassNodeIt() { }
+      ClassNodeIt(const Invalid& i) : n(i) { }
+      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
+	_G.s_false_t_true_map->first(n, _class); 
       }
       operator Node() const { return n; }
     };
-    class TNodeIt {
-      Node n;
-    public:
-      TNodeIt() { }
-      TNodeIt(const Invalid& i) : n(i) { }
-      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
-	_G.s_false_t_true_map->first(n, true); 
-      }
-      operator Node() const { return n; }
-    };
+//     class SNodeIt {
+//       Node n;
+//     public:
+//       SNodeIt() { }
+//       SNodeIt(const Invalid& i) : n(i) { }
+//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+// 	_G.s_false_t_true_map->first(n, false); 
+//       }
+//       operator Node() const { return n; }
+//     };
+//     class TNodeIt {
+//       Node n;
+//     public:
+//       TNodeIt() { }
+//       TNodeIt(const Invalid& i) : n(i) { }
+//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+// 	_G.s_false_t_true_map->first(n, true); 
+//       }
+//       operator Node() const { return n; }
+//     };
     class OutEdgeIt { 
     public:
+
       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=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
+	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
 	else 
 	  e=INVALID;
       }
@@ -932,7 +952,7 @@
       InEdgeIt(const Invalid& i) : e(i) { }
       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
 	if ((*(_G.s_false_t_true_map))[_n]) 
-	  e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
+	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
 	else 
 	  e=INVALID;
       }
@@ -940,16 +960,29 @@
     };
 
     using GraphWrapper<Graph>::first;
-    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
-    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
+    ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
+      n=SNodeIt(*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;
+    }
 
     using GraphWrapper<Graph>::next;
-    SNodeIt& next(SNodeIt& n) const { 
+    ClassNodeIt& next(ClassNodeIt& 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; 
-    }
+//     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 { graph->next(i.e); return i; }
+    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
 
     Node tail(const Edge& e) { 
       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
@@ -976,186 +1009,473 @@
     Node bNode(const InEdgeIt& e) const { 
       return Node(this->graph->bNode(e.e)); 
     }
+
+    bool inSClass(const Node& n) const {
+      return !(this->s_false_t_true_map[n]);
+    }
+    bool inTClass(const Node& n) const {
+      return (this->s_false_t_true_map[n]);
+    }
   };
 
 
+  /// experimentral, do not try it.
+  /// It eats a bipartite graph, oriented from S to T.
+  /// Such one can be made e.g. by the above wrapper.
+  template<typename Graph>
+  class stGraphWrapper : public GraphWrapper<Graph> {
+  public:
+    class Node; 
+//GN, int
+//0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 
+//es a vege a false azaz (invalid, 3)    
+    class NodeIt;
+//GNI, int
+    class Edge;
+//GE, int, GN
+//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
+//invalid: (invalid, 3, invalid)
+    class OutEdgeIt;
+//GO, int, GNI
+//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
+//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
+//t-bol (invalid, 3, invalid)
+    class InEdgeIt;
+//GI, int, GNI
+//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
+//s-be (invalid, 3, invalid)
+//t-be (invalid, 2, first), ... (invalid, 3, invalid)
+    class EdgeIt;
+//(first, 0, invalid) ...
+//(invalid, 1, vmi)
+//(invalid, 2, vmi)
+//invalid, 3, invalid)
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
 
-//   /// experimentral, do not try it.
-//   template<typename Graph>
-//   class stGraphWrapper : public GraphWrapper<Graph> {
-//   public:
-//     class Node;
-//     class NodeIt;
-//     class Edge;
-//     class OutEdgeIt;
-//     class InEdgeIt;
-//     class EdgeIt;
+//    template <typename T> friend class NodeMap;
+//    template <typename T> friend class EdgeMap;
 
-//     const Node s;
-//     const Node t;
+    const Node S_NODE;
+    const Node T_NODE;
 
-//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph), 
-// 				    s(INVALID, 1), t(INVALID, 2) { }
+    static const bool S_CLASS=false;
+    static const bool T_CLASS=true;
 
-//     class Node : public Graph::Node {
-//       friend class GraphWrapper<Graph>;
-//       friend class stGraphWrapper<Graph>;
-//     protected:
-//       int spec; //0 if real node, 1 iff s, 2 iff t
-//     public:
-//       Node() { }
-//       Node(const typename Graph::Node& _n, int _spec=0) : 
-// 	Graph::Node(_n), spec(_spec) { }
-//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
-//       //invalid: (invalid, 2);
-//     };
+    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 
+				    S_NODE(INVALID, 1), 
+				    T_NODE(INVALID, 2) { }
 
-//     class NodeIt { 
-//       friend class GraphWrapper<Graph>;
-//       friend class stGraphWrapper<Graph>;
-//       typename Graph::NodeIt n;
-//       int spec; 
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) : 
-// 	n(_n), spec(_spec) { }
-//       NodeIt(const Invalid& i) : n(i), spec(2) { }
-//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
-// 	if (!_G->valid(n)) spec=1;
-//       }
-//       operator Node() const { return Node(n, spec); }
-//     };
-// //    typedef typename Graph::Edge Edge;
-//     class Edge : public Graph::Edge {
-//       friend class GraphWrapper<Graph>;
-//       friend class stGraphWrapper<Graph>;
-//       Node tail_spec;
-//       Node head_spec;
-//     public:
-//       Edge() { }
-//       Edge(const typename Graph::Edge& _e) : 
-// 	Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) { 
-// 	//a tail-t es a head-et real node-ra csinaljuk
-//       }
-//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
-//     };
-//     class OutEdgeIt { 
-//       friend class GraphWrapper<Graph>;
-//       friend class stGraphWrapper<Graph>;
-//       typename Graph::OutEdgeIt e;
-//       Node tail_spec;
-//       Node head_spec;
-//     public:
-//       OutEdgeIt() { }
-//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : 
-// 	e(_e), tail_spec(i, 0), head_spec(i, 0) { 
-// 	//a tail-t es a head-et real node-ra csinaljuk
-//       }
-//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
-//       //invalid: (barmi, 0, 2)
-//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
-// 	switch (_n.spec) {
-// 	case 0 : 
-// 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 
-// 	  _tail.spec=0;
-// 	  _head.spec=0;
-// 	  if (!_G.graph->valid(e)) spec=1;
-// 	  break;
-// 	case 1:
-// 	  e=INVALID;
-// 	  _tail.spec=1;
-// 	  _head(_G.graph->first(typename Graph::NodeIt()));
-// 	  if _head.spec==1
-// 	  break;
-// 	};
-	
-// 	  }
-//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
-//     };
-//     class InEdgeIt { 
-//       friend class GraphWrapper<Graph>;
-//       typename Graph::InEdgeIt e;
-//     public:
-//       InEdgeIt() { }
-//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-//       InEdgeIt(const Invalid& i) : e(i) { }
-//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
-// 	e(*(_G.graph), typename Graph::Node(_n)) { }
-//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
-//     };
-//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
-//     class EdgeIt { 
-//       friend class GraphWrapper<Graph>;
-//       typename Graph::EdgeIt e;
-//     public:
-//       EdgeIt() { }
-//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-//       EdgeIt(const Invalid& i) : e(i) { }
-//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
-//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
-//     };
+    class Node : public Graph::Node {
+    protected:
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
+      int spec; 
+    public:
+      Node() { }
+      Node(const typename Graph::Node& _n, int _spec=0) : 
+	Graph::Node(_n), spec(_spec) { }
+      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
+      friend bool operator==(const Node& u, const Node& v) { 
+	return (u.spec==v.spec && 
+		static_cast<typename Graph::Node>(u)==
+		static_cast<typename Graph::Node>(v));
+      } 
+      friend bool operator!=(const Node& u, const Node& v) { 
+	return (v.spec!=u.spec || 
+		static_cast<typename Graph::Node>(u)!=
+		static_cast<typename Graph::Node>(v));
+      } 
+      int getSpec() const { return spec; }
+    };
+    class NodeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::NodeIt n;
+      int spec; 
+     public:
+      NodeIt() { }
+      NodeIt(const typename Graph::NodeIt& _n, int _spec) : 
+	n(_n), spec(_spec) { }
+      NodeIt(const Invalid& i) : n(i), spec(3) { }
+      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
+	if (!_G->valid(n)) spec=1;
+      }
+      operator Node() const { return Node(n, spec); }
+    };
+    class Edge : public Graph::Edge {
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
+      int spec;
+      typename Graph::Node n;
+    public:
+      Edge() { }
+      Edge(const typename Graph::Edge& _e, int _spec, 
+	   const typename Graph::Node& _n) : 
+	Graph::Edge(_e), spec(_spec), n(_n) { 
+      }
+      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
+      friend bool operator==(const Edge& u, const Edge& v) { 
+	return (u.spec==v.spec && 
+		static_cast<typename Graph::Edge>(u)==
+		static_cast<typename Graph::Edge>(v) && 
+		u.n==v.n);
+      } 
+      friend bool operator!=(const Edge& u, const Edge& v) { 
+	return (v.spec!=u.spec || 
+		static_cast<typename Graph::Edge>(u)!=
+		static_cast<typename Graph::Edge>(v) || 
+		u.n!=v.n);
+      } 
+      int getSpec() const { return spec; }
+    };
+    class OutEdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::OutEdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 
+		const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { 
+      }
+      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
+	switch (_n.spec) {
+	  case 0 : 
+	    if (_G.graph->inSClass) { //S, van normalis kiel 
+	      e=typename Graph::OutEdgeIt(*(_G.graph), 
+					  typename Graph::Node(_n)); 
+	      spec=0;
+	      n=INVALID;
+	      if (!_G.graph->valid(e)) spec=3;
+	    } else { //T, specko kiel van
+	      e=INVALID;
+	      spec=2;
+	      n=_n;
+	    }
+	    break;
+	  case 1:
+	    e=INVALID;
+	    spec=1;
+	    _G.graph->first(n, S_CLASS); //s->vmi;
+	    if (!_G.graph->valid(n)) spec=3; //Ha S ures
+	    break;
+	  case 2:
+	    e=INVALID;
+	    spec=3;
+	    n=INVALID;
+	    break;
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
+    class InEdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::InEdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 
+	       const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { 
+      }
+      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
+	switch (_n.spec) {
+	  case 0 : 
+	    if (_G.graph->inTClass) { //T, van normalis beel 
+	      e=typename Graph::InEdgeIt(*(_G.graph), 
+					 typename Graph::Node(_n)); 
+	      spec=0;
+	      n=INVALID;
+	      if (!_G.graph->valid(e)) spec=3;
+	    } else { //S, specko beel van
+	      e=INVALID;
+	      spec=1;
+	      n=_n;
+	    }
+	    break;
+	  case 1:
+	    e=INVALID;
+	    spec=3;
+	    n=INVALID;
+	  case 2:
+	    e=INVALID;
+	    spec=1;
+	    _G.graph->first(n, T_CLASS); //vmi->t;
+	    if (!_G.graph->valid(n)) spec=3; //Ha T ures
+	    break;
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
+    class EdgeIt { 
+      friend class GraphWrapper<Graph>;
+      friend class stGraphWrapper<Graph>;
+      typename Graph::EdgeIt e;
+      int spec;
+      typename Graph::ClassNodeIt n;
+    public:
+      EdgeIt() { }
+      EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 
+	     const typename Graph::ClassNodeIt& _n) : 
+	e(_e), spec(_spec), n(_n) { }
+      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
+      EdgeIt(const GraphWrapper<Graph>& _G) : 
+	e(*(_G.graph)), spec(0), n(INVALID) { 
+	if (!_G.graph->valid(e)) {
+	  spec=1;
+	  _G.graph->first(n, S_CLASS);
+	  if (!_G.graph->valid(n)) { //Ha S ures
+	    spec=2;
+	    _G.graph->first(n, T_CLASS);
+	    if (!_G.graph->valid(n)) { //Ha T ures
+	      spec=3;
+	    }
+	  }
+	}
+      }
+      operator Edge() const { return Edge(e, spec, n); }
+    };
    
-//     NodeIt& first(NodeIt& i) const { 
-//       i=NodeIt(*this); 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;
-//     }
-//     EdgeIt& first(EdgeIt& i) const { 
-//       i=EdgeIt(*this); return i;
-//     }
+    NodeIt& first(NodeIt& i) const { 
+      i=NodeIt(*this); 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;
+    }
+    EdgeIt& first(EdgeIt& i) const { 
+      i=EdgeIt(*this); return i;
+    }
 
-//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
-//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
-//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
-//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
+    NodeIt& next(NodeIt& i) const { 
+      switch (i.spec) {
+	case 0:
+	  graph->next(i.n);
+	  if (!graph->valid(i.n)) {
+	    i.spec=1;
+	  }
+	  break;
+	case 1:
+	  i.spec=2;
+	  break;
+	case 2:
+	  i.spec=3;
+	  break;
+      }
+      return i; 
+    }
+    OutEdgeIt& next(OutEdgeIt& i) const { 
+      switch (i.spec) {
+	case 0: //normal edge
+	  typename Graph::Node v=graph->aNode(i.e);
+	  graph->next(i.e);
+	  if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
+	    if (graph->inSClass(v)) { //S, nincs kiel
+	      i.spec=3;
+	      i.n=INVALID;
+	    } else { //T, van kiel
+	      i.spec=2; 
+	      i.n=v;
+	    }
+	  }
+	  break;
+	case 1: //s->vmi
+	  graph->next(i.n);
+	  if (!graph->valid(i.n)) i.spec=3;
+	  break;
+	case 2: //vmi->t
+	  i.spec=3;
+	  i.n=INVALID;
+	  break;
+      }
+      return i; 
+    }
+    InEdgeIt& next(InEdgeIt& i) const { 
+      switch (i.spec) {
+	case 0: //normal edge
+	  typename Graph::Node v=graph->aNode(i.e);
+	  graph->next(i.e);
+	  if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
+	    if (graph->inTClass(v)) { //S, nincs beel
+	      i.spec=3;
+	      i.n=INVALID;
+	    } else { //S, van beel
+	      i.spec=1; 
+	      i.n=v;
+	    }
+	  }
+	  break;
+	case 1: //s->vmi
+	  i.spec=3;
+	  i.n=INVALID;
+	  break;
+	case 2: //vmi->t
+	  graph->next(i.n);
+	  if (!graph->valid(i.n)) i.spec=3;
+	  break;
+      }
+      return i; 
+    }
 
-//     Node head(const Edge& e) const { 
-//       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
-//     Node tail(const Edge& e) const { 
-//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
+    EdgeIt& next(EdgeIt& i) const { 
+      switch (i.spec) {
+	case 0:
+	  graph->next(i.e);
+	  if (!graph->valid(i.e)) { 
+	    i.spec=1;
+	    graph->first(n, S_CLASS);
+	    if (!graph->valid(i.n)) {
+	      i.spec=2;
+	      graph->first(n, T_CLASS);
+	      if (!graph->valid(i.n)) spec=3;
+	    }
+	  }
+	  break;
+	case 1:
+	  graph->next(i.n);
+	  if (!graph->valid(i.n)) {
+	    i.spec=2;
+	    graph->first(n, T_CLASS);
+	    if (!graph->valid(i.n)) spec=3;
+	  }
+	  break;
+	case 2:
+	  graph->next(i.n);
+	  if (!graph->valid(i.n)) i.spec=3;
+	  break;
+      }
+      return i; 
+    }    
 
-//     bool valid(const Node& n) const { 
-//       return graph->valid(static_cast<typename Graph::Node>(n)); }
-//     bool valid(const Edge& e) const { 
-//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
+    Node tail(const Edge& e) const { 
+      switch (e.spec) {
+	case 0: 
+	  return Node(graph->tail(e));
+	  break;
+	case 1:
+	  return S_NODE;
+	  break;
+	case 2:
+	  return Node(e.n);
+	  break;
+      }
+    }
+    Node head(const Edge& e) const { 
+      switch (e.spec) {
+	case 0: 
+	  return Node(graph->head(e));
+	  break;
+	case 1:
+	  return Node(e.n);
+	  break;
+	case 2:
+	  return T_NODE;
+	  break;
+      }
+    }
 
-//     int nodeNum() const { return graph->nodeNum(); }
-//     int edgeNum() const { return graph->edgeNum(); }
+    bool valid(const Node& n) const { return (n.spec<3); }
+    bool valid(const Edge& e) const { return (e.spec<3); }
+
+//    int nodeNum() const { return graph->nodeNum(); }
+//    int edgeNum() const { return graph->edgeNum(); }
   
-//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
-//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
+    Node aNode(const OutEdgeIt& e) const { return tail(e); }
+    Node aNode(const InEdgeIt& e) const { return head(e); }
+    Node bNode(const OutEdgeIt& e) const { return head(e); }
+    Node bNode(const InEdgeIt& e) const { return tail(e); }
   
-//     Node addNode() const { return Node(graph->addNode()); }
-//     Edge addEdge(const Node& tail, const Node& head) const { 
-//       return Edge(graph->addEdge(tail, head)); }
+//    Node addNode() const { return Node(graph->addNode()); }
+//    Edge addEdge(const Node& tail, const Node& head) const { 
+//      return Edge(graph->addEdge(tail, head)); }
 
-//     void erase(const Node& i) const { graph->erase(i); }
-//     void erase(const Edge& i) const { graph->erase(i); }
+//    void erase(const Node& i) const { graph->erase(i); }
+//    void erase(const Edge& i) const { graph->erase(i); }
   
-//     void clear() const { graph->clear(); }
+//    void clear() const { graph->clear(); }
     
-//     template<typename T> class NodeMap : public Graph::NodeMap<T> { 
-//     public:
-//       NodeMap(const GraphWrapper<Graph>& _G) :  
-// 	Graph::NodeMap<T>(*(_G.graph)) { }
-//       NodeMap(const GraphWrapper<Graph>& _G, T a) : 
-// 	Graph::NodeMap<T>(*(_G.graph), a) { }
-//     };
+    template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> { 
+      T s_value, t_value;
+    public:
+      NodeMap(const stGraphWrapper<Graph>& _G) :  
+	GraphWrapper<Graph>::NodeMap<T>(_G) { }
+      NodeMap(const stGraphWrapper<Graph>& _G, T a) : 
+	GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
+      T operator[](const Node& n) const { 
+	switch (n.spec) {
+	  case 0: 
+	    return (*this)[n];
+	    break;
+	  case 1:
+	    return s_value;
+	    break;
+	  case 2:
+	    return t_value;
+	    break;
+	}
+      }
+      void set(const Node& n, T t) { 
+	switch (n.spec) {
+	  case 0: 
+	    GraphWrapper<Graph>::NodeMap<T>::set(n, t);
+	    break;
+	  case 1:
+	    s_value=t;
+	    break;
+	  case 2:
+	    t_value=t;
+	    break;
+	}
+      }
+    };
 
-//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 
-//     public:
-//       EdgeMap(const GraphWrapper<Graph>& _G) :  
-// 	Graph::EdgeMap<T>(*(_G.graph)) { }
-//       EdgeMap(const GraphWrapper<Graph>& _G, T a) : 
-// 	Graph::EdgeMap<T>(*(_G.graph), a) { }
-//     };
-//   };
+    template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> { 
+      typename GraphWrapper<Graph>::NodeMap<T> node_value;
+    public:
+      EdgeMap(const stGraphWrapper<Graph>& _G) :  
+	GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
+      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : 
+	GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
+      T operator[](const Edge& e) const { 
+	switch (e.spec) {
+	  case 0: 
+	    return (*this)[e];
+	    break;
+	  case 1:
+	    return node_value[e.n];
+	    break;
+	  case 2:
+	    return node_value[e.n];
+	    break;
+	}
+      }
+      void set(const Edge& e, T t) { 
+	switch (e.spec) {
+	  case 0: 
+	    GraphWrapper<Graph>::set(e, t);
+	    break;
+	  case 1:
+	    node_value.set(e, t);
+	    break;
+	  case 2:
+	    node_value.set(e, t);
+	    break;
+	}
+      }
+    };
+  };
+
 
 } //namespace hugo
 
diff -r c3f93631cd24 -r a5bff2813c4d src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc	Thu Apr 22 20:36:21 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc	Fri Apr 23 07:41:48 2004 +0000
@@ -35,7 +35,7 @@
     Timer ts;
     Graph::EdgeMap<int> flow(G); //0 flow
     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      pre_flow_test(G, s, t, cap, flow);
+      pre_flow_test(G, s, t, cap, flow, true);
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       max_flow_test(G, s, t, cap, flow);
 
@@ -109,7 +109,7 @@
     Timer ts;
     Graph::EdgeMap<int> flow(G); //0 flow
     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      pre_flow_test(G, s, t, cap, flow);
+      pre_flow_test(G, s, t, cap, flow, true);
     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       max_flow_test(G, s, t, cap, flow);