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

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

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

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

    }

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

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

    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<Digraph, Node>::ItemNotifier NodeNotifier;

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

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

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

    template <typename _Value>

    class NodeMap : public Digraph::template NodeMap<_Value> {

    public:

      typedef typename Digraph::template NodeMap<_Value> Parent;

      explicit NodeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

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

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

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

    }

      return _graph->findEdge(u, v, prev);

    }

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

    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }

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

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

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

    bool direction(const Arc& a) const { return _graph->direction(a); }

    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }

    int id(const Node& v) const { return _graph->id(v); }

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

  };

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

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

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

    }

  };

  /// \ingroup graph_adaptors

  ///

  ///

  ///

  class ReverseDigraph :

  public:

  protected:

    ReverseDigraph() { }

  public:

    /// \brief Constructor

    ///

    explicit ReverseDigraph(Digraph& digraph) {

      Parent::setDigraph(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:

    }

    void next(Arc& i) const {

      Parent::next(i);

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

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

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

        Parent::next(i);

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

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

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

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

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

        Parent::nextOut(i);

    }

    typedef False NodeNumTag;

    Arc findArc(const Node& source, const Node& target,

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

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

        arc = Parent::findArc(source, target, arc);

      }

      return arc;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

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

      Parent::firstOut(i, n);

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

    }

    void next(Node& i) const {

      Parent::next(i);

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

    }

    void next(Arc& i) const {

      Parent::next(i);

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

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

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

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

    }

    typedef False NodeNumTag;

    Arc findArc(const Node& source, const Node& target,

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

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

        arc = Parent::findArc(source, target, arc);

      }

      return arc;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      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

  ///

  ///

  ///

  ///

  /// \see FilterNodes

  /// \see FilterArcs

  public:

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

    }

    ///

    ///

    ///

    ///

    ///

    ///

    ///

    ///

  };

  ///

  }

  }

  }

  }

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

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

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

        Parent::nextIn(i);

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

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

        Parent::nextOut(i);

    }

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

      Parent::nextInc(i, d);

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

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

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

        Parent::nextInc(i, d);

    }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

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

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

        return INVALID;

      }

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

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

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

      }

      return arc;

    }

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

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

        return INVALID;

      }

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

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

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

      }

      return edge;

    }

    template <typename _Value>

    class NodeMap : public SubMapExtender<Adaptor,

      typename Parent::template NodeMap<_Value> > {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template NodeMap<Value> > MapParent;

      NodeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

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

        : MapParent(adaptor, value) {}

    private:

      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;

      }

    };

  };

    : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase() : Parent(),

                     _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  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_map)[i]) Parent::next(i);

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

    }

    void next(Arc& i) const {

      Parent::next(i);

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

    }

    void next(Edge& i) const {

      Parent::next(i);

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

    }

    void nextIn(Arc& i) const {

      Parent::nextIn(i);

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

    }

    void nextOut(Arc& i) const {

      Parent::nextOut(i);

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

    }

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

      Parent::nextInc(i, d);

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

    }