RhodeCode

///

/// This file contains several useful adaptors for digraphs and graphs.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/variant.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/tolerance.h>

#include <algorithm>

namespace lemon {

  template<typename _Digraph>

  class DigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase Adaptor;

    typedef Digraph ParentDigraph;

  protected:

    Digraph* _digraph;

    DigraphAdaptorBase() : _digraph(0) { }

    void setDigraph(Digraph& digraph) { _digraph = &digraph; }

  public:

    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    void first(Node& i) const { _digraph->first(i); }

    void first(Arc& i) const { _digraph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }

    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }

    void next(Node& i) const { _digraph->next(i); }

    void next(Arc& i) const { _digraph->next(i); }

    void nextIn(Arc& i) const { _digraph->nextIn(i); }

    void nextOut(Arc& i) const { _digraph->nextOut(i); }

    Node source(const Arc& a) const { return _digraph->source(a); }

    Node target(const Arc& a) const { return _digraph->target(a); }

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

    int nodeNum() const { return _digraph->nodeNum(); }

    int arcNum() const { return _digraph->arcNum(); }

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {

      return _digraph->findArc(u, v, prev);

    }

    Node addNode() { return _digraph->addNode(); }

    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }

    void erase(const Node& n) const { _digraph->erase(n); }

    void erase(const Arc& a) const { _digraph->erase(a); }

    void clear() const { _digraph->clear(); }

    int id(const Node& n) const { return _digraph->id(n); }

    int id(const Arc& a) const { return _digraph->id(a); }

    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }

    int maxNodeId() const { return _digraph->maxNodeId(); }

    int maxArcId() const { return _digraph->maxArcId(); }

    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }

    template <typename _Value>

    class NodeMap : public Digraph::template NodeMap<_Value> {

    public:

      typedef typename Digraph::template NodeMap<_Value> Parent;

      explicit NodeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      NodeMap(const Adaptor& adaptor, const _Value& value)

        : Parent(*adaptor._digraph, value) { }

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

  };

  template<typename _Graph>

  class GraphAdaptorBase {

  public:

    typedef _Graph Graph;

    typedef Graph ParentGraph;

  protected:

    Graph* _graph;

    GraphAdaptorBase() : _graph(0) {}

    void setGraph(Graph& graph) { _graph = &graph; }

  public:

    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}

    typedef typename Graph::Node Node;

    typedef typename Graph::Arc Arc;

    typedef typename Graph::Edge Edge;

    void first(Node& i) const { _graph->first(i); }

    void first(Arc& i) const { _graph->first(i); }

    void first(Edge& i) const { _graph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }

    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }

    void firstInc(Edge &i, bool &d, const Node &n) const {

      _graph->firstInc(i, d, n);

    }

    void next(Node& i) const { _graph->next(i); }

    void next(Arc& i) const { _graph->next(i); }

    void next(Edge& i) const { _graph->next(i); }

    void nextIn(Arc& i) const { _graph->nextIn(i); }

    void nextOut(Arc& i) const { _graph->nextOut(i); }

    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }

    Node u(const Edge& e) const { return _graph->u(e); }

    Node v(const Edge& e) const { return _graph->v(e); }

    Node source(const Arc& a) const { return _graph->source(a); }

    Node target(const Arc& a) const { return _graph->target(a); }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

    int nodeNum() const { return _graph->nodeNum(); }

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

    int edgeNum() const { return _graph->edgeNum(); }

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {

      return _graph->findArc(u, v, prev);

    }

    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {

      return _graph->findEdge(u, v, prev);

    }

    Node addNode() { return _graph->addNode(); }

    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }

    void erase(const Node& i) { _graph->erase(i); }

    void erase(const Edge& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    bool direction(const Arc& a) const { return _graph->direction(a); }

    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }

    int id(const Node& v) const { return _graph->id(v); }

    int id(const Arc& a) const { return _graph->id(a); }

    int id(const Edge& e) const { return _graph->id(e); }

    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }

    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxArcId(); }

    int maxEdgeId() const { return _graph->maxEdgeId(); }

    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }

    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }

    template <typename _Value>

    class NodeMap : public Graph::template NodeMap<_Value> {

    public:

      typedef typename Graph::template NodeMap<_Value> Parent;

      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)

        : Parent(*adapter._graph) {}

      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

        : Parent(*adapter._graph, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

    };

    template <typename _Value>

    class EdgeMap : public Graph::template EdgeMap<_Value> {

    public:

      typedef typename Graph::template EdgeMap<_Value> Parent;

      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)

        : Parent(*adapter._graph) {}

      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)

        : Parent(*adapter._graph, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename _Digraph>

  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  protected:

    ReverseDigraphBase() : Parent() { }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }

    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }

    void nextIn(Arc& a) const { Parent::nextOut(a); }

    void nextOut(Arc& a) const { Parent::nextIn(a); }

    Node source(const Arc& a) const { return Parent::target(a); }

    Node target(const Arc& a) const { return Parent::source(a); }

    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) {

      return Parent::findArc(v, u, prev);

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief A digraph adaptor which reverses the orientation of the arcs.

  ///

  /// ReverseDigraph reverses the arcs in the adapted digraph. The

  /// SubDigraph is conform to the \ref concepts::Digraph

  /// "Digraph concept".

  ///

  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph

  /// "Digraph concept". The type can be specified to be const.

  template<typename _Digraph>

  class ReverseDigraph :

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<

      ReverseDigraphBase<_Digraph> > Parent;

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

    /// Creates a reverse digraph adaptor for the given digraph

    explicit ReverseDigraph(Digraph& digraph) {

      Parent::setDigraph(digraph);

    }

  };

  /// \brief Just gives back a reverse digraph adaptor

  ///

  /// Just gives back a reverse digraph adaptor

  template<typename Digraph>

  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {

    return ReverseDigraph<const Digraph>(digraph);

  }

  template <typename _Digraph, typename _NodeFilterMap,

            typename _ArcFilterMap, bool _checked = true>

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

                              || !(*_node_filter)[Parent::source(i)]))

        Parent::nextIn(i);

    }

    void firstOut(Arc& i, const Node& n) const {

      Parent::firstOut(i, n);

      while (i != INVALID && (!(*_arc_filter)[i]

                              || !(*_node_filter)[Parent::target(i)]))

        Parent::nextOut(i);

    }

    void next(Node& i) const {

      Parent::next(i);

      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);

    }

    void next(Arc& i) const {

      Parent::next(i);

      while (i != INVALID && (!(*_arc_filter)[i]

                              || !(*_node_filter)[Parent::source(i)]

                              || !(*_node_filter)[Parent::target(i)]))

        Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i != INVALID && (!(*_arc_filter)[i]

                              || !(*_node_filter)[Parent::source(i)]))

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

      while (i != INVALID && (!(*_arc_filter)[i]

                              || !(*_node_filter)[Parent::target(i)]))

        Parent::nextOut(i);

    }

    void hide(const Node& n) const { _node_filter->set(n, false); }

    void hide(const Arc& a) const { _arc_filter->set(a, false); }

    void unHide(const Node& n) const { _node_filter->set(n, true); }

    void unHide(const Arc& a) const { _arc_filter->set(a, true); }

    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }

    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }

    typedef False NodeNumTag;

    Arc findArc(const Node& source, const Node& target,

                const Arc& prev = INVALID) {

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

      while (arc != INVALID && !(*_arc_filter)[arc]) {

        arc = Parent::findArc(source, target, arc);

      }

      return arc;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

    void first(Node& i) const {

      Parent::first(i);

      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

    }

    void first(Arc& i) const {

      Parent::first(i);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);

    }

    void firstIn(Arc& i, const Node& n) const {

      Parent::firstIn(i, n);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);

    }

    void firstOut(Arc& i, const Node& n) const {

      Parent::firstOut(i, n);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

    }

    void next(Node& i) const {

      Parent::next(i);

      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);

    }

    void next(Arc& i) const {

      Parent::next(i);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

    }

    void hide(const Node& n) const { _node_filter->set(n, false); }

    void hide(const Arc& e) const { _arc_filter->set(e, false); }

    void unHide(const Node& n) const { _node_filter->set(n, true); }

    void unHide(const Arc& e) const { _arc_filter->set(e, true); }

    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }

    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }

    typedef False NodeNumTag;

    Arc findArc(const Node& source, const Node& target,

                const Arc& prev = INVALID) {

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

      while (arc != INVALID && !(*_arc_filter)[arc]) {

        arc = Parent::findArc(source, target, arc);

      }

      return arc;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

    void next(Arc& i) const {

      Parent::next(i);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

                            || !(*_node_filter_map)[Parent::source(i)]

                            || !(*_node_filter_map)[Parent::target(i)]))

        Parent::next(i);

    }

    void next(Edge& i) const {

      Parent::next(i);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

                            || !(*_node_filter_map)[Parent::u(i)]

                            || !(*_node_filter_map)[Parent::v(i)]))

        Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

                            || !(*_node_filter_map)[Parent::source(i)]))

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

                            || !(*_node_filter_map)[Parent::target(i)]))

        Parent::nextOut(i);

    }

    void nextInc(Edge& i, bool& d) const {

      Parent::nextInc(i, d);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

                            || !(*_node_filter_map)[Parent::u(i)]

                            || !(*_node_filter_map)[Parent::v(i)]))

        Parent::nextInc(i, d);

    }

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) {

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(u, v, prev);

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

        arc = Parent::findArc(u, v, arc);

      }

      return arc;

    }

    Edge findEdge(const Node& u, const Node& v,

                  const Edge& prev = INVALID) {

      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {

        return INVALID;

      }

      Edge edge = Parent::findEdge(u, v, prev);

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

    }

    void firstOut(Arc& i, const Node& n) const {

      Parent::firstOut(i, n);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);

    }

    void firstInc(Edge& i, bool& d, const Node& n) const {

      Parent::firstInc(i, d, n);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);

    }

    void next(Node& i) const {

      Parent::next(i);

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);

    }

    void next(Arc& i) const {

      Parent::next(i);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);

    }

    void next(Edge& i) const {

      Parent::next(i);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);

    }

    void nextInc(Edge& i, bool& d) const {

      Parent::nextInc(i, d);

      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);

    }

    void hide(const Node& n) const { _node_filter_map->set(n, false); }

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

    void unHide(const Node& n) const { _node_filter_map->set(n, true); }

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }

    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) {

      Arc arc = Parent::findArc(u, v, prev);

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

        arc = Parent::findArc(u, v, arc);

      }

      return arc;

    }

    Edge findEdge(const Node& u, const Node& v,

                  const Edge& prev = INVALID) {

      Edge edge = Parent::findEdge(u, v, prev);

      while (edge != INVALID && !(*_edge_filter_map)[edge]) {

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      NodeMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      return _digraph->target(e);

    }

    Node source(const Arc &a) const {

      return a._forward ? _digraph->source(a) : _digraph->target(a);

    }

    Node target(const Arc &a) const {

      return a._forward ? _digraph->target(a) : _digraph->source(a);

    }

    static Arc direct(const Edge &e, bool d) {

      return Arc(e, d);

    }

    Arc direct(const Edge &e, const Node& n) const {

      return Arc(e, _digraph->source(e) == n);

    }

    static bool direction(const Arc &a) { return a._forward; }

    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

    Arc arcFromId(int ix) const {

      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));

    }

    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }

    int id(const Node &n) const { return _digraph->id(n); }

    int id(const Arc &a) const {

      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);

    }

    int id(const Edge &e) const { return _digraph->id(e); }

    int maxNodeId() const { return _digraph->maxNodeId(); }

    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }

    int maxEdgeId() const { return _digraph->maxArcId(); }

    Node addNode() { return _digraph->addNode(); }

    Edge addEdge(const Node& u, const Node& v) {

      return _digraph->addArc(u, v);

    }

    void erase(const Node& i) { _digraph->erase(i); }

    void erase(const Edge& i) { _digraph->erase(i); }

    void clear() { _digraph->clear(); }

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

    int nodeNum() const { return 2 * _digraph->arcNum(); }

    int arcNum() const { return 2 * _digraph->arcNum(); }

    int edgeNum() const { return _digraph->arcNum(); }

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

      if (p == INVALID) {

        Edge arc = _digraph->findArc(s, t);

        if (arc != INVALID) return direct(arc, true);

        arc = _digraph->findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else if (direction(p)) {

        Edge arc = _digraph->findArc(s, t, p);

        if (arc != INVALID) return direct(arc, true);

        arc = _digraph->findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else {

        Edge arc = _digraph->findArc(t, s, p);

        if (arc != INVALID) return direct(arc, false);

      }

      return INVALID;

    }

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

      if (s != t) {

        if (p == INVALID) {

          Edge arc = _digraph->findArc(s, t);

          if (arc != INVALID) return arc;

          arc = _digraph->findArc(t, s);

          if (arc != INVALID) return arc;

        } else if (_digraph->s(p) == s) {

          Edge arc = _digraph->findArc(s, t, p);

          if (arc != INVALID) return arc;

          arc = _digraph->findArc(t, s);

          if (arc != INVALID) return arc;

        } else {

          Edge arc = _digraph->findArc(t, s, p);

          if (arc != INVALID) return arc;

        }

      } else {

        return _digraph->findArc(s, t, p);

      }

      return INVALID;

    }

  private:

    template <typename _Value>

    class ArcMapBase {

    private:

      typedef typename Digraph::template ArcMap<_Value> MapImpl;

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef _Value Value;

      typedef Arc Key;

      ArcMapBase(const Adaptor& adaptor) :

        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

      ArcMapBase(const Adaptor& adaptor, const Value& v)

        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}

      void set(const Arc& a, const Value& v) {

        if (direction(a)) {

          _forward.set(a, v);

        } else {

          _backward.set(a, v);

  public:

    typedef _Graph Graph;

    typedef _DirectionMap DirectionMap;

    typedef typename Graph::Node Node;

    typedef typename Graph::Edge Arc;

    void reverseArc(const Arc& arc) {

      _direction->set(arc, !(*_direction)[arc]);

    }

    void first(Node& i) const { _graph->first(i); }

    void first(Arc& i) const { _graph->first(i); }

    void firstIn(Arc& i, const Node& n) const {

      bool d;

      _graph->firstInc(i, d, n);

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    }

    void firstOut(Arc& i, const Node& n ) const {

      bool d;

      _graph->firstInc(i, d, n);

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    }

    void next(Node& i) const { _graph->next(i); }

    void next(Arc& i) const { _graph->next(i); }

    void nextIn(Arc& i) const {

      bool d = !(*_direction)[i];

      _graph->nextInc(i, d);

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    }

    void nextOut(Arc& i) const {

      bool d = (*_direction)[i];

      _graph->nextInc(i, d);

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    }

    Node source(const Arc& e) const {

      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);

    }

    Node target(const Arc& e) const {

      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);

    }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

    int nodeNum() const { return _graph->nodeNum(); }

    int arcNum() const { return _graph->edgeNum(); }

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) {

      Arc arc = prev;

      bool d = arc == INVALID ? true : (*_direction)[arc];

      if (d) {

        arc = _graph->findEdge(u, v, arc);

        while (arc != INVALID && !(*_direction)[arc]) {

          _graph->findEdge(u, v, arc);

        }

        if (arc != INVALID) return arc;

      }

      _graph->findEdge(v, u, arc);

      while (arc != INVALID && (*_direction)[arc]) {

        _graph->findEdge(u, v, arc);

      }

      return arc;

    }

    Node addNode() {

      return Node(_graph->addNode());

    }

    Arc addArc(const Node& u, const Node& v) {

      Arc arc = _graph->addArc(u, v);

      _direction->set(arc, _graph->source(arc) == u);

      return arc;

    }

    void erase(const Node& i) { _graph->erase(i); }

    void erase(const Arc& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    int id(const Node& v) const { return _graph->id(v); }

    int id(const Arc& e) const { return _graph->id(e); }

    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }

    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxEdgeId(); }

    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }

    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

        return (_digraph->id(e._item.second()) << 1) | 1;

      }

    }

    Arc arcFromId(int ix) const {

      if ((ix & 1) == 0) {

        return Arc(_digraph->arcFromId(ix >> 1));

      } else {

        return Arc(_digraph->nodeFromId(ix >> 1));

      }

    }

    int maxArcId() const {

      return std::max(_digraph->maxNodeId() << 1,

                      (_digraph->maxArcId() << 1) | 1);

    }

    static bool inNode(const Node& n) {

      return n._in;

    }

    static bool outNode(const Node& n) {

      return !n._in;

    }

    static bool origArc(const Arc& e) {

      return e._item.firstState();

    }

    static bool bindArc(const Arc& e) {

      return e._item.secondState();

    }

    static Node inNode(const DigraphNode& n) {

      return Node(n, true);

    }

    static Node outNode(const DigraphNode& n) {

      return Node(n, false);

    }

    static Arc arc(const DigraphNode& n) {

      return Arc(n);

    }

    static Arc arc(const DigraphArc& e) {

      return Arc(e);

    }

    typedef True NodeNumTag;

    int nodeNum() const {

      return  2 * countNodes(*_digraph);

    }

    int arcNum() const {

      return countArcs(*_digraph) + countNodes(*_digraph);

    }

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) const {

      if (inNode(u)) {

        if (outNode(v)) {

          if (static_cast<const DigraphNode&>(u) ==

              static_cast<const DigraphNode&>(v) && prev == INVALID) {

            return Arc(u);

          }

        }

      } else {

        if (inNode(v)) {

          return Arc(::lemon::findArc(*_digraph, u, v, prev));

        }

      }

      return INVALID;

    }

  private:

    template <typename _Value>

    class NodeMapBase

      : public MapTraits<typename Parent::template NodeMap<_Value> > {

      typedef typename Parent::template NodeMap<_Value> NodeImpl;

    public:

      typedef Node Key;

      typedef _Value Value;

      NodeMapBase(const Adaptor& adaptor)

        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}

      NodeMapBase(const Adaptor& adaptor, const Value& value)

        : _in_map(*adaptor._digraph, value),

          _out_map(*adaptor._digraph, value) {}

      void set(const Node& key, const Value& val) {

        if (Adaptor::inNode(key)) { _in_map.set(key, val); }

        else {_out_map.set(key, val); }

      }

      typename MapTraits<NodeImpl>::ReturnValue

      operator[](const Node& key) {

        if (Adaptor::inNode(key)) { return _in_map[key]; }

        else { return _out_map[key]; }

      }

      typename MapTraits<NodeImpl>::ConstReturnValue

      operator[](const Node& key) const {

        if (Adaptor::inNode(key)) { return _in_map[key]; }

        else { return _out_map[key]; }