PyMaxflow

In PyMaxflow, the source node ($s$) and sink node ($t$) are always implicitly present in the network. You cannot declare them explicitly. Instead, you work with non-terminal nodes and define their relationship to the implicit terminals using two types of edges:

1. Non-terminal edges: Connect non-terminal nodes to each other. Use add_edge to create these. These edges are created with both forward and backward capacities.
2. Terminal edges: Connect non-terminal nodes to the implicit source or sink. Use add_tedge to create these. This allows you to assign weights (penalties) for a node belonging to the source or sink partition.

When using add_edge(node_a, node_b, cap_forward, cap_backward), you define the capacity between two non-terminal nodes. When using add_tedge(node, cap_source, cap_sink), you define the connection to the implicit terminals.

import maxflow

# Create a graph with integer capacities
# (2, 2) are initial estimations for number of nodes and non-terminal edges
g = maxflow.Graph[int](2, 2)

# Add non-terminal nodes
nodes = g.add_nodes(2)

# Add non-terminal edge between node 0 and 1
# capacities: forward=1, backward=2
g.add_edge(nodes[0], nodes[1], 1, 2)

# Add terminal edges
# node 0: capacity to source=2, capacity to sink=5
g.add_tedge(nodes[0], 2, 5)

# node 1: capacity to source=9, capacity to sink=4
g.add_tedge(nodes[1], 9, 4)

# Compute maxflow
flow = g.maxflow()

# Get partition (0 for source, 1 for sink)
print(f"Segment of node 0: {g.get_segment(nodes[0])}")

For large-scale problems like image processing, using add_edge and add_tedge in a loop is extremely slow. PyMaxflow provides optimized 'grid' methods to build complex networks (like 4-connected or 8-connected grids) in a few calls:

• add_grid_nodes(shape): Adds multiple nodes and returns their indices as an n-dimensional array matching the provided shape.
• add_grid_edges(nodeids, weight): Adds edges between nodes in a grid based on a neighborhood structure. By default, it uses a 4-connected structure.
• add_grid_tedges(nodeids, source_caps, sink_caps): Sets terminal edge capacities for all nodes in the grid simultaneously using arrays for source and sink capacities.
• get_grid_segments(nodeids): Returns an array of segments with the same shape as nodeids. It is much faster than calling get_segment in a loop. It returns False for the source segment and True for the sink segment.

import maxflow
import numpy as np

# Assume 'img' is a 2D numpy array representing a binary image
# Create the graph
g = maxflow.Graph[int]()

# 1. Add nodes in a grid layout
nodeids = g.add_grid_nodes(img.shape)

# 2. Add non-terminal edges (e.g., 4-connected grid with weight 50)
g.add_grid_edges(nodeids, 50)

# 3. Add terminal edges using image data
# source_caps = img, sink_caps = 255 - img
g.add_grid_tedges(nodeids, img, 255 - img)

# 4. Compute maxflow
g.maxflow()

# 5. Get segments efficiently
sgm = g.get_grid_segments(nodeids)

# Convert boolean segments to binary image (0 and 1)
# Note: sgm is False for source (label 1) and True for sink (label 0)
img2 = np.int64(np.logical_not(sgm))

To compute a minimum cut, you define a Graph type with specific data types for nodes, edges, and capacities. You then instantiate the graph, add nodes, define terminal weights (source/sink capacities) using add_tweights, and define edges using add_edge. Finally, call maxflow() to compute the flow and use what_segment() to determine which nodes belong to the SOURCE or SINK sets.

#include <stdio.h>
#include "graph.h"

int main()
{
	typedef Graph<int,int,int> GraphType;
	GraphType *g = new GraphType(/*estimated # of nodes*/ 2, /*estimated # of edges*/ 1); 

	g -> add_node(); 
	g -> add_node(); 

	g -> add_tweights( 0,   /* capacities */  1, 5 );
	g -> add_tweights( 1,   /* capacities */  2, 6 );
	g -> add_edge( 0, 1,    /* capacities */  3, 4 );

	int flow = g -> maxflow();

	printf("Flow = %d\n", flow);
	printf("Minimum cut:\n");
	if (g->what_segment(0) == GraphType::SOURCE)
		printf("node0 is in the SOURCE set\n");
	else
		printf("node0 is in the SINK set\n");
	if (g->what_segment(1) == GraphType::SOURCE)
		printf("node1 is in the SOURCE set\n");
	else
		printf("node1 is in the SINK set\n");

	delete g;

	return 0;
}

The GraphInt and GraphFloat classes provide the following interface for building and solving maxflow problems:

Graph Construction

• __init__(): Initializes a new graph instance.
• add_nodes(n): Adds n nodes to the graph.
• add_grid_nodes(rows, cols): Adds a grid of nodes with specified dimensions.
• add_edge(u, v, capacity): Adds a directed edge from node u to node v with a given capacity.
• add_tedge(u, capacity): Adds a terminal edge (tedge) to node u with a given capacity.
• add_grid_edges(rows, cols, capacity): Adds edges between adjacent nodes in a grid.
• add_grid_tedges(rows, cols, capacity): Adds terminal edges to nodes in a grid.

Graph Inspection

• get_node_count(): Returns the total number of nodes in the graph.
• get_edge_count(): Returns the total number of edges in the graph.
• get_nx_graph(): Returns the graph representation compatible with NetworkX.

Computation and Results

• maxflow(): Computes the maximum flow / minimum cut in the graph.
• get_segment(): Retrieves the segmentation result (the min-cut partition).
• get_grid_segments(): Retrieves the segmentation result for grid-based graphs.

The add_grid_edges method allows for highly customized network topologies using a structure array.

Arguments:

• nodeids: An array of node identifiers. It can be reshaped or reorganized to create non-standard layouts. It can even contain repeated IDs to connect one node to multiple others.
• weights: An array whose shape must be broadcastable to nodeids. Every node gets an associated weight.
• structure: An array with the same number of dimensions as nodeids and an odd shape (e.g., (3, 3) for 2D). This defines the local neighborhood.

How it works: For each node in nodeids, the structure array is centered on it. Edges are created from that node to the neighbors where the structure value is non-zero. The capacity of the new edge is the product of the node's weight and the corresponding value in structure. If symmetric=True (default), a reverse edge with the same capacity is also added.