networkx/networkx — pull request #1094 by ysitu (2014-04-04 21:14:49+00:00)
Title: Add Stoer–Wagner minimum cut algorithm

This is an implementation of the Stoer–Wagner algorithm for finding weighted minimum cuts of undirected graphs. Because it obviously does not work for the NP-complete maximum cut problem, only nonnegative weights are allowed. Also included are heap implementations that provide in-place key changes, on which the algorithm depends.

Frankly speaking, the measured running times do not look very pleasing to me considering that the asymptotic running time is just a little over Θ(*nm* + *n*² log *n*). (It would have been precisely Θ(*nm* + *n*² log *n*) had I used Fibonacci heaps, but they apparently felt slower than pairing heaps and binary heaps.) For a 500-node 5050-edge random graph, it measures 4.7 seconds (with binary heaps) and 8.4 seconds (with pairing heaps) with Python 3.4 on my machine, although running it under PyPy 2.2.1 shaves the time to 1.6 seconds when pairing heaps are used.

##### Reference
1. Stoer, M.; Wagner, F. (1997). "[A simple min-cut algorithm](http://dx.doi.org/10.1145/263867.263872)". Journal of the ACM **44** (4): 585–591.