HPF- Hochbaum's PseudoFlow

The pseudoflow algorithm solves the minimum cut and the maximum flow problem employing only pseudoflows and without generating flows explicitly. The algorithm solves directly a problem equivalent to the minimum cut problem and then recovers a maximum flow, if needed.

HPF and its practical performance is described in:

D. S. Hochbaum. The Pseudoflow algorithm: A new algorithm for the maximum flow problem. Operations Research Vol 58(4) 992-1009, July-Aug (2008)

B. Chandran and D. S. Hochbaum. A Computational Study of the Pseudoflow and Push-relabel Algorithms for the Maximum Flow Problem. Operations Research. Vol. 57(2) 358-376, March-April 2009.

The solver solves a single instance of the maximum flow problem using the pseudoflow algorithm.

License Information

The source code is subject to the following academic license. Note this is not an open source license.

Copyright © 2001. The Regents of the University of California (Regents). All Rights Reserved.

Permission to use, copy, modify, and distribute this software and its documentation for educational, research, and not-for-profit purposes, without fee and without a signed licensing agreement, is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies, modifications, and distributions. Contact The Office of Technology Licensing, UC Berkeley, 2150 Shattuck Avenue, Suite 510, Berkeley, CA 94720-1620, (510) 643-7201, for commercial licensing opportunities. Created by Bala Chandran and Dorit S. Hochbaum, Department of Industrial Engineering and Operations Research, University of California, Berkeley.

IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Source Code

The source (Solver Version 3.23) is available as a tar file [pseudo-max-3.23_2.tar].
MATLAB implementation at [MatlabHPF.zip].

Installation Instructions

The code is designed to compile under gcc on a unix system. After downloading the file, run the following commands:
tar -xvf pseudo-max-3.23_2.tar
This will create a folder named "pseudo_max". Enter this directory and type
make
This will create four executables in the "bin/" directory:

pseudo_fifo: Highest label pseudoflow algorithm with FIFO buckets.
pseudo_lifo: Highest label pseudoflow algorithm with LIFO buckets.
pseudo_lo_fifo: Lowest label pseudoflow algorithm with FIFO buckets.
pseudo_lo_lifo: Lowest label pseudoflow algorithm with LIFO buckets.

The pseudo_fifo code is in general the fastest of the implementations.

The input is read from stdin and output is written to stdout. See the "README" file for further details on usage.