source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1305:c3dc75d4af24

/* -*- 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 Combinatorial Optimization Research Group, 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)), 
        backward_map(*(gw.graph2)) { }
      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw, 
              const _Value& value) : 
        forward_map(*(gw.Parent1::graph), value), 
        backward_map(*(gw.graph2), value) { }
      _Value operator[](const Edge& n) const {
        if (!n.backward) 
          return forward_map[n];
        else 
          return backward_map[n];
      }
      void set(const Edge& 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 class 
    for merging two graphs (of type _Graph1 and _Graph2)
    with 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.
   */  
  template <typename _Graph1, typename _Graph2>
  class AugmentingGraphWrapper : public 
  IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
  public:
    typedef 
    IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
    Parent;
    typedef _Graph1 Graph1;
    typedef _Graph2 Graph2;
  protected:
    AugmentingGraphWrapper() { }
  public:
    AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
      setGraph(_graph1); 
      setGraph2(_graph2);
    }
  };

} //namespace lemon

#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H