source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 1278:4abea330614d

// -*- c++ -*-
#ifndef LEMON_BIPARTITE_GRAPH_WRAPPER_H
#define LEMON_BIPARTITE_GRAPH_WRAPPER_H

///\ingroup gwrappers
///\file
///\brief Several graph wrappers.
///
///This file contains several useful graph wrapper functions.
///
///\author Marton Makai

#include <lemon/invalid.h>
#include <iter_map.h>
#include <lemon/graph_wrapper.h>
#include <for_each_macros.h>

namespace lemon {

  /// \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> {
  public:
    typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
    SFalseTTrueMap;
  protected:
    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;

    /// This method is to reach the iterable maps of the bipartite graph or 
    /// bipartite graph wrapper.
    const SFalseTTrueMap& sFalseTTrueMap() const { 
      return *s_false_t_true_map; 
    }
    
    //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 : public Node {
      friend class BipartiteGraphWrapper<Graph>;
    protected:
      const BipartiteGraphWrapper<Graph>* gw;
    public:
      ClassNodeIt() { }
      ClassNodeIt(Invalid i) : Node(i) { }
      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) : 
        Node(), gw(&_gw) { 
        _gw.s_false_t_true_map->first(*this, _class); 
      }
      //FIXME needed in new concept, important here
      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) : 
        Node(n), gw(&_gw) { }
      ClassNodeIt& operator++() { 
        gw->s_false_t_true_map->next(*this);
        return *this; 
      }
    };
//     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 source(const Edge& e) { 
//       if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 
//      return Node(this->graph->source(e));
//       else
//      return Node(this->graph->target(e));    
//     }
//     Node target(const Edge& e) { 
//       if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 
//      return Node(this->graph->target(e));
//       else
//      return Node(this->graph->source(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;
    typename Parent::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 source have to be in \c S_Class and \c target in \c T_Class.
    Edge addEdge(const Node& source, const Node& target) {
      return Parent::graph->addEdge(source, target);
    }

    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, typename sIterableMap, typename tIterableMap>
  class stGraphWrapper;

  /// Easier stuff for bipartite graphs.
  template<typename Graph>
  class stBipartiteGraphWrapper : public 
  stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 
                 typename Graph::SFalseTTrueMap> {
  public:
    typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 
                           typename Graph::SFalseTTrueMap> Parent;
    stBipartiteGraphWrapper(Graph& _graph) : 
      Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }
  };

//   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, typename sIterableMap, typename tIterableMap>
  class stGraphWrapper : public GraphWrapper<Graph> {
  protected:    
    const sIterableMap* s_iterable_map;
    const tIterableMap* t_iterable_map;
  public:
    class Node; 
    friend class Node;
//GN, int
//0 normalis, 1 s, 2 t, 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;

    // \bug not too nice constructor.
    stGraphWrapper(Graph& _graph, 
                   const sIterableMap& _s_iterable_map, 
                   const tIterableMap& _t_iterable_map) : 
      GraphWrapper<Graph>(_graph), 
      s_iterable_map(&_s_iterable_map), 
      t_iterable_map(&_t_iterable_map), 
      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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>& _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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>& _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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>& _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, sIterableMap, tIterableMap>;
      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, sIterableMap, tIterableMap>& _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 source(const Edge& e) const { 
      switch (e.spec) {
      case 0: 
        return Node(this->graph->source(e));
        break;
      case 1:
        return S_NODE;
        break;
      case 2:
      default:
        return Node(e.n);
        break;
      }
    }
    Node target(const Edge& e) const { 
      switch (e.spec) {
      case 0: 
        return Node(this->graph->target(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 source(e); }
    Node aNode(const InEdgeIt& e) const { return target(e); }
    Node bNode(const OutEdgeIt& e) const { return target(e); }
    Node bNode(const InEdgeIt& e) const { return source(e); }

    void addNode() const { }
    void addEdge() const { }
    
//    Node addNode() const { return Node(this->graph->addNode()); }
//    Edge addEdge(const Node& source, const Node& target) const { 
//      return Edge(this->graph->addEdge(source, target)); }

//    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, sIterableMap, tIterableMap>& _G) : 
        Parent(_G), 
        s_value(), 
        t_value() { }
      NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _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, sIterableMap, tIterableMap>.
    template<typename NM> class NodeMapWrapper { 
    public:
      typedef Node Key;
      typedef typename NM::Value Value;
    protected:
      NM* nm;
      Value* s_value, t_value;
    public:
      NodeMapWrapper(NM& _nm, Value& _s_value, Value& _t_value) : 
        nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
      Value 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, Value 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, sIterableMap, tIterableMap>& _G) 
        : Parent(_G), 
          node_value(_G) { }
      EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _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, sIterableMap, tIterableMap>.
    template<typename EM, typename NM> 
    class EdgeMapWrapper {
    public: 
      typedef Edge Key;
      typedef typename EM::Value Value;
    protected:
      EM* em;
      NM* nm;
    public:
      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
      Value 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, Value 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 lemon


#endif //LEMON_BIPARTITE_GRAPH_WRAPPER_H