Index: src/work/marci/lp/max_flow_by_lp.cc
===================================================================
--- src/work/marci/lp/max_flow_by_lp.cc	(revision 1017)
+++ src/work/marci/lp/max_flow_by_lp.cc	(revision 1025)
@@ -22,5 +22,5 @@
 
   typedef ListGraph MutableGraph;
-  typedef SmartGraph Graph;
+  typedef ListGraph Graph;
   typedef Graph::Node Node;
   typedef Graph::Edge Edge;
@@ -179,4 +179,5 @@
   MinCostGenFlow<Graph, int, Excess, LCap> 
     min_cost(g, excess, lcap, cap, flow, cost); 
+  min_cost.feasible();
   min_cost.run();
 
Index: src/work/marci/lp/min_cost_gen_flow.h
===================================================================
--- src/work/marci/lp/min_cost_gen_flow.h	(revision 1017)
+++ src/work/marci/lp/min_cost_gen_flow.h	(revision 1025)
@@ -2,15 +2,16 @@
 #ifndef LEMON_MIN_COST_GEN_FLOW_H
 #define LEMON_MIN_COST_GEN_FLOW_H
-//#include <iostream>
+#include <iostream>
 //#include <fstream>
 
-//#include <lemon/smart_graph.h>
-//#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
 //#include <lemon/dimacs.h>
 //#include <lemon/time_measure.h>
 //#include <graph_wrapper.h>
-//#include <lemon/preflow.h>
+#include <lemon/preflow.h>
 //#include <augmenting_flow.h>
 //#include <preflow_res.h>
+#include <../merge_node_graph_wrapper.h>
 #include <lemon/../work/marci/lp/lp_solver_wrapper.h>
 
@@ -52,4 +53,69 @@
       g(_g), excess(_excess), lcapacity(_lcapacity),
       capacity(_capacity), flow(_flow), cost(_cost) { }
