ResidualDigraph

Declared in lemon/adaptors.h, in the group Adaptor Classes for Graphs; the same class on the Doxygen site.

template< typename DGR , typename CM , typename FM , typename TL >
class ResidualDigraph

Adaptor class for composing the residual digraph for directed flow and circulation problems.

ResidualDigraph can be used for composing the residual digraph for directed flow and circulation problems. Let \( G=(V, A) \) be a directed graph and let \( F \) be a number type. Let \( flow, cap: A\to F \) be functions on the arcs. This adaptor implements a digraph structure with node set \( V \) and arc set \( A_{forward}\cup A_{backward} \), where \( A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \) and \( A_{backward}=\{vu : uv\in A, flow(uv)>0\} \), i.e. the so called residual digraph. When the union \( A_{forward}\cup A_{backward} \) is taken, multiplicities are counted, i.e. the adaptor has exactly \( |A_{forward}| + |A_{backward}|\) arcs (it may have parallel arcs). This class conforms to the Digraph concept.

This class provides only linear time counting for nodes and arcs.

Note

This adaptor is implemented as a SubDigraph of an Undirector of the digraph.

Note

The Node type of this adaptor and the adapted digraph are convertible to each other, moreover the Arc type of the adaptor is convertible to the Arc type of the adapted digraph.

Template Parameters:
  • DGR – The type of the adapted digraph. It must conform to the Digraph concept. It is implicitly const.

  • CM – The type of the capacity map. It must be an arc map of some numerical type, which defines the capacities in the flow problem. It is implicitly const. The default type is DGR::ArcMap< int >.

  • FM – The type of the flow map. It must be an arc map of some numerical type, which defines the flow values in the flow problem. The default type is CM.

  • TL – The tolerance type for handling inexact computation. The default tolerance type depends on the value type of the capacity map.

Public Types

typedef DGR Digraph

The type of the underlying digraph.

typedef CM CapacityMap

The type of the capacity map.

typedef FM FlowMap

The type of the flow map.

typedef TL Tolerance

The tolerance type.

typedef CapacityMap::Value Value
typedef ResidualDigraph Adaptor
typedef Parent::Arc Arc

Public Functions

inline ResidualDigraph(
const DGR & digraph,
const CM & capacity,
FM & flow,
const TL & tolerance = Tolerance()
)

Constructor.

Constructor of the residual digraph adaptor. The parameters are the digraph, the capacity map, the flow map, and a tolerance object.

inline ResidualDigraph( const ResidualDigraph & other )

Copy constructor.

Creates a residual digraph of the same digraph, capacity map, flow map and tolerance, which refers to none of the members of other.

inline ResidualDigraph & operator=( const ResidualDigraph & other )

Assignment.

Makes this adaptor the residual digraph of the digraph, capacity map, flow map and tolerance of other.

inline Value residualCapacity( const Arc & a ) const

Returns the residual capacity of the given arc.

inline void augment( const Arc & a , const Value & v ) const

Augments on the given arc in the residual digraph. It increases or decreases the flow value on the original arc according to the direction of the residual arc.

inline ResidualCapacity residualCapacity() const

Returns a residual capacity map.

This function just returns a residual capacity map.

Public Static Functions

static inline bool forward( const Arc & a )

Returns true if the given residual arc is a forward arc.

Returns true if the given residual arc has the same orientation as the original arc, i.e. it is a so called forward arc.

static inline bool backward( const Arc & a )

Returns true if the given residual arc is a backward arc.

Returns true if the given residual arc has the opposite orientation than the original arc, i.e. it is a so called backward arc.

static inline Arc forward( const typename Digraph::Arc & a )

Returns the forward oriented residual arc.

Returns the forward oriented residual arc related to the given arc of the underlying digraph.

static inline Arc backward( const typename Digraph::Arc & a )

Returns the backward oriented residual arc.

Returns the backward oriented residual arc related to the given arc of the underlying digraph.

Protected Types

typedef Undirector< const Digraph > Undirected
typedef ConstMap< typename DGR::Node , Const< bool , true > > NodeFilter
typedef _adaptor_bits::ResForwardFilter< const DGR , CM , FM , TL > ForwardFilter
typedef _adaptor_bits::ResBackwardFilter< const DGR , CM , FM , TL > BackwardFilter
typedef Undirected::template CombinedArcMap< ForwardFilter , BackwardFilter > ArcFilter
typedef SubDigraph< Undirected , NodeFilter , ArcFilter > Parent

Protected Attributes

const CapacityMap * _capacity
FlowMap * _flow
Undirected _graph
NodeFilter _node_filter
ForwardFilter _forward_filter
BackwardFilter _backward_filter
ArcFilter _arc_filter
class ResidualCapacity

Residual capacity map.

This map adaptor class can be used for obtaining the residual capacities as an arc map of the residual digraph. Its value type is inherited from the capacity map.

Public Types

typedef Arc Key

The key type of the map.

typedef CapacityMap::Value Value

The value type of the map.

Public Functions

inline ResidualCapacity( const ResidualDigraph< DGR , CM , FM , TL > & adaptor )

Constructor.

inline Value operator[]( const Arc & a ) const

Returns the value associated with the given residual arc.

Protected Attributes

const Adaptor * _adaptor