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.

 *

 */

///\ingroup demos

///\file

///\brief Argument parser demo

///

/// This example shows how the argument parser can be used.

///

/// \include arg_parser_demo.cc

#include <lemon/arg_parser.h>

using namespace lemon;

int main(int argc, char **argv)

{

  // Initialize the argument parser

  ArgParser ap(argc, argv);

  int i;

  std::string s;

  double d = 1.0;

  bool b, nh;

  bool g1, g2, g3;

  // Add a mandatory integer option with storage reference

  ap.refOption("n", "An integer input.", i, true);

  // Add a double option with storage reference (the default value is 1.0)

  ap.refOption("val", "A double input.", d);

  // Add a double option without storage reference (the default value is 3.14)

  ap.doubleOption("val2", "A double input.", 3.14);

  // Set synonym for -val option

  ap.synonym("vals", "val");

  // Add a string option

  ap.refOption("name", "A string input.", s);

  // Add bool options

  ap.refOption("f", "A switch.", b)

    .refOption("nohelp", "", nh)

    .refOption("gra", "Choice A", g1)

    .refOption("grb", "Choice B", g2)

    .refOption("grc", "Choice C", g3);

  // Bundle -gr* options into a group

  ap.optionGroup("gr", "gra")

    .optionGroup("gr", "grb")

    .optionGroup("gr", "grc");

  // Set the group mandatory

  ap.mandatoryGroup("gr");

  // Set the options of the group exclusive (only one option can be given)

  ap.onlyOneGroup("gr");

  // Add non-parsed arguments (e.g. input files)

  ap.other("infile", "The input file.")

    .other("...");

  // Throw an exception when problems occurs. The default behavior is to

  // exit(1) on these cases, but this makes Valgrind falsely warn

  // about memory leaks.

  ap.throwOnProblems();

  // Perform the parsing process

  // (in case of any error it terminates the program)

  // The try {} construct is necessary only if the ap.trowOnProblems()

  // setting is in use.

  try {

    ap.parse();

  } catch (ArgParserException &) { return 1; }

  // Check each option if it has been given and print its value

  std::cout << "Parameters of '" << ap.commandName() << "':\n";

  std::cout << "  Value of -n: " << i << std::endl;

  if(ap.given("val")) std::cout << "  Value of -val: " << d << std::endl;

  if(ap.given("val2")) {

    d = ap["val2"];

    std::cout << "  Value of -val2: " << d << std::endl;

  }

  if(ap.given("name")) std::cout << "  Value of -name: " << s << std::endl;

  if(ap.given("f")) std::cout << "  -f is given\n";

  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << nh << std::endl;

  if(ap.given("gra")) std::cout << "  -gra is given\n";

  if(ap.given("grb")) std::cout << "  -grb is given\n";

  if(ap.given("grc")) std::cout << "  -grc is given\n";

  switch(ap.files().size()) {

  case 0:

    std::cout << "  No file argument was given.\n";

    break;

  case 1:

    std::cout << "  1 file argument was given. It is:\n";

    break;

  default:

    std::cout << "  "

              << ap.files().size() << " file arguments were given. They are:\n";

  }

  for(unsigned int i=0;i<ap.files().size();++i)

    std::cout << "    '" << ap.files()[i] << "'\n";

  return 0;

}

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

\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only

in conjunction with other graph representations.

You are free to use the graph structure that fit your requirements

the best, most graph algorithms and auxiliary data structures can be used

with any graph structure.

<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

*/

