dimod.generators.graph_partition

graph_partition(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, num_partitions: int) → ConstrainedQuadraticModel

Find a constrained quadratic model for the graph’s partitions.

Defines a CQM with ground states corresponding to a balanced k-partition of graph. A k-partition is a collection of k subsets of the vertices of graph such that each vertex is in exactly one subset, and the number of edges between vertices in different subsets is as small as possible. If graph is a weighted graph, the sum of weights over those edges are minimized.

Parameters:

• graph – The graph to partition. Either an integer n, interpreted as a complete graph of size n, a nodes/edges pair, a list of edges or a NetworkX graph. When NetworkX graph is provided, optional edge weights can be provided in the weight attribute.

• num_partitions – The number of subsets in the desired partition.

Returns:

A constrained quadratic model with ground states corresponding to a partition problem. The nodes of graph are discrete logical variables of the CQM, where the cases are the different partitions the node can be assigned to. The objective is given as the number of edges connecting nodes in different partitions.