source: lemon-0.x/src/work/marci/graph_wrapper.h @ 457:8fbd472b1a22

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

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

#include <invalid.h>
#include <iter_map.h>

namespace hugo {

  // Graph wrappers

  /// \addtogroup gwrappers
  /// A main parts of HUGOlib are the different graph structures, 
  /// generic graph algorithms, graph concepts which couple these, and 
  /// graph wrappers. While the previous ones are more or less clear, the 
  /// latter notion needs further explanation.
  /// Graph wrappers are graph classes which serve for considering graph 
  /// structures in different ways. A short example makes the notion much 
  /// clearer. 
  /// Suppose that we have an instance \c g of a directed graph
  /// type say \c ListGraph and an algorithm 
  /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
  /// is needed to run on the reversely oriented graph. 
  /// It may be expensive (in time or in memory usage) to copy 
  /// \c g with the reverse orientation. 
  /// Thus, a wrapper class
  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
  /// The code looks as follows
  /// \code
  /// ListGraph g;
  /// RevGraphWrapper<ListGraph> rgw(g);
  /// int result=algorithm(rgw);
  /// \endcode
  /// After running the algorithm, the original graph \c g 
  /// remains untouched. Thus the graph wrapper used above is to consider the 
  /// original graph with reverse orientation. 
  /// This techniques gives rise to an elegant code, and 
  /// based on stable graph wrappers, complex algorithms can be 
  /// implemented easily. 
  /// In flow, circulation and bipartite matching problems, the residual 
  /// graph is of particular importance. Combining a wrapper implementing 
  /// this, shortest path algorithms and minimum mean cycle algorithms, 
  /// a range of weighted and cardinality optimization algorithms can be 
  /// obtained. For lack of space, for other examples, 
  /// the interested user is referred to the detailed documentation of graph 
  /// wrappers. 
  /// The behavior of graph wrappers can be very different. Some of them keep 
  /// capabilities of the original graph while in other cases this would be 
  /// meaningless. This means that the concepts that they are a model of depend 
  /// on the graph wrapper, and the wrapped graph(s). 
  /// If an edge of \c rgw is deleted, this is carried out by 
  /// deleting the corresponding edge of \c g. But for a residual 
  /// graph, this operation has no sense. 
  /// Let we stand one more example here to simplify your work. 
  /// wrapper class
  /// \code template<typename Graph> class RevGraphWrapper; \endcode 
  /// has constructor 
  /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
  /// This means that in a situation, 
  /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
  /// \code
  /// int algorithm1(const ListGraph& g) {
  ///   RevGraphWrapper<const ListGraph> rgw(g);
  ///   return algorithm2(rgw);
  /// }
  /// \endcode

  /// \addtogroup gwrappers
  /// @{

  ///Base type for the Graph Wrappers

  ///This is the base type for the Graph Wrappers.
  ///\todo Some more docs... 
  ///
  ///\author Marton Makai
 
  template<typename Graph>
  class GraphWrapper {
  protected:
    Graph* graph;
  
  public:
    typedef Graph BaseGraph;
    typedef Graph ParentGraph;

//     GraphWrapper() : graph(0) { }
    GraphWrapper(Graph& _graph) : graph(&_graph) { }
//     void setGraph(Graph& _graph) { graph=&_graph; }
//     Graph& getGraph() const { return *graph; }
 
//    typedef typename Graph::Node Node;
    class Node : public Graph::Node {
      friend class GraphWrapper<Graph>;
    public:
      Node() { }
      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
      Node(const Invalid& i) : Graph::Node(i) { }
    };
    class NodeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
//    typedef typename Graph::Edge Edge;
    class Edge : public Graph::Edge {
      friend class GraphWrapper<Graph>;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
      Edge(const Invalid& i) : Graph::Edge(i) { }
    };
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
   
    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 { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    

    Node tail(const Edge& e) const { 
      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    Node head(const Edge& e) const { 
      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }

    bool valid(const Node& n) const { 
      return graph->valid(static_cast<typename Graph::Node>(n)); }
    bool valid(const Edge& e) const { 
      return graph->valid(static_cast<typename Graph::Edge>(e)); }

    int nodeNum() const { return graph->nodeNum(); }
    int edgeNum() const { return graph->edgeNum(); }
  
    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
  
    Node addNode() const { return Node(graph->addNode()); }
    Edge addEdge(const Node& tail, const Node& head) const { 
      return Edge(graph->addEdge(tail, head)); }

    void erase(const Node& i) const { graph->erase(i); }
    void erase(const Edge& i) const { graph->erase(i); }
  
    void clear() const { graph->clear(); }
    
    template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
      typedef typename Graph::template NodeMap<T> Parent;
    public:
      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    };

    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
      typedef typename Graph::template EdgeMap<T> Parent;
    public:
      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
    };
  };

