RhodeCode

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.

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

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

                             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,

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

    }

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

  ///

  ///

  ///

  class FilterArcs :

    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,

                      _ArcFilterMap, false> {

  public:

    typedef _Digraph Digraph;

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,

                       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

    ///

    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)

      : Parent(), const_true_map(true) {

      Parent::setDigraph(digraph);

      Parent::setNodeFilterMap(const_true_map);

      Parent::setArcFilterMap(arc_filter);

    }

    ///

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

    ///

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

    ///

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

  };

  ///

  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

  ///