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

Water flows downhill

There is a useful analogy for the preflow-push algorithm in terms of water trying to flow downhill to a destination.

landscape-nature-forest-trees

  • We move the source uphill so that water flows from it towards the downhill nodes.
  • In general water flows downhill towards the sink.
  • Sometimes flow becomes trapped at a node that has no downhill neighbours.
  • We move this node higher and water continues to flow downhill to the sink.
  • Eventually no more flow can reach the sink.
  • As we continue to move nodes higher the remaining flow returns to the source.
  • The algorithm terminates when all the flow is at the source or the sink.

Example: Preflow-push

This slideshow requires JavaScript.

Note that in the example above, the steps correspond to what we will do next. This action has been completed on the slide.

Variants of the Algorithm

If you were paying attention to the simple example above you might have noticed that we seemingly picked at random which node to select when we had multiple nodes containing an excess. This was exactly the case; the above example just uses the generic preflow-push algorithm which is about as good as the best augmenting path algorithms.

The attraction of the preflow-push algorithms is that they can be significantly improved by incorporating clever rules for deciding which nodes to pick. These tend to be heuristics and are briefly described below.

  • Generic preflow-push algorithm  \rightarrow O(n^2m)

This is the standard algorithm for preflow-push which forms the basis for most subsequent modifications.

  • FIFO preflow-push algorithm  \rightarrow O(n^3)

This modification of the generic algorithm examines active nodes (nodes with an excess) in the order of first-in-first-out.

  • Highest-label preflow-push algorithm  \rightarrow O(n^2\sqrt{m})

This version is probably the most efficient algorithm in practice and decides to select the node with the highest excess when a choice has to be made.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s