  /// A graph wrapper which reverses the orientation of the edges.

  /// A graph wrapper which reverses the orientation of the edges.
  ///
  ///\author Marton Makai
  template<typename Graph>
  class RevGraphWrapper : public GraphWrapper<Graph> {
  public:

    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    //If Graph::OutEdgeIt is not defined
    //and we do not want to use RevGraphWrapper::InEdgeIt,
    //the typdef techinque does not work.
    //Unfortunately all the typedefs are instantiated in templates.
    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::InEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class RevGraphWrapper<Graph>;
      typename Graph::OutEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
    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;
    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 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)); }

    Node tail(const Edge& e) const { 
      return GraphWrapper<Graph>::head(e); }
    Node head(const Edge& e) const { 
      return GraphWrapper<Graph>::tail(e); }

  };

  /// Wrapper for hiding nodes and edges from a graph.
  
  /// This wrapper shows a graph with filtered node-set and 
  /// edge-set. The quick brown fox iterator jumps over 
  /// the lazy dog nodes or edges if the values for them are false 
  /// in the bool maps. 
  ///
  ///\author Marton Makai
  template<typename Graph, typename NodeFilterMap, 
           typename EdgeFilterMap>
  class SubGraphWrapper : public GraphWrapper<Graph> {
  protected:
    NodeFilterMap* node_filter_map;
    EdgeFilterMap* edge_filter_map;
  public:

    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
                    EdgeFilterMap& _edge_filter_map) : 
      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
      edge_filter_map(&_edge_filter_map) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
    class NodeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::NodeIt n;
     public:
      NodeIt() { }
      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
      NodeIt(const Invalid& i) : n(i) { }
      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        n(*(_G.graph)) { 
        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
          _G.graph->next(n);
      }
      operator Node() const { return Node(typename Graph::Node(n)); }
    };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
                const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
        e(*(_G.graph)) { 
        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
          _G.graph->next(e);
      }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    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 {
      this->graph->next(i.n); 
      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
        this->graph->next(i.n); }
      return i;
    }
    OutEdgeIt& next(OutEdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }
    InEdgeIt& next(InEdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }
    EdgeIt& next(EdgeIt& i) const {
      this->graph->next(i.e); 
      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
        this->graph->next(i.e); }
      return i;
    }

    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)); }

    ///\todo
    ///Some doki, please.
    void hide(const Node& n) const { node_filter_map->set(n, false); }
    ///\todo
    ///Some doki, please.
    void hide(const Edge& e) const { edge_filter_map->set(e, false); }

    ///\todo
    ///Some doki, please.
    void unHide(const Node& n) const { node_filter_map->set(n, true); }
    ///\todo
    ///Some doki, please.
    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

    ///\todo
    ///Some doki, please.
    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
    ///\todo
    ///Some doki, please.
    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
  };

  /// A wrapper for forgetting the orientation of a graph.

  /// A wrapper for getting an undirected graph by forgetting
  /// the orientation of a directed one.
  template<typename Graph>
  class UndirGraphWrapper : public GraphWrapper<Graph> {
  public:
    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    typedef typename GraphWrapper<Graph>::Edge Edge;
    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  

    class OutEdgeIt {
      friend class UndirGraphWrapper<Graph>;
      bool out_or_in; //true iff out
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const Invalid& i) : Edge(i) { }
      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
        out_or_in=true; _G.graph->first(out, _n);
        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
      } 
      operator Edge() const { 
        if (out_or_in) return Edge(out); else return Edge(in); 
      }
    };

