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.
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:
- The augmenting path is a cycle and the (residual) edge length of this cycle is negative. Then augmentation will decrease the overall costs of the flow.
- The start node of the augmenting path is oversaturated and the end node is undersaturated. In that case, augmentation will reduce the node imbalances.
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]
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:
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]
The min-cost flow solver is one of the library cornerstones for several resaons:
- Min-cost flow is indeed one of the most important graph optimization models. An important library internal application is in the weighted matching code.
- The solver includes various alternative methods, some are intended for practical computations, others have been added only for didactic purposes.
- The primal network simplex, the cost-scaling and the capacity scaling method are performant enough to solve problem instances with 10000s of edges.
- Min-cost flow perfectly illustrates the application of linear programming duality to graph optimization models.
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:
- The Klein and the minimum mean cycle canceling method operate on the original edge lengths and so do not depend on the node potentials. In principle, the Klein method computes node potentials in every iteration from scratch.
- The cost scaling method initializes the scaling parameter with the most-negative reduced arc length. If nothing has changed since the last solver call, the method detects this.
- The capacity scaling method starts with an arbitrary pseudo-flow and searches a restricted residual network depending on the scaling parameter and the reduced edge length. Again, If nothing has changed since the last solver call, no flow augmentations or potential updates occur.
- The primal network simplex method starts with growing a spanning tree from the edges with zero reduced length. Even if nothing has changed since the last solver call, degenerate pivots can occur. Explicit application of an LP solver is similar.
[See API]
Return to main page
