{ "info": { "author": "Quico Spaen", "author_email": "qspaen@berkeley.edu", "bugtrack_url": null, "classifiers": [ "Development Status :: 3 - Alpha", "Programming Language :: Python :: 3" ], "description": "# Hochbaum's Pseudoflow (HPF) Algorithm for (Linear) Fully Parametric Minimum Cut\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`.\n\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.\n\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).\n\nThe package provides interfaces for Python, C, and Matlab.\n\nThis implementation uses a variant of the fully parametric HPF algorithm as described in:\n> DS Hochbaum (2008), The Pseudoflow algorithm: A new algorithm for the maximum flow problem. Operations Research, 58(4):992-1009.\n\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.\n\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.\n\n\n## Instructions for Python\n\nInstall the package with `pip`:\n\n```bash\n pip install pseudoflow\n```\n\n#### Example\n```python\nimport networkx as nx\nimport pseudoflow\n\nG = nx.DiGraph()\nG.add_edge(0, 1, const=1, mult=5)\nG.add_edge(1, 2, const=9, mult=-3)\n\n\nsource = 0\nsink = 2\nlambda_range = [0., 2.]\n\nbreakpoints, cuts, info = pseudoflow.hpf(\n G, # Networkx directed graph.\n source, # Node id of the source node.\n sink, # Node id of the sink node.\n const_cap=\"const\", # Edge attribute with the constant capacity.\n mult_cap=\"mult\", # Edge attribute with the lambda multiplier.\n lambdaRange=lambda_range, # (lower, upper) bounds for the lambda parameter.\n roundNegativeCapacity=False # True if negative arc capacities should be rounded to zero.\n)\n\n# breakpoints: list of upper bounds for the lambda intervals.\n# cuts: A dictionary with for each node a list indicating whether\n# the node is in the source set of the minimum cut.\nprint(breakpoints) # Output: [1., 2.]\nprint(cuts) # Output: {0: [1, 1], 1: [0, 1], 2: [0, 0]}\n```\n\n## Instructions for C\nNavigate to directory `src/pseudoflow/c`, and compile the `hpf` executable with `make`.\n\nTo execute the solver, use:\n```bash\nhpf input-file.txt output-file.txt\n```\n\nThe input file should contain the graph structure and is assumed to have the following format:\n```\n c \n p <# nodes> <# arcs> \n n s\n n t\n a \n```\nwhere the `a` line is repeated for each arc. The file should satisfy the following conditions:\n- Nodes are labeled `0 .. <# nodes> - 1`.\n- `` is non-negative if ` == ` and ` != `.\n- `` is non-positive if ` != ` and ` == `.\n- `` is zero if ` != ` and ` != `.\n- `` takes value 1 if the any negative capacity arc should be rounded to 0, and value 0 otherwise.\n\nThe solver will generate the following output file:\n```\nt