Skip to main content

Pseudoflow algorithm for the parametric minimum cut problem.

Project description

Hochbaum's Pseudoflow (HPF) Algorithm for (Linear) Fully Parametric Minimum Cut

This package provides a 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 package provides an option to round capacities that are negative for certain lambda values to zero. This option should only be used when each node has a source adjacent arc with capacity max(0, a * lambda + b) and a corresponding sink adjacent arc with capacity max(0, -a * lambda - b). Otherwise, the intersection of the cut capacities is wrongly identified.

Instructions for Python

Install the package with pip:

    pip install pseudoflow

Example

import networkx as nx  # igraph is also supported
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 or igraph 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]}

Instructions for C

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:

    c <comment lines>
    p <# nodes> <# arcs> <lower bound> <upper bound> <round if negative>
    n <source node> s
    n <sink node> t
    a <from-node> <to-node> <constant capacity> <lambda multiplier>

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:

t <time (in sec) read data> <time (in sec) initialize> <time (in sec) solve>
s <# arc scans> <# mergers> <# pushes> <# relabels > <# gap >
p <number of lambda intervals = k>
l <lambda upperbound interval 1> ... <lambda upperbound interval k>
n <node-id> <sourceset indicator interval 1 > .. <indicator interval k>

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.

Instructions for Matlab

Copy the content of src/pseudoflow/matlab to your current directory.

From within Matlab, compile the mex extension with:

    mex hpfMatlab.c

The solver is accessible via the hpf function with the following signature:

    [cuts, lambdas, stats, times]  = hpf(arcmatrix, num_nodes, source, sink lambda_range, rounding);

Inputs:

  • 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.

Outputs:

  • 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.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pseudoflow-2022.12.0.tar.gz (86.7 kB view details)

Uploaded Source

Built Distribution

pseudoflow-2022.12.0-cp38-cp38-win_amd64.whl (20.0 kB view details)

Uploaded CPython 3.8 Windows x86-64

File details

Details for the file pseudoflow-2022.12.0.tar.gz.

File metadata

  • Download URL: pseudoflow-2022.12.0.tar.gz
  • Upload date:
  • Size: 86.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.11.1

File hashes

Hashes for pseudoflow-2022.12.0.tar.gz
Algorithm Hash digest
SHA256 83751d670b57d6e45f108a8546899d7c58fe1605137876e37e56c5d7cfb2ed47
MD5 8e0f86461b5b4df6e19d86f86e794dd0
BLAKE2b-256 7f733026ba04192286d1caa9415d669ece7fe77469f3fe4ef245a9fbaa8b1101

See more details on using hashes here.

File details

Details for the file pseudoflow-2022.12.0-cp38-cp38-win_amd64.whl.

File metadata

File hashes

Hashes for pseudoflow-2022.12.0-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 a4a3c684a0d158af15d5c8244cd5aee04d1c6d0204a088449d8649ca63e76fbc
MD5 4cb9bc096e3ab9e535407de9f7a9ae03
BLAKE2b-256 c34158cf145137ecd083088eee309316e7b5c75524545d601010775dbe7d209c

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page