igraph.cut

模块文档
（源代码）

表示图上的割和流的类。

函数 _all_st_cuts 返回有向图中源顶点和目标顶点之间的所有切割。
函数 _all_st_mincuts 返回有向图中源顶点和目标顶点之间的所有最小割。
函数 _gomory_hu_tree 计算无向图的 Gomory-Hu 树，可选择带有边容量。
函数 _maxflow 返回图中给定源顶点和目标顶点之间的最大流。
函数 _mincut 计算给定源顶点和目标顶点之间或整个图中的最小割。
函数 _st_mincut 计算图中源顶点和目标顶点之间的最小切割。
def _all_st_cuts(graph, source, target): (source)

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

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

参考: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351-372, 1996.

参数
graph未文档化
source源顶点 ID
target目标顶点 ID
返回
Cut 对象的列表。
def _all_st_mincuts(graph, source, target, capacity=None): (source)

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

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

参考: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351-372, 1996.

参数
graph未文档化
source源顶点 ID
target目标顶点 ID
capacity边容量（权重）。如果None，所有边权重相等。也可以是属性名。
返回
Cut 对象的列表。
def _gomory_hu_tree(graph, capacity=None, flow='flow'): (source)

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

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

参数
graph未文档化
capacity边容量（权重）。如果None，所有边权重相等。也可以是属性名。
flow返回图中用于存储流值的边属性的名称。
返回
Gomory-Hu 树，一个 Graph 对象。
def _maxflow(graph, source, target, capacity=None): (source)

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

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

  1. 对于每条边，流（即分配的数值）不大于边的容量（参见 capacity 参数）
  2. 对于除源顶点和目标顶点之外的每个顶点，入流与出流相等。

流的值是目标顶点的入流或源顶点的出流（两者相等）。最大流是可能的最大值。

参数
graph未文档化
source未文档化
target未文档化
capacity边容量（权重）。如果None，所有边权重相等。也可以是属性名。
返回
一个 Flow 对象，描述最大流。
def _mincut(graph, source=None, target=None, capacity=None): (source)

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

最小割是指需要移除的最小边集，以分离源顶点和目标顶点（如果给出）或断开图（如果源顶点和目标顶点均未给出）。最小割是使用边的权重（容量）计算的，因此计算的是总容量最小的割。

对于无向图且未指定源顶点和目标顶点的情况，该方法使用 Stoer-Wagner 算法。对于给定源顶点和目标顶点的情况，该方法使用 push-relabel 算法；请参阅下面的参考资料。

参数
graph未文档化
source源顶点ID。如果None，目标也必须是None，并且计算将针对整个图进行（即所有可能的顶点对）。
target目标顶点ID。如果None，源也必须是None，并且计算将针对整个图进行（即所有可能的顶点对）。
capacity边容量（权重）。如果None，所有边权重相等。也可以是属性名。
返回
一个 Cut 对象，描述最小割。
def _st_mincut(graph, source, target, capacity=None): (source)

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

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