+    bool feasible() {
+      //      std::cout << "making new vertices..." << std::endl; 
+      typedef ListGraph Graph2;
+      Graph2 g2;
+      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
+      //      std::cout << "merging..." << std::endl; 
+      GW gw(g, g2);
+      typename GW::Node s(INVALID, g2.addNode(), true);
+      typename GW::Node t(INVALID, g2.addNode(), true);
+      typedef SmartGraph Graph3;
+      //      std::cout << "making extender graph..." << std::endl; 
+      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
+//       {
+// 	checkConcept<StaticGraph, GWW>();   
+//       }
+      GWW gww(gw);
+      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
+      GWWW gwww(gw, gww);
+
+      //      std::cout << "making new edges..." << std::endl; 
+      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
+
+      for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
+      translated_cap.set(typename GWWW::Edge(e,INVALID,false), 
+			 capacity[e]-lcapacity[e]);
+
+      Num expected=0;
+
+      //      std::cout << "making new edges 2..." << std::endl; 
+      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
+	Num a=0;
+	for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
+	  a+=lcapacity[e];
+	for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
+	  a-=lcapacity[e];
+	if (excess[n]>a) {
+	  typename GWW::Edge e=
+	    gww.addEdge(typename GW::Node(n,INVALID,false), t);
+	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
+			     excess[n]-a);
+	}
+	if (excess[n]<a) {
+	  typename GWW::Edge e=
+	    gww.addEdge(s, typename GW::Node(n,INVALID,false));
+	  translated_cap.set(typename GWWW::Edge(INVALID, e, true), 
+			     a-excess[n]);
+	  expected+=a-excess[n];
+	}
+      }
+
+      //      std::cout << "preflow..." << std::endl; 
+      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
+      Preflow<GWWW, Num> preflow(gwww, s, t, 
+				 translated_cap, translated_flow);
+      preflow.run();
+      //      std::cout << "fv: " << preflow.flowValue() << std::endl; 
+      //      std::cout << "expected: " << expected << std::endl; 
+
+      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
+	typename GW::Edge ew(e, INVALID, false);
+	typename GWWW::Edge ewww(ew, INVALID, false);
+	flow.set(e, translated_flow[ewww]+lcapacity[e]);
+      }
+      return (expected>=preflow.flowValue());
+    }
     void run() {
       LPSolverWrapper lp;
Index: src/work/marci/merge_node_graph_wrapper.h
===================================================================
--- src/work/marci/merge_node_graph_wrapper.h	(revision 1016)
+++ src/work/marci/merge_node_graph_wrapper.h	(revision 1025)
@@ -41,11 +41,6 @@
 
 
-  /*! A graph wrapper base class 
-    for merging the node-set of two node-disjoint graphs 
-    into the node-set of one graph. 
-    Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
-   */
   template <typename _Graph1, typename _Graph2, typename Enable=void>
-  class MergeNodeGraphWrapperBase : 
+  class MergeNodeGraphWrapperBaseBase : 
     public P1<_Graph1>, public P2<_Graph2> {
   public:
@@ -58,11 +53,9 @@
     typedef typename Parent2::Node Graph2Node;
   protected:
-    MergeNodeGraphWrapperBase() { }
-  public:
-    template <typename _Value> class NodeMap;
+    MergeNodeGraphWrapperBaseBase() { }
+  public:
 
     class Node : public Graph1Node, public Graph2Node {
-      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
-      template <typename _Value> friend class NodeMap;
+      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
     protected:
       bool backward; //true, iff backward
@@ -89,77 +82,13 @@
     };
 
-    //typedef void Edge;
-    class Edge { };
-    
-    void first(Node& i) const {
-      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
-      i.backward=false;
-      if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	i.backward=true;
-      }
-    }
-    void next(Node& i) const {
-      if (!(i.backward)) {
-	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
-	if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	  i.backward=true;
-	}
-      } else {
-	Parent2::graph->next(*static_cast<Graph2Node*>(&i));
-      }
-    }
-
-    int id(const Node& n) const { 
-      if (!n.backward) 
-	return this->Parent1::graph->id(n);
-      else
-	return this->Parent2::graph->id(n);
-    }
-
-    template <typename _Value> 
-    class NodeMap { 
-    protected:
-      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
-      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
-      ParentMap1 forward_map;
-      ParentMap2 backward_map;
-    public:
-      typedef _Value Value;
-      typedef Node Key;
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
-	forward_map(*(gw.Parent1::graph)), 
-	backward_map(*(gw.Parent2::graph)) { }
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
-	      const _Value& value) : 
-	forward_map(*(gw.Parent1::graph), value), 
-	backward_map(*(gw.Parent2::graph), value) { }
-      _Value operator[](const Node& n) const {
-	if (!n.backward) 
-	  return forward_map[n];
-	else 
-	  return backward_map[n];
-      }
-      void set(const Node& n, const _Value& value) {
-	if (!n.backward) 
-	  forward_map.set(n, value);
-	else 
-	  backward_map.set(n, value);
-      }
-//       using ParentMap1::operator[];
-//       using ParentMap2::operator[];
-    };
-
-  };
-
-
-  /*! A graph wrapper base class 
-    for merging the node-set of two node-disjoint graphs 
-    into the node-set of one graph. 
-    Specialization for the case when _Graph1::Node are the same _Graph2::Node.
-   */
+    static bool forward(const Node& n) { return !n.backward; }
+    static bool backward(const Node& n) { return n.backward; }
+    static void setForward(Node& n) { n.backward=false; }
+    static void setBackward(Node& n) { n.backward=true; }    
+  };
+
+
   template <typename _Graph1, typename _Graph2>
-  class MergeNodeGraphWrapperBase<
+  class MergeNodeGraphWrapperBaseBase<
     _Graph1, _Graph2, typename boost::enable_if<
     boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
@@ -174,11 +103,9 @@
     typedef typename Parent2::Node Graph2Node;
   protected:
