# Source code for dwave_networkx.algorithms.max_cut

from dwave_networkx.exceptions import DWaveNetworkXException

__all__ = ["maximum_cut", "weighted_maximum_cut"]

def maximum_cut(G, sampler=None, **sampler_args):
"""Returns an approximate maximum cut.

Defines an Ising problem with ground states corresponding to
a maximum cut and uses the sampler to sample from it.

A maximum cut is a subset S of the vertices of G such that
the number of edges between S and the complementary subset
is as large as possible.

Parameters
----------
G : NetworkX graph
The graph on which to find a maximum cut.

sampler
A binary quadratic model sampler. A sampler is a process that
samples from low energy states in models defined by an Ising
equation or a Quadratic Unconstrained Binary Optimization
Problem (QUBO). A sampler is expected to have a 'sample_qubo'
and 'sample_ising' method. A sampler is expected to return an
iterable of samples, in order of increasing energy. If no
sampler is provided, one must be provided using the
set_default_sampler function.

sampler_args
Additional keyword parameters are passed to the sampler.

Returns
-------
S : set
A maximum cut of G.

Example
-------
This example uses a sampler from
dimod <https://github.com/dwavesystems/dimod>_ to find a maximum cut
for a graph of a Chimera unit cell created using the chimera_graph()
function.

>>> import dimod
...
>>> sampler = dimod.SimulatedAnnealingSampler()
>>> G = dnx.chimera_graph(1, 1, 4)
>>> cut = dnx.maximum_cut(G, 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.

"""
# In order to form the Ising problem, we want to increase the
# energy by 1 for each edge between two nodes of the same color.
# The linear biases can all be 0.
h = {v: 0. for v in G}
J = {(u, v): 1 for u, v in G.edges}

# draw the lowest energy sample from the sampler
response = sampler.sample_ising(h, J, **sampler_args)
sample = next(iter(response))

return set(v for v in G if sample[v] >= 0)

[docs]def weighted_maximum_cut(G, sampler=None, **sampler_args):
"""Returns an approximate weighted maximum cut.

Defines an Ising problem with ground states corresponding to
a weighted maximum cut and uses the sampler to sample from it.

A weighted maximum cut is a subset S of the vertices of G that
maximizes the sum of the edge weights between S and its
complementary subset.

Parameters
----------
G : NetworkX graph
The graph on which to find a weighted maximum cut. Each edge in G should
have a numeric weight attribute.

sampler
A binary quadratic model sampler. A sampler is a process that
samples from low energy states in models defined by an Ising
equation or a Quadratic Unconstrained Binary Optimization
Problem (QUBO). A sampler is expected to have a 'sample_qubo'
and 'sample_ising' method. A sampler is expected to return an
iterable of samples, in order of increasing energy. If no
sampler is provided, one must be provided using the
set_default_sampler function.

sampler_args
Additional keyword parameters are passed to the sampler.

Returns
-------
S : set
A maximum cut of G.

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

"""
# In order to form the Ising problem, we want to increase the
# energy by 1 for each edge between two nodes of the same color.
# The linear biases can all be 0.
h = {v: 0. for v in G}
try:
J = {(u, v): G[u][v]['weight'] for u, v in G.edges}
except KeyError:
raise DWaveNetworkXException("edges must have 'weight' attribute")

# draw the lowest energy sample from the sampler
response = sampler.sample_ising(h, J, **sampler_args)
sample = next(iter(response))

return set(v for v in G if sample[v] >= 0)