Network flows

By a pseudo-flow, one usually denotes a subgraph multiplicity vector bounded by given lower and upper capacity vectors. In the library, this is only true for directed arcs. For undirected edges, lower capacity bounds have to be zero, the absolute flow value is bounded by the upper capacity bound, and a negative flow value denotes a flow running in the implicit backward direction.

The standard network flow models also use the node demand labels and the concept of node divergence: The divergence of a node v is the flow sum of arcs entering v minus the flow sum of arcs leaving v. A b-flow is a pseudo-flow where all node divergences match the respective node demands (say: the nodes are balanced). So in the standard notation, the node demand vector is abbreviated by b.


Low level operations

There is a technique which occurs in nearly all network flow methods, called augmentation. This means pushing flow along a given path, increasing the subgraph multiplicities of forward arcs and decreasing the subgraph multiplicities of arcs which occur in backward direction. For a single arc, this is exactly what abstractDiGraph::Push() does to the subgraph multiplicities (the procedure also updates the node degree labels).

There are two obvious applications of the augmentation technique:

In both situations, the methods abstractDiGraph::FindCap() and abstractDiGraph::Augment() apply. The first determines the minimum amount of flow which can be pushed along a path, and the second method actually modifies the subgraph multiplicities and the node degree labels.

Augmenting paths are usually determined by searching the so-called residual network which is implicitly defined by the functions abstractMixedGraph::ResCap() and abstractMixedGraph::RedLength(). The latter function depends on an array of node potentials (usually stored in the so-named register) and is called in the weighted setting only.

[See API]


Maximum st-flow and feasible b-flow

The maximum st-flow problem distinguishes two nodes s (the source) and t (the sink or target) from the other graph nodes. An st-flow denotes a pseudo-flow which is balanced at all nodes other than s and t. It is maximum if the flow divergence at s is minimized (and maximized at t).

The following shows a maximum st-flow where s is the left-most node, and t is the right-most node in the drawing. A minimum cut is indicated by the node colours, and the node labels of the white left-hand nodes denote the distance from source in the residual graph:

maxFlow.gif

A feasible b-flow (a b-flow which satisfies the capacity bounds) can be determined in the same time complexity order as a maximum st-flow. This is achieved by identifying the divergent nodes and then transforming to a maximum st-flow problem instance.

[See API]


Minimum cost st-flow, b-flow and circulation

The min-cost flow solver is one of the library cornerstones for several resaons:

The min-cost flow dual variables in terms linear programming are called node potentials as usual, and are stored by the register attribute with this name. All min-cost flow methods return with an optimal flow and with optimal node potentials. When the solver is restarted, it dependends on the particular method and on the intermediate manipulations, if and how the method draws benefit of maintaining the node potentials:

[See API]


Related topics

Return to main page