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:

For each edge, the flow (i.e. the assigned number) is not more than the capacity of the edge (see the capacity argument)
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