# Copyright 2018 D-Wave Systems Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
# ================================================================================================
from __future__ import division
from dwave_networkx.utils import binary_quadratic_model_sampler
__all__ = ["maximum_weighted_independent_set", "maximum_independent_set", "is_independent_set"]
[docs]@binary_quadratic_model_sampler(2)
def maximum_weighted_independent_set(G, weight=None, sampler=None, lagrange=2.0, **sampler_args):
"""Returns an approximate maximum weighted independent set.
Defines a QUBO with ground states corresponding to a
maximum weighted independent set and uses the sampler to sample
from it.
An independent set is a set of nodes such that the subgraph
of G induced by these nodes contains no edges. A maximum
independent set is an independent set of maximum total node weight.
Parameters
----------
G : NetworkX graph
The graph on which to find a maximum cut weighted independent set.
weight : string, optional (default None)
If None, every node has equal weight. If a string, use this node
attribute as the node weight. A node without this attribute is
assumed to have max weight.
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.
lagrange : optional (default 2)
Lagrange parameter to weight constraints (no edges within set)
versus objective (largest set possible).
sampler_args
Additional keyword parameters are passed to the sampler.
Returns
-------
indep_nodes : list
List of nodes that form a maximum weighted independent set, as
determined by the given 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.
References
----------
`Independent Set on Wikipedia <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
`QUBO on Wikipedia <https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization>`_
.. [AL] Lucas, A. (2014). Ising formulations of many NP problems.
Frontiers in Physics, Volume 2, Article 5.
"""
# Get a QUBO representation of the problem
Q = maximum_weighted_independent_set_qubo(G, weight, lagrange)
# use the sampler to find low energy states
response = sampler.sample_qubo(Q, **sampler_args)
# we want the lowest energy sample
sample = next(iter(response))
# nodes that are spin up or true are exactly the ones in S.
return [node for node in sample if sample[node] > 0]
[docs]@binary_quadratic_model_sampler(1)
def maximum_independent_set(G, sampler=None, lagrange=2.0, **sampler_args):
"""Returns an approximate maximum independent set.
Defines a QUBO with ground states corresponding to a
maximum independent set and uses the sampler to sample from
it.
An independent set is a set of nodes such that the subgraph
of G induced by these nodes contains no edges. A maximum
independent set is an independent set of largest possible size.
Parameters
----------
G : NetworkX graph
The graph on which to find a maximum cut independent set.
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.
lagrange : optional (default 2)
Lagrange parameter to weight constraints (no edges within set)
versus objective (largest set possible).
sampler_args
Additional keyword parameters are passed to the sampler.
Returns
-------
indep_nodes : list
List of nodes that form a maximum independent set, as
determined by the given sampler.
Example
-------
This example uses a sampler from
`dimod <https://github.com/dwavesystems/dimod>`_ to find a maximum
independent set 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)
>>> indep_nodes = dnx.maximum_independent_set(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.
References
----------
`Independent Set on Wikipedia <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
`QUBO on Wikipedia <https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization>`_
.. [AL] Lucas, A. (2014). Ising formulations of many NP problems.
Frontiers in Physics, Volume 2, Article 5.
"""
return maximum_weighted_independent_set(G, None, sampler, lagrange, **sampler_args)
[docs]def is_independent_set(G, indep_nodes):
"""Determines whether the given nodes form an independent set.
An independent set is a set of nodes such that the subgraph
of G induced by these nodes contains no edges.
Parameters
----------
G : NetworkX graph
The graph on which to check the independent set.
indep_nodes : list
List of nodes that form a maximum independent set, as
determined by the given sampler.
Returns
-------
is_independent : bool
True if indep_nodes form an independent set.
Example
-------
This example checks two sets of nodes, both derived from a
single Chimera unit cell, for an independent set. The first set is
the horizontal tile's nodes; the second has nodes from the horizontal and
verical tiles.
>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> dnx.is_independent_set(G, [0, 1, 2, 3])
True
>>> dnx.is_independent_set(G, [0, 4])
False
"""
return len(G.subgraph(indep_nodes).edges) == 0
[docs]def maximum_weighted_independent_set_qubo(G, weight=None, lagrange=2.0):
"""Return the QUBO with ground states corresponding to a maximum weighted independent set.
Parameters
----------
G : NetworkX graph
weight : string, optional (default None)
If None, every node has equal weight. If a string, use this node
attribute as the node weight. A node without this attribute is
assumed to have max weight.
lagrange : optional (default 2)
Lagrange parameter to weight constraints (no edges within set)
versus objective (largest set possible).
Returns
-------
QUBO : dict
The QUBO with ground states corresponding to a maximum weighted independent set.
Examples
--------
>>> from dwave_networkx.algorithms.independent_set import maximum_weighted_independent_set_qubo
...
>>> G = nx.path_graph(3)
>>> Q = maximum_weighted_independent_set_qubo(G, weight='weight', lagrange=2.0)
>>> Q[(0, 0)]
-1.0
>>> Q[(1, 1)]
-1.0
>>> Q[(0, 1)]
2.0
"""
# empty QUBO for an empty graph
if not G:
return {}
# We assume that the sampler can handle an unstructured QUBO problem, so let's set one up.
# Let us define the largest independent set to be S.
# For each node n in the graph, we assign a boolean variable v_n, where v_n = 1 when n
# is in S and v_n = 0 otherwise.
# We call the matrix defining our QUBO problem Q.
# On the diagnonal, we assign the linear bias for each node to be the negative of its weight.
# This means that each node is biased towards being in S. Weights are scaled to a maximum of 1.
# Negative weights are considered 0.
# On the off diagnonal, we assign the off-diagonal terms of Q to be 2. Thus, if both
# nodes are in S, the overall energy is increased by 2.
cost = dict(G.nodes(data=weight, default=1))
scale = max(cost.values())
Q = {(node, node): min(-cost[node] / scale, 0.0) for node in G}
Q.update({edge: lagrange for edge in G.edges})
return Q