dwave_networkx.algorithms.partition.partition#

partition(G, num_partitions=2, sampler=None, **sampler_args)[source]#

Returns an approximate k-partition of G.

Defines an CQM with ground states corresponding to a balanced k-partition of G and uses the sampler to sample from it. A k-partition is a collection of k subsets of the vertices of G 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 G is a weighted graph, the sum of weights over those edges are minimized.

Parameters:

  • G (NetworkX graph) – The graph to partition.

  • num_partitions (int, optional (default 2)) – The number of subsets in the desired partition.

  • sampler – A constrained quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Model, with or without constraints. The sampler is expected to have a ‘sample_cqm’ method. A sampler is expected to return an iterable of samples, in order of increasing energy.

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

Returns:

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

Return type:

dict

Example

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

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

Notes

Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.