RhodeCode

    private:

      const CapacityMap* _capacity;

      const FlowMap* _flow;

      Tolerance _tolerance;

    public:

      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,

                        const Tolerance& tolerance = Tolerance())

        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }

      bool operator[](const typename Digraph::Arc& a) const {

        return _tolerance.positive((*_flow)[a]);

      }

    };

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for composing the residual digraph for directed

  /// flow and circulation problems.

  ///

  /// This adaptor implements a digraph structure with node set \f$ V \f$

  /// and arc set \f$ A_{forward}\cup A_{backward} \f$,

  /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and

  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so

  /// called residual digraph.

  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,

  /// multiplicities are counted, i.e. the adaptor has exactly

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

  /// arcs).

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

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

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

  /// It is implicitly \c const.

  /// \tparam CM The type of the capacity map.

  /// It must be an arc map of some numerical type, which defines

  /// the capacities in the flow problem. It is implicitly \c const.

  /// The default type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam FM The type of the flow map.

  /// It must be an arc map of some numerical type, which defines

  /// the flow values in the flow problem. The default type is \c CM.

  /// \tparam TL The tolerance type for handling inexact computation.

  /// The default tolerance type depends on the value type of the

  /// capacity map.

  ///

  /// \note This adaptor is implemented using Undirector and FilterArcs

  /// adaptors.

  ///

  /// \note The \c Node type of this adaptor and the adapted digraph are

  /// convertible to each other, moreover the \c Arc type of the adaptor

  /// is convertible to the \c Arc type of the adapted digraph.

#ifdef DOXYGEN

  template<typename GR, typename CM, typename FM, typename TL>

#else

  template<typename GR,

           typename CM = typename GR::template ArcMap<int>,

           typename FM = CM,

           typename TL = Tolerance<typename CM::Value> >

    public FilterArcs<

      Undirector<const GR>,

      typename Undirector<const GR>::template CombinedArcMap<

        _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,

        _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >

#endif

  {

  public:

    /// The type of the underlying digraph.

    typedef GR Digraph;

    /// The type of the capacity map.

    typedef CM CapacityMap;

    /// The type of the flow map.

    typedef FM FlowMap;

    /// The tolerance type.

    typedef TL Tolerance;

    typedef typename CapacityMap::Value Value;

  protected:

    typedef Undirector<const Digraph> Undirected;

    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,

                                            FlowMap, Tolerance> ForwardFilter;

    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,

                                             FlowMap, Tolerance> BackwardFilter;

    typedef typename Undirected::

      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;

    typedef FilterArcs<Undirected, ArcFilter> Parent;

    const CapacityMap* _capacity;

    FlowMap* _flow;

    Undirected _graph;

    ForwardFilter _forward_filter;

    BackwardFilter _backward_filter;

    ArcFilter _arc_filter;

  public:

    /// \brief Constructor

    ///

    /// Constructor of the residual digraph adaptor. The parameters are the

    /// digraph, the capacity map, the flow map, and a tolerance object.

      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),

        _forward_filter(capacity, flow, tolerance),

        _backward_filter(capacity, flow, tolerance),

        _arc_filter(_forward_filter, _backward_filter)

    {

      Parent::setDigraph(_graph);

      Parent::setArcFilterMap(_arc_filter);

    }

    typedef typename Parent::Arc Arc;

    /// \brief Returns the residual capacity of the given arc.

    ///

    /// Returns the residual capacity of the given arc.

    Value residualCapacity(const Arc& a) const {

      if (Undirected::direction(a)) {

        return (*_capacity)[a] - (*_flow)[a];

      } else {

        return (*_flow)[a];

      }

    }

    /// \brief Augments on the given arc in the residual digraph.

    ///

      ResidualCapacity(const Adaptor& 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 Residual adaptor.

  /// \ingroup graph_adaptors

  /// \relates Residual

  template<typename GR, typename CM, typename FM>

  }

  template <typename _Digraph>

  class SplitNodesBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<const _Digraph> Parent;

    typedef SplitNodesBase Adaptor;

    typedef typename Digraph::Node DigraphNode;

    typedef typename Digraph::Arc DigraphArc;

    class Node;

    class Arc;

  private:

    template <typename T> class NodeMapBase;

    template <typename T> class ArcMapBase;

  public:

    bk_map[a] = -digraph.id(a);

  }

  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >

    comb_map(fw_map, bk_map);

  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

    if (adaptor.source(a) == digraph.source(a)) {

      check(comb_map[a] == fw_map[a], "Wrong combined map");

    } else {

      check(comb_map[a] == bk_map[a], "Wrong combined map");

    }

  }

  // Check the conversion of nodes and arcs/edges

  Digraph::Node nd = n3;

  nd = n3;

  Adaptor::Node na = n1;

  na = n2;

  Digraph::Arc ad = e3;

  ad = e3;

  Adaptor::Edge ea = a1;

  ea = a2;

}

  // Check concepts

  // Create a digraph and an adaptor

  typedef ListDigraph Digraph;

  typedef Digraph::ArcMap<int> IntArcMap;

  Digraph digraph;

  IntArcMap capacity(digraph), flow(digraph);

  Adaptor adaptor(digraph, capacity, flow);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Node n4 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n1, n4);

  Digraph::Arc a4 = digraph.addArc(n2, n3);

  Digraph::Arc a5 = digraph.addArc(n2, n4);

  Digraph::Arc a6 = digraph.addArc(n3, n4);

  capacity[a1] = 8;

  capacity[a2] = 6;

  capacity[a3] = 4;

  capacity[a4] = 4;

  capacity[a5] = 6;

  capacity[a6] = 10;

  // Check uuadaptor

  checkGraphNodeList(uuadaptor, 8);

  checkGraphEdgeList(uuadaptor, 16);

  checkGraphArcList(uuadaptor, 32);

  checkGraphConEdgeList(uuadaptor, 16);

  checkGraphConArcList(uuadaptor, 32);

  checkNodeIds(uuadaptor);

  checkEdgeIds(uuadaptor);

  checkArcIds(uuadaptor);

  checkGraphNodeMap(uuadaptor);

  checkGraphEdgeMap(uuadaptor);

  checkGraphArcMap(uuadaptor);

}

int main(int, const char **) {

  // Check the digraph adaptors (using ListDigraph)

  checkReverseDigraph();

  checkSubDigraph();

  checkFilterNodes1();

  checkFilterArcs();

  checkUndirector();

  checkSplitNodes();

  // Check the graph adaptors (using ListGraph)

  checkSubGraph();

  checkFilterNodes2();

  checkFilterEdges();

  checkOrienter();

  // Combine adaptors (using GridGraph)

  checkCombiningAdaptors();

  return 0;

}