-    MergeNodeGraphWrapperBase() { }
-  public:
-    template <typename _Value> class NodeMap;
+    MergeNodeGraphWrapperBaseBase() { }
+  public:
 
     class Node : public Graph1Node {
-      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
-      template <typename _Value> friend class NodeMap;
+      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
     protected:
       bool backward; //true, iff backward
@@ -190,5 +117,5 @@
       Node(const Graph1Node& n1, 
 	   const Graph2Node& n2, bool _backward) : 
-	Graph1Node(!backward ? n1 : n2), backward(_backward) { }
+	Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
       Node(Invalid i) : Graph1Node(i), backward(true) { }
       bool operator==(const Node& v) const { 
@@ -201,78 +128,13 @@
     };
 
-    //typedef void Edge;
-    class Edge { };
-    
-    void first(Node& i) const {
-      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
-      i.backward=false;
-      if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	Parent2::graph->first(*static_cast<Graph1Node*>(&i));
-	i.backward=true;
-      }
-    }
-    void next(Node& i) const {
-      if (!(i.backward)) {
-	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
-	if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph1Node*>(&i));
-	  i.backward=true;
-	}
-      } else {
-	Parent2::graph->next(*static_cast<Graph1Node*>(&i));
-      }
-    }
-
-    int id(const Node& n) const { 
-      if (!n.backward) 
-	return this->Parent1::graph->id(n);
-      else
-	return this->Parent2::graph->id(n);
-    }
-
-    template <typename _Value> 
-    class NodeMap { 
-    protected:
-      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
-      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
-      ParentMap1 forward_map;
-      ParentMap2 backward_map;
-    public:
-      typedef _Value Value;
-      typedef Node Key;
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
-	forward_map(*(gw.Parent1::graph)), 
-	backward_map(*(gw.Parent2::graph)) { }
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
-	      const _Value& value) : 
-	forward_map(*(gw.Parent1::graph), value), 
-	backward_map(*(gw.Parent2::graph), value) { }
-      _Value operator[](const Node& n) const {
-	if (!n.backward) 
-	  return forward_map[n];
-	else 
-	  return backward_map[n];
-      }
-      void set(const Node& n, const _Value& value) {
-	if (!n.backward) 
-	  forward_map.set(n, value);
-	else 
-	  backward_map.set(n, value);
-      }
-//       using ParentMap1::operator[];
-//       using ParentMap2::operator[];
-    };
-
-  };
-
-
-  /*! A graph wrapper base class 
-    for merging the node-set of two node-disjoint graphs 
-    into the node-set of one graph. 
-    Specialization for the case when 
-    _Graph1::Node is a base class and _Graph2::Node is derived from it.
-   */
+    static bool forward(const Node& n) { return !n.backward; }
+    static bool backward(const Node& n) { return n.backward; }
+    static void setForward(Node& n) { n.backward=false; }
+    static void setBackward(Node& n) { n.backward=true; }
+  };
+
+
   template <typename _Graph1, typename _Graph2>
-  class MergeNodeGraphWrapperBase<
+  class MergeNodeGraphWrapperBaseBase<
     _Graph1, _Graph2, typename boost::enable_if<
     boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
@@ -287,11 +149,9 @@
     typedef typename Parent2::Node Graph2Node;
   protected:
-    MergeNodeGraphWrapperBase() { }
-  public:
-    template <typename _Value> class NodeMap;
+    MergeNodeGraphWrapperBaseBase() { }
+  public:
 
     class Node : public Graph2Node {
-      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
-      template <typename _Value> friend class NodeMap;
+      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
     protected:
       bool backward; //true, iff backward
@@ -320,78 +180,13 @@
     };
 
-    //typedef void Edge;
-    class Edge { };
-    
-    void first(Node& i) const {
-      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
-      i.backward=false;
-      if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	i.backward=true;
-      }
-    }
-    void next(Node& i) const {
-      if (!(i.backward)) {
-	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
-	if (*static_cast<Graph1Node*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	  i.backward=true;
-	}
-      } else {
-	Parent2::graph->next(*static_cast<Graph2Node*>(&i));
-      }
-    }
-
-    int id(const Node& n) const { 
-      if (!n.backward) 
-	return this->Parent1::graph->id(n);
-      else
-	return this->Parent2::graph->id(n);
-    }
-
-    template <typename _Value> 
-    class NodeMap { 
-    protected:
-      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
-      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
-      ParentMap1 forward_map;
-      ParentMap2 backward_map;
-    public:
-      typedef _Value Value;
-      typedef Node Key;
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
-	forward_map(*(gw.Parent1::graph)), 
-	backward_map(*(gw.Parent2::graph)) { }
-      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
-	      const _Value& value) : 
-	forward_map(*(gw.Parent1::graph), value), 
-	backward_map(*(gw.Parent2::graph), value) { }
-      _Value operator[](const Node& n) const {
-	if (!n.backward) 
-	  return forward_map[n];
-	else 
-	  return backward_map[n];
-      }
-      void set(const Node& n, const _Value& value) {
-	if (!n.backward) 
-	  forward_map.set(n, value);
-	else 
-	  backward_map.set(n, value);
-      }
-//       using ParentMap1::operator[];
-//       using ParentMap2::operator[];
-    };
-
-  };
-
-
-  /*! A graph wrapper base class 
-    for merging the node-set of two node-disjoint graphs 
-    into the node-set of one graph. 
-    Specialized implementaton for the case when _Graph1::Node is derived 
-    from _Graph2::Node.
-   */
+    static bool forward(const Node& n) { return !n.backward; }
+    static bool backward(const Node& n) { return n.backward; }
+    static void setForward(Node& n) { n.backward=false; }
+    static void setBackward(Node& n) { n.backward=true; }
+  };
+  
+
   template <typename _Graph1, typename _Graph2>
