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)
>>> g.add_nodes(2)
0
>>> g.add_edge(0, 1, 1, 2)
>>> g.add_tedge(0, 2, 5)
>>> g.add_tedge(1, 9, 4)
>>> g.maxflow()
8
>>> g.get_segments()
array([ True, False], dtype=bool)

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 with which they work. Therefore, we only include here the documentation of one of them. You can access these classes using the dictionary maxflow.Graph: maxflow.Graph[int] and maxflow.Graph[float].

class maxflow.GraphInt
__init__

x.__init__(...) initializes x; see help(type(x)) for signature

add_edge(self, int i, int j, long capacity, long rcapacity)

Adds a bidirectional edge between nodes i and j with the weights cap and rev_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. weights is an array containing the capacities of the edges starting at every node. nodeids and weights must have the same shape or be broadcastable to the same shape.

structure indicates the neighborhood around each node. For every node the structure array 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 of structure. The capacities of these added edges is computed as the product between the weight corresponding to the central node and the value in structure.

If structure is 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, 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_nodes(self, int num_nodes)

Add non-terminal node(s) to the graph. By default, one node is added. If num_nodes>1, then num_nodes nodes 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_source and another edge ‘i->SINK’ with capacity cap_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_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 call get_segment for many nodes, but much faster.

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 weight of 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_edge and their corresponding grid equivalents, add_grid_tedges and add_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 to get_nx_graph is done before or after calling GraphInt.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, since get_nx_graph ignores 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)

Perform the maxflow computation in the graph. Returns the capacity of the minimum cut or, equivalently, the maximum flow of the graph.

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.

D must 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).

V is 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 require V to define a metric.

The optional N-dimensional array labels gives 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.

D must 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).

V is 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 by V must be a metric or the aexpansion might fail.

The optional N-dimensional array labels gives 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, V and labels, see the documentation of aexpansion_grid.

Returns the energy of the labeling.

Table Of Contents

Previous topic

Tutorial

This Page