lukes_partitioning#
- lukes_partitioning(G, max_size, node_weight=None, edge_weight=None)[source]#
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[1].
- Parameters:
- Ggraph
- max_sizeint
Maximum weight a partition can have in terms of sum of node_weight for all nodes in the partition
- edge_weightkey
Edge data key to use as weight. If None, the weights are all set to one.
- node_weightkey
Node data key to use as weight. If None, the weights are all set to one. The data must be int.
- Returns:
- partitionlist
A list of sets of nodes representing the clusters of the partition.
- Raises:
- NotATree
If G is not a tree.
- TypeError
If any of the values of node_weight is not int.
References