-  class MergeNodeGraphWrapperBase<
+  class MergeNodeGraphWrapperBaseBase<
     _Graph1, _Graph2, typename boost::enable_if<
     boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : 
@@ -406,11 +201,9 @@
     typedef typename Parent2::Node Graph2Node;
   protected:
-    MergeNodeGraphWrapperBase() { }
-  public:
-    template <typename _Value> class NodeMap;
+    MergeNodeGraphWrapperBaseBase() { }
+  public:
 
     class Node : public Graph1Node {
-      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
-      template <typename _Value> friend class NodeMap;
+      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
     protected:
       bool backward; //true, iff backward
@@ -439,21 +232,40 @@
     };
 
-    //typedef void Edge;
+    static bool forward(const Node& n) { return !n.backward; }
+    static bool backward(const Node& n) { return n.backward; }
+    static void setForward(Node& n) { n.backward=false; }
+    static void setBackward(Node& n) { n.backward=true; }
+  };
+
+
+  template <typename _Graph1, typename _Graph2>
+  class MergeNodeGraphWrapperBase : 
+    public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
+  public:
+    typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
+    typedef _Graph1 Graph1;
+    typedef _Graph2 Graph2;
+    typedef P1<_Graph1> Parent1;
+    typedef P2<_Graph2> Parent2;
+    typedef typename Parent1::Node Graph1Node;
+    typedef typename Parent2::Node Graph2Node;
+
+    typedef typename Parent::Node Node; 
     class Edge { };
     
     void first(Node& i) const {
       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
-      i.backward=false;
+      this->setForward(i);
       if (*static_cast<Graph1Node*>(&i)==INVALID) {
 	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	i.backward=true;
+	this->setBackward(i);
       }
     }
     void next(Node& i) const {
-      if (!(i.backward)) {
+      if (this->forward(i)) {
 	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
 	if (*static_cast<Graph1Node*>(&i)==INVALID) {
 	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
-	  i.backward=true;
+	  this->setBackward(i);
 	}
       } else {
@@ -463,5 +275,5 @@
 
     int id(const Node& n) const { 
-      if (!n.backward) 
+      if (this->forward(n)) 
 	return this->Parent1::graph->id(n);
       else
@@ -487,5 +299,5 @@
 	backward_map(*(gw.Parent2::graph), value) { }
       _Value operator[](const Node& n) const {
-	if (!n.backward) 
+	if (Parent::forward(n)) 
 	  return forward_map[n];
 	else 
@@ -493,5 +305,5 @@
       }
       void set(const Node& n, const _Value& value) {
-	if (!n.backward) 
+	if (Parent::forward(n)) 
 	  forward_map.set(n, value);
 	else 
@@ -506,9 +318,22 @@
 
   /*! A graph wrapper class 
-    fors merging the node-set of two node-disjoint graphs 
-    into one node-set. It does not satisfy 
+    for merging the node-set of two node-disjoint graphs 
+    into the node-set of one graph. 
+    Different implementations are according to the relation of 
+    _Graph1::Node and _Graph2::Node. 
+    If _Graph1::Node and _Graph2::Node are unrelated, then 
+    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
+    is derived from both. 
+    If _Graph1::Node and _Graph2::Node are the same type, then 
+    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
+    is derived from _Graph1::Node. 
+    If one of _Graph1::Node and _Graph2::Node 
+    is derived from the other one, then 
+    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
+    is derived from the derived type.
+    It does not satisfy 
     StaticGraph concept as it has no edge-set which 
     works together with the node-set.
-   */
+  */
   template <typename _Graph1, typename _Graph2>
   class MergeNodeGraphWrapper : public 
@@ -583,4 +408,9 @@
     };
 
+    using Parent::forward;
+    using Parent::backward;
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
+
     using Parent::first;
     void first(Edge& i) const {
@@ -593,7 +423,11 @@
     }
     void firstIn(Edge& i, const Node& n) const {
-      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -601,7 +435,11 @@
     }
     void firstOut(Edge& i, const Node& n) const {
-      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -624,8 +462,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
@@ -635,8 +470,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
@@ -750,5 +582,5 @@
       Edge(const Graph1Edge& n1, 
 	   const Graph2Edge& n2, bool _backward) : 
-	Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
+	Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
       Edge(Invalid i) : Graph1Edge(i), backward(true) { }
       bool operator==(const Edge& v) const { 
@@ -760,4 +592,9 @@
       }
     };
+
+    using Parent::forward;
+    using Parent::backward;
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
 
     using Parent::first;
@@ -771,7 +608,11 @@
     }
     void firstIn(Edge& i, const Node& n) const {
-      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
 	i.backward=true;
@@ -779,7 +620,11 @@
     }
     void firstOut(Edge& i, const Node& n) const {
-      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
 	i.backward=true;
@@ -802,8 +647,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
@@ -813,8 +655,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
@@ -946,4 +785,9 @@
     };
 
+    using Parent::forward;
+    using Parent::backward;
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
+
     using Parent::first;
     void first(Edge& i) const {
@@ -956,7 +800,11 @@
     }
     void firstIn(Edge& i, const Node& n) const {
-      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -964,7 +812,11 @@
     }
     void firstOut(Edge& i, const Node& n) const {
-      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else	
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -987,8 +839,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
@@ -998,8 +847,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
@@ -1130,4 +976,9 @@
     };
 
+    using Parent::forward;
+    using Parent::backward;
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
+
     using Parent::first;
     void first(Edge& i) const {
@@ -1140,7 +991,11 @@
     }
     void firstIn(Edge& i, const Node& n) const {
-      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -1148,7 +1003,11 @@
     }
     void firstOut(Edge& i, const Node& n) const {
-      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
-      i.backward=false;
-      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
+      if (!backward(n)) {
+	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
+	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
+	  i=INVALID;
+	else	
+	  i.backward=false;
+      } else {
 	Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
 	i.backward=true;
@@ -1171,8 +1030,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
@@ -1182,8 +1038,5 @@
       if (!(i.backward)) {
 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
-	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
-	  i.backward=true;
-	}
+ 	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
       } else {
 	Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
@@ -1348,4 +1201,12 @@
     int edgeNum() const { return edge_set_graph->edgeNum(); }
 
+//     NNode addOldNode() {
+//       return Parent::addNode();
+//     }
+
+//     ENode addNewNode() {
+//       return edge_set_graph->addNode();
+//     }
+
     Edge addEdge(const Node& u, const Node& v) {
       return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
@@ -1393,5 +1254,5 @@
     typedef _EdgeSetGraph EdgeSetGraph;
     typedef IterableGraphExtender<
-      NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
+      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
   protected:
     NewEdgeSetGraphWrapper() { }
@@ -1410,4 +1271,49 @@
   };
 
+  /*! A graph wrapper class for the following functionality.
+    The same as NewEdgeSetGrapWrapper, but the bijection and the graph of 
+    new edges is andled inthe class.
+   */
+  template <typename _Graph, typename _EdgeSetGraph>
+  class NewEdgeSetGraphWrapper2 : 
+    public IterableGraphExtender<
+    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
+  public:
+    typedef _Graph Graph;
+    typedef _EdgeSetGraph EdgeSetGraph;
+    typedef IterableGraphExtender<
+      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
+  protected:
+    _EdgeSetGraph _edge_set_graph;
+    typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
+    typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
+    NewEdgeSetGraphWrapper2() { }
+  public:
+    typedef typename Graph::Node Node;
+    //    typedef typename Parent::Edge Edge;
+
+    NewEdgeSetGraphWrapper2(_Graph& _graph) : 
+      _edge_set_graph(), 
+      _e_node(_graph), _n_node(_edge_set_graph) { 
+      setGraph(_graph);
+      setEdgeSetGraph(_edge_set_graph);
+      setNodeMap(_n_node); setENodeMap(_e_node);
+      Node n;
+      for (this->first(n); n!=INVALID; this->next(n)) {
+	typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
+	_e_node.set(n, e);
+	_n_node.set(e, n);
+      }
+    }
+
+//     Node addNode() {
+//       Node n=(*this).Parent::addNode();
+//       typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
+//       _e_node.set(n, e);
+//       _n_node.set(e, n);
+//       return n;
+//     }
+
+  };
 
   /*! A graph wrapper base class 
@@ -1418,4 +1324,7 @@
     In an other point of view, _Graph1 is extended with 
     the edge-set of _Graph2.
+    \warning we need specialize dimplementations
+    \todo we need specialize dimplementations
+    \bug we need specialize dimplementations
    */
   template <typename _Graph1, typename _Graph2, typename Enable=void>
@@ -1507,7 +1416,8 @@
     void nextIn(Edge& i) const {
       if (!(i.backward)) {
+	Node n=target(i);
 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  graph2->first(*static_cast<Graph2Edge*>(&i));
+	  graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
 	  i.backward=true;
 	}
@@ -1518,7 +1428,8 @@
     void nextOut(Edge& i) const {
       if (!(i.backward)) {
+	Node n=source(i);
 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
-	  graph2->first(*static_cast<Graph2Edge*>(&i));
+	  graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
 	  i.backward=true;
 	}
Index: src/work/marci/merge_node_graph_wrapper_test.cc
===================================================================
--- src/work/marci/merge_node_graph_wrapper_test.cc	(revision 1016)
+++ src/work/marci/merge_node_graph_wrapper_test.cc	(revision 1025)
@@ -5,4 +5,5 @@
 #include <lemon/smart_graph.h>
 #include <lemon/dimacs.h>
+#include <lemon/preflow.h>
 #include <lemon/full_graph.h>
 #include <merge_node_graph_wrapper.h>
@@ -27,10 +28,12 @@
   cout << " nodes:" << endl;
   for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { 
-    cout << "  " << g.id(n) << endl;
+    cout << "  " << g.id(n) << ": out edges:" << endl;
+    for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) 
+      cout << "   " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
   }
   cout << " edges:" << endl;
-  for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) { 
-    cout << "  " << g.id(n) << ": " 
-	 << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
+  for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { 
+    cout << "   " << g.id(e) << ": " 
+	 << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
   }  
 }
@@ -39,23 +42,25 @@
   {
     cout << "FIRST TEST" << endl;
-    typedef SmartGraph Graph1;
+    //typedef SmartGraph Graph1;
+    typedef ListGraph Graph1;
     typedef ListGraph Graph2;
+    typedef SmartGraph Graph3;
     
-    {
-      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
-      MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); 
-      MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); 
-      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
-      MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); 
-      MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); 
-      typedef ResGraphWrapper<Graph1, int, 
-	ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
-      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();   
-      MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); 
-      MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
-      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();   
-      MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); 
-      MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge();  
-    }
+//     {
+//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
+//       MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); 
+//       MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); 
+//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
+//       MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); 
+//       MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); 
+//       typedef ResGraphWrapper<Graph1, int, 
+// 	ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
+//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();   
+//       MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); 
+//       MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
+//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();   
+//       MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); 
+//       MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge();  
+//     }
   
     Graph1 g1;
