RhodeCode

    /// arc of the underlying digraph.

    static Arc backward(const typename Digraph::Arc& a) {

      return Undirected::direct(a, false);

    }

    /// \brief Residual capacity map.

    ///

    /// This map adaptor class can be used for obtaining the residual

    /// capacities as an arc map of the residual digraph.

    /// Its value type is inherited from the capacity map.

    class ResidualCapacity {

    protected:

      const Adaptor* _adaptor;

    public:

      /// The key type of the map

      typedef Arc Key;

      /// The value type of the map

      typedef typename CapacityMap::Value Value;

      /// Constructor

      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 

        : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

      Value operator[](const Arc& a) const {

        return _adaptor->residualCapacity(a);

      }

    };

    /// \brief Returns a residual capacity map

    ///

    /// This function just returns a residual capacity map.

    ResidualCapacity residualCapacity() const {

      return ResidualCapacity(*this);

    }

  };

  /// \brief Returns a (read-only) Residual adaptor

  ///

  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates ResidualDigraph

    template<typename DGR, typename CM, typename FM>

  ResidualDigraph<DGR, CM, FM>

  residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) {

    return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map);

  }

  template <typename DGR>

  class SplitNodesBase {

  public:

    typedef DGR Digraph;

    typedef DigraphAdaptorBase<const DGR> Parent;

    typedef SplitNodesBase Adaptor;

    typedef typename DGR::Node DigraphNode;

    typedef typename DGR::Arc DigraphArc;

    class Node;

    class Arc;

  private:

    template <typename T> class NodeMapBase;

    template <typename T> class ArcMapBase;

  public:

    class Node : public DigraphNode {

      friend class SplitNodesBase;

      template <typename T> friend class NodeMapBase;

    private:

      bool _in;

      Node(DigraphNode node, bool in)

        : DigraphNode(node), _in(in) {}

    public:

      Node() {}

      Node(Invalid) : DigraphNode(INVALID), _in(true) {}

      bool operator==(const Node& node) const {

        return DigraphNode::operator==(node) && _in == node._in;

      }

      bool operator!=(const Node& node) const {

        return !(*this == node);

      }

      bool operator<(const Node& node) const {

        return DigraphNode::operator<(node) ||

          (DigraphNode::operator==(node) && _in < node._in);

      }

    };

    class Arc {

      friend class SplitNodesBase;

      template <typename T> friend class ArcMapBase;

    private:

      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;

      explicit Arc(const DigraphArc& arc) : _item(arc) {}

      explicit Arc(const DigraphNode& node) : _item(node) {}

      ArcImpl _item;

    public:

      Arc() {}

      Arc(Invalid) : _item(DigraphArc(INVALID)) {}

      bool operator==(const Arc& arc) const {

        if (_item.firstState()) {

          if (arc._item.firstState()) {

            return _item.first() == arc._item.first();

          }

        } else {

          if (arc._item.secondState()) {

            return _item.second() == arc._item.second();

          }

        }

        return false;

      }

      bool operator!=(const Arc& arc) const {

        return !(*this == arc);

      }

      bool operator<(const Arc& arc) const {

        if (_item.firstState()) {

          if (arc._item.firstState()) {

            return _item.first() < arc._item.first();

          }

          return false;

        } else {

          if (arc._item.secondState()) {

            return _item.second() < arc._item.second();

          }

          return true;

        }

      }

      operator DigraphArc() const { return _item.first(); }

      operator DigraphNode() const { return _item.second(); }

    };

    void first(Node& n) const {

      _digraph->first(n);

      n._in = true;

    }

    void next(Node& n) const {

      if (n._in) {

        n._in = false;

      } else {

        n._in = true;

        _digraph->next(n);

      }

    }

    void first(Arc& e) const {

      e._item.setSecond();

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

      if (e._item.second() == INVALID) {

        e._item.setFirst();

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

      }

    }

    void next(Arc& e) const {

      if (e._item.secondState()) {

        _digraph->next(e._item.second());

        if (e._item.second() == INVALID) {

          e._item.setFirst();

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

        }

      } else {

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

      }

    }

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

      if (n._in) {

        e._item.setSecond(n);

      } else {

        e._item.setFirst();

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

      }

    }

    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

    /// (\c InNodeMap).

    template <typename InNodeMap, typename OutNodeMap>

    class CombinedNodeMap {

    public:

      /// The key type of the map

      typedef Node Key;

      /// The value type of the map

      typedef typename InNodeMap::Value Value;

      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;

      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;

      /// Constructor

      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)

        : _in_map(in_map), _out_map(out_map) {}

      /// Returns the value associated with the given key.

      Value operator[](const Key& key) const {

        if (SplitNodesBase<const DGR>::inNode(key)) {

          return _in_map[key];

        } else {

          return _out_map[key];

        }

      }

      /// Returns a reference to the value associated with the given key.

      Value& operator[](const Key& key) {

        if (SplitNodesBase<const DGR>::inNode(key)) {

          return _in_map[key];

        } else {

          return _out_map[key];

        }

      }

      /// Sets the value associated with the given key.

      void set(const Key& key, const Value& value) {

        if (SplitNodesBase<const DGR>::inNode(key)) {

          _in_map.set(key, value);

        } else {

          _out_map.set(key, value);

        }

      }

    private:

      InNodeMap& _in_map;

      OutNodeMap& _out_map;

    };

    /// \brief Returns a combined node map

    ///

    /// This function just returns a combined node map.

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<InNodeMap, OutNodeMap>

    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {

      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<const InNodeMap, OutNodeMap>

    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {

      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<InNodeMap, const OutNodeMap>

    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<const InNodeMap, const OutNodeMap>

    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<const InNodeMap,

        const OutNodeMap>(in_map, out_map);

    }

    /// \brief Arc map combined from an arc map and a node map of the

    /// original digraph.

    ///

    /// This map adaptor class adapts an arc map and a node map of the

    /// original digraph to get an arc map of the split digraph.

    /// Its value type is inherited from the original arc map type

    /// (\c ArcMap).

    template <typename ArcMap, typename NodeMap>

    class CombinedArcMap {

    public:

      /// The key type of the map

      typedef Arc Key;

      /// The value type of the map

      typedef typename ArcMap::Value Value;

      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<ArcMap>::ReturnValue Reference;

      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;

      /// Constructor

      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)

        : _arc_map(arc_map), _node_map(node_map) {}

      /// Returns the value associated with the given key.

      Value operator[](const Key& arc) const {

        if (SplitNodesBase<const DGR>::origArc(arc)) {

          return _arc_map[arc];

        } else {

          return _node_map[arc];

        }

      }

      /// Returns a reference to the value associated with the given key.

      Value& operator[](const Key& arc) {

        if (SplitNodesBase<const DGR>::origArc(arc)) {

          return _arc_map[arc];

        } else {

          return _node_map[arc];

        }

      }

      /// Sets the value associated with the given key.

      void set(const Arc& arc, const Value& val) {

        if (SplitNodesBase<const DGR>::origArc(arc)) {

          _arc_map.set(arc, val);

        } else {

          _node_map.set(arc, val);

        }

      }

    private:

      ArcMap& _arc_map;

      NodeMap& _node_map;

    };

    /// \brief Returns a combined arc map

    ///

    /// This function just returns a combined arc map.

    template <typename ArcMap, typename NodeMap>

    static CombinedArcMap<ArcMap, NodeMap>

    combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {

      return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);

    }

    template <typename ArcMap, typename NodeMap>

    static CombinedArcMap<const ArcMap, NodeMap>

    combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {

      return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);

    }

    template <typename ArcMap, typename NodeMap>

    static CombinedArcMap<ArcMap, const NodeMap>

    combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {

      return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);

    }

    template <typename ArcMap, typename NodeMap>

    static CombinedArcMap<const ArcMap, const NodeMap>

    combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {

      return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);

    }

  };

  /// \brief Returns a (read-only) SplitNodes adaptor

  ///

  /// This function just returns a (read-only) \ref SplitNodes adaptor.

  /// \ingroup graph_adaptors

  /// \relates SplitNodes

  template<typename DGR>

  SplitNodes<DGR>

  splitNodes(const DGR& digraph) {

    return SplitNodes<DGR>(digraph);

  }

#undef LEMON_SCOPE_FIX

} //namespace lemon

#endif //LEMON_ADAPTORS_H