# ``igraph`.`cut``

module documentation
(source)

Classes representing cuts and flows on graphs.

Function | `_all_st_cuts` | Returns all the cuts between the source and target vertices in a directed graph.
Function | `_all_st_mincuts` | Returns all the mincuts between the source and target vertices in a directed graph.
Function | `_gomory_hu_tree` | Calculates the Gomory-Hu tree of an undirected graph with optional edge capacities.
Function | `_maxflow` | Returns a maximum flow between the given source and target vertices in a graph.
Function | `_mincut` | Calculates the minimum cut between the given source and target vertices or within the whole graph.
Function | `_st_mincut` | Calculates the minimum cut between the source and target vertices in a graph.

def _all_st_cuts(graph, source, target): (source)

Returns all the cuts between the source and target vertices in a directed graph.

This function lists all edge-cuts between a source and a target vertex. Every cut is listed exactly once.

Reference: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351-372, 1996.

Parameters
graph | Undocumented
source | the source vertex ID
target | the target vertex ID

Returns
a list of `Cut` objects.

def _all_st_mincuts(graph, source, target, capacity=None): (source)

Returns all the mincuts between the source and target vertices in a directed graph.

This function lists all minimum edge-cuts between a source and a target vertex.

Reference: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351-372, 1996.

Parameters
graph | Undocumented
source | the source vertex ID
target | the target vertex ID
capacity | the edge capacities (weights). If `None`, all edges have equal weight. May also be an attribute name.

Returns
a list of `Cut` objects.

def _gomory_hu_tree(graph, capacity=None, flow='flow'): (source)

Calculates the Gomory-Hu tree of an undirected graph with optional edge capacities.

The Gomory-Hu tree is a concise representation of the value of all the maximum flows (or minimum cuts) in a graph. The vertices of the tree correspond exactly to the vertices of the original graph in the same order. Edges of the Gomory-Hu tree are annotated by flow values. The value of the maximum flow (or minimum cut) between an arbitrary (u,v) vertex pair in the original graph is then given by the minimum flow value (i.e. edge annotation) along the shortest path between u and v in the Gomory-Hu tree.

Parameters
graph | Undocumented
capacity | the edge capacities (weights). If `None`, all edges have equal weight. May also be an attribute name.
flow | the name of the edge attribute in the returned graph in which the flow values will be stored.

Returns
the Gomory-Hu tree as a `Graph` object.

def _maxflow(graph, source, target, capacity=None): (source)

Returns a maximum flow between the given source and target vertices in a graph.

A maximum flow from source to target is an assignment of non-negative real numbers to the edges of the graph, satisfying two properties:

1. For each edge, the flow (i.e. the assigned number) is not more than the capacity of the edge (see the capacity argument)
2. For every vertex except the source and the target, the incoming flow is the same as the outgoing flow.

The value of the flow is the incoming flow of the target or the outgoing flow of the source (which are equal). The maximum flow is the maximum possible such value.

Parameters
graph | Undocumented
source | Undocumented
target | Undocumented
capacity | the edge capacities (weights). If `None`, all edges have equal weight. May also be an attribute name.

Returns
a `Flow` object describing the maximum flow

def _mincut(graph, source=None, target=None, capacity=None): (source)

Calculates the minimum cut between the given source and target vertices or within the whole graph.

The minimum cut is the minimum set of edges that needs to be removed to separate the source and the target (if they are given) or to disconnect the graph (if neither the source nor the target are given). The minimum is calculated using the weights (capacities) of the edges, so the cut with the minimum total capacity is calculated.

For undirected graphs and no source and target, the method uses the Stoer-Wagner algorithm. For a given source and target, the method uses the push-relabel algorithm; see the references below.

Parameters
graph | Undocumented
source | the source vertex ID. If `None`, the target must also be `None` and the calculation will be done for the entire graph (i.e. all possible vertex pairs).
target | the target vertex ID. If `None`, the source must also be `None` and the calculation will be done for the entire graph (i.e. all possible vertex pairs).
capacity | the edge capacities (weights). If `None`, all edges have equal weight. May also be an attribute name.

Returns
a `Cut` object describing the minimum cut

def _st_mincut(graph, source, target, capacity=None): (source)

Calculates the minimum cut between the source and target vertices in a graph.

Parameters
graph | Undocumented
source | the source vertex ID
target | the target vertex ID
capacity | the capacity of the edges. It must be a list or a valid attribute name or `None`. In the latter case, every edge will have the same capacity.

Returns
the value of the minimum cut, the IDs of vertices in the first and second partition, and the IDs of edges in the cut, packed in a 4-tuple