/**

@defgroup graph_adaptors Adaptor Classes for Graphs

@ingroup graphs

\brief Adaptor classes for digraphs and graphs

This group contains several useful adaptor classes for digraphs and graphs.

The main parts of LEMON are the different graph structures, generic

graph algorithms, graph concepts, which couple them, and graph

adaptors. While the previous notions are more or less clear, the

latter one needs further explanation. Graph adaptors are graph classes

which serve for considering graph structures in different ways.

A short example makes this much clearer.  Suppose that we have an

instance \c g of a directed graph type, say ListDigraph and an algorithm

\code

template <typename Digraph>

int algorithm(const Digraph&);

\endcode

is needed to run on the reverse oriented graph.  It may be expensive

(in time or in memory usage) to copy \c g with the reversed

arcs.  In this case, an adaptor class is used, which (according

to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.

The adaptor uses the original digraph structure and digraph operations when

methods of the reversed oriented graph are called.  This means that the adaptor

have minor memory usage, and do not perform sophisticated algorithmic

actions.  The purpose of it is to give a tool for the cases when a

graph have to be used in a specific alteration.  If this alteration is

obtained by a usual construction like filtering the node or the arc set or

considering a new orientation, then an adaptor is worthwhile to use.

To come back to the reverse oriented graph, in this situation

\code

template<typename Digraph> class ReverseDigraph;

\endcode

template class can be used. The code looks as follows

\code

ListDigraph g;

ReverseDigraph<ListDigraph> rg(g);

int result = algorithm(rg);

\endcode

During running the algorithm, the original digraph \c g is untouched.

This techniques give rise to an elegant code, and based on stable

graph adaptors, complex algorithms can be implemented easily.

In flow, circulation and matching problems, the residual

graph is of particular importance. Combining an adaptor implementing

this with shortest path algorithms or minimum mean cycle algorithms,

a range of weighted and cardinality optimization algorithms can be

obtained. For other examples, the interested user is referred to the

detailed documentation of particular adaptors.

The behavior of graph adaptors can be very different. Some of them keep

capabilities of the original graph while in other cases this would be

meaningless. This means that the concepts that they meet depend

on the graph adaptor, and the wrapped graph.

For example, if an arc of a reversed digraph is deleted, this is carried

out by deleting the corresponding arc of the original digraph, thus the

adaptor modifies the original digraph.

However in case of a residual digraph, this operation has no sense.

Let us stand one more example here to simplify your work.

ReverseDigraph has constructor

\code

ReverseDigraph(Digraph& digraph);

\endcode

This means that in a situation, when a <tt>const %ListDigraph&</tt>

reference to a graph is given, then it have to be instantiated with

<tt>Digraph=const %ListDigraph</tt>.

\code

int algorithm1(const ListDigraph& g) {

  ReverseDigraph<const ListDigraph> rg(g);

  return algorithm2(rg);

}

\endcode

*/

/**

@defgroup maps Maps

@ingroup datas

\brief Map structures implemented in LEMON.

This group contains the map structures implemented in LEMON.

LEMON provides several special purpose maps and map adaptors that e.g. combine

new maps from existing ones.

<b>See also:</b> \ref map_concepts "Map Concepts".

*/

/**

@defgroup graph_maps Graph Maps

@ingroup maps

\brief Special graph-related maps.

This group contains maps that are specifically designed to assign

values to the nodes and arcs/edges of graphs.

If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".

*/

/**

\defgroup map_adaptors Map Adaptors

\ingroup maps

\brief Tools to create new maps from existing ones

This group contains map adaptors that are used to create "implicit"

maps from other maps.

Most of them are \ref concepts::ReadMap "read-only maps".

They can make arithmetic and logical operations between one or two maps

(negation, shifting, addition, multiplication, logical 'and', 'or',

'not' etc.) or e.g. convert a map to another one of different Value type.

The typical usage of this classes is passing implicit maps to

algorithms.  If a function type algorithm is called then the function

type map adaptors can be used comfortable. For example let's see the

usage of map adaptors with the \c graphToEps() function.

\code

  Color nodeColor(int deg) {

    if (deg >= 2) {

      return Color(0.5, 0.0, 0.5);

    } else if (deg == 1) {

      return Color(1.0, 0.5, 1.0);

    } else {

      return Color(0.0, 0.0, 0.0);

    }

  }

  Digraph::NodeMap<int> degree_map(graph);

  graphToEps(graph, "graph.eps")

    .coords(coords).scaleToA4().undirected()

    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

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

 *

 */

/**

\mainpage LEMON Documentation

\section intro Introduction

<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling

and <b>O</b>ptimization in <b>N</b>etworks</i>.

It is a C++ template library providing efficient implementations of common

data structures and algorithms with focus on combinatorial optimization

<b>

LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>

project.

You are free to use it in your commercial or

non-commercial applications under very permissive

\ref license "license terms".

</b>

<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on

Combinatorial Optimization</a> \ref egres

at the Operations Research Department of the

<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,

Budapest, Hungary.

LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>

initiative \ref coinor.

\section howtoread How to Read the Documentation

If you would like to get to know the library, see

<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.

If you are interested in starting to use the library, see the <a class="el"

href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation

Guide</a>.

If you know what you are looking for, then try to find it under the

<a class="el" href="modules.html">Modules</a> section.

If you are a user of the old (0.x) series of LEMON, please check out the

\ref migration "Migration Guide" for the backward incompatibilities.

*/

