RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/**

/**

@defgroup search Graph Search

@ingroup algs

\brief Common graph search algorithms.

This group contains the common graph search algorithms, namely

\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).

*/

/**

@defgroup shortest_path Shortest Path Algorithms

@ingroup algs

\brief Algorithms for finding shortest paths.

This group contains the algorithms for finding shortest paths in digraphs.

   source node when all arc lengths are non-negative.

 - \ref Suurballe A successive shortest path algorithm for finding

   arc-disjoint paths between two nodes having minimum total length.

*/

/**

@defgroup max_flow Maximum Flow Algorithms

@ingroup algs

\brief Algorithms for finding maximum flows.

This group contains the algorithms for finding maximum flows and

feasible circulations.

The \e maximum \e flow \e problem is to find a flow of maximum value between

a single source and a single target. Formally, there is a \f$G=(V,A)\f$

digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

\f$s, t \in V\f$ source and target nodes.

A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

following optimization problem.

\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]

\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

    \quad \forall u\in V\setminus\{s,t\} \f]

\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

\ref Preflow implements the preflow push-relabel algorithm of Goldberg and

Tarjan for solving this problem. It also provides functions to query the

minimum cut, which is the dual problem of maximum flow.

for finding feasible circulations, which is a somewhat different problem,

but it is strongly related to maximum flow.

For more information, see \ref Circulation.

*/

