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.

Parameters | graph | Undocumented |

source | the source vertex ID | |

target | the target vertex ID | |

Returns | a list of `Cut` objects. | |

Unknown Field: newfield | ref | Reference |

Unknown Field: ref | JS 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.

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. | |

Unknown Field: newfield | ref | Reference |

Unknown Field: ref | JS 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.

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):

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):

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):

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 |