//FIXME InEdgeIt
    typedef OutEdgeIt InEdgeIt; 

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//FIXME
//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
//       i=InEdgeIt(*this, p); return i;
//     }
//     EdgeIt& first(EdgeIt& i) const { 
//       i=EdgeIt(*this); return i;
//     }

    using GraphWrapper<Graph>::next;
//     NodeIt& next(NodeIt& n) const {
//       GraphWrapper<Graph>::next(n);
//       return n;
//     }
    OutEdgeIt& next(OutEdgeIt& e) const {
      if (e.out_or_in) {
        typename Graph::Node n=this->graph->tail(e.out);
        this->graph->next(e.out);
        if (!this->graph->valid(e.out)) { 
          e.out_or_in=false; this->graph->first(e.in, n); }
      } else {
        this->graph->next(e.in);
      }
      return e;
    }
    //FIXME InEdgeIt
//     EdgeIt& next(EdgeIt& e) const {
//       GraphWrapper<Graph>::next(n);
// //      graph->next(e.e);
//       return e;
//     }

    Node aNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return this->graph->tail(e); else 
        return this->graph->head(e); }
    Node bNode(const OutEdgeIt& e) const { 
      if (e.out_or_in) return this->graph->head(e); else 
        return this->graph->tail(e); }
  };
  
  /// A wrapper for composing the residual graph for directed flow and circulation problems.

  /// A wrapper for composing the residual graph for directed flow and circulation problems.
  template<typename Graph, typename Number, 
           typename CapacityMap, typename FlowMap>
  class ResGraphWrapper : public GraphWrapper<Graph> {
  protected:
    const CapacityMap* capacity;
    FlowMap* flow;
  public:

    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
                    FlowMap& _flow) : 
      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }

    class Edge; 
    class OutEdgeIt; 
    friend class Edge; 
    friend class OutEdgeIt; 

    typedef typename GraphWrapper<Graph>::Node Node;
    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    class Edge : public Graph::Edge {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      bool forward; //true, iff forward
//      typename Graph::Edge e;
    public:
      Edge() { }
      Edge(const typename Graph::Edge& _e, bool _forward) : 
        Graph::Edge(_e), forward(_forward) { }
      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
//the unique invalid iterator
      friend bool operator==(const Edge& u, const Edge& v) { 
        return (v.forward==u.forward && 
                static_cast<typename Graph::Edge>(u)==
                static_cast<typename Graph::Edge>(v));
      } 
      friend bool operator!=(const Edge& u, const Edge& v) { 
        return (v.forward!=u.forward || 
                static_cast<typename Graph::Edge>(u)!=
                static_cast<typename Graph::Edge>(v));
      } 
    };

    class OutEdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool forward;
    public:
      OutEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
//the unique invalid iterator
      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
        forward=true;
        resG.graph->first(out, v);
        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
        if (!resG.graph->valid(out)) {
          forward=false;
          resG.graph->first(in, v);
          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->forward) 
          return Edge(out, this->forward); 
        else 
          return Edge(in, this->forward);
      }
    };

    class InEdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::OutEdgeIt out;
      typename Graph::InEdgeIt in;
      bool forward;
    public:
      InEdgeIt() { }
      //FIXME
//      OutEdgeIt(const Edge& e) : Edge(e) { }
      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
//the unique invalid iterator
      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
        forward=true;
        resG.graph->first(in, v);
        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
        if (!resG.graph->valid(in)) {
          forward=false;
          resG.graph->first(out, v);
          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
        }
      }
      operator Edge() const { 
//      Edge e;
//      e.forward=this->forward;
//      if (this->forward) e=out; else e=in;
//      return e;
        if (this->forward) 
          return Edge(in, this->forward); 
        else 
          return Edge(out, this->forward);
      }
    };

    class EdgeIt {
      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    protected:
      typename Graph::EdgeIt e;
      bool forward;
    public:
      EdgeIt() { }
      EdgeIt(const Invalid& i) : e(i), forward(false) { }
      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
        forward=true;
        resG.graph->first(e);
        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        if (!resG.graph->valid(e)) {
          forward=false;
          resG.graph->first(e);
          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
        }
      }
      operator Edge() const { 
        return Edge(e, this->forward);
      }
    };

    using GraphWrapper<Graph>::first;
