- lukes_partitioning(G, max_size: int, node_weight=None, edge_weight=None) list ¶
Optimal partitioning of a weighted tree using the Lukes algorithm.
This algorithm partitions a connected, acyclic graph featuring integer node weights and float edge weights. The resulting clusters are such that the total weight of the nodes in each cluster does not exceed max_size and that the weight of the edges that are cut by the partition is minimum. The algorithm is based on LUKES.
Maximum weight a partition can have in terms of sum of node_weight for all nodes in the partition
Edge data key to use as weight. If None, the weights are all set to one.
Node data key to use as weight. If None, the weights are all set to one. The data must be int.
A list of sets of nodes representing the clusters of the partition.
If G is not a tree.
If any of the values of node_weight is not int.