Preflow-push Algorithms

As we talked about previously the idea of preflow-push is to start with the maximum flow in the network that is allowed. This is known as `flooding the network’. From there we try to send flow towards the sink.

An important concept in this case is the fact that during the algorithm we often violate mass-balance constraints. In other words we can have more flow going into a particular node than leaves it. The difference between the flow in and flow out is referred to as the `excess’. In order to find a feasible solution we need all the nodes apart from the source or sink to have a total excess of zero. We remove this excess by `pushing’ flow to adjacent nodes.

Preflow2

Flooding the network

Continue reading

Augmenting Path Algorithms

In this post I will briefly describe one type of algorithm that has been used to solve the well-known max flow problem. This problem is essentially how to find the maximum flow that can be sent from a source node to a sink node in a network. Think of a graph connected with nodes and arcs each having a certain capacity or limit of flow that it can hold. This could be a very literal thing such as network of pipes or internet cables, but other stranger uses for network flow problems do exist such as the baseball elimination problem I talked about before.

Residual Capacities

The augmenting path algorithm utilises ideas in capacitated graphs called the residual capacity and the residual flow. This is the potential for flow to move along particular arcs. It can be summed up as Residual Flow = Capacity – Forwards Flow + Backwards Flow. See the diagram below to see how it works (the first number is the flow, the second the capacity).

ripoffresidual

Residual capacities

Continue reading