// -*- c++ -*-

 #ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H

 #define HUGO_BIPARTITE_GRAPH_WRAPPER_H

 ///\ingroup gwrappers

 ///\file

 ///\brief Several graph wrappers.

 ///

 ///This file contains several useful graph wrapper functions.

 ///

 ///\author Marton Makai

 #include <hugo/invalid.h>

 #include <iter_map.h>

 #include <hugo/graph_wrapper.h>

 namespace hugo {

   /// \brief A wrapper for composing a bipartite graph from a graph 

   /// and from a node-map showing for any node which color class it belongs to.

   ///

   /// A wrapper for composing a bipartite graph.

   /// \c _graph have to be a reference to a graph of type \c Graph 

   /// and \c _s_false_t_true_map is an \c IterableBoolMap 

   /// reference containing the elements for the 

   /// color classes S and T. \c _graph is to be referred to an undirected 

   /// graph or a directed graph with edges oriented from S to T.

   ///

   /// \author Marton Makai

   template<typename Graph> 

   class BipartiteGraphWrapper : public GraphWrapper<Graph> {

   protected:

     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 

     SFalseTTrueMap;

     SFalseTTrueMap* s_false_t_true_map;

     BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, 

 						     S_CLASS(false), T_CLASS(true)*/ { }

     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { 

       s_false_t_true_map=&_s_false_t_true_map;

     }

   public:

     //marci

     //FIXME vhogy igy kellene, csak az en forditom nem eszi meg

     static const bool S_CLASS;

     static const bool T_CLASS;

     //bool S_CLASS;

     //bool T_CLASS;

     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 

       : GraphWrapper<Graph>(_graph), 

 	s_false_t_true_map(&_s_false_t_true_map)/*, 

 						  S_CLASS(false), T_CLASS(true)*/ { }

     typedef typename GraphWrapper<Graph>::Node Node;

     //using GraphWrapper<Graph>::NodeIt;

     typedef typename GraphWrapper<Graph>::Edge Edge;

     //using GraphWrapper<Graph>::EdgeIt;

     class ClassNodeIt;

     friend class ClassNodeIt;

     class OutEdgeIt;

     friend class OutEdgeIt;

     class InEdgeIt;

     friend class InEdgeIt;

     class ClassNodeIt {

       friend class BipartiteGraphWrapper<Graph>;

     protected:

       Node n;

     public:

       ClassNodeIt() { }

       ClassNodeIt(const Invalid& i) : n(i) { }

       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 

 	_G.s_false_t_true_map->first(n, _class); 

       }

       //FIXME needed in new concept, important here

       ClassNodeIt(const Node& _n) : n(_n) { }

       operator Node() const { return n; }

     };

 //     class SNodeIt {

 //       Node n;

 //     public:

 //       SNodeIt() { }

 //       SNodeIt(const Invalid& i) : n(i) { }

 //       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 

 // 	_G.s_false_t_true_map->first(n, false); 

 //       }

 //       operator Node() const { return n; }

 //     };

 //     class TNodeIt {

 //       Node n;

 //     public:

 //       TNodeIt() { }

 //       TNodeIt(const Invalid& i) : n(i) { }

 //       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 

 // 	_G.s_false_t_true_map->first(n, true); 

 //       }

 //       operator Node() const { return n; }

 //     };

     class OutEdgeIt { 

       friend class BipartiteGraphWrapper<Graph>;

     protected:

       typename Graph::OutEdgeIt e;

     public:

       OutEdgeIt() { }

       OutEdgeIt(const Invalid& i) : e(i) { }

       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

 	if (!(*(_G.s_false_t_true_map))[_n]) 

 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));

 	else 

 	  e=INVALID;

       }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     class InEdgeIt { 

       friend class BipartiteGraphWrapper<Graph>;

     protected:

       typename Graph::InEdgeIt e;

     public:

       InEdgeIt() { }

       InEdgeIt(const Invalid& i) : e(i) { }

       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

 	if ((*(_G.s_false_t_true_map))[_n]) 

 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));

 	else 

 	  e=INVALID;

       }

       operator Edge() const { return Edge(typename Graph::Edge(e)); }

     };

     using GraphWrapper<Graph>::first;

     ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 

       n=ClassNodeIt(*this, _class) ; return n; }

 //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }

 //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }

     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

       i=OutEdgeIt(*this, p); return i;

     }

     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

       i=InEdgeIt(*this, p); return i;

     }

     using GraphWrapper<Graph>::next;

     ClassNodeIt& next(ClassNodeIt& n) const { 

       this->s_false_t_true_map->next(n.n); return n; 

     }

 //     SNodeIt& next(SNodeIt& n) const { 

 //       this->s_false_t_true_map->next(n); return n; 

 //     }

 //     TNodeIt& next(TNodeIt& n) const { 

 //       this->s_false_t_true_map->next(n); return n; 

 //     }

     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }

     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

     Node tail(const Edge& e) { 

       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 

 	return Node(this->graph->tail(e));

       else

 	return Node(this->graph->head(e));	

     }

     Node head(const Edge& e) { 

       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 

 	return Node(this->graph->head(e));

       else

 	return Node(this->graph->tail(e));	

     }

     Node aNode(const OutEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); 

     }

     Node aNode(const InEdgeIt& e) const { 

       return Node(this->graph->aNode(e.e)); 

     }

     Node bNode(const OutEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); 

     }

     Node bNode(const InEdgeIt& e) const { 

       return Node(this->graph->bNode(e.e)); 

     }

     /// Returns true iff \c n is in S.

     bool inSClass(const Node& n) const {

       return !(*(this->s_false_t_true_map))[n];

     }

     /// Returns true iff \c n is in T.

     bool inTClass(const Node& n) const {

       return (*(this->s_false_t_true_map))[n];

     }

   };

   template<typename G>

   const bool BipartiteGraphWrapper<G>::S_CLASS=false;

   template<typename G>

   const bool BipartiteGraphWrapper<G>::T_CLASS=true;

   /// \brief A bipartite graph template class

   ///

   /// This class composes a bipartite graph over a directed or undirected 

   /// graph structure of type \c Graph.

   /// \c _graph have to be a reference to a graph of type \c Graph 

   /// and \c _s_false_t_true_map is an \c IterableBoolMap 

   /// reference containing the elements for the 

   /// color classes S and T. \c _graph is to be referred to an undirected 

   /// graph or a directed graph with edges oriented from S to T.

   ///

   ///\bug experimental. Do not use this while the bipartitemap augmentation 

   /// does not work well.

   template<typename Graph>

   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 

     SFalseTTrueMap;

     typedef BipartiteGraphWrapper<Graph> Parent;

   protected:

     Graph gr;

     typename Graph::template NodeMap<int> bipartite_map;

     SFalseTTrueMap s_false_t_true_map;

   public:

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

     BipartiteGraph() : BipartiteGraphWrapper<Graph>(), 

 		       gr(), bipartite_map(gr, -1), 

 		       s_false_t_true_map(bipartite_map) { 

       Parent::setGraph(gr); 

       Parent::setSFalseTTrueMap(s_false_t_true_map);

     }

     /// the \c bool parameter which can be \c S_Class or \c T_Class shows 

     /// the color class where the new node is to be inserted.

     Node addNode(bool b) {

       Node n=Parent::graph->addNode();

       bipartite_map.update();

       //bipartite_map.set(n, -1);

       s_false_t_true_map.insert(n, b);

       return n;

     }

     /// A new edge is inserted.

     ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.

     Edge addEdge(const Node& tail, const Node& head) {

       return Parent::graph->addEdge(tail, head);

     }

     void erase(const Node& n) {

       s_false_t_true_map.remove(n);

       Parent::graph->erase(n);

     }

     void erase(const Edge& e) {

       Parent::graph->erase(e);

     }

     void clear() {

       FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);

       FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);

     }

   };

   template<typename Graph>

   class stGraphWrapper;

 //   template<typename Graph> 

 //   std::ostream& 

 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { 

 //     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 

 //     return os; 

 //   }

 //   template<typename Graph> 

 //   std::ostream& 

 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { 

 //     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 

 //       " node: " << i.n << ")"; 

 //     return os; 

 //   }

   /// \brief A wrapper for adding extra nodes s and t to a bipartite graph

   /// and edges from s to each node of S and form each node of T to t.

   /// 

   /// A wrapper for adding extra nodes s and t to a bipartite graph

   /// and edges from s to each node of S and form each node of T to t.

   /// This class is very useful to reduce some matching or more

   /// generally, capacitataed b-matching problem to a flow problem.

   /// According to the bipartite graph concepts the bipartite 

   /// graph have to be oriented from S to T.

   ///

   /// \author Marton Makai

   template<typename Graph>

   class stGraphWrapper : public GraphWrapper<Graph> {

   public:

     class Node; 

     friend class Node;

 //GN, int

 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 

 //es a vege a false azaz (invalid, 3)    

     class NodeIt;

     friend class NodeIt;

 //GNI, int

     class Edge;

     friend class Edge;

 //GE, int, GN

 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,

 //invalid: (invalid, 3, invalid)

     class OutEdgeIt;

     friend class OutEdgeIt;

 //GO, int, GNI

 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)

 //s-bol (invalid, 1, first), ... (invalid, 3, invalid)

 //t-bol (invalid, 3, invalid)

     class InEdgeIt;

     friend class InEdgeIt;

 //GI, int, GNI

 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)

 //s-be (invalid, 3, invalid)

 //t-be (invalid, 2, first), ... (invalid, 3, invalid)

     class EdgeIt;

     friend class EdgeIt;

 //(first, 0, invalid) ...

 //(invalid, 1, vmi)

 //(invalid, 2, vmi)

 //invalid, 3, invalid)

     template <typename T> class NodeMap;

     template <typename T> class EdgeMap;

 //    template <typename T> friend class NodeMap;

 //    template <typename T> friend class EdgeMap;

     ///\todo FIXME ezt majd static-ra kell javitani

     const Node S_NODE;

     const Node T_NODE;

     static const bool S_CLASS=false;

     static const bool T_CLASS=true;

     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 

 				    S_NODE(INVALID, 1), 

 				    T_NODE(INVALID, 2) { }

 //    std::ostream& 

 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

 //    friend std::ostream& 

 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

 //    friend std::ostream& 

 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);

     class Node : public Graph::Node {

     protected:

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       template <typename T> friend class NodeMap;

       friend class Edge;

       friend class OutEdgeIt;

       friend class InEdgeIt;

       friend class EdgeIt;

       int spec; 

     public:

       Node() { }

       Node(const typename Graph::Node& _n, int _spec=0) : 

 	Graph::Node(_n), spec(_spec) { }

       Node(const Invalid& i) : Graph::Node(i), spec(3) { }

       friend bool operator==(const Node& u, const Node& v) { 

 	return (u.spec==v.spec && 

 		static_cast<typename Graph::Node>(u)==

 		static_cast<typename Graph::Node>(v));

       } 

       friend bool operator!=(const Node& u, const Node& v) { 

 	return (v.spec!=u.spec || 

 		static_cast<typename Graph::Node>(u)!=

 		static_cast<typename Graph::Node>(v));

       }

 //      template<typename G> 

 //      friend std::ostream& 

 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); 

       friend std::ostream& operator<< (std::ostream& os, const Node& i);

       int getSpec() const { return spec; }

     };

     class NodeIt { 

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       typename Graph::NodeIt n;

       int spec; 

      public:

       NodeIt() { }

       NodeIt(const typename Graph::NodeIt& _n, int _spec) : 

 	n(_n), spec(_spec) { }

       NodeIt(const Invalid& i) : n(i), spec(3) { }

       NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 

 	if (!_G.graph->valid(n)) spec=1;

       }

       operator Node() const { return Node(n, spec); }

     };

     class Edge : public Graph::Edge {

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       template <typename T> friend class EdgeMap;

       int spec;

       typename Graph::Node n;

     public:

       Edge() { }

       Edge(const typename Graph::Edge& _e, int _spec, 

 	   const typename Graph::Node& _n) : 

 	Graph::Edge(_e), spec(_spec), n(_n) { 

       }

       Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }

       friend bool operator==(const Edge& u, const Edge& v) { 

 	return (u.spec==v.spec && 

 		static_cast<typename Graph::Edge>(u)==

 		static_cast<typename Graph::Edge>(v) && 

 		u.n==v.n);

       } 

       friend bool operator!=(const Edge& u, const Edge& v) { 

 	return (v.spec!=u.spec || 

 		static_cast<typename Graph::Edge>(u)!=

 		static_cast<typename Graph::Edge>(v) || 

 		u.n!=v.n);

       } 

 //      template<typename G> 

 //      friend std::ostream& 

 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); 

       friend std::ostream& operator<< (std::ostream& os, const Edge& i);

       int getSpec() const { return spec; }

       typename Graph::Node getNode() const { return n; }

     };

     class OutEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       typename Graph::OutEdgeIt e;

       int spec;

       typename Graph::ClassNodeIt n;

     public:

       OutEdgeIt() { }

       OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 

 		const typename Graph::ClassNodeIt& _n) : 

 	e(_e), spec(_spec), n(_n) { 

       }

       OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

       OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {

 	switch (_n.spec) {

 	  case 0 : 

 	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 

 	      e=typename Graph::OutEdgeIt(*(_G.graph), 

 					  typename Graph::Node(_n)); 

 	      spec=0;

 	      n=INVALID;

 	      if (!_G.graph->valid(e)) spec=3;

 	    } else { //T, specko kiel van

 	      e=INVALID;

 	      spec=2;

 	      n=_n;

 	    }

 	    break;

 	  case 1:

 	    e=INVALID;

 	    spec=1;

 	    _G.graph->first(n, S_CLASS); //s->vmi;

 	    if (!_G.graph->valid(n)) spec=3; //Ha S ures

 	    break;

 	  case 2:

 	    e=INVALID;

 	    spec=3;

 	    n=INVALID;

 	    break;

 	}

       }

       operator Edge() const { return Edge(e, spec, n); }

     };

     class InEdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       typename Graph::InEdgeIt e;

       int spec;

       typename Graph::ClassNodeIt n;

     public:

       InEdgeIt() { }

       InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 

 	       const typename Graph::ClassNodeIt& _n) : 

 	e(_e), spec(_spec), n(_n) { 

       }

       InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

       InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {

 	switch (_n.spec) {

 	  case 0 : 

 	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 

 	      e=typename Graph::InEdgeIt(*(_G.graph), 

 					 typename Graph::Node(_n)); 

 	      spec=0;

 	      n=INVALID;

 	      if (!_G.graph->valid(e)) spec=3;

 	    } else { //S, specko beel van

 	      e=INVALID;

 	      spec=1;

 	      n=_n;

 	    }

 	    break;

 	  case 1:

 	    e=INVALID;

 	    spec=3;

 	    n=INVALID;

 	    break;

 	  case 2:

 	    e=INVALID;

 	    spec=2;

 	    _G.graph->first(n, T_CLASS); //vmi->t;

 	    if (!_G.graph->valid(n)) spec=3; //Ha T ures

 	    break;

 	}

       }

       operator Edge() const { return Edge(e, spec, n); }

     };

     class EdgeIt { 

       friend class GraphWrapper<Graph>;

       friend class stGraphWrapper<Graph>;

       typename Graph::EdgeIt e;

       int spec;

       typename Graph::ClassNodeIt n;

     public:

       EdgeIt() { }

       EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 

 	     const typename Graph::ClassNodeIt& _n) : 

 	e(_e), spec(_spec), n(_n) { }

       EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

       EdgeIt(const stGraphWrapper<Graph>& _G) : 

 	e(*(_G.graph)), spec(0), n(INVALID) { 

 	if (!_G.graph->valid(e)) {

 	  spec=1;

 	  _G.graph->first(n, S_CLASS);

 	  if (!_G.graph->valid(n)) { //Ha S ures

 	    spec=2;

 	    _G.graph->first(n, T_CLASS);

 	    if (!_G.graph->valid(n)) { //Ha T ures

 	      spec=3;

 	    }

 	  }

 	}

       }

       operator Edge() const { return Edge(e, spec, n); }

     };

     NodeIt& first(NodeIt& i) const { 

       i=NodeIt(*this); return i;

     }

     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

       i=OutEdgeIt(*this, p); return i;

     }

     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

       i=InEdgeIt(*this, p); return i;

     }

     EdgeIt& first(EdgeIt& i) const { 

       i=EdgeIt(*this); return i;

     }

     NodeIt& next(NodeIt& i) const { 

       switch (i.spec) {

 	case 0:

 	  this->graph->next(i.n);

 	  if (!this->graph->valid(i.n)) {

 	    i.spec=1;

 	  }

 	  break;

 	case 1:

 	  i.spec=2;

 	  break;

 	case 2:

 	  i.spec=3;

 	  break;

       }

       return i; 

     }

     OutEdgeIt& next(OutEdgeIt& i) const { 

       typename Graph::Node v;

       switch (i.spec) {

 	case 0: //normal edge

 	  v=this->graph->aNode(i.e);

 	  this->graph->next(i.e);

 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

 	    if (this->graph->inSClass(v)) { //S, nincs kiel

 	      i.spec=3;

 	      i.n=INVALID;

 	    } else { //T, van kiel

 	      i.spec=2; 

 	      i.n=v;

 	    }

 	  }

 	  break;

 	case 1: //s->vmi

 	  this->graph->next(i.n);

 	  if (!this->graph->valid(i.n)) i.spec=3;

 	  break;

 	case 2: //vmi->t

 	  i.spec=3;

 	  i.n=INVALID;

 	  break;

       }

       return i; 

     }

     InEdgeIt& next(InEdgeIt& i) const { 

       typename Graph::Node v;

       switch (i.spec) {

 	case 0: //normal edge

 	  v=this->graph->aNode(i.e);

 	  this->graph->next(i.e);

 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

 	    if (this->graph->inTClass(v)) { //S, nincs beel

 	      i.spec=3;

 	      i.n=INVALID;

 	    } else { //S, van beel

 	      i.spec=1; 

 	      i.n=v;

 	    }

 	  }

 	  break;

 	case 1: //s->vmi

 	  i.spec=3;

 	  i.n=INVALID;

 	  break;

 	case 2: //vmi->t

 	  this->graph->next(i.n);

 	  if (!this->graph->valid(i.n)) i.spec=3;

 	  break;

       }

       return i; 

     }

     EdgeIt& next(EdgeIt& i) const { 

       switch (i.spec) {

 	case 0:

 	  this->graph->next(i.e);

 	  if (!this->graph->valid(i.e)) { 

 	    i.spec=1;

 	    this->graph->first(i.n, S_CLASS);

 	    if (!this->graph->valid(i.n)) {

 	      i.spec=2;

 	      this->graph->first(i.n, T_CLASS);

 	      if (!this->graph->valid(i.n)) i.spec=3;

 	    }

 	  }

 	  break;

 	case 1:

 	  this->graph->next(i.n);

 	  if (!this->graph->valid(i.n)) {

 	    i.spec=2;

 	    this->graph->first(i.n, T_CLASS);

 	    if (!this->graph->valid(i.n)) i.spec=3;

 	  }

 	  break;

 	case 2:

 	  this->graph->next(i.n);

 	  if (!this->graph->valid(i.n)) i.spec=3;

 	  break;

       }

       return i; 

     }    

     Node tail(const Edge& e) const { 

       switch (e.spec) {

       case 0: 

 	return Node(this->graph->tail(e));

 	break;

       case 1:

 	return S_NODE;

 	break;

       case 2:

       default:

 	return Node(e.n);

 	break;

       }

     }

     Node head(const Edge& e) const { 

       switch (e.spec) {

       case 0: 

 	return Node(this->graph->head(e));

 	break;

       case 1:

 	return Node(e.n);

 	break;

       case 2:

       default:

 	return T_NODE;

 	break;

       }

     }

     bool valid(const Node& n) const { return (n.spec<3); }

     bool valid(const Edge& e) const { return (e.spec<3); }

     int nodeNum() const { return this->graph->nodeNum()+2; }

     int edgeNum() const { 

       return this->graph->edgeNum()+this->graph->nodeNum(); 

     }

     Node aNode(const OutEdgeIt& e) const { return tail(e); }

     Node aNode(const InEdgeIt& e) const { return head(e); }

     Node bNode(const OutEdgeIt& e) const { return head(e); }

     Node bNode(const InEdgeIt& e) const { return tail(e); }

     void addNode() const { }

     void addEdge() const { }

 //    Node addNode() const { return Node(this->graph->addNode()); }

 //    Edge addEdge(const Node& tail, const Node& head) const { 

 //      return Edge(this->graph->addEdge(tail, head)); }

 //    void erase(const Node& i) const { this->graph->erase(i); }

 //    void erase(const Edge& i) const { this->graph->erase(i); }

 //    void clear() const { this->graph->clear(); }

     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 

       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;

     protected:

       T s_value, t_value;

     public:

       NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 

 						  s_value(), 

 						  t_value() { }

       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 

 						      s_value(a), 

 						      t_value(a) { }

       T operator[](const Node& n) const { 

 	switch (n.spec) {

 	case 0: 

 	  return Parent::operator[](n);

 	case 1:

 	  return s_value;

 	case 2: 

 	default:

 	  return t_value;

 	}

       }

       void set(const Node& n, T t) { 

 	switch (n.spec) {

 	case 0: 

 	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);

 	  break;

 	case 1:

 	  s_value=t;

 	  break;

 	case 2:

 	default:

 	  t_value=t;

 	  break;

 	}

       }

     };

     /// This class is to wrap a node-map of \c Graph and two variables 

     /// storing values for \c S_NODE and \c T_NODE to a node-map of 

     /// stGraphWrapper<Graph>.

     template<typename NM> class NodeMapWrapper { 

     public:

       typedef Node KeyType;

       typedef typename NM::ValueType ValueType;

     protected:

       NM* nm;

       ValueType* s_value, t_value;

     public:

       NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) : 

 	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }

       ValueType operator[](const Node& n) const { 

 	switch (n.getSpec()) {

 	case 0: 

 	  return (*nm)[n];

 	case 1:

 	  return *s_value;

 	case 2: 

 	default:

 	  return *t_value;

 	}

       }

       void set(const Node& n, ValueType t) { 

 	switch (n.getSpec()) {

 	case 0: 

 	  nm->set(n, t);

 	  break;

 	case 1:

 	  *s_value=t;

 	  break;

 	case 2:

 	default:

 	  *t_value=t;

 	  break;

 	}

       }

     };

     template<typename T> 

     class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 

       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;

     protected:

       typename GraphWrapper<Graph>::template NodeMap<T> node_value;

     public:

       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 

 						 node_value(_G) { }

       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 

 						      node_value(_G, a) { }

       T operator[](const Edge& e) const { 

 	switch (e.spec) {

 	case 0: 

 	  return Parent::operator[](e);

 	case 1:

 	  return node_value[e.n];

 	case 2:

 	default:

 	  return node_value[e.n];

 	}

       }

       void set(const Edge& e, T t) { 

 	switch (e.spec) {

 	case 0: 

 	  Parent::set(e, t);

 	  break;

 	case 1:

 	  node_value.set(e.n, t);

 	  break;

 	case 2:

 	default:

 	  node_value.set(e.n, t);

 	  break;

 	}

       }

     };

     /// This class is to wrap an edge-map and a node-map of \c Graph 

     /// to an edge-map of stGraphWrapper<Graph>.

     template<typename EM, typename NM> 

     class EdgeMapWrapper {

     public: 

       typedef Edge KeyType;

       typedef typename EM::ValueType ValueType;

     protected:

       EM* em;

       NM* nm;

     public:

       EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }

       ValueType operator[](const Edge& e) const { 

 	switch (e.getSpec()) {

 	case 0: 

 	  return (*em)[e];

 	case 1:

 	  return (*nm)[e.getNode()];

 	case 2:

 	default:

 	  return (*nm)[e.getNode()];

 	}

       }

       void set(const Edge& e, ValueType t) { 

 	switch (e.getSpec()) {

 	case 0: 

 	  em->set(e, t);

 	  break;

 	case 1:

 	  nm->set(e.getNode(), t);

 	  break;

 	case 2:

 	default:

 	  nm->set(e.getNode(), t);

 	  break;

 	}

       }

     };

 //  template<typename G> 

     friend std::ostream& 

     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { 

       os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 

       return os; 

     }

 //  template<typename G> 

     friend std::ostream& 

     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { 

       os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 

 	" node: " << i.n << ")"; 

       return os; 

     }

   };

   ///@}

 } //namespace hugo

 #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H