# 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.
#
# ================================================================================================
import itertools
from dwave_networkx.utils import binary_quadratic_model_sampler
from dwave_networkx import _PY2
__all__ = ['min_maximal_matching', 'is_matching', 'is_maximal_matching']
# compatibility for python 2/3
if _PY2:
range = xrange
def iteritems(d): return d.iteritems()
def itervalues(d): return d.itervalues()
else:
def iteritems(d): return d.items()
def itervalues(d): return d.values()
@binary_quadratic_model_sampler(1)
def maximal_matching(G, sampler=None, **sampler_args):
"""Finds an approximate maximal matching.
Defines a QUBO with ground states corresponding to a maximal
matching and uses the sampler to sample from it.
A matching is a subset of edges in which no node occurs more than
once. A maximal matching is one in which no edges from G can be
added without violating the matching rule.
Parameters
----------
G : NetworkX graph
The graph on which to find a maximal matching.
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
-------
matching : set
A maximal matching of the graph.
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
----------
`Matching on Wikipedia <https://en.wikipedia.org/wiki/Matching_(graph_theory)>`_
`QUBO on Wikipedia <https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization>`_
Based on the formulation presented in [AL]_
"""
# the maximum degree
delta = max(G.degree(node) for node in G)
# use the maximum degree to determine the infeasible gaps
A = 1.
if delta == 2:
B = .75
else:
B = .75 * A / (delta - 2.) # we want A > (delta - 2) * B
# each edge in G gets a variable, so let's create those
edge_mapping = _edge_mapping(G)
# build the QUBO
Q = _maximal_matching_qubo(G, edge_mapping, magnitude=B)
Qm = _matching_qubo(G, edge_mapping, magnitude=A)
for edge, bias in Qm.items():
if edge not in Q:
Q[edge] = bias
else:
Q[edge] += bias
# 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))
# the matching are the edges that are 1 in the sample
return set(edge for edge in G.edges if sample[edge_mapping[edge]] > 0)
[docs]@binary_quadratic_model_sampler(1)
def min_maximal_matching(G, sampler=None, **sampler_args):
"""Returns an approximate minimum maximal matching.
Defines a QUBO with ground states corresponding to a minimum
maximal matching and uses the sampler to sample from it.
A matching is a subset of edges in which no node occurs more than
once. A maximal matching is one in which no edges from G can be
added without violating the matching rule. A minimum maximal
matching is the smallest maximal matching for G.
Parameters
----------
G : NetworkX graph
The graph on which to find a minimum maximal matching.
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
-------
matching : set
A minimum maximal matching of the graph.
Example
-------
This example uses a sampler from
`dimod <https://github.com/dwavesystems/dimod>`_ to find a minimum maximal
matching for a Chimera unit cell.
>>> import dimod
>>> sampler = dimod.ExactSolver()
>>> G = dnx.chimera_graph(1, 1, 4)
>>> matching = dnx.min_maximal_matching(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
----------
`Matching on Wikipedia <https://en.wikipedia.org/wiki/Matching_(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.
"""
# the maximum degree
delta = max(G.degree(node) for node in G)
# use the maximum degree to determine the infeasible gaps
A = 1.
if delta == 2:
B = .75
else:
B = .75 * A / (delta - 2.) # we want A > (delta - 2) * B
C = .75 * B # we want B > C
# each edge in G gets a variable, so let's create those
edge_mapping = _edge_mapping(G)
# build the QUBO
Q = _maximal_matching_qubo(G, edge_mapping, magnitude=B)
Qm = _matching_qubo(G, edge_mapping, magnitude=A)
for edge, bias in Qm.items():
if edge not in Q:
Q[edge] = bias
else:
Q[edge] += bias
# to enforce the minimal constraint, we additionally add a small bias to
# each variable
for v in set(edge_mapping.values()):
if (v, v) not in Q:
Q[(v, v)] = C
else:
Q[(v, v)] += C
# 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))
# the matching are the edges that are 1 in the sample
return set(edge for edge in G.edges if sample[edge_mapping[edge]] > 0)
[docs]def is_matching(edges):
"""Determines whether the given set of edges is a matching.
A matching is a subset of edges in which no node occurs more than
once.
Parameters
----------
edges : iterable
A iterable of edges.
Returns
-------
is_matching : bool
True if the given edges are a matching.
Example
-------
This example checks two sets of edges, both derived from a
single Chimera unit cell, for a matching. Because every node in a Chimera
unit cell connects to four other nodes in the cell, the first set, which
contains all the edges, repeats each node 4 times; the second is a subset
of those edges found using the `min_maximal_matching()` function.
>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> dnx.is_matching(G.edges())
False
>>> dnx.is_matching({(0, 4), (1, 5), (2, 7), (3, 6)})
True
"""
return len(set().union(*edges)) == len(edges) * 2
[docs]def is_maximal_matching(G, matching):
"""Determines whether the given set of edges is a maximal matching.
A matching is a subset of edges in which no node occurs more than
once. The cardinality of a matching is the number of matched edges.
A maximal matching is one where one cannot add any more edges
without violating the matching rule.
Parameters
----------
G : NetworkX graph
The graph on which to check the maximal matching.
edges : iterable
A iterable of edges.
Returns
-------
is_matching : bool
True if the given edges are a maximal matching.
Example
-------
This example checks two sets of edges, both derived from a
single Chimera unit cell, for a matching. The first set (a matching) is
a subset of the second, which was found using the `min_maximal_matching()`
function.
>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> dnx.is_matching({(0, 4), (2, 7)})
True
>>> dnx.is_maximal_matching(G,{(0, 4), (2, 7)})
False
>>> dnx.is_maximal_matching(G,{(0, 4), (1, 5), (2, 7), (3, 6)})
True
"""
touched_nodes = set().union(*matching)
# first check if a matching
if len(touched_nodes) != len(matching) * 2:
return False
# now for each edge, check that at least one of its variables is
# already in the matching
for (u, v) in G.edges:
if u not in touched_nodes and v not in touched_nodes:
return False
return True
def _edge_mapping(G):
"""Assigns a variable for each edge in G.
(u, v) and (v, u) map to the same variable.
"""
edge_mapping = {edge: idx for idx, edge in enumerate(G.edges)}
edge_mapping.update({(e1, e0): idx for (e0, e1), idx in edge_mapping.items()})
return edge_mapping
def _maximal_matching_qubo(G, edge_mapping, magnitude=1.):
"""Generates a QUBO that when combined with one as generated by _matching_qubo,
induces a maximal matching on the given graph G.
The variables in the QUBO are the edges, as given my edge_mapping.
ground_energy = -1 * magnitude * |edges|
infeasible_gap >= magnitude
"""
Q = {}
# for each node n in G, define a variable y_n to be 1 when n has a colored edge
# and 0 otherwise.
# for each edge (u, v) in the graph we want to enforce y_u OR y_v. This is because
# if both y_u == 0 and y_v == 0, then we could add (u, v) to the matching.
for (u, v) in G.edges:
# 1 - y_v - y_u + y_v*y_u
# for each edge connected to u
for edge in G.edges(u):
x = edge_mapping[edge]
if (x, x) not in Q:
Q[(x, x)] = -1 * magnitude
else:
Q[(x, x)] -= magnitude
# for each edge connected to v
for edge in G.edges(v):
x = edge_mapping[edge]
if (x, x) not in Q:
Q[(x, x)] = -1 * magnitude
else:
Q[(x, x)] -= magnitude
for e0 in G.edges(v):
x0 = edge_mapping[e0]
for e1 in G.edges(u):
x1 = edge_mapping[e1]
if x0 < x1:
if (x0, x1) not in Q:
Q[(x0, x1)] = magnitude
else:
Q[(x0, x1)] += magnitude
else:
if (x1, x0) not in Q:
Q[(x1, x0)] = magnitude
else:
Q[(x1, x0)] += magnitude
return Q
def _matching_qubo(G, edge_mapping, magnitude=1.):
"""Generates a QUBO that induces a matching on the given graph G.
The variables in the QUBO are the edges, as given my edge_mapping.
ground_energy = 0
infeasible_gap = magnitude
"""
Q = {}
# We wish to enforce the behavior that no node has two colored edges
for node in G:
# for each pair of edges that contain node
for edge0, edge1 in itertools.combinations(G.edges(node), 2):
v0 = edge_mapping[edge0]
v1 = edge_mapping[edge1]
# penalize both being True
Q[(v0, v1)] = magnitude
return Q