networkx.algorithms.community.lukes.lukes_partitioning

lukes_partitioning(G, max_size: int, node_weight=None, edge_weight=None) → list[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

  • G (graph)

  • max_size (int) – Maximum weight a partition can have in terms of sum of node_weight for all nodes in the partition

  • edge_weight (key) – Edge data key to use as weight. If None, the weights are all set to one.

  • node_weight (key) – Node data key to use as weight. If None, the weights are all set to one. The data must be int.

Returns

partition – A list of sets of nodes representing the clusters of the partition.

Return type

list

Raises

  • NotATree – If G is not a tree.

  • TypeError – If any of the values of node_weight is not int.

References