lukes_partitioning#
- lukes_partitioning(G, max_size, node_weight=None, edge_weight=None)[source]#
使用 Lukes 算法对加权树进行最优划分。
该算法对具有整数节点权重和浮点边权重的连通无环图进行划分。生成的簇使得每个簇中节点的总权重不超过 max_size，并且划分所切断的边的权重最小。该算法基于 [1]。
- 参数:
- GNetworkX 图
- max_sizeint
划分中所有节点的 node_weight 之和的最大权重
- edge_weightkey
用作权重的边数据键。如果为 None，则所有权重都设置为 1。
- node_weightkey
用作权重的节点数据键。如果为 None，则所有权重都设置为 1。数据必须为 int 类型。
- 返回:
- partitionlist
一个由节点集合组成的列表，表示划分的簇。
- 引发:
- NotATree
如果 G 不是树。
- TypeError
如果 node_weight 的任何值不是 int 类型。
参考文献
[1]Lukes, J. A. (1974). “Efficient Algorithm for the Partitioning of Trees.” IBM Journal of Research and Development, 18(3), 217–224.