lukes_partitioning#

lukes_partitioning(G, max_size, node_weight=None, edge_weight=None)[源代码]#

基于Lukes算法的加权树的最优划分。

该算法划分了一个具有整数节点权值和浮边权值的连通非循环图。生成的簇使得每个簇中节点的总权重不超过max_size,并且被分区切割的边的权重最小。该算法基于LUKES [1] .

参数
G图表
max_size集成

分区可以具有的最大权重,以分区中所有节点的node_weight之和表示

edge_weight钥匙

要用作权重的边数据关键点。如果没有,则所有权重都设置为1。

node_weight钥匙

要用作权重的节点数据键。如果没有,则所有权重都设置为1。数据必须为int。

返回
partition列表

表示分区的集群的节点集列表。

加薪
NotATree

如果G不是树。

TypeError

如果节点权重的任何值不是int。

工具书类