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:
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.