2.3. igraph_mincut — Calculates the minimum cut in a graph.

2.3. `igraph_mincut` — Calculates the minimum cut in a graph.

int igraph_mincut(const igraph_t *graph,
		  igraph_real_t *value,
		  igraph_vector_t *partition,
		  igraph_vector_t *partition2,
		  igraph_vector_t *cut,
		  const igraph_vector_t *capacity);

This function calculates the minimum cut in a graph. Right now it is implemented only for undirected graphs, in which case it uses the Stoer-Wagner algorithm, as described in M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.

The minimum cut is the mimimum set of edges which needs to be removed to disconnect the graph. The minimum is calculated using the weigths (capacity) of the edges, so the cut with the minimum total capacity is calculated.

The first implementation of the actual cut calculation was made by Gregory Benison, thanks Greg.

Arguments:

`graph`:	The input graph.
`value`:	Pointer to an integer, the value of the cut will be stored here.
`partition`:	Pointer to an initialized vector, the ids of the vertices in the first partition after separating the graph will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer.
`partition2`:	Pointer to an initialized vector the ids of the vertices in the second partition will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer.
`cut`:	Pointer to an initialized vector, the ids of the edges in the cut will be stored here. This argument is ignored if it is a NULL pointer.
`capacity`:	A numeric vector giving the capacities of the edges. If a null pointer then all edges have unit capacity.

Returns:

Error code.

See also:

igraph_mincut_value(), a simpler interface for calculating the value of the cut only.

Time complexity: for undirected graphs it is O(|V|E|+|V|^2 log|V|), |V| and |E| are the number of vertices and edges respectively.