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 datas Data Structures

This group contains the several data structures implemented in LEMON.

*/

/**

@defgroup graphs Graph Structures

@ingroup datas

\brief Graph structures implemented in LEMON.

The implementation of combinatorial algorithms heavily relies on

efficient graph implementations. LEMON offers data structures which are

planned to be easily used in an experimental phase of implementation studies,

and thereafter the program code can be made efficient by small modifications.

The most efficient implementation of diverse applications require the

usage of different physical graph implementations. These differences

appear in the size of graph we require to handle, memory or time usage

limitations or in the set of operations through which the graph can be

accessed.  LEMON provides several physical graph structures to meet

the diverging requirements of the possible users.  In order to save on

running time or on memory usage, some structures may fail to provide

some graph features like arc/edge or node deletion.

Alteration of standard containers need a very limited number of

operations, these together satisfy the everyday requirements.

In the case of graph structures, different operations are needed which do

not alter the physical graph, but gives another view. If some nodes or

arcs have to be hidden or the reverse oriented graph have to be used, then

this is the case. It also may happen that in a flow implementation

the residual graph can be accessed by another algorithm, or a node-set

is to be shrunk for another algorithm.

LEMON also provides a variety of graphs for these requirements called

@ingroup datas

\brief %Path structures implemented in LEMON.

This group contains the path structures implemented in LEMON.

LEMON provides flexible data structures to work with paths.

All of them have similar interfaces and they can be copied easily with

assignment operators and copy constructors. This makes it easy and

efficient to have e.g. the Dijkstra algorithm to store its result in

any kind of path structure.

\sa lemon::concepts::Path

*/

/**

@defgroup auxdat Auxiliary Data Structures

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

This group contains some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup algs Algorithms

\brief This group contains the several algorithms

implemented in LEMON.

This group contains the several algorithms

implemented in 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

Simplex algorithm for finding minimum cost flows. It also provides dual

solution (node potentials), if an optimal flow is found.

*/

/**

@defgroup min_cut Minimum Cut Algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group contains the algorithms for finding minimum cut in graphs.

The \e minimum \e cut \e problem is to find a non-empty and non-complete

\f$X\f$ subset of the nodes with minimum overall capacity on

outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

cut is the \f$X\f$ solution of the next optimization problem:

\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]

LEMON contains several algorithms related to minimum cut problems:

- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

  in directed graphs.

- \ref GomoryHu "Gomory-Hu tree computation" for calculating

  all-pairs minimum cut in undirected graphs.

If you want to find minimum cut just between two distinict nodes,

see the \ref max_flow "maximum flow problem".

*/

/* -*- 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 {

/*!

\page lgf-format LEMON Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

/* -*- 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 {

/**

\page min_cost_flow Minimum Cost Flow Problem

\section mcf_def Definition (GEQ form)

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

minimum total cost from a set of supply nodes to a set of demand nodes

in a network with capacity constraints (lower and upper bounds)

and arc costs.

Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and

upper bounds for the flow values on the arcs, for which

\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,

\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow

on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the

signed supply values of the nodes.

If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

\f$-sup(u)\f$ demand.

A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution

of the following optimization problem.

\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) \geq

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

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

The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

zero or negative in order to have a feasible solution (since the sum

of the expressions on the left-hand side of the inequalities is zero).

It means that the total demand must be greater or equal to the total

supply and all the supplies have to be carried out from the supply nodes,

but there could be demands that are not satisfied.

If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

constraints have to be satisfied with equality, i.e. all demands

have to be satisfied and all supplies have to be used.

\section mcf_algs Algorithms

LEMON contains several algorithms for solving this problem, for more

information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".

A feasible solution for this problem can be found using \ref Circulation.

\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) =

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

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

However if the sum of the supply values is zero, then these two problems

are equivalent.

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.

An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem

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

node potentials the following 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$.

*/

}

/* -*- 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

/// \ingroup graph_adaptors

/// \file

/// \brief Adaptor classes for digraphs and graphs

///

/// This file contains several useful adaptors for digraphs and graphs.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/variant.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/bits/map_extender.h>

#include <lemon/tolerance.h>

#include <algorithm>

namespace lemon {

#ifdef _MSC_VER

#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED

#else

#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED

#endif

  template<typename DGR>

  class DigraphAdaptorBase {

  public:

    typedef DGR Digraph;

    typedef DigraphAdaptorBase Adaptor;

  protected:

    DGR* _digraph;

  class ReverseDigraph :

    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {

#endif

    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;

  public:

    /// The type of the adapted digraph.

    typedef DGR Digraph;

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

    /// Creates a reverse digraph adaptor for the given digraph.

    explicit ReverseDigraph(DGR& digraph) {

      Parent::initialize(digraph);

    }

  };

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

  ///

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

  /// \ingroup graph_adaptors

  /// \relates ReverseDigraph

  template<typename DGR>

  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {

    return ReverseDigraph<const DGR>(digraph);

  }

  template <typename DGR, typename NF, typename AF, bool ch = true>

  class SubDigraphBase : public DigraphAdaptorBase<DGR> {

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

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

        Parent::next(i);

    }

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

      Parent::firstIn(i, n);

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

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

        Parent::nextIn(i);

    }

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

      Parent::firstOut(i, n);

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

                              || !(*_node_filter)[Parent::target(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]

                              || !(*_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);

    }

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False NodeNumTag;

    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;

    }

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

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename DGR, typename NF, typename AF>

  class SubDigraphBase<DGR, NF, AF, false>

    : public DigraphAdaptorBase<DGR> {

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

    }

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

      Parent::firstIn(i, n);

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

    }

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

    }

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False NodeNumTag;

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

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for hiding nodes and arcs in a digraph

  ///

  /// SubDigraph can be used for hiding nodes and arcs in a digraph.

  /// A \c bool node map and a \c bool arc map must be specified, which

  /// define the filters for nodes and arcs.

  /// Only the nodes and arcs with \c true filter value are

  /// shown in the subdigraph. The arcs that are incident to hidden

  /// nodes are also filtered out.

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

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

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

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

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

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

        Parent::nextOut(i);

    }

    void nextInc(Edge& i, bool& d) const {

      Parent::nextInc(i, d);

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

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

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

        Parent::nextInc(i, d);

    }

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Edge& e) const { return (*_edge_filter)[e]; }

    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)[u] || !(*_node_filter)[v]) {

        return INVALID;

      }

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

      while (arc != INVALID && !(*_edge_filter)[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)[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 CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

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

    }

    void first(Arc& i) const {

      Parent::first(i);

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

    }

    void first(Edge& i) const {

      Parent::first(i);

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

    }

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

      Parent::firstIn(i, n);

      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);

    }

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

      Parent::firstOut(i, n);

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

    }

    void firstInc(Edge& i, bool& d, const Node& n) const {

      Parent::firstInc(i, d, n);

      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);

    }

    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 && !(*_edge_filter)[i]) Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

    }

    void nextInc(Edge& i, bool& d) const {

      Parent::nextInc(i, d);

      while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d);

    }

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Edge& e, bool v) const { _edge_filter->set(e, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Edge& e) const { return (*_edge_filter)[e]; }

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