dimod.generators.maximum_weight_independent_set#

maximum_weight_independent_set(edges: Iterable[Tuple[Hashable, Hashable]], nodes: Iterable[Tuple[Hashable, float]] | None = None, *, strength: float | None = None, strength_multiplier: float = 2) → BinaryQuadraticModel[source]#

Generate a binary quadratic model encoding a maximum-weight independent set problem.

Given a graph G, an independent set is a set of nodes such that the subgraph of G induced by these nodes contains no edges. A maximum-weight independent set is the independent set with the highest total node weight.

Parameters:

  • edges – Edges of the graph.

  • nodes – Nodes of the graph as an iterable of two-tuples, where the first element of the tuple is the node label and the second element is the node weight. Nodes not specified are given a weight of 1.

  • strength – Strength of the quadratic biases. Must be strictly greater than 1 to enforce the independent set constraint. If not given, determined by strength_multiplier.

  • strength_multiplier – Multiplies the maximum node weight to set the value of the quadratic biases.

Returns:

A binary quadratic model (BQM) with variables and interactions corresponding to nodes and edges.

Examples

>>> from dimod.generators import maximum_weight_independent_set

Generate a maximum-weight independent set BQM from a list of edges and nodes.

>>> maximum_weight_independent_set([(0, 1)], [(0, .25), (1, .5), (2, 1)])
BinaryQuadraticModel({0: -0.25, 1: -0.5, 2: -1.0}, {(1, 0): 2.0}, 0.0, 'BINARY')

Generate a maximum-weight independent set BQM from a networkx.Graph.

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edges_from([(0, 1), (1, 2)])
>>> G.add_nodes_from([0, 2], weight=.25)
>>> G.add_node(1, weight=.5)
>>> maximum_weight_independent_set(G.edges, G.nodes('weight'))
BinaryQuadraticModel({0: -0.25, 1: -0.5, 2: -0.25}, {(1, 0): 1.0, (2, 1): 1.0}, 0.0, 'BINARY')