Loading...
Searching...
No Matches
ResidualDigraph< DGR, CM, FM, TL > Class Template Reference
Data Structures » Graph Structures » Adaptor Classes for Graphs

## 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 be a directed graph and let be a number type. Let be functions on the arcs. This adaptor implements a digraph structure with node set and arc set , where and , i.e. the so called residual digraph. When the union is taken, multiplicities are counted, i.e. the adaptor has exactly 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 GR::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 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>`

## 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
| Returns the residual capacity of the given arc.
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 Symbols

(Note that these are not member symbols.)
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()

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.

## Member Function Documentation

## residualCapacity() [1/2]

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

Value residualCapacity | ( | const Arc & | a | ) | const

inline

Returns the residual capacity of the given arc.

## augment()

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

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.

## forward() [1/2]

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

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.

## backward() [1/2]

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

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.

## forward() [2/2]

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

Arc forward | ( | const typename Digraph::Arc & | a | ) |

inline static

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

## backward() [2/2]

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

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() [2/2]

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

ResidualCapacity residualCapacity | ( |  | ) | const

inline

This function just returns a residual capacity map.