@@ -63,4 +68,8 @@
     typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
     GW gw(g1, g2);
+    Graph1::Node s1, t1;
+    Graph2::Node s2, t2;
+    Graph1::EdgeMap<int> cap1(g1);
+    Graph2::EdgeMap<int> cap2(g2);
 
     std::ifstream f1("graph1.dim");
@@ -68,14 +77,92 @@
     readDimacs(f1, g1);
     readDimacs(f2, g2);
+
+//     GW::NodeMap<int> ize(gw, 8);
+//     for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9);
+//     GW::EdgeMap<int> mize(gw, 8);
+//     for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7);
+
+//     std::ifstream f1("flow-1.dim");
+//     std::ifstream f2("flow2.dim");
+//     readDimacs(f1, g1, cap1, s1, t1);
+//     readDimacs(f2, g2, cap2, s2, t2);
     
-    cout << "1st graph" << endl;
-    printGraph(g1);
-
-    cout << "2nd graph" << endl;
-    printGraph(g2);
-
-    cout << "merged graph" << endl;
-    printGraph(gw);
-
+//     GW::EdgeMap<int> cap(gw);
+//     for (GW::EdgeIt e(gw); e!=INVALID; ++e) {
+//       if (gw.forward(e)) cap.set(e, cap1[e]);
+//       if (gw.backward(e)) cap.set(e, cap2[e]);
+//     }
+
+//     {
+//       GW::EdgeMap<int> flow(gw, 0);
+//       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), 
+// 			       GW::Node(t1, INVALID, false), cap, flow);
+//       preflow.run();
+//       std::cout << "s1->t1: " << preflow.flowValue() << std::endl; 
+//     }
+//     {
+//       GW::EdgeMap<int> flow(gw, 0);
+//       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), 
+// 			       GW::Node(INVALID, t2, true), cap, flow);
+//       preflow.run();
+//       std::cout << "s2->t2: " << preflow.flowValue() << std::endl; 
+//     }
+//     {
+//       GW::EdgeMap<int> flow(gw, 0);
+//       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), 
+// 			       GW::Node(INVALID, t2, true), cap, flow);
+//       preflow.run();
+//       std::cout << "s1->t2: " << preflow.flowValue() << std::endl; 
+//     }
+//     {
+//       GW::EdgeMap<int> flow(gw, 0);
+//       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), 
+// 			       GW::Node(s1, INVALID, false), cap, flow);
+//       preflow.run();
+//       std::cout << "s2->t1: " << preflow.flowValue() << std::endl; 
+//     }
+     cout << "1st graph" << endl;
+     printGraph(g1);
+
+     cout << "2nd graph" << endl;
+     printGraph(g2);
+
+     cout << "merged graph" << endl;
+     printGraph(gw);
+     
+//      for (GW::NodeIt n(gw); n!=INVALID; ++n) 
+//        std::cout << ize[n] << std::endl;
+//      for (GW::EdgeIt n(gw); n!=INVALID; ++n) 
+//        std::cout << mize[n] << std::endl;
+     
+     typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
+//     {
+//       checkConcept<StaticGraph, GWW>();   
+//     }
+
+     GWW gww(gw);
+ 
+     cout << "new edges graph" << endl;
+     printGraph(gww);
+
+     GWW::NodeIt n(gww);
+     GWW::Node n1=n; 
+     ++n;
+     GWW::Node n2=n; 
+     gww.addEdge(n1, n2);
+     //     gww.addNode();
+     //     gww.addNode();
+
+     cout << "new edges graph" << endl;
+     printGraph(gww);
+
+     typedef AugmentingGraphWrapper<GW, GWW> GWWW;
+     //     {
+     //       checkConcept<StaticGraph, GWWW>();   
+     //     }
+     GWWW gwww(gw, gww);
+
+     cout << "fully merged graph" << endl;
+     printGraph(gwww);
   }
 
