one_exchange#
- one_exchange(G, initial_cut=None, seed=None, weight=None)[源代码]#
计算图节点的划分和相应的割值。
使用贪婪的一交换策略来找到局部最大割及其值，它通过找到对当前割贡献最大（即产生最高增益）的节点加入割，并重复此过程直到无法改进为止。
- 参数:
- Gnetworkx 图
用于寻找最大割的图。
- initial_cut集合
用作起点的割。如果未提供，算法将从空割开始。
- seed整数、random_state 或 None (默认)
随机数生成状态的指示器。参见 随机性。
- weight对象
用作权重的边属性键。如果未指定，边的权重为一。
- 返回:
- cut_value标量
最大割的值。
- partition节点集对
定义最大割的节点划分。
- 引发:
- NetworkXNotImplemented
如果图是有向图或多重图。
示例
>>> G = nx.complete_graph(5) >>> curr_cut_size, partition = nx.approximation.one_exchange(G, seed=1) >>> curr_cut_size 6 >>> partition ({0, 2}, {1, 3, 4})