RhodeCode

 */

namespace lemon {

/**

@defgroup datas Data Structures

This group describes 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".

*/

/**

@ingroup graphs

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

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

\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

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

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;

int result = algorithm(rg);

\endcode

graph adaptors, complex algorithms can be implemented easily.

graph is of particular importance. Combining an adaptor implementing

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

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

\code

ReverseDigraph(Digraph& digraph);

\endcode

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

\code

int algorithm1(const ListDigraph& g) {

  return algorithm2(rg);

}

\endcode

*/

/**

@defgroup semi_adaptors Semi-Adaptor Classes for Graphs

@ingroup graphs

\brief Graph types between real graphs and graph adaptors.

This group describes some graph types between real graphs and graph adaptors.

These classes wrap graphs to give new functionality as the adaptors do it.

On the other hand they are not light-weight structures as the adaptors.

*/

/**

@defgroup maps Maps

@ingroup datas

\brief Map structures implemented in LEMON.

This group describes 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 describes 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 describes map adaptors that are used to create "implicit"

maps from other maps.

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

 *

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

 *

 * Copyright (C) 2003-2008

 * 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

///

/// 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/tolerance.h>

#include <algorithm>

namespace lemon {

  template<typename _Digraph>

  class DigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase Adaptor;

    typedef Digraph ParentDigraph;

  protected:

    Digraph* _digraph;

    DigraphAdaptorBase() : _digraph(0) { }

    void setDigraph(Digraph& digraph) { _digraph = &digraph; }

  public:

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::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<Digraph> NodeNumTag;

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

        : 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 _Digraph>

  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  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<Digraph> FindArcTag;

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

                const Arc& prev = INVALID) const {

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

    }

  };

  /// \ingroup graph_adaptors

  ///

  ///

  ///

  template<typename _Digraph>

  class ReverseDigraph :

    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<

      ReverseDigraphBase<_Digraph> > Parent;

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

    explicit ReverseDigraph(Digraph& digraph) {

      Parent::setDigraph(digraph);

    }

  };

  ///

  template<typename Digraph>

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

    return ReverseDigraph<const Digraph>(digraph);

  }

  template <typename _Digraph, typename _NodeFilterMap,

            typename _ArcFilterMap, bool _checked = true>

  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphBase Adaptor;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  protected:

    NodeFilterMap* _node_filter;

    ArcFilterMap* _arc_filter;

    SubDigraphBase()

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

    void setNodeFilterMap(NodeFilterMap& node_filter) {

      _node_filter = &node_filter;

    }

    void setArcFilterMap(ArcFilterMap& arc_filter) {

      _arc_filter = &arc_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);

    }

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap : public SubMapExtender<Adaptor,

      typename Parent::template ArcMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template ArcMap<Value> > MapParent;

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  ///

  /// filtered out.

  ///

  ///

  /// \see FilterNodes

  /// \see FilterArcs

  template<typename _Digraph,

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,

           bool _checked = true>

  class SubDigraph

    : public DigraphAdaptorExtender<

      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

    Parent;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  protected:

    SubDigraph() { }

  public:

    /// \brief Constructor

    ///

    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,

               ArcFilterMap& arc_filter) {

      setDigraph(digraph);

      setNodeFilterMap(node_filter);

      setArcFilterMap(arc_filter);

    }

    ///

    void hide(const Node& n) const { Parent::hide(n); }

    ///

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

    ///

    void unHide(const Node& n) const { Parent::unHide(n); }

    ///

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

    ///

    ///

    bool hidden(const Arc& a) const { return Parent::hidden(a); }

  };

  ///

  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>

  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap,

      const ArcFilterMap>(digraph, nfm, afm);

  }

  template <typename _Graph, typename _NodeFilterMap,

            typename _EdgeFilterMap, bool _checked = true>

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

      ArcMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class EdgeMap : public SubMapExtender<Adaptor,

      typename Parent::template EdgeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template EdgeMap<Value> > MapParent;

      EdgeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      EdgeMap(const Adaptor& adaptor, const _Value& value)

        : MapParent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  ///

  /// filtered out.

  ///

  ///

  /// \see FilterNodes

  /// \see FilterEdges

  class SubGraph

    : public GraphAdaptorExtender<

  public:

    typedef _Graph Graph;

    typedef GraphAdaptorExtender<

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

  protected:

    SubGraph() { }

  public:

    /// \brief Constructor

    ///

             EdgeFilterMap& edge_filter_map) {

      setNodeFilterMap(node_filter_map);

      setEdgeFilterMap(edge_filter_map);

    }

    ///

    void hide(const Node& n) const { Parent::hide(n); }

    ///

    void hide(const Edge& e) const { Parent::hide(e); }

    ///

    void unHide(const Node& n) const { Parent::unHide(n); }

    ///

    void unHide(const Edge& e) const { Parent::unHide(e); }

    ///

    ///

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

  };

  ///

  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,

           NodeFilterMap& nfm, const ArcFilterMap& efm) {

    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>

      (graph, nfm, efm);

  }

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

  subGraph(const Graph& graph,

           const NodeFilterMap& nfm, const ArcFilterMap& efm) {

    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>

      (graph, nfm, efm);

  }

  /// \ingroup graph_adaptors

  ///

  ///

  ///

#ifdef DOXYGEN

#else

  template<typename _Digraph,

           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,

           bool _checked = true,

           typename Enable = void>

#endif

  class FilterNodes

    : public SubDigraph<_Digraph, _NodeFilterMap,

                        ConstMap<typename _Digraph::Arc, bool>, _checked> {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubDigraph<Digraph, NodeFilterMap,

                       ConstMap<typename Digraph::Arc, bool>, _checked>

    Parent;

    typedef typename Parent::Node Node;

  protected:

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

    FilterNodes() : const_true_map(true) {

      Parent::setArcFilterMap(const_true_map);

    }

  public:

    /// \brief Constructor

    ///

    /// given node filter map.

      Parent(), const_true_map(true) {

      Parent::setNodeFilterMap(node_filter);

      Parent::setArcFilterMap(const_true_map);

    }

    ///

    void hide(const Node& n) const { Parent::hide(n); }

    ///

    void unHide(const Node& n) const { Parent::unHide(n); }

    ///

    bool hidden(const Node& n) const { return Parent::hidden(n); }

  };

  template<typename _Graph, typename _NodeFilterMap, bool _checked>

  class FilterNodes<_Graph, _NodeFilterMap, _checked,