Rice University, L1-Related Optimization Project

::News      ::Courses      ::People      ::Papers and Reports      ::Software

PGC: A Preflow-Push based Graph-Cut Solver

Latest Update

Version 2.32 (June 13, 2008). [Download]

  • Language: C/C++
  • Interface: MATLAB (MEX)
  • MATLAB: 6.5 or higher
  • Platforms: Unix, Windows, Mac
  • Tested compilers: gcc (Unix, Windows/MinGW, Mac), Microsoft Visual Studio (Windows). MATLAB's lcc does not support C++.
  • Note for 64-bit platform: users report OK after removing Lines 26 and 37 of Common_DNC_MT_types.h

The Graph-Cut problem

Given a graph (N,A) where N is the set of nodes and A is the set of arcs, find the binary-valued mapping u: N to {0,1} that solves

minimize sum{(i,j) in A} wij([ui-uj]+) + sum{i in N} fi(ui),

where wij>=0 is the weight (capacity) of arc (i,j), ([ui-uj]+) = 1 if and only if ui=1 and uj=0, and fi is any given function defined on {0,1}.

The solver PGC solves the above problem by (i) reformulating the problem on a graph with two additional nodes s and t (a 2D example is shown above), and then (ii) finding the max s-t flow / min s-t cut by calling a customized version of HIPR, which was originally written by A. Goldberg.

Comparison with MAXFLOW by Y. Boykov and V. Kolmogorov

The underlying algorithm is significantly different from the one used in MAXFLOW by Y. Boykov and V. Kolmogorov (URL: http://www.cs.adastral.ucl.ac.uk/~vnk/software.html).

Our impression from limited numerical experiments is that this solver (PGC) is generally faster than MAXFLOW on graphs in which max flows take relatively long paths. Such graphs include (i) the graphs for total variation in which a node is connected to more than 8 other nodes; (ii) some 3D or high-dimensional graphs; (iii) the graphs in which terminal arcs (those connect from the source or to the sink) have relatively larger capacities than non-terminal arcs.

On sparser graphs, PGC is expected to be slower than MAXFLOW.

Reference

Wotao Yin. PGC: A Preflow-Push based Graph-Cut Solver, URL: www.caam.rice.edu/~wy1/graph-cut/, 2008.

License and disclaimer

Copyright 2008, Wotao Yin (wotao.yin@rice.edu).

This software can be used for non-commercial research purposes only.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Related software and links

  • Graph cut solvers for total variation: Goldfarb and Yin [link]; Darbon and Sigelle [link]
  • Cornell graph cuts webpage [link]
  • Some graph cut software (including MAXFLOW) [link]
  • Goldberg's Network Optimization Library [link]