A thin Maxflow wrapper for Python
Project description
Thin wrapper for Maxflow
Thin Python wrapper for a modified version of the Maxflow algorithm by Yuri Boykov and Vladimir Kolmogorov. The original source code by Vladimir Kolmogorov availbable at http://pub.ist.ac.at/~vnk/software.html. This wrapper uses a modified version with support for larger graphs and slightly lower memory usage. See submodule repository for more details.
Maxflow vs. QPBO
A more advanced alternative to the Maxflow algorithm is (quadratic pseudo-Boolean optimization) QPBO, which also uses s-t graph cut. Unlike Maxflow, it allows for non-submodular energy terms, which Maxflow doesn't (unless you construct the graph in a specific way, which is what QPBO does). Amongst other things, this allows QPBO to solve optimization problems with exclusions terms, which can be very usefull. QPBO uses more memory and is slightly slower than Maxflow.
Installation
Install package using pip install thinmaxflow
or clone this repository (including submodule). Building the package requires Cython.
Graph types
Currently, there are four different types of graphs: GraphInt
, GraphShort
, GraphFloat
and GraphDouble
. The only difference is the underlying datatypes used for the edge capacities in the graph. For stability, it is recommended to use GraphInt
for integer capacities and GraphDouble
for floating point capacities. However, in some cases, it maybe be favourable to use GraphShort
or GraphFloat
to reduce memory consumption.
Tiny example
import thinmaxflow as tf
# Create graph object.
graph = tf.GraphInt()
# Number of nodes to add.
nodes_to_add = 2
# Add two nodes.
first_node_id = graph.add_node(nodes_to_add)
# Add edges.
graph.add_tweights(0, 5, 0) # s --5-> n(0)
graph.add_tweights(0, 0, 1) # n(0) --1-> t
graph.add_tweights(1, 0, 3) # n(1) --3-> t
graph.add_edge(0, 1, 2, 1) # n(0) --2-> n(1)
# n(1) --1-> n(0)
# Find maxflow/cut graph.
flow = graph.maxflow()
for n in range(nodes_to_add):
segment = graph.what_segment(n)
print('Node %d belongs to segment %d.' % (n, segment))
# Node 0 belongs to segment 0.
# Node 1 belongs to segment 1.
print('Maximum flow: %s' % flow)
# Maximum flow: 3
License
As the Maxflow implementation is distributed under the GPLv3 license, so is this package.
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
Built Distribution
Hashes for thinmaxflow-0.1.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e98cb92991217f755e1032097e00909e16361d4ad7c9e39ac75a39e0bc822cde |
|
MD5 | 1743cf0e1ce9faa6cc13cbc7f5078afc |
|
BLAKE2b-256 | 17ac6ed5a91c2c2cb93c5cf5674f80cb8fd0e99833b0eb017c093dab7ea5f601 |