RhodeCode

    }

    void next(Arc& i) const {

      Parent::next(i);

      while (i != INVALID && (!(*_arc_filter)[i]

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

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

        Parent::next(i);

    }

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

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> 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 _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

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

      Parent::firstOut(i, n);

      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);

    }

    void next(Node& i) const {

      Parent::next(i);

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

    }

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

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> 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 _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> >

    Parent;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  protected:

    SubDigraph() { }

  public:

    /// \brief Constructor

    ///

    /// Creates a subdigraph for the given digraph with the

    /// given node and arc filter maps.

    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,

               ArcFilterMap& arc_filter) {

      setDigraph(digraph);

      setNodeFilterMap(node_filter);

      setArcFilterMap(arc_filter);

    }

    ///

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

    ///

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

    ///

    ///

    ///

    ///

  };

  /// \brief Returns a read-only SubDigraph adaptor

  ///

  /// This function just returns a read-only \ref SubDigraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates SubDigraph

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i!=INVALID && (!(*_edge_filter_map)[i]

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

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

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

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef False EdgeNumTag;

    typedef FindArcTagIndicator<Graph> FindArcTag;

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

                const Arc& prev = INVALID) const {

      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;

    }

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

                  const Edge& prev = INVALID) const {

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

        return INVALID;

      }

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

    }

    void next(Arc& i) const {

      Parent::next(i);

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

    }

    void next(Edge& i) const {

      Parent::next(i);

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

    }

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

    }

    typedef False NodeNumTag;

    typedef False ArcNumTag;

    typedef False EdgeNumTag;

    typedef FindArcTagIndicator<Graph> FindArcTag;

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

                const Arc& prev = INVALID) const {

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

      while (arc != INVALID && !(*_edge_filter_map)[arc]) {

        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_map)[edge]) {

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

      }

      return edge;

    }

    /// The type of the edge filter map.

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef GraphAdaptorExtender<

      SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent;

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

  protected:

    SubGraph() { }

  public:

    /// \brief Constructor

    ///

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

    /// and edge filter maps.

    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,

             EdgeFilterMap& edge_filter_map) {

      setGraph(graph);

      setNodeFilterMap(node_filter_map);

      setEdgeFilterMap(edge_filter_map);

    }

    ///

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

    ///

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

    ///

    ///

    ///

    ///

  };

  /// \brief Returns a read-only SubGraph adaptor

  ///

  /// This function just returns a read-only \ref SubGraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates SubGraph

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>

  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

  subGraph(const Graph& graph,

           const NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>

      (graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

  subGraph(const Graph& graph,

  protected:

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

    FilterNodes() : const_true_map(true) {

      Parent::setArcFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

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

    /// given node filter map.

#ifdef DOXYGEN

    FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) :

#else

    FilterNodes(Digraph& graph, NodeFilterMap& node_filter) :

#endif

      Parent(), const_true_map(true) {

      Parent::setDigraph(graph);

      Parent::setNodeFilterMap(node_filter);

      Parent::setArcFilterMap(const_true_map);

    }

    ///

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

    ///

    ///

  };

  template<typename _Graph, typename _NodeFilterMap, bool _checked>

  class FilterNodes<_Graph, _NodeFilterMap, _checked,

                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>

    : public SubGraph<_Graph, _NodeFilterMap,

                      ConstMap<typename _Graph::Edge, bool>, _checked> {

  public:

    typedef _Graph Graph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubGraph<Graph, NodeFilterMap,

                     ConstMap<typename Graph::Edge, bool> > Parent;

    typedef typename Parent::Node Node;

  protected:

    ConstMap<typename Graph::Edge, bool> const_true_map;

    FilterNodes() : const_true_map(true) {

      Parent::setEdgeFilterMap(const_true_map);

    }

  public:

    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :

      Parent(), const_true_map(true) {

      Parent::setGraph(_graph);

      Parent::setNodeFilterMap(node_filter_map);

      Parent::setEdgeFilterMap(const_true_map);

    }

  };

  /// \brief Returns a read-only FilterNodes adaptor

  ///

  /// This function just returns a read-only \ref FilterNodes adaptor.

  /// \ingroup graph_adaptors

  /// \relates FilterNodes

  template<typename Digraph, typename NodeFilterMap>

  FilterNodes<const Digraph, NodeFilterMap>

  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {

    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);

  }

  template<typename Digraph, typename NodeFilterMap>

  FilterNodes<const Digraph, const NodeFilterMap>

  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {

    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding arcs in a digraph.

                       ArcFilterMap, false> Parent;

    typedef typename Parent::Arc Arc;

  protected:

    ConstMap<typename Digraph::Node, bool> const_true_map;

    FilterArcs() : const_true_map(true) {

      Parent::setNodeFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

    /// Creates a subdigraph for the given digraph with the given arc

    /// filter map.

    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)

      : Parent(), const_true_map(true) {

      Parent::setDigraph(digraph);

      Parent::setNodeFilterMap(const_true_map);

      Parent::setArcFilterMap(arc_filter);

    }

    ///

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

    ///

    ///

  };

  /// \brief Returns a read-only FilterArcs adaptor

  ///

  /// This function just returns a read-only \ref FilterArcs adaptor.

  /// \ingroup graph_adaptors

  /// \relates FilterArcs

  template<typename Digraph, typename ArcFilterMap>

  FilterArcs<const Digraph, ArcFilterMap>

  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {

    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);

  }

  template<typename Digraph, typename ArcFilterMap>

  FilterArcs<const Digraph, const ArcFilterMap>

  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {

    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);

  }

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding edges in a graph.

  ///

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,

                     EdgeFilterMap, false> Parent;

    typedef typename Parent::Edge Edge;

  protected:

    ConstMap<typename Graph::Node, bool> 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.

    FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :

      Parent(), const_true_map(true) {

      Parent::setGraph(graph);

      Parent::setNodeFilterMap(const_true_map);

      Parent::setEdgeFilterMap(edge_filter_map);

    }

    ///

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

    ///

    ///

  };

  /// \brief Returns a read-only FilterEdges adaptor

  ///

  /// This function just returns a read-only \ref FilterEdges adaptor.

  /// \ingroup graph_adaptors

  /// \relates FilterEdges

  template<typename Graph, typename EdgeFilterMap>

  FilterEdges<const Graph, EdgeFilterMap>

  filterEdges(const Graph& graph, EdgeFilterMap& efm) {

    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);

  }

  template<typename Graph, typename EdgeFilterMap>

  FilterEdges<const Graph, const EdgeFilterMap>

  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {

    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);

  }

  template <typename _Digraph>

  class UndirectorBase {

  public:

    Residual(const Digraph& digraph, const CapacityMap& capacity,

             FlowMap& flow, const Tolerance& tolerance = Tolerance())

      : 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];

      }

    }

    ///

    /// or decreases the flow value on the original arc according to the

    /// direction of the residual arc.

    void augment(const Arc& a, const Value& v) const {

      if (Undirected::direction(a)) {

        _flow->set(a, (*_flow)[a] + v);

      } else {

        _flow->set(a, (*_flow)[a] - v);

      }

    }

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

    ///

    /// Returns \c true if the given residual arc has the same orientation

    /// as the original arc, i.e. it is a so called forward arc.

    static bool forward(const Arc& a) {

      return Undirected::direction(a);

    }

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

    ///

    /// Returns \c true if the given residual arc has the opposite orientation

    /// than the original arc, i.e. it is a so called backward arc.

    static bool backward(const Arc& a) {

      return !Undirected::direction(a);