lukes_partitioning

lukes_partitioning(G, max_size, node_weight=None, edge_weight=None)

使用Lukes算法对加权树进行最优划分。

该算法对具有整数节点权重和浮点边权重的连通无环图进行划分。生成的簇使得每个簇中节点的总权重不超过max_size，并且被划分切割的边的权重最小。该算法基于[1]。

Parameters:

GNetworkX图

max_sizeint

分区中节点的总权重不超过的最大值，即分区中所有节点的node_weight之和

edge_weightkey

用作边权重的边数据键。如果为None，则所有边的权重都设为1。

node_weightkey

用作节点权重的节点数据键。如果为None，则所有节点的权重都设为1。数据必须是int类型。

Returns:

partitionlist

表示分区簇的节点集合列表。

Raises:

NotATree

如果G不是树。

TypeError

如果node_weight的任何值不是int类型。

References

[1]

Lukes, J. A. (1974). “Efficient Algorithm for the Partitioning of Trees.” IBM Journal of Research and Development, 18(3), 217–224.