Classes representing cuts and flows on graphs.
Function | _all |
Returns all the cuts between the source and target vertices in a directed graph. |
Function | _all |
Returns all the mincuts between the source and target vertices in a directed graph. |
Function | _gomory |
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 |
Calculates the minimum cut between the source and target vertices in a graph. |
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. |
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. |
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. |
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 |
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 |
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 |