igraph.cut

module documentation

表示图上切割和流的类。

函数	`_all_st_cuts`	返回有向图中源顶点和目标顶点之间的所有切割。
函数	`_all_st_mincuts`	返回有向图中源顶点和目标顶点之间的所有最小割。
函数	`_gomory_hu_tree`	计算具有可选边容量的无向图的Gomory-Hu树。
函数	`_maxflow`	返回图中给定源顶点和目标顶点之间的最大流。
函数	`_mincut`	计算给定源顶点和目标顶点之间的最小割或整个图中的最小割。
函数	`_st_mincut`	计算图中源顶点和目标顶点之间的最小割。

返回有向图中源顶点和目标顶点之间的所有切割。

此函数列出源顶点和目标顶点之间的所有边割。每个割仅列出一次。

参考文献: JS Provan 和 DR Shier: 一种列出图中(s,t)-割的范式。 算法学 15, 351-372, 1996.

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

返回有向图中源顶点和目标顶点之间的所有最小割。

此函数列出源顶点和目标顶点之间的所有最小边割。

参考文献: JS Provan 和 DR Shier: 图中列出(s,t)-割的范例. 算法学 15, 351-372, 1996.

参数
graph	未记录
source	源顶点ID
target	目标顶点ID
capacity	边的容量（权重）。如果为`None`，则所有边的权重相等。也可以是属性名称。
返回
一个`Cut`对象的列表。

计算具有可选边容量的无向图的Gomory-Hu树。

Gomory-Hu树是图中所有最大流（或最小割）值的简洁表示。树的顶点与原始图的顶点完全对应，顺序相同。Gomory-Hu树的边由流值标注。原始图中任意(u,v)顶点对之间的最大流（或最小割）值由Gomory-Hu树中u和v之间最短路径上的最小流值（即边标注）给出。

参数
graph	未记录
capacity	边的容量（权重）。如果 `None`，所有边的权重相等。也可以是属性名称。
flow	返回的图中存储流值的边属性的名称。
返回
Gomory-Hu 树作为一个 `Graph` 对象。

返回图中给定源顶点和目标顶点之间的最大流。

从源到目标的最大流是对图的边分配非负实数，满足两个属性：

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.

流量的值是目标的流入流量或源的流出流量（它们是相等的）。最大流量是可能的最大值。

参数
graph	未记录
source	未记录
target	未记录
capacity	边的容量（权重）。如果为`None`，则所有边的权重相等。也可以是属性名称。
返回
一个 `Flow` 对象，描述最大流

计算给定源顶点和目标顶点之间或整个图中的最小割。

最小割是需要移除的最小边集，以分离源和目标（如果它们被给出）或断开图的连接（如果既没有源也没有目标被给出）。最小割是使用边的权重（容量）计算的，因此计算的是具有最小总容量的割。

对于无向图且没有源和目标的情况，该方法使用Stoer-Wagner算法。对于给定的源和目标，该方法使用推流-重标算法；请参阅下面的参考文献。

参数
graph	未记录
source	源顶点ID。如果为`None`，则目标也必须为`None`，并且计算将针对整个图进行（即所有可能的顶点对）。
target	目标顶点ID。如果为`None`，则源也必须为`None`，并且计算将针对整个图进行（即所有可能的顶点对）。
capacity	边的容量（权重）。如果为`None`，则所有边的权重相等。也可以是属性名称。
返回
一个 `Cut` 对象，描述最小割

计算图中源顶点和目标顶点之间的最小割。

参数
graph	未记录
source	源顶点ID
target	目标顶点ID
capacity	边的容量。它必须是一个列表或有效的属性名称或`None`。在后一种情况下，每条边将具有相同的容量。
返回
最小割的值，第一个和第二个分区中的顶点ID，以及割中的边ID，打包在一个4元组中