marci@915: /* -*- C++ -*-
alpar@921:  * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
marci@915:  *
marci@915:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
marci@915:  * (Egervary Combinatorial Optimization Research Group, EGRES).
marci@915:  *
marci@915:  * Permission to use, modify and distribute this software is granted
marci@915:  * provided that this copyright notice appears in all copies. For
marci@915:  * precise terms see the accompanying LICENSE file.
marci@915:  *
marci@915:  * This software is provided "AS IS" with no warranty of any kind,
marci@915:  * express or implied, and with no claim as to its suitability for any
marci@915:  * purpose.
marci@915:  *
marci@915:  */
marci@915: 
alpar@921: #ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
alpar@921: #define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
marci@917: 
alpar@921: #include <lemon/invalid.h>
alpar@921: #include <lemon/maps.h>
alpar@921: #include <lemon/map_defines.h>
alpar@921: #include <lemon/graph_wrapper.h>
marci@915: #include <iostream>
marci@1013: 
marci@1008: using std::cout;
marci@1008: using std::endl;
marci@915: 
marci@1007: #include <boost/type_traits.hpp>
marci@1007: #include <boost/utility/enable_if.hpp>
marci@1007: 
alpar@921: namespace lemon {
marci@915: 
marci@1007:   template <class _Graph1>
marci@1007:   class P1 : public GraphWrapperBase<_Graph1> {
marci@1007:   };
marci@1007: 
marci@1007:   template <class _Graph2>
marci@1007:   class P2 : public GraphWrapperBase<_Graph2> {
marci@1007:   };
marci@1007: 
marci@1013: 
marci@1002:   template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1025:   class MergeNodeGraphWrapperBaseBase : 
marci@1007:     public P1<_Graph1>, public P2<_Graph2> {
marci@915:   public:
marci@1013:     static void printNode() { std::cout << "node: generic" << std::endl; }
marci@1002:     typedef _Graph1 Graph1;
marci@1002:     typedef _Graph2 Graph2;
marci@1007:     typedef P1<_Graph1> Parent1;
marci@1007:     typedef P2<_Graph2> Parent2;
marci@1002:     typedef typename Parent1::Node Graph1Node;
marci@1002:     typedef typename Parent2::Node Graph2Node;
marci@1002:   protected:
marci@1025:     MergeNodeGraphWrapperBaseBase() { }
marci@1002:   public:
marci@915: 
marci@915:     class Node : public Graph1Node, public Graph2Node {
marci@1025:       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@915:     protected:
marci@915:       bool backward; //true, iff backward
marci@915:     public:
marci@915:       Node() { }
marci@915:       /// \todo =false is needed, or causes problems?
marci@915:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@915:       /// original one, otherwise its oppositely directed pair is obtained.
marci@915:       Node(const Graph1Node& n1, 
marci@915: 	   const Graph2Node& n2, bool _backward) : 
marci@915: 	Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
marci@915:       Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
marci@915:       bool operator==(const Node& v) const { 
marci@1013: 	if (backward) 
marci@1013: 	  return (v.backward && 
marci@1013: 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 
marci@1013: 	else 
marci@1013: 	  return (!v.backward && 
marci@1013: 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 
marci@915:       } 
marci@915:       bool operator!=(const Node& v) const { 
marci@1013: 	return !(*this==v);
marci@915:       }
marci@915:     };
marci@915: 
marci@1025:     static bool forward(const Node& n) { return !n.backward; }
marci@1025:     static bool backward(const Node& n) { return n.backward; }
marci@1025:     static void setForward(Node& n) { n.backward=false; }
marci@1025:     static void setBackward(Node& n) { n.backward=true; }    
marci@1002:   };
marci@1002: 
marci@1013: 
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1025:   class MergeNodeGraphWrapperBaseBase<
marci@1007:     _Graph1, _Graph2, typename boost::enable_if<
marci@1007:     boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
marci@1007:     public P1<_Graph1>, public P2<_Graph2> {
marci@1013:   public:
marci@1013:     static void printNode() { std::cout << "node: same" << std::endl; }
marci@1007:     typedef _Graph1 Graph1;
marci@1007:     typedef _Graph2 Graph2;
marci@1007:     typedef P1<_Graph1> Parent1;
marci@1007:     typedef P2<_Graph2> Parent2;
marci@1007:     typedef typename Parent1::Node Graph1Node;
marci@1007:     typedef typename Parent2::Node Graph2Node;
marci@1007:   protected:
marci@1025:     MergeNodeGraphWrapperBaseBase() { }
marci@1007:   public:
marci@1013: 
marci@1013:     class Node : public Graph1Node {
marci@1025:       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1013:     protected:
marci@1013:       bool backward; //true, iff backward
marci@1013:     public:
marci@1013:       Node() { }
marci@1013:       /// \todo =false is needed, or causes problems?
marci@1013:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1013:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1013:       Node(const Graph1Node& n1, 
marci@1013: 	   const Graph2Node& n2, bool _backward) : 
marci@1025: 	Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
marci@1013:       Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1013:       bool operator==(const Node& v) const { 
marci@1013: 	return (backward==v.backward && 
marci@1013: 		static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
marci@1013:       } 
marci@1013:       bool operator!=(const Node& v) const { 
marci@1013: 	return !(*this==v);
marci@1013:       }
marci@1013:     };
marci@1013: 
marci@1025:     static bool forward(const Node& n) { return !n.backward; }
marci@1025:     static bool backward(const Node& n) { return n.backward; }
marci@1025:     static void setForward(Node& n) { n.backward=false; }
marci@1025:     static void setBackward(Node& n) { n.backward=true; }
marci@1007:   };
marci@1007: 
marci@1013: 
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1025:   class MergeNodeGraphWrapperBaseBase<
marci@1007:     _Graph1, _Graph2, typename boost::enable_if<
marci@1007:     boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
marci@1007:     public P1<_Graph1>, public P2<_Graph2> {
marci@1007:   public :
marci@1013:     static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
marci@1007:     typedef _Graph1 Graph1;
marci@1007:     typedef _Graph2 Graph2;
marci@1007:     typedef P1<_Graph1> Parent1;
marci@1007:     typedef P2<_Graph2> Parent2;
marci@1007:     typedef typename Parent1::Node Graph1Node;
marci@1007:     typedef typename Parent2::Node Graph2Node;
marci@1007:   protected:
marci@1025:     MergeNodeGraphWrapperBaseBase() { }
marci@1007:   public:
marci@1016: 
marci@1016:     class Node : public Graph2Node {
marci@1025:       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016:     protected:
marci@1016:       bool backward; //true, iff backward
marci@1016:     public:
marci@1016:       Node() { }
marci@1016:       /// \todo =false is needed, or causes problems?
marci@1016:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1016:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1016:       Node(const Graph1Node& n1, 
marci@1016: 	   const Graph2Node& n2, bool _backward) : 
marci@1016: 	Graph2Node(n2), backward(_backward) { 
marci@1016: 	if (!backward) *this=n1;
marci@1016:       }
marci@1016:       Node(Invalid i) : Graph2Node(i), backward(true) { }
marci@1016:       bool operator==(const Node& v) const { 
marci@1016: 	if (backward) 
marci@1016: 	  return (v.backward && 
marci@1016: 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 
marci@1016: 	else 
marci@1016: 	  return (!v.backward && 
marci@1016: 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 
marci@1016:       } 
marci@1016:       bool operator!=(const Node& v) const { 
marci@1016: 	return !(*this==v);
marci@1016:       }
marci@1016:     };
marci@1016: 
marci@1025:     static bool forward(const Node& n) { return !n.backward; }
marci@1025:     static bool backward(const Node& n) { return n.backward; }
marci@1025:     static void setForward(Node& n) { n.backward=false; }
marci@1025:     static void setBackward(Node& n) { n.backward=true; }
marci@1025:   };
marci@1025:   
marci@1016: 
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1025:   class MergeNodeGraphWrapperBaseBase<
marci@1007:     _Graph1, _Graph2, typename boost::enable_if<
marci@1007:     boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : 
marci@1007:     public P1<_Graph1>, public P2<_Graph2> {
marci@1007:   public :
marci@1013:     static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
marci@1007:     typedef _Graph1 Graph1;
marci@1007:     typedef _Graph2 Graph2;
marci@1007:     typedef P1<_Graph1> Parent1;
marci@1007:     typedef P2<_Graph2> Parent2;
marci@1007:     typedef typename Parent1::Node Graph1Node;
marci@1007:     typedef typename Parent2::Node Graph2Node;
marci@1007:   protected:
marci@1025:     MergeNodeGraphWrapperBaseBase() { }
marci@1007:   public:
marci@1016: 
marci@1016:     class Node : public Graph1Node {
marci@1025:       friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016:     protected:
marci@1016:       bool backward; //true, iff backward
marci@1016:     public:
marci@1016:       Node() { }
marci@1016:       /// \todo =false is needed, or causes problems?
marci@1016:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1016:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1016:       Node(const Graph1Node& n1, 
marci@1016: 	   const Graph2Node& n2, bool _backward) : 
marci@1016: 	Graph1Node(n1), backward(_backward) { 
marci@1016: 	if (backward) *this=n2;
marci@1016:       }
marci@1016:       Node(Invalid i) : Graph1Node(i), backward(true) { }
marci@1016:       bool operator==(const Node& v) const { 
marci@1016: 	if (backward) 
marci@1016: 	  return (v.backward && 
marci@1016: 		  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 
marci@1016: 	else 
marci@1016: 	  return (!v.backward && 
marci@1016: 		  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 
marci@1016:       } 
marci@1016:       bool operator!=(const Node& v) const { 
marci@1016: 	return !(*this==v);
marci@1016:       }
marci@1016:     };
marci@1016: 
marci@1025:     static bool forward(const Node& n) { return !n.backward; }
marci@1025:     static bool backward(const Node& n) { return n.backward; }
marci@1025:     static void setForward(Node& n) { n.backward=false; }
marci@1025:     static void setBackward(Node& n) { n.backward=true; }
marci@1025:   };
marci@1025: 
marci@1025: 
marci@1025:   template <typename _Graph1, typename _Graph2>
marci@1025:   class MergeNodeGraphWrapperBase : 
marci@1025:     public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
marci@1025:   public:
marci@1025:     typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1025:     typedef _Graph1 Graph1;
marci@1025:     typedef _Graph2 Graph2;
marci@1025:     typedef P1<_Graph1> Parent1;
marci@1025:     typedef P2<_Graph2> Parent2;
marci@1025:     typedef typename Parent1::Node Graph1Node;
marci@1025:     typedef typename Parent2::Node Graph2Node;
marci@1025: 
marci@1025:     typedef typename Parent::Node Node; 
marci@1007:     class Edge { };
marci@1016:     
marci@1016:     void first(Node& i) const {
marci@1016:       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
marci@1025:       this->setForward(i);
marci@1016:       if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1016: 	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1025: 	this->setBackward(i);
marci@1016:       }
marci@1016:     }
marci@1016:     void next(Node& i) const {
marci@1025:       if (this->forward(i)) {
marci@1016: 	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
marci@1016: 	if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1016: 	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1025: 	  this->setBackward(i);
marci@1016: 	}
marci@1016:       } else {
marci@1016: 	Parent2::graph->next(*static_cast<Graph2Node*>(&i));
marci@1016:       }
marci@1016:     }
marci@1016: 
marci@1016:     int id(const Node& n) const { 
marci@1025:       if (this->forward(n)) 
marci@1016: 	return this->Parent1::graph->id(n);
marci@1016:       else
marci@1016: 	return this->Parent2::graph->id(n);
marci@1016:     }
marci@1016: 
marci@1016:     template <typename _Value> 
marci@1016:     class NodeMap { 
marci@1016:     protected:
marci@1016:       typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
marci@1016:       typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
marci@1016:       ParentMap1 forward_map;
marci@1016:       ParentMap2 backward_map;
marci@1016:     public:
marci@1016:       typedef _Value Value;
marci@1016:       typedef Node Key;
marci@1016:       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
marci@1016: 	forward_map(*(gw.Parent1::graph)), 
marci@1016: 	backward_map(*(gw.Parent2::graph)) { }
marci@1016:       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
marci@1016: 	      const _Value& value) : 
marci@1016: 	forward_map(*(gw.Parent1::graph), value), 
marci@1016: 	backward_map(*(gw.Parent2::graph), value) { }
marci@1016:       _Value operator[](const Node& n) const {
marci@1025: 	if (Parent::forward(n)) 
marci@1016: 	  return forward_map[n];
marci@1016: 	else 
marci@1016: 	  return backward_map[n];
marci@1016:       }
marci@1016:       void set(const Node& n, const _Value& value) {
marci@1025: 	if (Parent::forward(n)) 
marci@1016: 	  forward_map.set(n, value);
marci@1016: 	else 
marci@1016: 	  backward_map.set(n, value);
marci@1016:       }
marci@1016: //       using ParentMap1::operator[];
marci@1016: //       using ParentMap2::operator[];
marci@1016:     };
marci@1016: 
marci@1007:   };
marci@1007: 
marci@1002: 
marci@1013:   /*! A graph wrapper class 
marci@1025:     for merging the node-set of two node-disjoint graphs 
marci@1025:     into the node-set of one graph. 
marci@1025:     Different implementations are according to the relation of 
marci@1025:     _Graph1::Node and _Graph2::Node. 
marci@1025:     If _Graph1::Node and _Graph2::Node are unrelated, then 
marci@1025:     MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
marci@1025:     is derived from both. 
marci@1025:     If _Graph1::Node and _Graph2::Node are the same type, then 
marci@1025:     MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
marci@1025:     is derived from _Graph1::Node. 
marci@1025:     If one of _Graph1::Node and _Graph2::Node 
marci@1025:     is derived from the other one, then 
marci@1025:     MergeNodeGraphWrapper<_Graph1, _Graph2>::Node 
marci@1025:     is derived from the derived type.
marci@1025:     It does not satisfy 
marci@1013:     StaticGraph concept as it has no edge-set which 
marci@1013:     works together with the node-set.
marci@1025:   */
marci@1009:   template <typename _Graph1, typename _Graph2>
marci@1002:   class MergeNodeGraphWrapper : public 
marci@1009:   IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1002:   public:
marci@1002:     typedef _Graph1 Graph1;
marci@1002:     typedef _Graph2 Graph2;
marci@1002:     typedef IterableGraphExtender<
marci@1009:       MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1002:   protected:
marci@1002:     MergeNodeGraphWrapper() { }
marci@1002:   public:
marci@1002:     MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
marci@1002:       Parent::Parent1::setGraph(_graph1);
marci@1002:       Parent::Parent2::setGraph(_graph2);
marci@1002:     }
marci@915:   };
marci@915: 
marci@1009: 
marci@1013:   /*! A grah wrapper base class 
marci@1013:     for merging the node-sets and edge-sets of 
marci@1009:     two node-disjoint graphs 
marci@1009:     into one graph.
marci@1013:     Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
marci@1009:    */
marci@1009:   template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1026:   class MergeEdgeGraphWrapperBaseBase : 
marci@1009:     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1009:   public:
marci@1013:     static void printEdge() { std::cout << "edge: generic" << std::endl; }
marci@1009:     typedef _Graph1 Graph1;
marci@1009:     typedef _Graph2 Graph2;
marci@1009:     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1009:     typedef typename Parent::Parent1 Parent1;
marci@1009:     typedef typename Parent::Parent2 Parent2;
marci@1009: //     typedef P1<_Graph1> Parent1;
marci@1009: //     typedef P2<_Graph2> Parent2;
marci@1009:     typedef typename Parent1::Edge Graph1Edge;
marci@1009:     typedef typename Parent2::Edge Graph2Edge;
marci@1009:   protected:
marci@1026:     MergeEdgeGraphWrapperBaseBase() { }
marci@1009:   public:
marci@1009: 
marci@1009:     class Edge : public Graph1Edge, public Graph2Edge {
marci@1026:       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1009:     protected:
marci@1009:       bool backward; //true, iff backward
marci@1009:     public:
marci@1009:       Edge() { }
marci@1009:       /// \todo =false is needed, or causes problems?
marci@1009:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1009:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1009:       Edge(const Graph1Edge& n1, 
marci@1009: 	   const Graph2Edge& n2, bool _backward) : 
marci@1009: 	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1009:       Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1009:       bool operator==(const Edge& v) const { 
marci@1013: 	if (backward) 
marci@1013: 	  return (v.backward && 
marci@1013: 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 
marci@1013: 	else 
marci@1013: 	  return (!v.backward && 
marci@1013: 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 
marci@1009:       } 
marci@1009:       bool operator!=(const Edge& v) const { 
marci@1013: 	return !(*this==v);
marci@1009:       }
marci@1009:     };
marci@1009: 
marci@1025:     using Parent::forward;
marci@1025:     using Parent::backward;
marci@1026:     using Parent::setForward;
marci@1026:     using Parent::setBackward;
marci@1026:     static bool forward(const Edge& e) { return !e.backward; }
marci@1026:     static bool backward(const Edge& e) { return e.backward; }
marci@1026:     static void setForward(Edge& e) { e.backward=false; }
marci@1026:     static void setBackward(Edge& e) { e.backward=true; }
marci@1026:   };
marci@1025: 
marci@1009: 
marci@1009: 
marci@1013:   /*! A graph wrapper base class 
marci@1013:     for merging the node-sets and edge-sets of 
marci@1013:     two node-disjoint graphs 
marci@1013:     into one graph.
marci@1013:     Specialization for the case when _Graph1::Edge and _Graph2::Edge
marci@1013:     are the same.
marci@1013:    */
marci@1013:   template <typename _Graph1, typename _Graph2>
marci@1026:   class MergeEdgeGraphWrapperBaseBase<
marci@1013:     _Graph1, _Graph2, typename boost::enable_if<
marci@1016:     boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : 
marci@1013:     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1013:   public:
marci@1013:     static void printEdge() { std::cout << "edge: same" << std::endl; }
marci@1013:     typedef _Graph1 Graph1;
marci@1013:     typedef _Graph2 Graph2;
marci@1013:     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1013:     typedef typename Parent::Parent1 Parent1;
marci@1013:     typedef typename Parent::Parent2 Parent2;
marci@1013: //     typedef P1<_Graph1> Parent1;
marci@1013: //     typedef P2<_Graph2> Parent2;
marci@1013:     typedef typename Parent1::Edge Graph1Edge;
marci@1013:     typedef typename Parent2::Edge Graph2Edge;
marci@1013:   protected:
marci@1026:     MergeEdgeGraphWrapperBaseBase() { }
marci@1013:   public:
marci@1013: 
marci@1013:     class Edge : public Graph1Edge {
marci@1026:       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1013:     protected:
marci@1013:       bool backward; //true, iff backward
marci@1013:     public:
marci@1013:       Edge() { }
marci@1013:       /// \todo =false is needed, or causes problems?
marci@1013:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1013:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1013:       Edge(const Graph1Edge& n1, 
marci@1013: 	   const Graph2Edge& n2, bool _backward) : 
marci@1025: 	Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
marci@1013:       Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1013:       bool operator==(const Edge& v) const { 
marci@1013: 	return (backward==v.backward && 
marci@1013: 		static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 
marci@1013:       }
marci@1013:       bool operator!=(const Edge& v) const { 
marci@1013: 	return !(*this==v);
marci@1013:       }
marci@1013:     };
marci@1013: 
marci@1025:     using Parent::forward;
marci@1025:     using Parent::backward;
marci@1026:     using Parent::setForward;
marci@1026:     using Parent::setBackward;
marci@1026:     static bool forward(const Edge& e) { return !e.backward; }
marci@1026:     static bool backward(const Edge& e) { return e.backward; }
marci@1026:     static void setForward(Edge& e) { e.backward=false; }
marci@1026:     static void setBackward(Edge& e) { e.backward=true; }
marci@1013:   };
marci@1013: 
marci@1013: 
marci@1016:   /*! A grah wrapper base class 
marci@1016:     for merging the node-sets and edge-sets of 
marci@1016:     two node-disjoint graphs 
marci@1016:     into one graph. 
marci@1016:     Specialized implementation for the case 
marci@1016:     when _Graph1::Edge is a base class and _Graph2::Edge
marci@1016:     is derived from it.
marci@1016:    */
marci@1016:   template <typename _Graph1, typename _Graph2>
marci@1026:   class MergeEdgeGraphWrapperBaseBase<
marci@1016:     _Graph1, _Graph2, typename boost::enable_if<
marci@1016:     boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : 
marci@1016:     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016:   public:
marci@1016:     static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
marci@1016:     typedef _Graph1 Graph1;
marci@1016:     typedef _Graph2 Graph2;
marci@1016:     typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
marci@1016:     typedef typename Parent::Parent1 Parent1;
marci@1016:     typedef typename Parent::Parent2 Parent2;
marci@1016: //     typedef P1<_Graph1> Parent1;
marci@1016: //     typedef P2<_Graph2> Parent2;
marci@1016:     typedef typename Parent1::Edge Graph1Edge;
marci@1016:     typedef typename Parent2::Edge Graph2Edge;
marci@1016:   protected:
marci@1026:     MergeEdgeGraphWrapperBaseBase() { }
marci@1016:   public:
marci@1016: 
marci@1016:     class Edge : public Graph2Edge {
marci@1026:       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016:     protected:
marci@1016:       bool backward; //true, iff backward
marci@1016:     public:
marci@1016:       Edge() { }
marci@1016:       /// \todo =false is needed, or causes problems?
marci@1016:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1016:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1016:       Edge(const Graph1Edge& n1, 
marci@1016: 	   const Graph2Edge& n2, bool _backward) : 
marci@1016: 	Graph2Edge(n2), backward(_backward) { 
marci@1016: 	if (!backward) *this=n1;
marci@1016:       }
marci@1016:       Edge(Invalid i) : Graph2Edge(i), backward(true) { }
marci@1016:       bool operator==(const Edge& v) const { 
marci@1016: 	if (backward) 
marci@1016: 	  return (v.backward && 
marci@1016: 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 
marci@1016: 	else 
marci@1016: 	  return (!v.backward && 
marci@1016: 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 
marci@1016:       } 
marci@1016:       bool operator!=(const Edge& v) const { 
marci@1016: 	return !(*this==v);
marci@1016:       }
marci@1016:     };
marci@1016: 
marci@1025:     using Parent::forward;
marci@1025:     using Parent::backward;
marci@1026:     using Parent::setForward;
marci@1026:     using Parent::setBackward;
marci@1026:     static bool forward(const Edge& e) { return !e.backward; }
marci@1026:     static bool backward(const Edge& e) { return e.backward; }
marci@1026:     static void setForward(Edge& e) { e.backward=false; }
marci@1026:     static void setBackward(Edge& e) { e.backward=true; }
marci@1016:   };
marci@1016: 
marci@1016: 
marci@1016:   /*! A grah wrapper base class 
marci@1016:     for merging the node-sets and edge-sets of 
marci@1016:     two node-disjoint graphs 
marci@1016:     into one graph. 
marci@1016:     Specialized implementation for the case 
marci@1016:     when _Graph1::Edge is derived from _Graph2::Edge.
marci@1016:    */
marci@1016:   template <typename _Graph1, typename _Graph2>
marci@1026:   class MergeEdgeGraphWrapperBaseBase<
marci@1016:     _Graph1, _Graph2, typename boost::enable_if<
marci@1016:     boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> : 
marci@1016:     public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
marci@1016:   public:
marci@1016:     static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
marci@1016:     typedef _Graph1 Graph1;
marci@1016:     typedef _Graph2 Graph2;
marci@1026:     typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1016:     typedef typename Parent::Parent1 Parent1;
marci@1016:     typedef typename Parent::Parent2 Parent2;
marci@1016: //     typedef P1<_Graph1> Parent1;
marci@1016: //     typedef P2<_Graph2> Parent2;
marci@1016:     typedef typename Parent1::Edge Graph1Edge;
marci@1016:     typedef typename Parent2::Edge Graph2Edge;
marci@1016:   protected:
marci@1026:     MergeEdgeGraphWrapperBaseBase() { }
marci@1016:   public:
marci@1016: 
marci@1016:     class Edge : public Graph1Edge {
marci@1026:       friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
marci@1016:     protected:
marci@1016:       bool backward; //true, iff backward
marci@1016:     public:
marci@1016:       Edge() { }
marci@1016:       /// \todo =false is needed, or causes problems?
marci@1016:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1016:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1016:       Edge(const Graph1Edge& n1, 
marci@1016: 	   const Graph2Edge& n2, bool _backward) : 
marci@1016: 	Graph1Edge(n1), backward(_backward) { 
marci@1016: 	if (backward) *this=n2;
marci@1016:       }
marci@1016:       Edge(Invalid i) : Graph1Edge(i), backward(true) { }
marci@1016:       bool operator==(const Edge& v) const { 
marci@1016: 	if (backward) 
marci@1016: 	  return (v.backward && 
marci@1016: 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 
marci@1016: 	else 
marci@1016: 	  return (!v.backward && 
marci@1016: 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 
marci@1016:       } 
marci@1016:       bool operator!=(const Edge& v) const { 
marci@1016: 	return !(*this==v);
marci@1016:       }
marci@1016:     };
marci@1016: 
marci@1025:     using Parent::forward;
marci@1025:     using Parent::backward;
marci@1026:     using Parent::setForward;
marci@1026:     using Parent::setBackward;
marci@1026:     static bool forward(const Edge& e) { return !e.backward; }
marci@1026:     static bool backward(const Edge& e) { return e.backward; }
marci@1026:     static void setForward(Edge& e) { e.backward=false; }
marci@1026:     static void setBackward(Edge& e) { e.backward=true; }
marci@1026:   };
marci@1026: 
marci@1026: 
marci@1026:   template <typename _Graph1, typename _Graph2>
marci@1026:   class MergeEdgeGraphWrapperBase : 
marci@1026:     public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {
marci@1026:   public:
marci@1026:     typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
marci@1026:     typedef _Graph1 Graph1;
marci@1026:     typedef _Graph2 Graph2;
marci@1026:     typedef typename Parent::Parent1 Parent1;
marci@1026:     typedef typename Parent::Parent2 Parent2;
marci@1026:     typedef typename Parent1::Node Graph1Node;
marci@1026:     typedef typename Parent2::Node Graph2Node;
marci@1026:     typedef typename Parent1::Edge Graph1Edge;
marci@1026:     typedef typename Parent2::Edge Graph2Edge;
marci@1026: 
marci@1026:     typedef typename Parent::Node Node;
marci@1026:     typedef typename Parent::Edge Edge;
marci@1025: 
marci@1016:     using Parent::first;
marci@1016:     void first(Edge& i) const {
marci@1016:       Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
marci@1026:       this->setForward(i);
marci@1016:       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1016: 	Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
marci@1026: 	this->setBackward(i);
marci@1016:       }
marci@1016:     }
marci@1016:     void firstIn(Edge& i, const Node& n) const {
marci@1026:       if (forward(n)) {
marci@1025: 	Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
marci@1025: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
marci@1025: 	  i=INVALID;
marci@1025: 	else
marci@1026: 	  this->setForward(i);
marci@1025:       } else {
marci@1016: 	Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1026: 	this->setBackward(i);
marci@1016:       }
marci@1016:     }
marci@1016:     void firstOut(Edge& i, const Node& n) const {
marci@1026:       if (forward(n)) {
marci@1025: 	Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
marci@1025: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) 
marci@1025: 	  i=INVALID;
marci@1026: 	else
marci@1026: 	  this->setForward(i);
marci@1025:       } else {
marci@1016: 	Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1026: 	this->setBackward(i);
marci@1016:       }
marci@1016:     }
marci@1016: 
marci@1016:     using Parent::next;
marci@1016:     void next(Edge& i) const {
marci@1026:       if (forward(i)) {
marci@1016: 	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
marci@1016: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1016: 	  Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
marci@1026: 	  this->setBackward(i);
marci@1016: 	}
marci@1016:       } else {
marci@1016: 	Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
marci@1016:       }
marci@1016:     }
marci@1016:     void nextIn(Edge& i) const {
marci@1026:       if (forward(i)) {
marci@1016: 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
marci@1025:  	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
marci@1016:       } else {
marci@1016: 	Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
marci@1016:       }
marci@1016:     }
marci@1016:     void nextOut(Edge& i) const {
marci@1026:       if (Parent::forward(i)) {
marci@1016: 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
marci@1025:  	if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
marci@1016:       } else {
marci@1016: 	Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
marci@1016:       }
marci@1016:     }
marci@1016: 
marci@1016:     Node source(const Edge& i) const {
marci@1026:       if (forward(i)) {
marci@1016: 	return 
marci@1016: 	  Node(Parent1::graph->source(i), INVALID, false);
marci@1016:       } else {
marci@1016: 	return 
marci@1016: 	  Node(INVALID, Parent2::graph->source(i), true);
marci@1016:       }
marci@1016:     }
marci@1016: 
marci@1016:     Node target(const Edge& i) const {
marci@1026:       if (forward(i)) {
marci@1016: 	return 
marci@1016: 	  Node(Parent1::graph->target(i), INVALID, false);
marci@1016:       } else {
marci@1016: 	return 
marci@1016: 	  Node(INVALID, Parent2::graph->target(i), true);
marci@1016:       }
marci@1016:     }
marci@1016: 
marci@1016:     using Parent::id;
marci@1016:     int id(const Edge& n) const { 
marci@1026:       if (forward(n)) 
marci@1016: 	return this->Parent1::graph->id(n);
marci@1016:       else
marci@1016: 	return this->Parent2::graph->id(n);
marci@1016:     }
marci@1016: 
marci@1016:     template <typename _Value> 
marci@1016:     class EdgeMap { 
marci@1016:     protected:
marci@1016:       typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
marci@1016:       typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
marci@1016:       ParentMap1 forward_map;
marci@1016:       ParentMap2 backward_map;
marci@1016:     public:
marci@1016:       typedef _Value Value;
marci@1016:       typedef Edge Key;
marci@1016:       EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
marci@1016: 	forward_map(*(gw.Parent1::graph)), 
marci@1016: 	backward_map(*(gw.Parent2::graph)) { }
marci@1016:       EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, 
marci@1016: 	      const _Value& value) : 
marci@1016: 	forward_map(*(gw.Parent1::graph), value), 
marci@1016: 	backward_map(*(gw.Parent2::graph), value) { }
marci@1016:       _Value operator[](const Edge& n) const {
marci@1026: 	if (Parent::forward(n)) 
marci@1016: 	  return forward_map[n];
marci@1016: 	else 
marci@1016: 	  return backward_map[n];
marci@1016:       }
marci@1016:       void set(const Edge& n, const _Value& value) {
marci@1026: 	if (Parent::forward(n)) 
marci@1016: 	  forward_map.set(n, value);
marci@1016: 	else 
marci@1016: 	  backward_map.set(n, value);
marci@1016:       }
marci@1016: //       using ParentMap1::operator[];
marci@1016: //       using ParentMap2::operator[];
marci@1016:     };
marci@1016: 
marci@1016:   };
marci@1016: 
marci@1016: 
marci@1026: 
marci@1013:   /*! A graph wrapper class 
marci@1026:     for merging two node-disjoint graphs 
marci@1026:     into one graph. 
marci@1026:     Different implementations are according to the relation of 
marci@1026:     _Graph1::Edge and _Graph2::Edge. 
marci@1026:     If _Graph1::Edge and _Graph2::Edge are unrelated, then 
marci@1026:     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 
marci@1026:     is derived from both. 
marci@1026:     If _Graph1::Edge and _Graph2::Edge are the same type, then 
marci@1026:     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 
marci@1026:     is derived from _Graph1::Edge. 
marci@1026:     If one of _Graph1::Edge and _Graph2::Edge 
marci@1026:     is derived from the other one, then 
marci@1026:     MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge 
marci@1026:     is derived from the derived type.
marci@1026:     It does not satisfy 
marci@1026:   */
marci@1009:   template <typename _Graph1, typename _Graph2>
marci@1009:   class MergeEdgeGraphWrapper : public 
marci@1009:   IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
marci@1009:   public:
marci@1009:     typedef _Graph1 Graph1;
marci@1009:     typedef _Graph2 Graph2;
marci@1009:     typedef IterableGraphExtender<
marci@1009:       MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
marci@1009:   protected:
marci@1009:     MergeEdgeGraphWrapper() { }
marci@1009:   public:
marci@1009:     MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
marci@1009:       Parent::Parent1::setGraph(_graph1);
marci@1009:       Parent::Parent2::setGraph(_graph2);
marci@1009:     }
marci@1009:   };
marci@1009: 
marci@1008:   
marci@1013:   /*! A graph wrapper base class for the following functionality.
marci@1013:     If a bijection is given between the node-sets of two graphs, 
marci@1013:     then the second one can be considered as a new edge-set 
marci@1013:     over th first node-set. 
marci@1013:    */
marci@1008:   template <typename _Graph, typename _EdgeSetGraph>
marci@1008:   class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
marci@1008:   public:
marci@1008:     typedef GraphWrapperBase<_Graph> Parent; 
marci@1008:     typedef _Graph Graph;
marci@1008:     typedef _EdgeSetGraph EdgeSetGraph;
marci@1008:     typedef typename _Graph::Node Node;
marci@1008:     typedef typename _EdgeSetGraph::Node ENode;
marci@1008:   protected:
marci@1008:     EdgeSetGraph* edge_set_graph;
marci@1008:     typename Graph::NodeMap<ENode>* e_node;
marci@1008:     typename EdgeSetGraph::NodeMap<Node>* n_node;
marci@1008:     void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) { 
marci@1008:       edge_set_graph=&_edge_set_graph; 
marci@1008:     }
marci@1008:     /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
marci@1008:     void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) { 
marci@1008:       n_node=&_n_node; 
marci@1008:     }
marci@1008:     /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
marci@1008:     void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) { 
marci@1008:       e_node=&_e_node; 
marci@1008:     }
marci@1008:   public:
marci@1008:     class Edge : public EdgeSetGraph::Edge {
marci@1008:       typedef typename EdgeSetGraph::Edge Parent;
marci@1008:     public:
marci@1008:       Edge() { }
marci@1008:       Edge(const Parent& e) : Parent(e) { }
marci@1008:       Edge(Invalid i) : Parent(i) { }
marci@1008:     };
marci@1008: 
marci@1008:     using Parent::first;
marci@1008:     void first(Edge &e) const { 
marci@1008:       edge_set_graph->first(e);
marci@1008:     }
marci@1008:     void firstOut(Edge& e, const Node& n) const {
marci@1008: //       cout << e_node << endl;
marci@1008: //       cout << n_node << endl;
marci@1008:       edge_set_graph->firstOut(e, (*e_node)[n]);
marci@1008:     }
marci@1008:     void firstIn(Edge& e, const Node& n) const {
marci@1008:       edge_set_graph->firstIn(e, (*e_node)[n]);
marci@1008:     }
marci@1008: 
marci@1008:     using Parent::next;
marci@1008:     void next(Edge &e) const { 
marci@1008:       edge_set_graph->next(e);
marci@1008:     }
marci@1008:     void nextOut(Edge& e) const {
marci@1008:       edge_set_graph->nextOut(e);
marci@1008:     }
marci@1008:     void nextIn(Edge& e) const {
marci@1008:       edge_set_graph->nextIn(e);
marci@1008:     }
marci@1008: 
marci@1008:     Node source(const Edge& e) const { 
marci@1008:       return (*n_node)[edge_set_graph->source(e)];
marci@1008:     }
marci@1008:     Node target(const Edge& e) const { 
marci@1008:       return (*n_node)[edge_set_graph->target(e)];
marci@1008:     }
marci@1008: 
marci@1008:     int edgeNum() const { return edge_set_graph->edgeNum(); }
marci@1008: 
marci@1025: //     NNode addOldNode() {
marci@1025: //       return Parent::addNode();
marci@1025: //     }
marci@1025: 
marci@1025: //     ENode addNewNode() {
marci@1025: //       return edge_set_graph->addNode();
marci@1025: //     }
marci@1025: 
marci@1008:     Edge addEdge(const Node& u, const Node& v) {
marci@1008:       return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
marci@1008:     }
marci@1008: 
marci@1008:     using Parent::erase;
marci@1008:     void erase(const Edge& i) const { edge_set_graph->erase(i); }
marci@1008:   
marci@1008:     void clear() const { Parent::clear(); edge_set_graph->clear(); }
marci@1008: 
marci@1008:     bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
marci@1008:     bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
marci@1008: 
marci@1013:     int id(const Node& e) const { return Parent::id(e); }
marci@1008:     int id(const Edge& e) const { return edge_set_graph->id(e); }
marci@1008:     
marci@1008:     Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
marci@1008: 
marci@1008:     template <typename _Value>
marci@1008:     class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
marci@1008:     public:
marci@1008:       typedef typename EdgeSetGraph::EdgeMap<_Value> Parent; 
marci@1008:       typedef _Value Value;
marci@1008:       typedef Edge Key;
marci@1008:       EdgeMap(const NewEdgeSetGraphWrapperBase& gw) : 
marci@1008: 	Parent(*(gw.edge_set_graph)) { }
marci@1008:       EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) : 
marci@1008: 	Parent(*(gw.edge_set_graph), _value) { }
marci@1008:     };
marci@1008: 
marci@1008:   };
marci@1008: 
marci@1013: 
marci@1013:   /*! A graph wrapper class for the following functionality.
marci@1013:     If a bijection is given between the node-sets of two graphs, 
marci@1013:     then the second one can be considered as a new edge-set 
marci@1013:     over th first node-set. 
marci@1013:    */
marci@1008:   template <typename _Graph, typename _EdgeSetGraph>
marci@1008:   class NewEdgeSetGraphWrapper : 
marci@1008:     public IterableGraphExtender<
marci@1008:     NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
marci@1008:   public:
marci@1008:     typedef _Graph Graph;
marci@1008:     typedef _EdgeSetGraph EdgeSetGraph;
marci@1008:     typedef IterableGraphExtender<
marci@1025:       NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
marci@1008:   protected:
marci@1008:     NewEdgeSetGraphWrapper() { }
marci@1008:   public:
marci@1008:     NewEdgeSetGraphWrapper(_Graph& _graph, 
marci@1008: 			   _EdgeSetGraph& _edge_set_graph, 
marci@1008: 			   typename _Graph::
marci@1008: 			   NodeMap<typename _EdgeSetGraph::Node>& _e_node, 
marci@1008: 			   typename _EdgeSetGraph::
marci@1008: 			   NodeMap<typename _Graph::Node>& _n_node) { 
marci@1008:       setGraph(_graph);
marci@1008:       setEdgeSetGraph(_edge_set_graph);
marci@1008:       setNodeMap(_n_node);
marci@1008:       setENodeMap(_e_node);
marci@1008:     }
marci@1008:   };
marci@1008: 
marci@1025:   /*! A graph wrapper class for the following functionality.
marci@1025:     The same as NewEdgeSetGrapWrapper, but the bijection and the graph of 
marci@1025:     new edges is andled inthe class.
marci@1025:    */
marci@1025:   template <typename _Graph, typename _EdgeSetGraph>
marci@1025:   class NewEdgeSetGraphWrapper2 : 
marci@1025:     public IterableGraphExtender<
marci@1025:     NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
marci@1025:   public:
marci@1025:     typedef _Graph Graph;
marci@1025:     typedef _EdgeSetGraph EdgeSetGraph;
marci@1025:     typedef IterableGraphExtender<
marci@1025:       NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
marci@1025:   protected:
marci@1025:     _EdgeSetGraph _edge_set_graph;
marci@1025:     typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
marci@1025:     typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
marci@1025:     NewEdgeSetGraphWrapper2() { }
marci@1025:   public:
marci@1025:     typedef typename Graph::Node Node;
marci@1025:     //    typedef typename Parent::Edge Edge;
marci@1025: 
marci@1025:     NewEdgeSetGraphWrapper2(_Graph& _graph) : 
marci@1025:       _edge_set_graph(), 
marci@1025:       _e_node(_graph), _n_node(_edge_set_graph) { 
marci@1025:       setGraph(_graph);
marci@1025:       setEdgeSetGraph(_edge_set_graph);
marci@1025:       setNodeMap(_n_node); setENodeMap(_e_node);
marci@1025:       Node n;
marci@1025:       for (this->first(n); n!=INVALID; this->next(n)) {
marci@1025: 	typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
marci@1025: 	_e_node.set(n, e);
marci@1025: 	_n_node.set(e, n);
marci@1025:       }
marci@1025:     }
marci@1025: 
marci@1025: //     Node addNode() {
marci@1025: //       Node n=(*this).Parent::addNode();
marci@1025: //       typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
marci@1025: //       _e_node.set(n, e);
marci@1025: //       _n_node.set(e, n);
marci@1025: //       return n;
marci@1025: //     }
marci@1025: 
marci@1025:   };
marci@1013: 
marci@1013:   /*! A graph wrapper base class 
marci@1013:     for merging graphs of type _Graph1 and _Graph2 
marci@1013:     which are given on the same node-set 
marci@1013:     (specially on the node-set of Graph1) 
marci@1013:     into one graph.
marci@1013:     In an other point of view, _Graph1 is extended with 
marci@1013:     the edge-set of _Graph2.
marci@1025:     \warning we need specialize dimplementations
marci@1025:     \todo we need specialize dimplementations
marci@1025:     \bug we need specialize dimplementations
marci@1013:    */
marci@1013:   template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1013:   class AugmentingGraphWrapperBase : 
marci@1013:     public P1<_Graph1> {
marci@1013:   public:
marci@1013:     void printAugment() const { std::cout << "generic" << std::endl; }
marci@1013:     typedef _Graph1 Graph1;
marci@1013:     typedef _Graph2 Graph2;
marci@1013:     typedef P1<_Graph1> Parent1;
marci@1013:     typedef P2<_Graph2> Parent2;
marci@1013:     typedef typename Parent1::Edge Graph1Edge;
marci@1013:     typedef typename Parent2::Edge Graph2Edge;
marci@1013:   protected:
marci@1013:     AugmentingGraphWrapperBase() { }
marci@1013:     _Graph2* graph2;
marci@1013:     void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
marci@1013:   public:
marci@1013:     
marci@1013:     template <typename _Value> class EdgeMap;
marci@1013: 
marci@1013:     typedef typename Parent1::Node Node;
marci@1013: 
marci@1013:     class Edge : public Graph1Edge, public Graph2Edge {
marci@1013:       friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
marci@1013:       template <typename _Value> friend class EdgeMap;
marci@1013:     protected:
marci@1013:       bool backward; //true, iff backward
marci@1013:     public:
marci@1013:       Edge() { }
marci@1013:       /// \todo =false is needed, or causes problems?
marci@1013:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@1013:       /// original one, otherwise its oppositely directed pair is obtained.
marci@1013:       Edge(const Graph1Edge& n1, 
marci@1013: 	   const Graph2Edge& n2, bool _backward) : 
marci@1013: 	Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
marci@1013:       Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
marci@1013:       bool operator==(const Edge& v) const { 
marci@1013: 	if (backward) 
marci@1013: 	  return (v.backward && 
marci@1013: 		  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 
marci@1013: 	else 
marci@1013: 	  return (!v.backward && 
marci@1013: 		  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 
marci@1013:       } 
marci@1013:       bool operator!=(const Edge& v) const { 
marci@1013: 	return !(*this==v);
marci@1013:       }
marci@1013:     };
marci@1013: 
marci@1013:     using Parent1::first;
marci@1013:     void first(Edge& i) const {
marci@1013:       Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
marci@1013:       i.backward=false;
marci@1013:       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: 	graph2->first(*static_cast<Graph2Edge*>(&i));
marci@1013: 	i.backward=true;
marci@1013:       }
marci@1013:     }
marci@1013:     void firstIn(Edge& i, const Node& n) const {
marci@1013:       Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
marci@1013:       i.backward=false;
marci@1013:       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: 	graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1013: 	i.backward=true;
marci@1013:       }
marci@1013:     }
marci@1013:     void firstOut(Edge& i, const Node& n) const {
marci@1013:       Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
marci@1013:       i.backward=false;
marci@1013:       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: 	graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1013: 	i.backward=true;
marci@1013:       }
marci@1013:     }
marci@1013: 
marci@1013:     using Parent1::next;
marci@1013:     void next(Edge& i) const {
marci@1013:       if (!(i.backward)) {
marci@1013: 	Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
marci@1013: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1013: 	  graph2->first(*static_cast<Graph2Edge*>(&i));
marci@1013: 	  i.backward=true;
marci@1013: 	}
marci@1013:       } else {
marci@1013: 	graph2->next(*static_cast<Graph2Edge*>(&i));
marci@1013:       }
marci@1013:     }
marci@1013:     void nextIn(Edge& i) const {
marci@1013:       if (!(i.backward)) {
marci@1025: 	Node n=target(i);
marci@1013: 	Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
marci@1013: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1025: 	  graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
marci@1013: 	  i.backward=true;
marci@1013: 	}
marci@1013:       } else {
marci@1013: 	graph2->nextIn(*static_cast<Graph2Edge*>(&i));
marci@1013:       }
marci@1013:     }
marci@1013:     void nextOut(Edge& i) const {
marci@1013:       if (!(i.backward)) {
marci@1025: 	Node n=source(i);
marci@1013: 	Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
marci@1013: 	if (*static_cast<Graph1Edge*>(&i)==INVALID) {
marci@1025: 	  graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
marci@1013: 	  i.backward=true;
marci@1013: 	}
marci@1013:       } else {
marci@1013: 	graph2->nextOut(*static_cast<Graph2Edge*>(&i));
marci@1013:       }
marci@1013:     }
marci@1013: 
marci@1013:     Node source(const Edge& i) const {
marci@1013:       if (!(i.backward)) {
marci@1013: 	return Parent1::graph->source(i);
marci@1013:       } else {
marci@1013: 	return graph2->source(i);
marci@1013:       }
marci@1013:     }
marci@1013: 
marci@1013:     Node target(const Edge& i) const {
marci@1013:       if (!(i.backward)) {
marci@1013: 	return Parent1::graph->target(i);
marci@1013:       } else {
marci@1013: 	return graph2->target(i);
marci@1013:       }
marci@1013:     }
marci@1013: 
marci@1013:     int id(const Node& n) const {
marci@1013:       return Parent1::id(n);
marci@1013:     };
marci@1013:     int id(const Edge& n) const { 
marci@1013:       if (!n.backward) 
marci@1013: 	return this->Parent1::graph->id(n);
marci@1013:       else
marci@1013: 	return this->graph2->id(n);
marci@1013:     }
marci@1013: 
marci@1013:     template <typename _Value> 
marci@1013:     class EdgeMap { 
marci@1013:     protected:
marci@1013:       typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
marci@1013:       typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
marci@1013:       ParentMap1 forward_map;
marci@1013:       ParentMap2 backward_map;
marci@1013:     public:
marci@1013:       typedef _Value Value;
marci@1013:       typedef Edge Key;
marci@1013:       EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) : 
marci@1013: 	forward_map(*(gw.Parent1::graph)), 
marci@1013: 	backward_map(*(gw.graph2)) { }
marci@1013:       EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw, 
marci@1013: 	      const _Value& value) : 
marci@1013: 	forward_map(*(gw.Parent1::graph), value), 
marci@1013: 	backward_map(*(gw.graph2), value) { }
marci@1013:       _Value operator[](const Edge& n) const {
marci@1013: 	if (!n.backward) 
marci@1013: 	  return forward_map[n];
marci@1013: 	else 
marci@1013: 	  return backward_map[n];
marci@1013:       }
marci@1013:       void set(const Edge& n, const _Value& value) {
marci@1013: 	if (!n.backward) 
marci@1013: 	  forward_map.set(n, value);
marci@1013: 	else 
marci@1013: 	  backward_map.set(n, value);
marci@1013:       }
marci@1013: //       using ParentMap1::operator[];
marci@1013: //       using ParentMap2::operator[];
marci@1013:     };
marci@1013: 
marci@1013:   };
marci@1013: 
marci@1013: 
marci@1013:   /*! A graph wrapper class 
marci@1013:     for merging two graphs (of type _Graph1 and _Graph2)
marci@1013:     with the same node-set 
marci@1013:     (specially on the node-set of Graph1) 
marci@1013:     into one graph. 
marci@1013:     In an other point of view, _Graph1 is extended with 
marci@1013:     the edge-set of _Graph2.
marci@1013:    */  
marci@1013:   template <typename _Graph1, typename _Graph2>
marci@1013:   class AugmentingGraphWrapper : public 
marci@1013:   IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
marci@1013:   public:
marci@1013:     typedef 
marci@1013:     IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
marci@1013:     Parent;
marci@1013:     typedef _Graph1 Graph1;
marci@1013:     typedef _Graph2 Graph2;
marci@1013:   protected:
marci@1013:     AugmentingGraphWrapper() { }
marci@1013:   public:
marci@1013:     AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
marci@1013:       setGraph(_graph1); 
marci@1013:       setGraph2(_graph2);
marci@1013:     }
marci@1013:   };
marci@1013: 
alpar@921: } //namespace lemon
marci@915: 
alpar@921: #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H