//     NodeIt& first(NodeIt& i) const { 
//       i=NodeIt(*this); return i;
//     }
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
      i=OutEdgeIt(*this, p); return i;
    }
//    FIXME not tested
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
      i=InEdgeIt(*this, p); return i;
    }
    EdgeIt& first(EdgeIt& i) const { 
      i=EdgeIt(*this); return i;
    }
  
    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    OutEdgeIt& next(OutEdgeIt& e) const { 
      if (e.forward) {
        Node v=this->graph->aNode(e.out);
        this->graph->next(e.out);
        while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
          this->graph->next(e.out); }
        if (!this->graph->valid(e.out)) {
          e.forward=false;
          this->graph->first(e.in, v); 
          while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
            this->graph->next(e.in); }
        }
      } else {
        this->graph->next(e.in);
        while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
          this->graph->next(e.in); } 
      }
      return e;
    }
//     FIXME Not tested
    InEdgeIt& next(InEdgeIt& e) const { 
      if (e.forward) {
        Node v=this->graph->aNode(e.in);
        this->graph->next(e.in);
        while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
          this->graph->next(e.in); }
        if (!this->graph->valid(e.in)) {
          e.forward=false;
          this->graph->first(e.out, v); 
          while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
            this->graph->next(e.out); }
        }
      } else {
        this->graph->next(e.out);
        while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
          this->graph->next(e.out); } 
      }
      return e;
    }
    EdgeIt& next(EdgeIt& e) const {
      if (e.forward) {
        this->graph->next(e.e);
        while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
          this->graph->next(e.e); }
        if (!this->graph->valid(e.e)) {
          e.forward=false;
          this->graph->first(e.e); 
          while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
            this->graph->next(e.e); }
        }
      } else {
        this->graph->next(e.e);
        while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
          this->graph->next(e.e); } 
      }
      return e;
    }

    Node tail(Edge e) const { 
      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
    Node head(Edge e) const { 
      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }

    Node aNode(OutEdgeIt e) const { 
      return ((e.forward) ? this->graph->aNode(e.out) : 
              this->graph->aNode(e.in)); }
    Node bNode(OutEdgeIt e) const { 
      return ((e.forward) ? this->graph->bNode(e.out) : 
              this->graph->bNode(e.in)); }

    Node aNode(InEdgeIt e) const { 
      return ((e.forward) ? this->graph->aNode(e.in) : 
              this->graph->aNode(e.out)); }
    Node bNode(InEdgeIt e) const { 
      return ((e.forward) ? this->graph->bNode(e.in) : 
              this->graph->bNode(e.out)); }

//    int nodeNum() const { return graph->nodeNum(); }
    //FIXME
    void edgeNum() const { }
    //int edgeNum() const { return graph->edgeNum(); }


//    int id(Node v) const { return graph->id(v); }

    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
    bool valid(Edge e) const { 
      return this->graph->valid(e);
        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
    }

    void augment(const Edge& e, Number a) const {
      if (e.forward)  
//      flow->set(e.out, flow->get(e.out)+a);
        flow->set(e, (*flow)[e]+a);
      else  
//      flow->set(e.in, flow->get(e.in)-a);
        flow->set(e, (*flow)[e]-a);
    }

    Number resCap(const Edge& e) const { 
      if (e.forward) 
//      return (capacity->get(e.out)-flow->get(e.out)); 
        return ((*capacity)[e]-(*flow)[e]); 
      else 
//      return (flow->get(e.in)); 
        return ((*flow)[e]); 
    }

//     Number resCap(typename Graph::OutEdgeIt out) const { 
// //      return (capacity->get(out)-flow->get(out)); 
//       return ((*capacity)[out]-(*flow)[out]); 
//     }
    
//     Number resCap(typename Graph::InEdgeIt in) const { 
// //      return (flow->get(in)); 
//       return ((*flow)[in]); 
//     }

    template <typename T>
    class EdgeMap {
      typename Graph::template EdgeMap<T> forward_map, backward_map; 
    public:
      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
      void set(Edge e, T a) { 
        if (e.forward) 
          forward_map.set(e.out, a); 
        else 
          backward_map.set(e.in, a); 
      }
      T operator[](Edge e) const { 
        if (e.forward) 
          return forward_map[e.out]; 
        else 
          return backward_map[e.in]; 
      }
//       T get(Edge e) const { 
//      if (e.out_or_in) 
//        return forward_map.get(e.out); 
//      else 
//        return backward_map.get(e.in); 
//       }
    };
  };

  /// ErasingFirstGraphWrapper for blocking flows.

  /// ErasingFirstGraphWrapper for blocking flows.
  ///
  ///\author Marton Makai
  template<typename Graph, typename FirstOutEdgesMap>
  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
  protected:
    FirstOutEdgesMap* first_out_edges;
  public:
    ErasingFirstGraphWrapper(Graph& _graph, 
                             FirstOutEdgesMap& _first_out_edges) : 
      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  

    typedef typename GraphWrapper<Graph>::Node Node;
