This package provides an fully parametric implementation of pseudoflow for minimum cut on directed graphs. In the parametric minimum cut problem, the capacity of source-adjacent arcs is monotone non-decreasing in the parameter `lambda`

whereas the capacity of sink-adjacent arcs is monotone non-increasing in `lambda`

. This solver requires that the capacities of source and sink adjacent arcs are linear in `lambda`

: `capacity = constant + multiplier * lambda`

.

This fully parametric solver finds the optimal minimum cut for all `lambda`

values in a given range. The solution for all lambda values is represented with `O(n)`

intervals for the parameter lambda. In each interval, the optimal minimum cut remains the same.

A simple parametric minimum cut solver that provides the optimal minimum cut for a given list of arc capacities is available here, and a non-parametric maximum flow version of pseudoflow is available here.

The package provides interfaces for Python, C, and Matlab.

This implementation uses a variant of the fully parametric HPF algorithm as described in:

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

This implementation does not use *free runs* nor does it use warm starts with informatiom from previous runs (see pg.15). This implementation should therefore **not be used** for comparison with the fully parametric HPF algorithm.

The latest version of this software is available on GitHub. The source code is also available in ZIP format here.

Install the package with `pip`

:

` pip install pseudoflow`

import networkx as nx import pseudoflow G = nx.DiGraph() G.add_edge(0, 1, const=1, mult=5) G.add_edge(1, 2, const=9, mult=-3) source = 0 sink = 2 lambda_range = [0., 2.] breakpoints, cuts, info = pseudoflow.hpf( G, # Networkx directed graph. source, # Node id of the source node. sink, # Node id of the sink node. const_cap="const", # Edge attribute with the constant capacity. mult_cap="mult", # Edge attribute with the lambda multiplier. lambdaRange=lambda_range, # (lower, upper) bounds for the lambda parameter. roundNegativeCapacity=False # True if negative arc capacities should be rounded to zero. ) # breakpoints: list of upper bounds for the lambda intervals. # cuts: A dictionary with for each node a list indicating whether # the node is in the source set of the minimum cut. print(breakpoints) # Output: [1., 2.] print(cuts) # Output: {0: [1, 1], 1: [0, 1], 2: [0, 0]}

Navigate to directory `src/pseudoflow/c`

, and compile the `hpf`

executable with `make`

.

To execute the solver, use:

`hpf input-file.txt output-file.txt`

The input file should contain the graph structure and is assumed to have the following format:

where the `a`

line is repeated for each arc. The file should satisfy the following conditions:

- Nodes are labeled
`0 .. <# nodes> - 1`

. `<lambda multiplier>`

is non-negative if`<from-node> == <source node>`

and`<to-node> != <sink-node>`

.`<lambda multiplier>`

is non-positive if`<from-node> != <source node>`

and`<to-node> == <sink-node>`

.`<lambda multiplier>`

is zero if`<from-node> != <source node>`

and`<to-node> != <sink-node>`

.`<round if negative>`

takes value 1 if the any negative capacity arc should be rounded to 0, and value 0 otherwise.

The solver will generate the following output file:

The `n`

line appears for each node. `<sourceset indicator interval 1 >`

indicates whether the node is in the source set of the minimum cut for the first lambda interval.

See `src/pseudoflow/c/example`

for an example.

Copy the content of `src/pseudoflow/matlab`

to your current directory.

From within Matlab, compile the mex extension with:

` .`

The solver is accessible via the `hpf`

function with the following signature:

` = ;`

**arcmatrix**: Each row of the matrix has the following structure:`[from_node, to_node, constant capacity, lambda multiplier]`

**num_nodes**: Number of nodes in the graph**source_node**: The numeric label of the source node**sink_node**: The numeric label of the sink node**lambda_range**: [lower bound, upper bound] for the lambda parameter.**rounding**: Set to 1 if negative arc capacities should be rounded to zero, and 0 otherwise.

**cuts**: n x k matrix where`A(i,j)`

is 1 if node`i`

is in the source set for lambda interval`j`

, and 0 otherwise.**lambdas**: 1 x k matrix where`L(j)`

is the upper bound of the lambda interval`j`

.

The source code is subject to the following academic license. Note that 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 Quico Spaen and Dorit S. Hochbaum, Department of Industrial Engineering and Operations Research, University of California, Berkeley. This work is adapted from the Pseudoflow implementation by Bala Chandran and Dorit S. Hochbaum available at https://riot.ieor.berkeley.edu/Applications/Pseudoflow/maxflow.html

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.