dwave.graphs.algorithms.partition.partition#

partition(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, sampler: Sampler, num_partitions: int = 2, **sampler_args) → Mapping[Hashable, int][source]#

Return an approximate k-partition of graph.

Defines a CQM with ground states corresponding to a balanced k-partition of graph and uses the sampler to sample from it. 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.

  • sampler – A dimod sampler.

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

  • **sampler_args – Additional keyword parameters are passed to the sampler.

Returns:

The partition as a dictionary mapping each node to subsets labelled as integers 0, 1, 2, … num_partitions.

Example

This example uses a dimod reference sampler ExactCQMSolver to find a 2-partition for a graph of a Chimera unit cell created using the chimera_graph() function.

>>> import dimod
>>> import dwave.graphs
...
>>> sampler = dimod.ExactCQMSolver()
>>> G = dwave.graphs.chimera_graph(1, 1, 4)
>>> partitions = dwave.graphs.partition(G, sampler=sampler)