Adaptor class for composing the residual digraph for directed flow and circulation problems.
More...
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
-
| 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. |
- Note
- This adaptor is implemented as a SubDigraph of an Undirector of the digraph.
-
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< typename DGR , typename CM , typename FM , typename TL >
| 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.
template< typename DGR , typename CM , typename FM , typename TL >
| ResidualDigraph |
( |
const ResidualDigraph< DGR , CM , FM , TL > & | other | ) |
|
|
inline |
Creates a residual digraph of the same digraph, capacity map, flow map and tolerance, which refers to none of the members of other.