python-igraph API reference

List of all classes, functions and methods in python-igraph

module documentation

Classes representing cuts and flows on graphs.

Class Cut A cut of a given graph.
Class Flow A flow of a given graph.
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):

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.

ParametersgraphUndocumented
sourcethe source vertex ID
targetthe target vertex ID
Returnsa list of Cut objects.
Unknown Field: newfieldrefReference
Unknown Field: refJS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351--372, 1996.
def _all_st_mincuts(graph, source, target, capacity=None):

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.

ParametersgraphUndocumented
sourcethe source vertex ID
targetthe target vertex ID
capacitythe edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returnsa list of Cut objects.
Unknown Field: newfieldrefReference
Unknown Field: refJS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351--372, 1996.
def _gomory_hu_tree(graph, capacity=None, flow='flow'):

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.

ParametersgraphUndocumented
capacitythe edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
flowthe name of the edge attribute in the returned graph in which the flow values will be stored.
Returnsthe Gomory-Hu tree as a Graph object.
def _maxflow(graph, source, target, capacity=None):

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.

ParametersgraphUndocumented
sourceUndocumented
targetUndocumented
capacitythe edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returnsa Flow object describing the maximum flow
def _mincut(graph, source=None, target=None, capacity=None):

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.

ParametersgraphUndocumented
sourcethe 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).
targetthe 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).
capacitythe edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returnsa Cut object describing the minimum cut
def _st_mincut(graph, source, target, capacity=None):

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

ParametersgraphUndocumented
sourcethe source vertex ID
targetthe target vertex ID
capacitythe 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.
Returnsthe 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
API Documentation for igraph, generated by pydoctor 21.2.2.