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@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@1002:   template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1002:   class MergeNodeGraphWrapperBase : 
marci@1007:     public P1<_Graph1>, public P2<_Graph2> {
marci@915:   public:
marci@1007:     void print() const { std::cout << "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@1002:     MergeNodeGraphWrapperBase() { }
marci@1002:   public:
marci@1002:     template <typename _Value> class NodeMap;
marci@915: 
marci@915:     class Node : public Graph1Node, public Graph2Node {
marci@1002:       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
marci@1002:       template <typename Value> friend class NodeMap;
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@915: 	return (this->backward==v.backward && 
marci@915: 		static_cast<Graph1Node>(*this)==
marci@915: 		static_cast<Graph1Node>(v) && 
marci@915: 		static_cast<Graph2Node>(*this)==
marci@915: 		static_cast<Graph2Node>(v));
marci@915:       } 
marci@915:       bool operator!=(const Node& v) const { 
marci@915: 	return (this->backward!=v.backward || 
marci@915: 		static_cast<Graph1Node>(*this)!=
marci@915: 		static_cast<Graph1Node>(v) || 
marci@915: 		static_cast<Graph2Node>(*this)!=
marci@915: 		static_cast<Graph2Node>(v));
marci@915:       }
marci@915:     };
marci@915: 
marci@1002:     //typedef void Edge;
marci@1002:     class Edge { };
marci@1002:     
marci@1002:     void first(Node& i) const {
marci@1002:       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
marci@1002:       i.backward=false;
marci@1002:       if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1002: 	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1002: 	i.backward=true;
marci@1002:       }
marci@1002:     }
marci@1002:     void next(Node& i) const {
marci@1002:       if (!(i.backward)) {
marci@1002: 	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
marci@1002: 	if (*static_cast<Graph1Node*>(&i)==INVALID) {
marci@1002: 	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
marci@1002: 	  i.backward=true;
marci@915: 	}
marci@1002:       } else {
marci@1002: 	Parent2::graph->next(*static_cast<Graph2Node*>(&i));
marci@915:       }
marci@1002:     }
marci@915: 
marci@915:     int id(const Node& n) const { 
marci@915:       if (!n.backward) 
marci@915: 	return this->Parent1::graph->id(n);
marci@915:       else
marci@915: 	return this->Parent2::graph->id(n);
marci@915:     }
marci@915: 
marci@1002:     template <typename _Value> 
marci@1002:     class NodeMap : public Parent1::template NodeMap<_Value>, 
marci@1002: 		    public Parent2::template NodeMap<_Value> { 
marci@1002:       typedef typename Parent1::template NodeMap<_Value> ParentMap1;
marci@1002:       typedef typename Parent2::template NodeMap<_Value> ParentMap2;
marci@917:     public:
marci@1002:       typedef _Value Value;
marci@1002:       typedef Node Key;
marci@1002:       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
marci@1002: 	ParentMap1(gw), ParentMap2(gw) { }
marci@1002:       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
marci@1002: 	      const _Value& value) : 
marci@1002: 	ParentMap1(gw, value), ParentMap2(gw, value) { }
marci@1002:       _Value operator[](const Node& n) const {
marci@917: 	if (!n.backward) 
marci@917: 	  return ParentMap1::operator[](n);
marci@917: 	else 
marci@917: 	  return ParentMap2::operator[](n);
marci@917:       }
marci@1002:       void set(const Node& n, const _Value& value) {
marci@917: 	if (!n.backward) 
marci@917: 	  ParentMap1::set(n, value);
marci@917: 	else 
marci@917: 	  ParentMap2::set(n, value);
marci@917:       }
marci@917:       using ParentMap1::operator[];
marci@917:       using ParentMap2::operator[];
marci@917:     };
marci@1002: 
marci@1002:   };
marci@1002: 
marci@1008:   //not yet working
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1007:   class MergeNodeGraphWrapperBase<
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@1007:   public :
marci@1007:     void print() const { std::cout << "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@1007:     MergeNodeGraphWrapperBase() { }
marci@1007:   public:
marci@1007:     class Node { };
marci@1007:     class Edge { };
marci@1007:     void first() const;
marci@1007:     void next() const;
marci@1007:   };
marci@1007: 
marci@1008:   //not yet working
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1007:   class MergeNodeGraphWrapperBase<
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@1007:     void print() const { std::cout << "2. nagyobb" << 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@1007:     MergeNodeGraphWrapperBase() { }
marci@1007:   public:
marci@1007:     class Node { };
marci@1007:     class Edge { };
marci@1007:     void first() const;
marci@1007:     void next() const;
marci@1007:   };
marci@1007: 
marci@1008:   //not yet working
marci@1007:   template <typename _Graph1, typename _Graph2>
marci@1007:   class MergeNodeGraphWrapperBase<
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@1007:     void print() const { std::cout << "1. nagyobb" << 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@1007:     MergeNodeGraphWrapperBase() { }
marci@1007:   public:
marci@1007:     class Node { };
marci@1007:     class Edge { };
marci@1007:     void first() const;
marci@1007:     void next() const;
marci@1007:   };
marci@1007: 
marci@1002: 
marci@1002:   template <typename _Graph1, typename _Graph2, typename Enable=void>
marci@1002:   class MergeNodeGraphWrapper : public 
marci@1002:   IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > {
marci@1002:   public:
marci@1002:     typedef _Graph1 Graph1;
marci@1002:     typedef _Graph2 Graph2;
marci@1002:     typedef IterableGraphExtender<
marci@1002:       MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > 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@1008:   
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@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@1008:     using Parent::id;
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@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@1008:       NewEdgeSetGraphWrapper<_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: 
alpar@921: } //namespace lemon
marci@915: 
alpar@921: #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H