/**

@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms

@ingroup algs

\brief Algorithms for finding minimum cost flows and circulations.

This group contains the algorithms for finding minimum cost flows and

circulations. For more information about this problem and its dual

solution see \ref min_cost_flow "Minimum Cost Flow Problem".

\ref NetworkSimplex is an efficient implementation of the primal Network

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/*!

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/**

\section mcf_dual Dual Solution

The dual solution of the minimum cost flow problem is represented by

node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.

An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal

if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials

the following \e complementary \e slackness optimality conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - \f$\pi(u)<=0\f$;

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

All algorithms provide dual solution (node potentials), as well,

if an optimal flow is found.

\section mcf_eq Equality Form

The above \ref mcf_def "definition" is actually more general than the

usual formulation of the minimum cost flow problem, in which strict

equalities are required in the supply/demand contraints.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =

The \ref min_cost_flow_algs "algorithms" in LEMON support the general

form, so if you need the equality form, you have to ensure this additional

contraint manually.

\section mcf_leq Opposite Inequalites (LEQ Form)

Another possible definition of the minimum cost flow problem is

when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,

instead of the <em>"greater or equal"</em> (GEQ) constraints.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or

positive) and all the demands have to be satisfied, but there

could be supplies that are not carried out from the supply

nodes.

The equality form is also a special case of this form, of course.

You could easily transform this case to the \ref mcf_def "GEQ form"

of the problem by reversing the direction of the arcs and taking the

negative of the supply values (e.g. using \ref ReverseDigraph and

\ref NegMap adaptors).

However \ref NetworkSimplex algorithm also supports this form directly

for the sake of convenience.

Note that the optimality conditions for this supply constraint type are

slightly differ from the conditions that are discussed for the GEQ form,

namely the potentials have to be non-negative instead of non-positive.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_ADAPTORS_H

#define LEMON_ADAPTORS_H

    typedef DigraphAdaptorBase<DGR> Parent;

  public:

    typedef DGR Digraph;

    typedef NF NodeFilterMap;

    typedef AF ArcFilterMap;

    typedef SubDigraphBase Adaptor;

  protected:

    NF* _node_filter;

    AF* _arc_filter;

    SubDigraphBase()

      : Parent(), _node_filter(0), _arc_filter(0) { }

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    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]

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

    typedef FindArcTagIndicator<DGR> FindArcTag;

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

                const Arc& prev = INVALID) const {

      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;

    }

  public:

    template <typename V>

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

    public:

      typedef V Value;

      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

        : Parent(adaptor) {}

      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& 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>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

        : Parent(adaptor) {}

      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)

        : Parent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

    typedef DigraphAdaptorBase<DGR> Parent;

  public:

    typedef DGR Digraph;

    typedef NF NodeFilterMap;

    typedef AF ArcFilterMap;

    typedef SubDigraphBase Adaptor;

  protected:

    NF* _node_filter;

    AF* _arc_filter;

    SubDigraphBase()

      : Parent(), _node_filter(0), _arc_filter(0) { }

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

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

    }

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<DGR> FindArcTag;

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

                const Arc& prev = INVALID) const {

      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 V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

        : Parent(adaptor) {}

      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& 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>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

        : Parent(adaptor) {}

      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)

        : Parent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

    }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

                  const Edge& prev = INVALID) const {

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

        return INVALID;

      }

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

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

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

      }

      return edge;

    }

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

        : Parent(adaptor) {}

      NodeMap(const SubGraphBase<GR, NF, EF, ch>& 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>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

        : Parent(adaptor) {}

      ArcMap(const SubGraphBase<GR, NF, EF, ch>& 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;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

    public:

      typedef V Value;

      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

        : Parent(adaptor) {}

      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)

        : Parent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

  };

  template <typename GR, typename NF, typename EF>

  class SubGraphBase<GR, NF, EF, false>

    : public GraphAdaptorBase<GR> {

    typedef GraphAdaptorBase<GR> Parent;

  public:

    typedef GR Graph;

    typedef NF NodeFilterMap;

    typedef EF EdgeFilterMap;

    typedef SubGraphBase Adaptor;

  protected:

    NF* _node_filter;

    EF* _edge_filter;

    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

      Parent::initialize(graph);

      _node_filter = &node_filter;

      _edge_filter = &edge_filter;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

      Parent::first(i);

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

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

      }

      return arc;

    }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

                  const Edge& prev = INVALID) const {

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

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

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

      }

      return edge;

    }

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        : Parent(adaptor) {}

      NodeMap(const SubGraphBase<GR, NF, EF, false>& 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>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        : Parent(adaptor) {}

      ArcMap(const SubGraphBase<GR, NF, EF, false>& 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;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

    public:

      typedef V Value;

      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        : Parent(adaptor) {}

      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)

        : Parent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

  ///

  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the

  /// adapted (di)graph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR, typename NF>

  class FilterNodes {

#else

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

           typename Enable = void>

  class FilterNodes :

    public DigraphAdaptorExtender<

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,

                     true> > {

#endif

    typedef DigraphAdaptorExtender<

                     true> > Parent;

  public:

    typedef GR Digraph;

    typedef NF NodeFilterMap;

    typedef typename Parent::Node Node;

  protected:

    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;

    FilterNodes() : const_true_map() {}

  public:

    /// \brief Constructor

    ///

    /// Creates a subgraph for the given digraph or graph with the

    /// given node filter map.

      : Parent(), const_true_map()

    {

      Parent::initialize(graph, node_filter, const_true_map);

    }

    /// \brief Sets the status of the given node

    ///

    /// This function sets the status of the given node.

    /// It is done by simply setting the assigned value of \c n

    /// to \c v in the node filter map.

    void status(const Node& n, bool v) const { Parent::status(n, v); }

    /// \brief Returns the status of the given node

    ///

    /// This function returns the status of the given node.

    /// It is \c true if the given node is enabled (i.e. not hidden).

    /// jumps over it.

    /// It is the same as \ref status() "status(n, false)".

    void disable(const Node& n) const { Parent::status(n, false); }

    /// \brief Enables the given node

    ///

    /// This function enables the given node.

    /// It is the same as \ref status() "status(n, true)".

    void enable(const Node& n) const { Parent::status(n, true); }

  };

  template<typename GR, typename NF>

  class FilterNodes<GR, NF,

                    typename enable_if<UndirectedTagIndicator<GR> >::type> :

    public GraphAdaptorExtender<

                   true> > {

    typedef GraphAdaptorExtender<

                   true> > Parent;

  public:

    typedef GR Graph;

    typedef NF NodeFilterMap;

    typedef typename Parent::Node Node;

  protected:

    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;

    FilterNodes() : const_true_map() {}

  public:

  ///

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

  /// digraph are convertible to each other.

#ifdef DOXYGEN

  template<typename DGR,

           typename AF>

  class FilterArcs {

#else

  template<typename DGR,

           typename AF = typename DGR::template ArcMap<bool> >

  class FilterArcs :

    public DigraphAdaptorExtender<

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

                     AF, false> > {

#endif

    typedef DigraphAdaptorExtender<

                     AF, false> > Parent;

  public:

    /// The type of the adapted digraph.

    typedef DGR Digraph;

    /// The type of the arc filter map.

    typedef AF ArcFilterMap;

    typedef typename Parent::Arc Arc;

  protected:

    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;

    FilterArcs() : const_true_map() {}

  /// \tparam EF The type of the edge filter map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the

  /// adapted graph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR,

           typename EF>

  class FilterEdges {

#else

  template<typename GR,

           typename EF = typename GR::template EdgeMap<bool> >

  class FilterEdges :

    public GraphAdaptorExtender<

                   EF, false> > {

#endif

    typedef GraphAdaptorExtender<

                   EF, false> > Parent;

  public:

    /// The type of the adapted graph.

    typedef GR Graph;

    /// The type of the edge filter map.

    typedef EF EdgeFilterMap;

    typedef typename Parent::Edge Edge;

  protected:

    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;

    FilterEdges() : const_true_map(true) {

      Parent::setNodeFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

    /// Creates a subgraph for the given graph with the given edge

    /// filter map.

      : Parent(), const_true_map() {

      Parent::initialize(graph, const_true_map, edge_filter);

    }

    /// \brief Sets the status of the given edge

    ///

    /// This function sets the status of the given edge.

    /// It is done by simply setting the assigned value of \c e

    /// to \c v in the edge filter map.

    void status(const Edge& e, bool v) const { Parent::status(e, v); }

    /// \brief Returns the status of the given edge

    ///

    /// This function returns the status of the given edge.

    /// It is \c true if the given edge is enabled (i.e. not hidden).

    bool status(const Edge& e) const { return Parent::status(e); }

  class UndirectorBase {

  public:

    typedef DGR Digraph;

    typedef UndirectorBase Adaptor;

    typedef True UndirectedTag;

    typedef typename Digraph::Arc Edge;

    typedef typename Digraph::Node Node;

    class Arc {

      friend class UndirectorBase;

    protected:

      Edge _edge;

      bool _forward;

        : _edge(edge), _forward(forward) {}

    public:

      Arc() {}

      Arc(Invalid) : _edge(INVALID), _forward(true) {}

      operator const Edge&() const { return _edge; }

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

        return _forward == other._forward && _edge == other._edge;

      }

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

        return _forward != other._forward || _edge != other._edge;

      }

      bool operator<(const Arc &other) const {

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef V Value;

      typedef Arc Key;

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;

      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;

      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;

      typedef typename MapTraits<MapImpl>::ReturnValue Reference;

      ArcMapBase(const UndirectorBase<DGR>& adaptor) :

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

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

          _backward(*adaptor._digraph, value) {}

      void set(const Arc& a, const V& value) {

        if (direction(a)) {

          _forward.set(a, value);

        } else {

          _backward.set(a, value);

        }

      }

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

        if (direction(a)) {

          return _forward[a];

        } else {

          return _backward[a];

        }

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

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

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

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

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

    typedef EdgeNotifier ArcNotifier;

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

  protected:

    UndirectorBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(DGR& digraph) {

      _digraph = &digraph;

    }

  };

  /// \ingroup graph_adaptors

  /// 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 DGR, typename CM, typename FM, typename TL>

  class ResidualDigraph

#else

  template<typename DGR,

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

           typename FM = CM,

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

    : public SubDigraph<

        Undirector<const DGR>,

        ConstMap<typename DGR::Node, Const<bool, true> >,

        typename Undirector<const DGR>::template CombinedArcMap<

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

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

#endif

  {

  public:

    /// The type of the underlying digraph.

    typedef DGR Digraph;

    /// The type of the capacity map.

    typedef CM CapacityMap;

    /// The type of the flow map.

    typedef FM FlowMap;

    FlowMap* _flow;

    Undirected _graph;

    NodeFilter _node_filter;

    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.

    ResidualDigraph(const DGR& digraph, const CM& capacity,

                    FM& flow, const TL& tolerance = Tolerance())

        _graph(digraph), _node_filter(),

        _forward_filter(capacity, flow, tolerance),

        _backward_filter(capacity, flow, tolerance),

        _arc_filter(_forward_filter, _backward_filter)

    {

      Parent::initialize(_graph, _node_filter, _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];