gatorgrouper icon indicating copy to clipboard operation
gatorgrouper copied to clipboard

Feature request: Unbalanced partitioning, allowing non-power of 2 splits

Open wmodes opened this issue 5 years ago • 2 comments

Currently using the Kernighan-Lin Grouping Method, only power of 2 group splits are supported. This is impractical for some course sizes if the goal is to create groups of a certain size. For instance, in a course size of 50, 8 groups results in very large groups of 6 members, but 16 groups results in small groups of 3.

I don't know the algorithm very well, but some hasty research revealed similar algorithms that can do unbalanced partitioning, such as shemetis (from this article)

shmetis can handle non-power of 2 partitions, by performing unbalanced bisections. That is, for a 3-way partition it computes a 2-way partition such that the first part has 2/3 of the total number of vertices, and the other part has 1/3. It then it bisects the first part into two equal-size parts, each containing 1/3 of the original number of vertices.

wmodes avatar Aug 15 '19 16:08 wmodes