A simple min cut algorithm

Find a minimal cut in a graph keeping a set of vertices together

Description

An implementation of "A min cut algorithm" by Stoer and Wagner.
In addition there is an option to find the minimal cut that does not separate a set of vertices.

This is not a mincut-maxflow algorithm.

Updated version.

• MATLAB release: MATLAB 7.1.0 (R14SP3)

[Sara Carvalho]

 

[Tai Fei]

could you please give some examples, then it is easy to understand the input of your code.... thx

[Roie Shlosberg]

אתה יכול לתת דוגמא בבקשה לקלט ופלט?

[Yohai Devir]

Here's a usage example:

Consider the graph appearing at
http://upload.wikimedia.org/wikipedia/commons/4/45/Dijksta_Anim.gif

The weights matrix is
W = [Inf,7,9,Inf,Inf,14;7,Inf,10,15,Inf,Inf;9,10,Inf,11,Inf,2;Inf,15,11,Inf,6,Inf;Inf,Inf,Inf,6,Inf,9;14,Inf,2,Inf,9,Inf;];

If we want to find the minimal cut such that vertices 1 and 5 are on the same side of the graph:
[MinCutGroupsList, MinCutWeight] = MinCut([1 5], W)

MinCutGroupsList =

     2 3 4 0 0 0
     1 5 6 0 0 0

MinCutWeight = 24

meaning that:
- Vertices 2,3,4 are on one side of the cut
- Vertices 1,5,6 are on the other side.
- The sum of weights along the cut is 24.

A few farther notes:
- Zero entries for a missing edges also works.
- The weights matrix must be symmetric. Directed edges are not supported.