Classes | Public Types | Public Member Functions | Static Public Member Functions | Related Functions

ResidualDigraph< DGR, CM, FM, TL > Class Template Reference


Detailed Description

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

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.

Template Parameters:
DGRThe type of the adapted digraph. It must conform to the Digraph concept. It is implicitly const.
CMThe 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 GR::ArcMap<int>.
FMThe 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.
TLThe tolerance type for handling inexact computation. The default tolerance type depends on the value type of the capacity map.
Note:
This adaptor is implemented using Undirector and FilterArcs adaptors.
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.

#include <lemon/adaptors.h>

List of all members.

Classes

class  ResidualCapacity
 Residual capacity map. More...

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.

Public Member Functions

 ResidualDigraph (const DGR &digraph, const CM &capacity, FM &flow, const TL &tolerance=Tolerance())
 Constructor.
Value residualCapacity (const Arc &a) const
void augment (const Arc &a, const Value &v) const
 Augments on the given arc in the residual digraph.
ResidualCapacity residualCapacity () const
 Returns a residual capacity map.

Static Public Member Functions

static bool forward (const Arc &a)
 Returns true if the given residual arc is a forward arc.
static bool backward (const Arc &a)
 Returns true if the given residual arc is a backward arc.
static Arc forward (const typename Digraph::Arc &a)
 Returns the forward oriented residual arc.
static Arc backward (const typename Digraph::Arc &a)
 Returns the backward oriented residual arc.

Related Functions

(Note that these are not member functions.)
template<typename DGR , typename CM , typename FM >
ResidualDigraph< DGR, CM, FM > residualDigraph (const DGR &digraph, const CM &capacity_map, FM &flow_map)
 Returns a (read-only) Residual adaptor.

Constructor & Destructor Documentation

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

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


Member Function Documentation

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

Returns the residual capacity of the given arc.

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

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.

static bool forward ( const Arc &  a) [inline, static]

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 bool backward ( const Arc &  a) [inline, static]

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 Arc forward ( const typename Digraph::Arc &  a) [inline, static]

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

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

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

ResidualCapacity residualCapacity ( ) const [inline]

This function just returns a residual capacity map.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines