/* -*- C++ -*-

  * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H

 #define LEMON_MERGE_NODE_GRAPH_WRAPPER_H

 #include <lemon/invalid.h>

 #include <lemon/maps.h>

 #include <lemon/map_defines.h>

 #include <lemon/graph_wrapper.h>

 #include <iostream>

 using std::cout;

 using std::endl;

 #include <boost/type_traits.hpp>

 #include <boost/utility/enable_if.hpp>

 namespace lemon {

   template <class _Graph1>

   class P1 : public GraphWrapperBase<_Graph1> {

   };

   template <class _Graph2>

   class P2 : public GraphWrapperBase<_Graph2> {

   };

   template <typename _Graph1, typename _Graph2, typename Enable=void>

   class MergeNodeGraphWrapperBaseBase : 

     public P1<_Graph1>, public P2<_Graph2> {

   public:

     static void printNode() { std::cout << "node: generic" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef P1<_Graph1> Parent1;

     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Node Graph1Node;

     typedef typename Parent2::Node Graph2Node;

   protected:

     MergeNodeGraphWrapperBaseBase() { }

   public:

     class Node : public Graph1Node, public Graph2Node {

       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Node() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Node(const Graph1Node& n1, 

 	   const Graph2Node& n2, bool _backward) : 

 	Graph1Node(n1), Graph2Node(n2), backward(_backward) { }

       Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }

       bool operator==(const Node& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 

       } 

       bool operator!=(const Node& v) const { 

 	return !(*this==v);

       }

     };

     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 MergeNodeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 

     public P1<_Graph1>, public P2<_Graph2> {

   public:

     static void printNode() { std::cout << "node: same" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef P1<_Graph1> Parent1;

     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Node Graph1Node;

     typedef typename Parent2::Node Graph2Node;

   protected:

     MergeNodeGraphWrapperBaseBase() { }

   public:

     class Node : public Graph1Node {

       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Node() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Node(const Graph1Node& n1, 

 	   const Graph2Node& n2, bool _backward) : 

 	Graph1Node(!_backward ? n1 : n2), backward(_backward) { }

       Node(Invalid i) : Graph1Node(i), backward(true) { }

       bool operator==(const Node& v) const { 

 	return (backward==v.backward && 

 		static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));

       } 

       bool operator!=(const Node& v) const { 

 	return !(*this==v);

       }

     };

     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 MergeNodeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : 

     public P1<_Graph1>, public P2<_Graph2> {

   public :

     static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef P1<_Graph1> Parent1;

     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Node Graph1Node;

     typedef typename Parent2::Node Graph2Node;

   protected:

     MergeNodeGraphWrapperBaseBase() { }

   public:

     class Node : public Graph2Node {

       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Node() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Node(const Graph1Node& n1, 

 	   const Graph2Node& n2, bool _backward) : 

 	Graph2Node(n2), backward(_backward) { 

 	if (!backward) *this=n1;

       }

       Node(Invalid i) : Graph2Node(i), backward(true) { }

       bool operator==(const Node& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 

       } 

       bool operator!=(const Node& v) const { 

 	return !(*this==v);

       }

     };

     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 MergeNodeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : 

     public P1<_Graph1>, public P2<_Graph2> {

   public :

     static void printNode() { std::cout << "node: 1st is derived" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef P1<_Graph1> Parent1;

     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Node Graph1Node;

     typedef typename Parent2::Node Graph2Node;

   protected:

     MergeNodeGraphWrapperBaseBase() { }

   public:

     class Node : public Graph1Node {

       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Node() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Node(const Graph1Node& n1, 

 	   const Graph2Node& n2, bool _backward) : 

 	Graph1Node(n1), backward(_backward) { 

 	if (backward) *this=n2;

       }

       Node(Invalid i) : Graph1Node(i), backward(true) { }

       bool operator==(const Node& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 

       } 

       bool operator!=(const Node& v) const { 

 	return !(*this==v);

       }

     };

     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));

       this->setForward(i);

       if (*static_cast<Graph1Node*>(&i)==INVALID) {

 	Parent2::graph->first(*static_cast<Graph2Node*>(&i));

 	this->setBackward(i);

       }

     }

     void next(Node& i) const {

       if (this->forward(i)) {

 	Parent1::graph->next(*static_cast<Graph1Node*>(&i));

 	if (*static_cast<Graph1Node*>(&i)==INVALID) {

 	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));

 	  this->setBackward(i);

 	}

       } else {

 	Parent2::graph->next(*static_cast<Graph2Node*>(&i));

       }

     }

     int id(const Node& n) const { 

       if (this->forward(n)) 

 	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 (Parent::forward(n)) 

 	  return forward_map[n];

 	else 

 	  return backward_map[n];

       }

       void set(const Node& n, const _Value& value) {

 	if (Parent::forward(n)) 

 	  forward_map.set(n, value);

 	else 

 	  backward_map.set(n, value);

       }

 //       using ParentMap1::operator[];

 //       using ParentMap2::operator[];

     };

   };

   /*! A graph wrapper class 

     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 

   IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {

   public:

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef IterableGraphExtender<

       MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;

   protected:

     MergeNodeGraphWrapper() { }

   public:

     MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 

       Parent::Parent1::setGraph(_graph1);

       Parent::Parent2::setGraph(_graph2);

     }

   };

   /*! A grah wrapper base class 

     for merging the node-sets and edge-sets of 

     two node-disjoint graphs 

     into one graph.

     Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.

    */

   template <typename _Graph1, typename _Graph2, typename Enable=void>

   class MergeEdgeGraphWrapperBaseBase : 

     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {

   public:

     static void printEdge() { std::cout << "edge: generic" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;

     typedef typename Parent::Parent1 Parent1;

     typedef typename Parent::Parent2 Parent2;

 //     typedef P1<_Graph1> Parent1;

 //     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

   protected:

     MergeEdgeGraphWrapperBaseBase() { }

   public:

     class Edge : public Graph1Edge, public Graph2Edge {

       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const Graph1Edge& n1, 

 	   const Graph2Edge& n2, bool _backward) : 

 	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }

       Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }

       bool operator==(const Edge& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 

       } 

       bool operator!=(const Edge& v) const { 

 	return !(*this==v);

       }

     };

     using Parent::forward;

     using Parent::backward;

     using Parent::setForward;

     using Parent::setBackward;

     static bool forward(const Edge& e) { return !e.backward; }

     static bool backward(const Edge& e) { return e.backward; }

     static void setForward(Edge& e) { e.backward=false; }

     static void setBackward(Edge& e) { e.backward=true; }

   };

   /*! A graph wrapper base class 

     for merging the node-sets and edge-sets of 

     two node-disjoint graphs 

     into one graph.

     Specialization for the case when _Graph1::Edge and _Graph2::Edge

     are the same.

    */

   template <typename _Graph1, typename _Graph2>

   class MergeEdgeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : 

     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {

   public:

     static void printEdge() { std::cout << "edge: same" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;

     typedef typename Parent::Parent1 Parent1;

     typedef typename Parent::Parent2 Parent2;

 //     typedef P1<_Graph1> Parent1;

 //     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

   protected:

     MergeEdgeGraphWrapperBaseBase() { }

   public:

     class Edge : public Graph1Edge {

       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const Graph1Edge& n1, 

 	   const Graph2Edge& n2, bool _backward) : 

 	Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }

       Edge(Invalid i) : Graph1Edge(i), backward(true) { }

       bool operator==(const Edge& v) const { 

 	return (backward==v.backward && 

 		static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 

       }

       bool operator!=(const Edge& v) const { 

 	return !(*this==v);

       }

     };

     using Parent::forward;

     using Parent::backward;

     using Parent::setForward;

     using Parent::setBackward;

     static bool forward(const Edge& e) { return !e.backward; }

     static bool backward(const Edge& e) { return e.backward; }

     static void setForward(Edge& e) { e.backward=false; }

     static void setBackward(Edge& e) { e.backward=true; }

   };

   /*! A grah wrapper base class 

     for merging the node-sets and edge-sets of 

     two node-disjoint graphs 

     into one graph. 

     Specialized implementation for the case 

     when _Graph1::Edge is a base class and _Graph2::Edge

     is derived from it.

    */

   template <typename _Graph1, typename _Graph2>

   class MergeEdgeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : 

     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {

   public:

     static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;

     typedef typename Parent::Parent1 Parent1;

     typedef typename Parent::Parent2 Parent2;

 //     typedef P1<_Graph1> Parent1;

 //     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

   protected:

     MergeEdgeGraphWrapperBaseBase() { }

   public:

     class Edge : public Graph2Edge {

       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const Graph1Edge& n1, 

 	   const Graph2Edge& n2, bool _backward) : 

 	Graph2Edge(n2), backward(_backward) { 

 	if (!backward) *this=n1;

       }

       Edge(Invalid i) : Graph2Edge(i), backward(true) { }

       bool operator==(const Edge& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 

       } 

       bool operator!=(const Edge& v) const { 

 	return !(*this==v);

       }

     };

     using Parent::forward;

     using Parent::backward;

     using Parent::setForward;

     using Parent::setBackward;

     static bool forward(const Edge& e) { return !e.backward; }

     static bool backward(const Edge& e) { return e.backward; }

     static void setForward(Edge& e) { e.backward=false; }

     static void setBackward(Edge& e) { e.backward=true; }

   };

   /*! A grah wrapper base class 

     for merging the node-sets and edge-sets of 

     two node-disjoint graphs 

     into one graph. 

     Specialized implementation for the case 

     when _Graph1::Edge is derived from _Graph2::Edge.

    */

   template <typename _Graph1, typename _Graph2>

   class MergeEdgeGraphWrapperBaseBase<

     _Graph1, _Graph2, typename boost::enable_if<

     boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> : 

     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {

   public:

     static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;

     typedef typename Parent::Parent1 Parent1;

     typedef typename Parent::Parent2 Parent2;

 //     typedef P1<_Graph1> Parent1;

 //     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

   protected:

     MergeEdgeGraphWrapperBaseBase() { }

   public:

     class Edge : public Graph1Edge {

       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const Graph1Edge& n1, 

 	   const Graph2Edge& n2, bool _backward) : 

 	Graph1Edge(n1), backward(_backward) { 

 	if (backward) *this=n2;

       }

       Edge(Invalid i) : Graph1Edge(i), backward(true) { }

       bool operator==(const Edge& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 

       } 

       bool operator!=(const Edge& v) const { 

 	return !(*this==v);

       }

     };

     using Parent::forward;

     using Parent::backward;

     using Parent::setForward;

     using Parent::setBackward;

     static bool forward(const Edge& e) { return !e.backward; }

     static bool backward(const Edge& e) { return e.backward; }

     static void setForward(Edge& e) { e.backward=false; }

     static void setBackward(Edge& e) { e.backward=true; }

   };

   template <typename _Graph1, typename _Graph2>

   class MergeEdgeGraphWrapperBase : 

     public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {

   public:

     typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef typename Parent::Parent1 Parent1;

     typedef typename Parent::Parent2 Parent2;

     typedef typename Parent1::Node Graph1Node;

     typedef typename Parent2::Node Graph2Node;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     using Parent::first;

     void first(Edge& i) const {

       Parent1::graph->first(*static_cast<Graph1Edge*>(&i));

       this->setForward(i);

       if (*static_cast<Graph1Edge*>(&i)==INVALID) {

 	Parent2::graph->first(*static_cast<Graph2Edge*>(&i));

 	this->setBackward(i);

       }

     }

     void firstIn(Edge& i, const Node& n) const {

       if (forward(n)) {

 	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);

 	if (*static_cast<Graph1Edge*>(&i)==INVALID) 

 	  i=INVALID;

 	else

 	  this->setForward(i);

       } else {

 	Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);

 	this->setBackward(i);

       }

     }

     void firstOut(Edge& i, const Node& n) const {

       if (forward(n)) {

 	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);

 	if (*static_cast<Graph1Edge*>(&i)==INVALID) 

 	  i=INVALID;

 	else

 	  this->setForward(i);

       } else {

 	Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);

 	this->setBackward(i);

       }

     }

     using Parent::next;

     void next(Edge& i) const {

       if (forward(i)) {

 	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));

 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {

 	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));

 	  this->setBackward(i);

 	}

       } else {

 	Parent2::graph->next(*static_cast<Graph2Edge*>(&i));

       }

     }

     void nextIn(Edge& i) const {

       if (forward(i)) {

 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));

  	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;

       } else {

 	Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));

       }

     }

     void nextOut(Edge& i) const {

       if (Parent::forward(i)) {

 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));

  	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;

       } else {

 	Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));

       }

     }

     Node source(const Edge& i) const {

       if (forward(i)) {

 	return 

 	  Node(Parent1::graph->source(i), INVALID, false);

       } else {

 	return 

 	  Node(INVALID, Parent2::graph->source(i), true);

       }

     }

     Node target(const Edge& i) const {

       if (forward(i)) {

 	return 

 	  Node(Parent1::graph->target(i), INVALID, false);

       } else {

 	return 

 	  Node(INVALID, Parent2::graph->target(i), true);

       }

     }

     using Parent::id;

     int id(const Edge& n) const { 

       if (forward(n)) 

 	return this->Parent1::graph->id(n);

       else

 	return this->Parent2::graph->id(n);

     }

     template <typename _Value> 

     class EdgeMap { 

     protected:

       typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;

       typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;

       ParentMap1 forward_map;

       ParentMap2 backward_map;

     public:

       typedef _Value Value;

       typedef Edge Key;

       EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : 

 	forward_map(*(gw.Parent1::graph)), 

 	backward_map(*(gw.Parent2::graph)) { }

       EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, 

 	      const _Value& value) : 

 	forward_map(*(gw.Parent1::graph), value), 

 	backward_map(*(gw.Parent2::graph), value) { }

       _Value operator[](const Edge& n) const {

 	if (Parent::forward(n)) 

 	  return forward_map[n];

 	else 

 	  return backward_map[n];

       }

       void set(const Edge& n, const _Value& value) {

 	if (Parent::forward(n)) 

 	  forward_map.set(n, value);

 	else 

 	  backward_map.set(n, value);

       }

 //       using ParentMap1::operator[];

 //       using ParentMap2::operator[];

     };

   };

   /*! A graph wrapper class 

     for merging two node-disjoint graphs 

     into one graph. 

     Different implementations are according to the relation of 

     _Graph1::Edge and _Graph2::Edge. 

     If _Graph1::Edge and _Graph2::Edge are unrelated, then 

     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 

     is derived from both. 

     If _Graph1::Edge and _Graph2::Edge are the same type, then 

     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 

     is derived from _Graph1::Edge. 

     If one of _Graph1::Edge and _Graph2::Edge 

     is derived from the other one, then 

     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 

     is derived from the derived type.

     It does not satisfy 

   */

   template <typename _Graph1, typename _Graph2>

   class MergeEdgeGraphWrapper : public 

   IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {

   public:

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef IterableGraphExtender<

       MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;

   protected:

     MergeEdgeGraphWrapper() { }

   public:

     MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 

       Parent::Parent1::setGraph(_graph1);

       Parent::Parent2::setGraph(_graph2);

     }

   };

   /*! A graph wrapper base class for the following functionality.

     If a bijection is given between the node-sets of two graphs, 

     then the second one can be considered as a new edge-set 

     over th first node-set. 

    */

   template <typename _Graph, typename _EdgeSetGraph>

   class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {

   public:

     typedef GraphWrapperBase<_Graph> Parent; 

     typedef _Graph Graph;

     typedef _EdgeSetGraph EdgeSetGraph;

     typedef typename _Graph::Node Node;

     typedef typename _EdgeSetGraph::Node ENode;

   protected:

     EdgeSetGraph* edge_set_graph;

     typename Graph::NodeMap<ENode>* e_node;

     typename EdgeSetGraph::NodeMap<Node>* n_node;

     void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) { 

       edge_set_graph=&_edge_set_graph; 

     }

     /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .

     void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) { 

       n_node=&_n_node; 

     }

     /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .

     void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) { 

       e_node=&_e_node; 

     }

   public:

     class Edge : public EdgeSetGraph::Edge {

       typedef typename EdgeSetGraph::Edge Parent;

     public:

       Edge() { }

       Edge(const Parent& e) : Parent(e) { }

       Edge(Invalid i) : Parent(i) { }

     };

     using Parent::first;

     void first(Edge &e) const { 

       edge_set_graph->first(e);

     }

     void firstOut(Edge& e, const Node& n) const {

 //       cout << e_node << endl;

 //       cout << n_node << endl;

       edge_set_graph->firstOut(e, (*e_node)[n]);

     }

     void firstIn(Edge& e, const Node& n) const {

       edge_set_graph->firstIn(e, (*e_node)[n]);

     }

     using Parent::next;

     void next(Edge &e) const { 

       edge_set_graph->next(e);

     }

     void nextOut(Edge& e) const {

       edge_set_graph->nextOut(e);

     }

     void nextIn(Edge& e) const {

       edge_set_graph->nextIn(e);

     }

     Node source(const Edge& e) const { 

       return (*n_node)[edge_set_graph->source(e)];

     }

     Node target(const Edge& e) const { 

       return (*n_node)[edge_set_graph->target(e)];

     }

     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]);

     }

     using Parent::erase;

     void erase(const Edge& i) const { edge_set_graph->erase(i); }

     void clear() const { Parent::clear(); edge_set_graph->clear(); }

     bool forward(const Edge& e) const { return edge_set_graph->forward(e); }

     bool backward(const Edge& e) const { return edge_set_graph->backward(e); }

     int id(const Node& e) const { return Parent::id(e); }

     int id(const Edge& e) const { return edge_set_graph->id(e); }

     Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }

     template <typename _Value>

     class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {

     public:

       typedef typename EdgeSetGraph::EdgeMap<_Value> Parent; 

       typedef _Value Value;

       typedef Edge Key;

       EdgeMap(const NewEdgeSetGraphWrapperBase& gw) : 

 	Parent(*(gw.edge_set_graph)) { }

       EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) : 

 	Parent(*(gw.edge_set_graph), _value) { }

     };

   };

   /*! A graph wrapper class for the following functionality.

     If a bijection is given between the node-sets of two graphs, 

     then the second one can be considered as a new edge-set 

     over th first node-set. 

    */

   template <typename _Graph, typename _EdgeSetGraph>

   class NewEdgeSetGraphWrapper : 

     public IterableGraphExtender<

     NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {

   public:

     typedef _Graph Graph;

     typedef _EdgeSetGraph EdgeSetGraph;

     typedef IterableGraphExtender<

       NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;

   protected:

     NewEdgeSetGraphWrapper() { }

   public:

     NewEdgeSetGraphWrapper(_Graph& _graph, 

 			   _EdgeSetGraph& _edge_set_graph, 

 			   typename _Graph::

 			   NodeMap<typename _EdgeSetGraph::Node>& _e_node, 

 			   typename _EdgeSetGraph::

 			   NodeMap<typename _Graph::Node>& _n_node) { 

       setGraph(_graph);

       setEdgeSetGraph(_edge_set_graph);

       setNodeMap(_n_node);

       setENodeMap(_e_node);

     }

   };

   /*! 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 

     for merging graphs of type _Graph1 and _Graph2 

     which are given on the same node-set 

     (specially on the node-set of Graph1) 

     into one graph.

     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>

   class AugmentingGraphWrapperBase : 

     public P1<_Graph1> {

   public:

     void printAugment() const { std::cout << "generic" << std::endl; }

     typedef _Graph1 Graph1;

     typedef _Graph2 Graph2;

     typedef P1<_Graph1> Parent1;

     typedef P2<_Graph2> Parent2;

     typedef typename Parent1::Edge Graph1Edge;

     typedef typename Parent2::Edge Graph2Edge;

   protected:

     AugmentingGraphWrapperBase() { }

     _Graph2* graph2;

     void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }

   public:

     template <typename _Value> class EdgeMap;

     typedef typename Parent1::Node Node;

     class Edge : public Graph1Edge, public Graph2Edge {

       friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;

       template <typename _Value> friend class EdgeMap;

     protected:

       bool backward; //true, iff backward

     public:

       Edge() { }

       /// \todo =false is needed, or causes problems?

       /// If \c _backward is false, then we get an edge corresponding to the 

       /// original one, otherwise its oppositely directed pair is obtained.

       Edge(const Graph1Edge& n1, 

 	   const Graph2Edge& n2, bool _backward) : 

 	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }

       Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }

       bool operator==(const Edge& v) const { 

 	if (backward) 

 	  return (v.backward && 

 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 

 	else 

 	  return (!v.backward && 

 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 

       } 

       bool operator!=(const Edge& v) const { 

 	return !(*this==v);

       }

     };

     using Parent1::first;

     void first(Edge& i) const {

       Parent1::graph->first(*static_cast<Graph1Edge*>(&i));

       i.backward=false;

       if (*static_cast<Graph1Edge*>(&i)==INVALID) {

 	graph2->first(*static_cast<Graph2Edge*>(&i));

 	i.backward=true;

       }

     }

     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) {

 	graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);

 	i.backward=true;

       }

     }

     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) {

 	graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);

 	i.backward=true;

       }

     }

     using Parent1::next;

     void next(Edge& i) const {

       if (!(i.backward)) {

 	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));

 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {

 	  graph2->first(*static_cast<Graph2Edge*>(&i));

 	  i.backward=true;

 	}

       } else {

 	graph2->next(*static_cast<Graph2Edge*>(&i));

       }

     }

     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->firstIn(*static_cast<Graph2Edge*>(&i), n);

 	  i.backward=true;

 	}

       } else {

 	graph2->nextIn(*static_cast<Graph2Edge*>(&i));

       }

     }

     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->firstOut(*static_cast<Graph2Edge*>(&i), n);

 	  i.backward=true;

 	}

       } else {

 	graph2->nextOut(*static_cast<Graph2Edge*>(&i));

       }

     }

     Node source(const Edge& i) const {

       if (!(i.backward)) {

 	return Parent1::graph->source(i);

       } else {

 	return graph2->source(i);

       }

     }

     Node target(const Edge& i) const {

       if (!(i.backward)) {

 	return Parent1::graph->target(i);

       } else {

 	return graph2->target(i);

       }

     }

     int id(const Node& n) const {

       return Parent1::id(n);

     };

     int id(const Edge& n) const { 

       if (!n.backward) 

 	return this->Parent1::graph->id(n);

       else

 	return this->graph2->id(n);

     }

     template <typename _Value> 

     class EdgeMap { 

     protected:

       typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;

       typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;

       ParentMap1 forward_map;

       ParentMap2 backward_map;

     public:

       typedef _Value Value;

       typedef Edge Key;

       EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) : 

 	forward_map(*(gw.Parent1::graph)),