Maxflow package¶
maxflow¶
maxflow is a Python module for max-flow/min-cut computations. It wraps
the C++ maxflow library by Vladimir Kolmogorov, which implements the
algorithm described in
An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. Yuri Boykov and Vladimir Kolmogorov. TPAMI.
This module aims to simplify the construction of graphs with complex
layouts. It provides two Graph classes, Graph[int] and Graph[float],
for integer and real data types.
Example:
>>> import maxflow
>>> g = maxflow.Graph[int](2, 2)
>>> nodes = g.add_nodes(2)
>>> g.add_edge(nodes[0], nodes[1], 1, 2)
>>> g.add_tedge(nodes[0], 2, 5)
>>> g.add_tedge(nodes[1], 9, 4)
>>> g.maxflow()
8
>>> g.get_grid_segments(nodes)
array([ True, False])
If you use this library for research purposes, you must cite the aforementioned paper in any resulting publication.
The module maxflow has the classes maxflow.GraphInt and
maxflow.GraphFloat. Both have the same methods and behavior. They
only differ in the data type of the flow network. For conciseness, this page
includes the documentation of just one of these classes.
Note that these classes can be accessed with a template-like syntax using the
dictionary maxflow.Graph: maxflow.Graph[int] and
maxflow.Graph[float].
-
class
maxflow.GraphInt¶ -
__init__()¶ Initialize self. See help(type(self)) for accurate signature.
-
add_edge(self, int i, int j, long capacity, long rcapacity)¶ Adds a bidirectional edge between nodes
iandjwith the weightscapandrev_cap.To add edges between a non-terminal node and terminal nodes, see
add_tedge.Important: see note about the constructor.
-
add_grid_edges(self, ndarray nodeids, weights=1, structure=None, int symmetric=0)¶ Add edges to a grid of nodes in a structured manner.
The grid of nodes is given by
nodeids, that contains the identifiers of the nodes.weightsis an array containing the capacities of the edges starting at every node.nodeidsandweightsmust have the same shape or be broadcastable to the same shape.structureindicates the neighborhood around each node. For every node thestructurearray will be centered on it (in a sliding window manner) and edges will be added from the central node to the nodes corresponding to non-zero entries ofstructure. The capacities of these added edges is computed as the product between the weight corresponding to the central node and the value instructure.If
structureis None (by default), it is equivalent to the output of vonNeumann_structure(ndim=nodeids.ndim, directed=symmetric). This creates a 4-connected grid.If symmetric is True, for every edge i->j another edge j->i with the same capacity will be added.
Examples
Standard 4-connected grid, all capacities set to 1:
>>> g = maxflow.GraphFloat() >>> nodeids = g.add_grid_nodes((250, 250)) >>> structure = np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0]]) >>> # Or structure = maxflow.vonNeumann_structure(ndim=2, directed=True) >>> g.add_grid_edges(nodeids, weights=1, structure=structure, symmetric=True)
XXX----1--->XXX----1--->XXX XXX<---1----XXX<---1----XXX | ^ | ^ | ^ | | | | | | 1| |1 1| |1 1| |1 | | | | | | V | V | V | XXX----1--->XXX----1--->XXX ... XXX<---1----XXX<---1----XXX | ^ | ^ | ^ | | | | | | 1| |1 1| |1 1| |1 | | | | | | V | V | V | XXX----1--->XXX----1--->XXX XXX<---1----XXX<---1----XXX . . . . . .
4-connected 3x3 grid, different capacities for different positions, not symmetric:
>>> g = maxflow.GraphFloat() >>> nodeids = g.add_grid_nodes((3, 3)) >>> structure = np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0]]) >>> weights = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) >>> g.add_grid_edges(nodeids, weights=weights, structure=structure, symmetric=False)
XXX----1--->XXX----2--->XXX XXX XXX XXX | | | | | | 1| 2| 3| | | | V V V XXX----4--->XXX----5--->XXX XXX XXX XXX | | | | | | 4| 5| 6| | | | V V V XXX----7--->XXX----8--->XXX XXX XXX XXX
4-connected 3x3 grid, different capacities for different positions, symmetric:
>>> g = maxflow.GraphFloat() >>> nodeids = g.add_grid_nodes((3, 3)) >>> structure = np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0]]) >>> weights = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) >>> g.add_grid_edges(nodeids, weights=weights, structure=structure, symmetric=True)
XXX----1--->XXX----2--->XXX XXX<---1----XXX<---2----XXX | ^ | ^ | ^ | | | | | | 1| |1 2| |2 3| |3 | | | | | | V | V | V | XXX----4--->XXX----5--->XXX XXX<---4----XXX<---5----XXX | ^ | ^ | ^ | | | | | | 4| |4 5| |5 6| |6 | | | | | | V | V | V | XXX----7--->XXX----8--->XXX XXX<---7----XXX<---8----XXX
4-connected 3x3 grid, different capacities for different positions, undirected structure and not symmetric:
>>> g = maxflow.GraphFloat() >>> nodeids = g.add_grid_nodes((3, 3)) >>> structure = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]]) >>> weights = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) >>> g.add_grid_edges(nodeids, weights=weights, structure=structure, symmetric=False)
XXX----1--->XXX----2--->XXX XXX<---2----XXX<---3----XXX | ^ | ^ | ^ | | | | | | 1| |4 2| |5 3| |6 | | | | | | V | V | V | XXX----4--->XXX----5--->XXX XXX<---5----XXX<---6----XXX | ^ | ^ | ^ | | | | | | 4| |7 5| |8 6| |9 | | | | | | V | V | V | XXX----7--->XXX----8--->XXX XXX<---8----XXX<---9----XXX
4-connected 3x3 grid, different capacities for different orientations, not symmetric:
>>> g = maxflow.GraphFloat() >>> nodeids = g.add_grid_nodes((3, 3)) >>> structure = np.array([[0, 1, 0], [4, 0, 2], [0, 3, 0]]) >>> g.add_grid_edges(nodeids, weights=1, structure=structure, symmetric=False)
XXX----2--->XXX----2--->XXX XXX<---4----XXX<---4----XXX | ^ | ^ | ^ | | | | | | 3| |1 3| |1 3| |1 | | | | | | V | V | V | XXX----2--->XXX----2--->XXX XXX<---4----XXX<---4----XXX | ^ | ^ | ^ | | | | | | 3| |1 3| |1 3| |1 | | | | | | V | V | V | XXX----2--->XXX----2--->XXX XXX<---4----XXX<---4----XXX
-
add_grid_nodes(self, shape)¶ Add a grid of non-terminal nodes. Return the identifiers of the added nodes in an array with the shape of the grid.
-
add_grid_tedges(self, ndarray nodeids, sourcecaps, sinkcaps)¶ Add terminal edges to a grid of nodes, given their identifiers in
nodeids.sourcecapsandsinkcapsare arrays with the capacities of the edges from the source node and to the sink node, respectively. The shape of all these arrays must be equal.This is equivalent to calling
add_tedgefor many nodes, but much faster.
-
add_nodes(self, int num_nodes)¶ Add non-terminal node(s) to the graph. By default, one node is added. If
num_nodes>1, thennum_nodesnodes are inserted. It returns the identifiers of the nodes added.The source and terminal nodes are included in the graph by default, and you must not add them.
Important: see note about the constructor.
-
add_tedge(self, int i, long cap_source, long cap_sink)¶ Add an edge ‘SOURCE->i’ with capacity
cap_sourceand another edge ‘i->SINK’ with capacitycap_sink. This method can be called multiple times for each node. Capacities can be negative.Note: No internal memory is allocated by this call. The capacities of terminal edges are stored in each node.
-
get_edge_count(self)¶ Returns the number of non-terminal edges.
-
get_grid_segments(self, ndarray nodeids)¶ After the maxflow is computed, this function returns which segment the given nodes belong to. The output is a boolean array of the same shape than the input array
nodeids.This is equivalent to calling
get_segmentfor many nodes, but much faster.
-
get_node_count(self)¶ Returns the number of non-terminal nodes.
-
get_nx_graph(self)¶ Build a NetworkX DiGraph with the status of the maxflow network. The resulting graph will contain the terminal and non-terminal nodes and edges. The attribute
weightof every edge will be set to its residual capacity. If the residual capacity of an edge is 0, the edge is not included in the DiGraph.The residual capacity for an edge is defined as the full capacity of the edge (set with the methods
add_tedge,add_edgeand their corresponding grid equivalents,add_grid_tedgesandadd_grid_edges) minus the amount of flow passing through it. Therefore, the weights of the DiGraph depend on the amount of flow passing through the network and, in turn, this depends on whether the call toget_nx_graphis done before or after callingGraphInt.maxflow.Before calling the
GraphInt.maxflow, there is no flow and therefore the residual capacity of every edge is equal to its full capacity.After calling
GraphInt.maxflow, a virtual flow traverses the network from the source node to the sink node, and the residual capacities will be lower than the full capacities. Note that in this case, sinceget_nx_graphignores edges with residual capacity 0, the edges in the minimum cut will not be included in the final DiGraph.Note that this function is slow and should be used only for debugging purposes.
This method requires the Python NetworkX package.
-
get_segment(self, i)¶ Returns which segment the given node belongs to.
-
maxflow(self, reuse_trees=False)¶ Perform the maxflow computation in the graph. Returns the capacity of the minimum cut or, equivalently, the maximum flow of the graph.
If flag reuse_trees is true while calling maxflow(), then search trees are reused from previous maxflow computation, as described in
“Efficiently Solving Dynamic Markov Random Fields Using Graph Cuts.” Pushmeet Kohli and Philip H.S. Torr International Conference on Computer Vision (ICCV), 2005
-
maxflow.fastmin¶
fastmin provides implementations of the algorithms for
fast energy minimization described in [BOYKOV01]: the alpha-expansion
and the alpha-beta-swap.
- BOYKOV01
Fast approximate energy minimization via graph cuts. Yuri Boykov, Olga Veksler and Ramin Zabih. TPAMI 2001.
Currently, the functions in this module are restricted to grids with von Neumann neighborhood.
-
maxflow.fastmin.abswap_grid(D, V, max_cycles=None, labels=None)¶ Minimize an energy function iterating the alpha-beta-swap until convergence or until a maximum number of cycles, given by
max_cycles, is reached.Dmust be a N+1-dimensional array with shape (S1,…,SN,L), where L is the number of labels considered. D[p1,…,pn,lbl] is the unary cost of assigning the label lbl to the variable (p1,…,pn).Vis a two-dimensional array. V[lbl1,lbl2] is the binary cost of assigning the labels lbl1 and lbl2 to a pair of neighbor variables. Note that the abswap algorithm, unlike the aexpansion, does not requireVto define a metric.The optional N-dimensional array
labelsgives the initial labeling for the algorithm. If not given, the function uses a plain initialization with all the labels set to 0.This function return the labeling reached at the end of the algorithm. If the user provides the parameter
labels, the algorithm will work modifying this array in-place.
-
maxflow.fastmin.aexpansion_grid(D, V, max_cycles=None, labels=None)¶ Minimize an energy function iterating the alpha-expansion until convergence or until a maximum number of cycles, given by
max_cycles, is reached.Dmust be an N+1-dimensional array with shape (S1,…,SN,L), where L is the number of labels considered. D[p1,…,pn,lbl] is the unary cost of assigning the label lbl to the variable (p1,…,pn).Vis a two-dimensional array. V[lbl1,lbl2] is the binary cost of assigning the labels lbl1 and lbl2 to a pair of neighbor variables. Note that the distance defined byVmust be a metric or the aexpansion might fail.The optional N-dimensional array
labelsgives the initial labeling of the algorithm. If not given, the function uses a plain initialization with all the labels set to 0.This function return the labeling reached at the end of the algorithm. If the user provides the parameter
labels, the algorithm will work modifying this array in-place.
-
maxflow.fastmin.energy_of_grid_labeling(D, V, labels)¶ Returns the energy of the labeling of a grid.
For details about
D,Vandlabels, see the documentation ofaexpansion_grid.Returns the energy of the labeling.