lukes_partitioning(G, max_size, node_weight=None, edge_weight=None)
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].
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.
If G is not a tree.
If any of the values of node_weight is not int.
A list of sets of nodes representing the clusters of the partition.
Optimal partitioning of a weighted tree using the Lukes algorithm.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them