@@ -84,7 +171,7 @@
     cout << "SECOND TEST" << endl;
     typedef SmartGraph Graph1;
-    {
-      checkConcept<StaticGraph, Graph1>();
-    }
+//     {
+//       checkConcept<StaticGraph, Graph1>();
+//     }
 
     Graph1 g1;
@@ -94,14 +181,14 @@
     typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> >
       Graph2;
-    {
-      checkConcept<StaticGraph, Graph2>();
-    }
+//     {
+//       checkConcept<StaticGraph, Graph2>();
+//     }
 
     Graph2 g2(pre_g2, const_false_map);
 
     typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
-    {
-      checkConcept<StaticGraph, GW>();   
-    }
+//     {
+//       checkConcept<StaticGraph, GW>();   
+//     }
     GW gw(g1, g2);
     GW::Node sw;
@@ -138,7 +225,7 @@
 
     typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW;
-    {
-      checkConcept<StaticGraph, GWW>();   
-    }
+//     {
+//       checkConcept<StaticGraph, GWW>();   
+//     }
 
     GWW gww(gw, g3, gwn, g3n);
@@ -159,7 +246,7 @@
 
     typedef AugmentingGraphWrapper<GW, GWW> GWWW;
-    {
-      checkConcept<StaticGraph, GWWW>();   
-    }
+//     {
+//       checkConcept<StaticGraph, GWWW>();   
+//     }
     GWWW gwww(gw, gww);
 
