RhodeCode

      }

    }

    void nextOut(Arc& e) const {

      if (!e._item.firstState()) {

        e._item.setFirst(INVALID);

      } else {

        _digraph->nextOut(e._item.first());

      }

    }

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

      if (!n._in) {

        e._item.setSecond(n);

      } else {

        e._item.setFirst();

        _digraph->firstIn(e._item.first(), n);

      }

    }

    void nextIn(Arc& e) const {

      if (!e._item.firstState()) {

        e._item.setFirst(INVALID);

      } else {

        _digraph->nextIn(e._item.first());

      }

    }

    Node source(const Arc& e) const {

      if (e._item.firstState()) {

        return Node(_digraph->source(e._item.first()), false);

      } else {

        return Node(e._item.second(), true);

      }

    }

    Node target(const Arc& e) const {

      if (e._item.firstState()) {

        return Node(_digraph->target(e._item.first()), true);

      } else {

        return Node(e._item.second(), false);

      }

    }

    int id(const Node& n) const {

      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);

    }

    Node nodeFromId(int ix) const {

      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);

    }

    int maxNodeId() const {

      return 2 * _digraph->maxNodeId() + 1;

    }

    int id(const Arc& e) const {

      if (e._item.firstState()) {

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

      } else {

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

    }

    typedef True ArcNumTag;

    int arcNum() const {

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

    }

    typedef True FindArcTag;

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

                const Arc& prev = INVALID) const {

      if (inNode(u) && outNode(v)) {

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

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

          return Arc(u);

        }

      }

      else if (outNode(u) && inNode(v)) {

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

      }

      return INVALID;

    }

  private:

    template <typename V>

    class NodeMapBase

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

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

    public:

      typedef Node Key;

      typedef V Value;

      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;

      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;

      NodeMapBase(const SplitNodesBase<DGR>& adaptor)

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

      NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)

        : _in_map(*adaptor._digraph, value),

          _out_map(*adaptor._digraph, value) {}

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

        if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }

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

      }

      ReturnValue operator[](const Node& key) {

        if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; }

        else { return _out_map[key]; }

      }

      ConstReturnValue operator[](const Node& key) const {

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

        else { return _out_map[key]; }

      }

    private:

      NodeImpl _in_map, _out_map;

    };

    template <typename V>

    class ArcMapBase

      : public MapTraits<typename Parent::template ArcMap<V> > {

      typedef typename Parent::template ArcMap<V> ArcImpl;

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

    public:

      typedef Arc Key;

      typedef V Value;

      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;

      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;

      ArcMapBase(const SplitNodesBase<DGR>& adaptor)

        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}

      ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)

        : _arc_map(*adaptor._digraph, value),

          _node_map(*adaptor._digraph, value) {}

      void set(const Arc& key, const V& val) {

        if (SplitNodesBase<DGR>::origArc(key)) {

        } else {

        }

      }

      ReturnValue operator[](const Arc& key) {

        if (SplitNodesBase<DGR>::origArc(key)) {

        } else {

        }

      }

      ConstReturnValue operator[](const Arc& key) const {

        if (SplitNodesBase<DGR>::origArc(key)) {

        } else {

        }

      }

    private:

      ArcImpl _arc_map;

      NodeImpl _node_map;

    };

  public:

    template <typename V>

    class NodeMap

      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >

    {

    public:

      typedef V Value;

      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;

      NodeMap(const SplitNodesBase<DGR>& adaptor)

        : Parent(adaptor) {}

      NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)

        : Parent(adaptor, 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 V>

    class ArcMap

      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >

    {

    public:

      typedef V Value;

      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;

      ArcMap(const SplitNodesBase<DGR>& adaptor)

        : Parent(adaptor) {}

      ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)

        : Parent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  protected:

    SplitNodesBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(Digraph& digraph) {

      _digraph = &digraph;

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for splitting the nodes of a digraph.

  ///

  /// SplitNodes adaptor can be used for splitting each node into an

  /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor

  /// replaces each node \f$ u \f$ in the digraph with two nodes,

  /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.

  /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the

  /// new target of the arc will be \f$ u_{in} \f$ and similarly the

  /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.

  /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$

  /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.

  ///

  /// The aim of this class is running an algorithm with respect to node

  /// costs or capacities if the algorithm considers only arc costs or

  /// capacities directly.

  /// In this case you can use \c SplitNodes adaptor, and set the node

  /// costs/capacities of the original digraph to the \e bind \e arcs

  /// in the adaptor.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It is implicitly \c const.

  ///

  /// \note The \c Node type of this adaptor is converible to the \c Node

  /// type of the adapted digraph.

  template <typename DGR>

#ifdef DOXYGEN

  class SplitNodes {

#else

  class SplitNodes

    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {

#endif

  public:

    typedef DGR Digraph;

    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;

    typedef typename DGR::Node DigraphNode;

    typedef typename DGR::Arc DigraphArc;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    /// \brief Constructor

    ///

    /// Constructor of the adaptor.

    SplitNodes(const DGR& g) {

      Parent::initialize(g);

    }

    /// \brief Returns \c true if the given node is an in-node.

    ///

    /// Returns \c true if the given node is an in-node.

    static bool inNode(const Node& n) {

      return Parent::inNode(n);

    }

    /// \brief Returns \c true if the given node is an out-node.

    ///

    /// Returns \c true if the given node is an out-node.

    static bool outNode(const Node& n) {

      return Parent::outNode(n);

    }

    /// \brief Returns \c true if the given arc is an original arc.

    ///

    /// Returns \c true if the given arc is one of the arcs in the

    /// original digraph.

    static bool origArc(const Arc& a) {

      return Parent::origArc(a);

    }

    /// \brief Returns \c true if the given arc is a bind arc.

    ///

    /// Returns \c true if the given arc is a bind arc, i.e. it connects

    /// an in-node and an out-node.

    static bool bindArc(const Arc& a) {

      return Parent::bindArc(a);

    }

    /// \brief Returns the in-node created from the given original node.

    ///

    /// Returns the in-node created from the given original node.

    static Node inNode(const DigraphNode& n) {

      return Parent::inNode(n);

    }

    /// \brief Returns the out-node created from the given original node.

    ///

    /// Returns the out-node created from the given original node.

    static Node outNode(const DigraphNode& n) {

      return Parent::outNode(n);

    }

    /// \brief Returns the bind arc that corresponds to the given

    /// original node.

    ///

    /// Returns the bind arc in the adaptor that corresponds to the given

    /// original node, i.e. the arc connecting the in-node and out-node

    /// of \c n.

    static Arc arc(const DigraphNode& n) {

      return Parent::arc(n);

    }

    /// \brief Returns the arc that corresponds to the given original arc.

    ///

    /// Returns the arc in the adaptor that corresponds to the given

    /// original arc.

    static Arc arc(const DigraphArc& a) {

      return Parent::arc(a);

    }

    /// \brief Node map combined from two original node maps

    ///

    /// This map adaptor class adapts two node maps of the original digraph

    /// to get a node map of the split digraph.

    /// Its value type is inherited from the first node map type