RhodeCode

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 {

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

#define LEMON_EDGE_SET_H

#include <lemon/core.h>

#include <lemon/bits/edge_set_extender.h>

/// \file

/// \brief ArcSet and EdgeSet classes.

///

/// Graphs which use another graph's node-set as own.

namespace lemon {

  template <typename GR>

  class ListArcSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out, first_in;

      NodeT() : first_out(-1), first_in(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node source, target;

      int next_out, next_in;

      int prev_out, prev_in;

      ArcT() : prev_out(-1), prev_in(-1) {}

    };

    std::vector<ArcT> arcs;

    int first_arc;

    int first_free_arc;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Arc {

      friend class ListArcSetBase<GR>;

    void nextIn(Arc& arc) const {

      arc.id = arcs[arc.id].next_in;

    }

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

    int id(const Arc& arc) const { return arc.id; }

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

    Arc arcFromId(int ix) const { return Arc(ix); }

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

    int maxArcId() const { return arcs.size() - 1; }

    Node source(const Arc& arc) const { return arcs[arc.id].source;}

    Node target(const Arc& arc) const { return arcs[arc.id].target;}

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

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

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

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

    public:

      explicit NodeMap(const ListArcSetBase<GR>& arcset)

        : Parent(*arcset._graph) {}

      NodeMap(const ListArcSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) {}

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  ///

  /// \brief Digraph using a node set of another digraph or graph and

  /// an own arc set.

  ///

  /// This structure can be used to establish another directed graph

  /// over a node set of an existing one. This class uses the same

  /// Node type as the underlying graph, and each valid node of the

  /// original graph is valid in this arc set, therefore the node

  /// objects of the original graph can be used directly with this

  /// class. The node handling functions (id handling, observing, and

  /// iterators) works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the outgoing and the incoming arcs make up lists, therefore

  /// one arc can be erased in constant time. It also makes possible,

  /// that node can be removed from the underlying graph, in this case

  /// all arcs incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This class fully conforms to the \ref concepts::Digraph

  /// "Digraph" concept.

  template <typename GR>

  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {

    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

      Parent::firstIn(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstIn(arc, node);

    static int id(Arc e) { return e.id; }

    static int id(Edge e) { return e.id; }

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

    static Arc arcFromId(int id) { return Arc(id);}

    static Edge edgeFromId(int id) { return Edge(id);}

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

    int maxEdgeId() const { return arcs.size() / 2 - 1; }

    int maxArcId() const { return arcs.size()-1; }

    Node source(Arc e) const { return arcs[e.id ^ 1].target; }

    Node target(Arc e) const { return arcs[e.id].target; }

    Node u(Edge e) const { return arcs[2 * e.id].target; }

    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }

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

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

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

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

    public:

      explicit NodeMap(const ListEdgeSetBase<GR>& arcset)

        : Parent(*arcset._graph) {}

      NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) {}

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  ///

  /// \brief Graph using a node set of another digraph or graph and an

  /// own edge set.

  ///

  /// This structure can be used to establish another graph over a

  /// node set of an existing one. This class uses the same Node type

  /// as the underlying graph, and each valid node of the original

  /// graph is valid in this arc set, therefore the node objects of

  /// the original graph can be used directly with this class. The

  /// node handling functions (id handling, observing, and iterators)

  /// works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the incident edges make up lists, therefore one edge can be

  /// erased in constant time. It also makes possible, that node can

  /// be removed from the underlying graph, in this case all edges

  /// incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set

  /// with this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This class fully conforms to the \ref concepts::Graph "Graph"

  /// concept.

  template <typename GR>

  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {

    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

    }

    void clearNodes() {

    void nextIn(Arc& arc) const {

      arc.id = arcs[arc.id].next_in;

    }

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

    int id(const Arc& arc) const { return arc.id; }

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

    Arc arcFromId(int ix) const { return Arc(ix); }

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

    int maxArcId() const { return arcs.size() - 1; }

    Node source(const Arc& arc) const { return arcs[arc.id].source;}

    Node target(const Arc& arc) const { return arcs[arc.id].target;}

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

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

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

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

    public:

      explicit NodeMap(const SmartArcSetBase<GR>& arcset)

        : Parent(*arcset._graph) { }

      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) { }

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  ///

  /// \brief Digraph using a node set of another digraph or graph and

  /// an own arc set.

  ///

  /// This structure can be used to establish another directed graph

  /// over a node set of an existing one. This class uses the same

  /// Node type as the underlying graph, and each valid node of the

  /// original graph is valid in this arc set, therefore the node

  /// objects of the original graph can be used directly with this

  /// class. The node handling functions (id handling, observing, and

  /// iterators) works equivalently as in the original graph.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This implementation is slightly faster than the \c ListArcSet,

  /// because it uses continuous storage for arcs and it uses just

  /// single-linked lists for enumerate outgoing and incoming

  /// arcs. Therefore the arcs cannot be erased from the arc sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is the source or target of one arc in the arc set, then

  /// the arc set is invalidated, and it cannot be used anymore. The

  /// validity can be checked with the \c valid() member function.

  ///

  /// This class fully conforms to the \ref concepts::Digraph

  /// "Digraph" concept.

  template <typename GR>

  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {

    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  protected:

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      if (typename Parent::InArcIt(*this, node) == INVALID &&

          typename Parent::OutArcIt(*this, node) == INVALID) {

        return;

      }

      throw typename NodesImplBase::Notifier::ImmediateDetach();

    static int id(Arc arc) { return arc.id; }

    static int id(Edge arc) { return arc.id; }

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

    static Arc arcFromId(int id) { return Arc(id); }

    static Edge edgeFromId(int id) { return Edge(id);}

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

    int maxArcId() const { return arcs.size() - 1; }

    int maxEdgeId() const { return arcs.size() / 2 - 1; }

    Node source(Arc e) const { return arcs[e.id ^ 1].target; }

    Node target(Arc e) const { return arcs[e.id].target; }

    Node u(Edge e) const { return arcs[2 * e.id].target; }

    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }

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

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

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

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

    public:

      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)

        : Parent(*arcset._graph) { }

      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) { }

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  ///

  /// \brief Graph using a node set of another digraph or graph and an

  /// own edge set.

  ///

  /// This structure can be used to establish another graph over a

  /// node set of an existing one. This class uses the same Node type

  /// as the underlying graph, and each valid node of the original

  /// graph is valid in this arc set, therefore the node objects of

  /// the original graph can be used directly with this class. The

  /// node handling functions (id handling, observing, and iterators)

  /// works equivalently as in the original graph.

  ///

  /// \param GR The type of the graph which shares its node set

  /// with this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  ///  concept.

  ///

  /// This implementation is slightly faster than the \c ListEdgeSet,

  /// because it uses continuous storage for edges and it uses just

  /// single-linked lists for enumerate incident edges. Therefore the

  /// edges cannot be erased from the edge sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is incident to one edge in the edge set, then the edge set

  /// is invalidated, and it cannot be used anymore. The validity can

  /// be checked with the \c valid() member function.

  ///

  /// This class fully conforms to the \ref concepts::Graph

  /// "Graph" concept.

  template <typename GR>

  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {

    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

  protected:

    typedef typename Parent::NodesImplBase NodesImplBase;

    void eraseNode(const Node& node) {

      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {

        return;

      }

      throw typename NodesImplBase::Notifier::ImmediateDetach();