min_S_T_cut

tangles.separations.finding.min_S_T_cut(A: csr_array, S: set | list, T: set | list)

Search a minimal weight S-T-cut in the graph with adjacency matrix A.

S and T are subsets of the graph’s vertex set. The cut separates the vertices in S from the vertices in T. Note: if S and T are not disjoint, the function will produce an error.

Parameters

Asparse.csr_array

The adjacency matrix of a graph.

Sset or list

Subset of the vertices of the graph with adjacency matrix A. The vertices are identified by the the index of the row (or equivalently column) of that vertex in A.

Tset or list

Subset of the vertices of the graph with adjacency matrix A. The vertices are identified by the the index of the row (or equivalently column) of that vertex in A.

Returns

tuple (float, np.ndarray)

The flow between S and T in the first component, a -1/1-array indicating the sides of the minimal cut between S and T in the second component.