//     class NodeIt { 
//       friend class GraphWrapper<Graph>;
//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//       typename Graph::NodeIt n;
//      public:
//       NodeIt() { }
//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
//       NodeIt(const Invalid& i) : n(i) { }
//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
//      n(*(_G.graph)) { }
//       operator Node() const { return Node(typename Graph::Node(n)); }
//     };
    typedef typename GraphWrapper<Graph>::Edge Edge;
    class OutEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
      typename Graph::OutEdgeIt e;
    public:
      OutEdgeIt() { }
      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
      OutEdgeIt(const Invalid& i) : e(i) { }
      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
                const Node& _n) : 
        e((*_G.first_out_edges)[_n]) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    class InEdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
      typename Graph::InEdgeIt e;
    public:
      InEdgeIt() { }
      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
      InEdgeIt(const Invalid& i) : e(i) { }
      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
               const Node& _n) : 
        e(*(_G.graph), typename Graph::Node(_n)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };
    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    class EdgeIt { 
      friend class GraphWrapper<Graph>;
      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
//      typedef typename Graph::EdgeIt GraphEdgeIt;
      typename Graph::EdgeIt e;
    public:
      EdgeIt() { }
      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
      EdgeIt(const Invalid& i) : e(i) { }
      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
        e(*(_G.graph)) { }
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    };

    using GraphWrapper<Graph>::first;
//     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;
    }

    using GraphWrapper<Graph>::next;
//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
    
    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)); }

    void erase(const OutEdgeIt& e) const {
      OutEdgeIt f=e;
      this->next(f);
      first_out_edges->set(this->tail(e), f.e);
    }
  };

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

  public:
    //marci
    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
    //static const bool S_CLASS=false;
    //static const bool T_CLASS=true;
    
    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)); 
    }

    bool inSClass(const Node& n) const {
      return !(*(this->s_false_t_true_map))[n];
    }
    bool inTClass(const Node& n) const {
      return (*(this->s_false_t_true_map))[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; 
//   }

  /// experimentral, do not try it.
  /// It eats a bipartite graph, oriented from S to T.
  /// Such one can be made e.g. by the above wrapper.
  ///
  ///\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, typename Parent> class EdgeMap;

//    template <typename T> friend class NodeMap;
//    template <typename T> friend class EdgeMap;

    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, typename Parent> 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; }
    };

    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;
      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);
          break;
        case 1:
          return s_value;
          break;
        case 2: 
        default:
          return t_value;
          break;
        }
      }
      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;
        }
      }
    };

    template<typename T, 
             typename Parent=
             typename GraphWrapper<Graph>::template EdgeMap<T> > 
    class EdgeMap : public Parent { 
      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
      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);
          break;
        case 1:
          return node_value[e.n];
          break;
        case 2:
        default:
          return node_value[e.n];
          break;
        }
      }
      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;
        }
      }
    };

//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
//       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);
//        break;
//      case 1:
//        return node_value[e.n];
//        break;
//      case 2:
//      default:
//        return node_value[e.n];
//        break;
//      }
//       }
//       void set(const Edge& e, T t) { 
//      switch (e.spec) {
//      case 0: 
//        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
//        break;
//      case 1:
//        node_value.set(e.n, t);
//        break;
//      case 2:
//      default:
//        node_value.set(e.n, 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_GRAPH_WRAPPER_H