HPF Simple Parametric Maximum Flow / Minimum Cut Solver Version 1.0

The solver solves a single instance of the parametric minimum cut problem using the highest label pseudoflow algorithm. The input for this version is in the format on multiple source-adjacent capacities vectors that are monotone non-decreasing and multiple sink-adjacent capacities that are monotone non-increasing.

License Information

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

Copyright © 2017. 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 is available as a tar file [pseudo-par-1.0.tar].

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-par-1.0.tar
This will create a folder named "pseudo_parametric". Enter this directory and type
make
This will create an executable in the "bin/" directory called "pseudo_par".

Usage

The input file is assumed to be in modified DIMACS format:

c < Comment lines > p par-max < # vertices > < # arcs > < # parameters > n < source > s n < sink > t a < from-node > < to-node > < capacity > a < source > < sink > < capacity > a < source > < to-node > < capacity1 > < capacity2 > < capacity3 > ... < capacityk > a < from-node > < sink > < capacity1 > < capacity2 > < capacity3 > ... < capacityk >
The nodes are assumed to be numbered consecutively from 1 to <# vertices>. The network contains the following arcs:

From	To	Capacity
Source	Sink	capacity
Source	Not sink	capacity1 <= capacity2 <= capacity3 ... <= capacityk
Not source	Sink	capacity1 >= capacity2 >= capacity3 ... >= capacityk
Not source	Not sink	capacity

It is assumed that there are no source-to-source or sink-to-sink loops.

The input is read from stdin and output is written to stdout.

Output

Two types of output are reported:

For each parameter value, the elapsed time (since reading the input file) and the corresponding min-cit value are reported.
For each node, the parameter number at which the node entered the source set is reported (for example, if a node was in the sink set for the (j-1)-th parameter and is in the source set for the j-th parameter, the parameter number "j" is associated with that node). The source by default enters the source set at parameter number zero. If there are "k" parameters, the nodes in the sink-set corresponding to the k-th parameter are assigned a parameter number of (k+1). The sink is assigned a parameter number of (k+2).

Pseudoflow Parametric Maximum Flow Solver Version 2.0 (Bounded precision and new interface)

This solver provides an implementation of the HPF algorithm to compute the minimum cut for a linear simple parametric flow problem. The problem is discretized over a user-specified precision.

The updated repository can be found at [Github Repository] and a zip file is provided to download in: [Bounded-precision-simple-parametric]

Input Format

The executable reads input from standard input in the following format:

c this is a comment
p max numNodes numArcs precision initParam endParam stepParam
n sourceID s
n sinkID t
a from_1 to_1 a_1 b_1
...
a from_m to_m a_m b_m

Compile

A makefile is provided. To compile into an executable just run the command

make