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
Nodetype of this adaptor and the adapted digraph are convertible to each other, moreover theArctype of the adaptor is convertible to theArctype 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 Functions
- inline ResidualDigraph( )
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
trueif the given residual arc is a forward arc.Returns
trueif 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
trueif the given residual arc is a backward arc.Returns
trueif the given residual arc has the opposite orientation than the original arc, i.e. it is a so called backward arc.
Protected Types
-
typedef Undirector< const Digraph > Undirected
-
typedef Undirected::template CombinedArcMap< ForwardFilter , BackwardFilter > ArcFilter
-
typedef SubDigraph< Undirected , NodeFilter , ArcFilter > Parent
Protected Attributes
-
const CapacityMap * _capacity
-
Undirected _graph
-
NodeFilter _node_filter
-
ForwardFilter _forward_filter
-
BackwardFilter _backward_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 CapacityMap::Value Value
The value type of the map.
Public Functions
-
typedef CapacityMap::Value Value