/* -*- 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 \ref amo93networkflows.

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

    DigraphAdaptorBase() : _digraph(0) { }

    void initialize(DGR& digraph) { _digraph = &digraph; }

  public:

    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }

    typedef typename DGR::Node Node;

    typedef typename DGR::Arc Arc;

    void first(Node& i) const { _digraph->first(i); }

    void first(Arc& i) const { _digraph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }

    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }

    void next(Node& i) const { _digraph->next(i); }

    void next(Arc& i) const { _digraph->next(i); }

    void nextIn(Arc& i) const { _digraph->nextIn(i); }

    void nextOut(Arc& i) const { _digraph->nextOut(i); }

    Node source(const Arc& a) const { return _digraph->source(a); }

    Node target(const Arc& a) const { return _digraph->target(a); }

    typedef NodeNumTagIndicator<DGR> NodeNumTag;

    int nodeNum() const { return _digraph->nodeNum(); }

    typedef ArcNumTagIndicator<DGR> ArcNumTag;

    int arcNum() const { return _digraph->arcNum(); }

    typedef FindArcTagIndicator<DGR> FindArcTag;

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {

      return _digraph->findArc(u, v, prev);

    }

    Node addNode() { return _digraph->addNode(); }

    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }

    void erase(const Node& n) { _digraph->erase(n); }

    void erase(const Arc& a) { _digraph->erase(a); }

    void clear() { _digraph->clear(); }

    int id(const Node& n) const { return _digraph->id(n); }

    int id(const Arc& a) const { return _digraph->id(a); }

    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }

    int maxNodeId() const { return _digraph->maxNodeId(); }

    int maxArcId() const { return _digraph->maxArcId(); }

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

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

    typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;

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

    template <typename V>

    class NodeMap : public DGR::template NodeMap<V> {

      typedef typename DGR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      NodeMap(const Adaptor& adaptor, const V& value)

        : Parent(*adaptor._digraph, 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 DGR::template ArcMap<V> {

      typedef typename DGR::template ArcMap<V> Parent;

    public:

      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)

        : Parent(*adaptor._digraph) {}

      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)

        : Parent(*adaptor._digraph, 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 GR>

  class GraphAdaptorBase {

  public:

    typedef GR Graph;

  protected:

    GR* _graph;

    GraphAdaptorBase() : _graph(0) {}

    void initialize(GR& graph) { _graph = &graph; }

  public:

    GraphAdaptorBase(GR& graph) : _graph(&graph) {}

    typedef typename GR::Node Node;

    typedef typename GR::Arc Arc;

    typedef typename GR::Edge Edge;

    void first(Node& i) const { _graph->first(i); }

    void first(Arc& i) const { _graph->first(i); }

    void first(Edge& i) const { _graph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }

    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }

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

      _graph->firstInc(i, d, n);

    }

    void next(Node& i) const { _graph->next(i); }

    void next(Arc& i) const { _graph->next(i); }

    void next(Edge& i) const { _graph->next(i); }

    void nextIn(Arc& i) const { _graph->nextIn(i); }

    void nextOut(Arc& i) const { _graph->nextOut(i); }

    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }

    Node u(const Edge& e) const { return _graph->u(e); }

    Node v(const Edge& e) const { return _graph->v(e); }

    Node source(const Arc& a) const { return _graph->source(a); }

    Node target(const Arc& a) const { return _graph->target(a); }

    int id(const Arc& a) const { return _graph->id(a); }

    int id(const Edge& e) const { return _graph->id(e); }

    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }

    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxArcId(); }

    int maxEdgeId() const { return _graph->maxEdgeId(); }

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

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

    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;

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

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

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

    template <typename V>

    class NodeMap : public GR::template NodeMap<V> {

      typedef typename GR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)

        : Parent(*adapter._graph) {}

      NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

        : Parent(*adapter._graph, 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 GR::template ArcMap<V> {

      typedef typename GR::template ArcMap<V> Parent;

    public:

      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)

        : Parent(*adapter._graph) {}

      ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)

        : Parent(*adapter._graph, 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>

    class EdgeMap : public GR::template EdgeMap<V> {

      typedef typename GR::template EdgeMap<V> Parent;

    public:

      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)

        : Parent(*adapter._graph) {}

      EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)

        : Parent(*adapter._graph, 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 DGR>

  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {

    typedef DigraphAdaptorBase<DGR> Parent;

  public:

    typedef DGR Digraph;

  protected:

    ReverseDigraphBase() : Parent() { }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }

    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }

    void nextIn(Arc& a) const { Parent::nextOut(a); }

    void nextOut(Arc& a) const { Parent::nextIn(a); }

    Node source(const Arc& a) const { return Parent::target(a); }

    Node target(const Arc& a) const { return Parent::source(a); }

    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }

    typedef FindArcTagIndicator<DGR> FindArcTag;

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

                const Arc& prev = INVALID) const {

      return Parent::findArc(v, u, prev);

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for reversing the orientation of the arcs in

  /// a digraph.

  ///

  /// ReverseDigraph can be used for reversing the arcs in a digraph.

  /// It 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.

  ///

  /// This class provides item counting in the same time as the adapted

  /// digraph structure.

  ///

  /// \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.

  ///

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

  /// digraph are convertible to each other.

  template<typename DGR>

#ifdef DOXYGEN

  class ReverseDigraph {

#else

  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;