A wrapper library for Boykov and Kolmogorov max-flow/min-cut implementation
Updated 16 Sep 2008

View License

Yuri Boykov's and Vladimir Kolmogorov's work on graph cuts and MRF optimization has been extensively cited in the academia, and their maximum flow implementation is widely used in computer vision and image processing research.

This is a MEX library that wraps their code, so that it could be easily accessed from MATLAB, using a sparse matrix graph representation. Typical usage:

[flow,labels] = maxflow(A,T);

Where A is the (sparse) adjacency matrix representation of the graph (smoothness term), and T contains the terminal connections (data term). Refer to maxflow.m for further details.

This library currently supports maximum flow calculation for the case of binary partition, based on their work:

Yuri Boykov and Vladimir Kolmogorov, 'An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision', IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.

It has been created on a Windows machine and tested with MATLAB R2007a. See README.txt for building instructions.

Please report any issues.

Future Steps:
1. Extend this wrapper to support reusing of search trees
2. Add support for their multi-label optimization algorithm
Both of these are rather straightforward and I expect to do them in the near future.

Cite As

Miki Rubinstein (2024). maxflow (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Graph and Network Algorithms in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

version 0.2