RhodeCode

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

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

  };

  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;

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

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

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

    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) {

    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:

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

      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: