# 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](https://riot.ieor.berkeley.edu/Applications/Pseudoflow/parametric.html), and a non-parametric maximum flow version of pseudoflow is available [here](https://riot.ieor.berkeley.edu/Applications/Pseudoflow/maxflow.html).
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`:
```bash
pip install pseudoflow
```
#### Example
```python
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:
```bash
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:
```matlab
mex hpfMatlab.c
```
The solver is accessible via the `hpf` function with the following signature:
```matlab
[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`.
Raw data
{
"_id": null,
"home_page": "https://github.com/quic0/pseudoflow",
"name": "pseudoflow",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "minimum cut,network flow,parametric",
"author": "Quico Spaen",
"author_email": "qspaen@berkeley.edu",
"download_url": "https://files.pythonhosted.org/packages/7f/73/3026ba04192286d1caa9415d669ece7fe77469f3fe4ef245a9fbaa8b1101/pseudoflow-2022.12.0.tar.gz",
"platform": null,
"description": "# Hochbaum's Pseudoflow (HPF) Algorithm for (Linear) Fully Parametric Minimum Cut\r\nThis 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`.\r\n\r\nThis 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.\r\n\r\nA simple parametric minimum cut solver that provides the optimal minimum cut for a given list of arc capacities is available [here](https://riot.ieor.berkeley.edu/Applications/Pseudoflow/parametric.html), and a non-parametric maximum flow version of pseudoflow is available [here](https://riot.ieor.berkeley.edu/Applications/Pseudoflow/maxflow.html).\r\n\r\nThe package provides interfaces for Python, C, and Matlab.\r\n\r\nThis implementation uses a variant of the fully parametric HPF algorithm as described in:\r\n> DS Hochbaum (2008), The Pseudoflow algorithm: A new algorithm for the maximum flow problem. Operations Research, 58(4):992-1009.\r\n\r\nThis 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.\r\n\r\nThe 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.\r\n\r\n\r\n## Instructions for Python\r\n\r\nInstall the package with `pip`:\r\n\r\n```bash\r\n pip install pseudoflow\r\n```\r\n\r\n#### Example\r\n```python\r\nimport networkx as nx # igraph is also supported\r\nimport pseudoflow\r\n\r\nG = nx.DiGraph()\r\nG.add_edge(0, 1, const=1, mult=5)\r\nG.add_edge(1, 2, const=9, mult=-3)\r\n\r\n\r\nsource = 0\r\nsink = 2\r\nlambda_range = [0., 2.]\r\n\r\nbreakpoints, cuts, info = pseudoflow.hpf(\r\n G, # Networkx or igraph directed graph.\r\n source, # Node id of the source node.\r\n sink, # Node id of the sink node.\r\n const_cap=\"const\", # Edge attribute with the constant capacity.\r\n mult_cap=\"mult\", # Edge attribute with the lambda multiplier.\r\n lambdaRange=lambda_range, # (lower, upper) bounds for the lambda parameter.\r\n roundNegativeCapacity=False # True if negative arc capacities should be rounded to zero.\r\n)\r\n\r\n# breakpoints: list of upper bounds for the lambda intervals.\r\n# cuts: A dictionary with for each node a list indicating whether\r\n# the node is in the source set of the minimum cut.\r\nprint(breakpoints) # Output: [1., 2.]\r\nprint(cuts) # Output: {0: [1, 1], 1: [0, 1], 2: [0, 0]}\r\n```\r\n\r\n## Instructions for C\r\nNavigate to directory `src/pseudoflow/c`, and compile the `hpf` executable with `make`.\r\n\r\nTo execute the solver, use:\r\n```bash\r\nhpf input-file.txt output-file.txt\r\n```\r\n\r\nThe input file should contain the graph structure and is assumed to have the following format:\r\n```\r\n c <comment lines>\r\n p <# nodes> <# arcs> <lower bound> <upper bound> <round if negative>\r\n n <source node> s\r\n n <sink node> t\r\n a <from-node> <to-node> <constant capacity> <lambda multiplier>\r\n```\r\nwhere the `a` line is repeated for each arc. The file should satisfy the following conditions:\r\n- Nodes are labeled `0 .. <# nodes> - 1`.\r\n- `<lambda multiplier>` is non-negative if `<from-node> == <source node>` and `<to-node> != <sink-node>`.\r\n- `<lambda multiplier>` is non-positive if `<from-node> != <source node>` and `<to-node> == <sink-node>`.\r\n- `<lambda multiplier>` is zero if `<from-node> != <source node>` and `<to-node> != <sink-node>`.\r\n- `<round if negative>` takes value 1 if the any negative capacity arc should be rounded to 0, and value 0 otherwise.\r\n\r\nThe solver will generate the following output file:\r\n```\r\nt <time (in sec) read data> <time (in sec) initialize> <time (in sec) solve>\r\ns <# arc scans> <# mergers> <# pushes> <# relabels > <# gap >\r\np <number of lambda intervals = k>\r\nl <lambda upperbound interval 1> ... <lambda upperbound interval k>\r\nn <node-id> <sourceset indicator interval 1 > .. <indicator interval k>\r\n```\r\nThe `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.\r\n\r\nSee `src/pseudoflow/c/example` for an example.\r\n\r\n## Instructions for Matlab\r\n\r\nCopy the content of `src/pseudoflow/matlab` to your current directory.\r\n\r\nFrom within Matlab, compile the mex extension with:\r\n```matlab\r\n mex hpfMatlab.c\r\n```\r\n\r\nThe solver is accessible via the `hpf` function with the following signature:\r\n```matlab\r\n [cuts, lambdas, stats, times] = hpf(arcmatrix, num_nodes, source, sink lambda_range, rounding);\r\n```\r\n\r\n#### Inputs:\r\n* **arcmatrix**: Each row of the matrix has the following structure: `[from_node, to_node, constant capacity, lambda multiplier]`\r\n* **num_nodes**: Number of nodes in the graph\r\n* **source_node**: The numeric label of the source node\r\n* **sink_node**: The numeric label of the sink node\r\n* **lambda_range**: [lower bound, upper bound] for the lambda parameter.\r\n* **rounding**: Set to 1 if negative arc capacities should be rounded to zero, and 0 otherwise.\r\n\r\n#### Outputs:\r\n* **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.\r\n* **lambdas**: 1 x k matrix where `L(j)` is the upper bound of the lambda interval `j`.\r\n",
"bugtrack_url": null,
"license": "Non-commercial license. Not an open-source license.",
"summary": "Pseudoflow algorithm for the parametric minimum cut problem.",
"version": "2022.12.0",
"split_keywords": [
"minimum cut",
"network flow",
"parametric"
],
"urls": [
{
"comment_text": "",
"digests": {
"md5": "4cb9bc096e3ab9e535407de9f7a9ae03",
"sha256": "a4a3c684a0d158af15d5c8244cd5aee04d1c6d0204a088449d8649ca63e76fbc"
},
"downloads": -1,
"filename": "pseudoflow-2022.12.0-cp38-cp38-win_amd64.whl",
"has_sig": false,
"md5_digest": "4cb9bc096e3ab9e535407de9f7a9ae03",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": null,
"size": 20002,
"upload_time": "2023-01-01T01:18:34",
"upload_time_iso_8601": "2023-01-01T01:18:34.325860Z",
"url": "https://files.pythonhosted.org/packages/c3/41/58cf145137ecd083088eee309316e7b5c75524545d601010775dbe7d209c/pseudoflow-2022.12.0-cp38-cp38-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "8e0f86461b5b4df6e19d86f86e794dd0",
"sha256": "83751d670b57d6e45f108a8546899d7c58fe1605137876e37e56c5d7cfb2ed47"
},
"downloads": -1,
"filename": "pseudoflow-2022.12.0.tar.gz",
"has_sig": false,
"md5_digest": "8e0f86461b5b4df6e19d86f86e794dd0",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 86735,
"upload_time": "2023-01-01T01:18:36",
"upload_time_iso_8601": "2023-01-01T01:18:36.335334Z",
"url": "https://files.pythonhosted.org/packages/7f/73/3026ba04192286d1caa9415d669ece7fe77469f3fe4ef245a9fbaa8b1101/pseudoflow-2022.12.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-01 01:18:36",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "quic0",
"github_project": "pseudoflow",
"travis_ci": true,
"coveralls": false,
"github_actions": false,
"lcname": "pseudoflow"
}
JSON
