Source code for qiskit_optimization.applications.max_cut

# This code is part of a Qiskit project.
# (C) Copyright IBM 2018, 2023.
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""An application class for the Max-cut."""

from typing import List, Dict, Optional, Union
import networkx as nx
import numpy as np
from import Model

from qiskit_optimization.algorithms import OptimizationResult
from qiskit_optimization.problems.quadratic_program import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp
from .graph_optimization_application import GraphOptimizationApplication

[docs]class Maxcut(GraphOptimizationApplication): """Optimization application for the "max-cut" [1] problem based on a NetworkX graph. References: [1]: "Maximum cut", """
[docs] def to_quadratic_program(self) -> QuadraticProgram: """Convert a Max-cut problem instance into a :class:`~qiskit_optimization.problems.QuadraticProgram` Returns: The :class:`~qiskit_optimization.problems.QuadraticProgram` created from the Max-cut problem instance. """ mdl = Model(name="Max-cut") x = {i: mdl.binary_var(name=f"x_{i}") for i in range(self._graph.number_of_nodes())} for w, v in self._graph.edges: self._graph.edges[w, v].setdefault("weight", 1) objective = mdl.sum( self._graph.edges[i, j]["weight"] * x[i] * (1 - x[j]) + self._graph.edges[i, j]["weight"] * x[j] * (1 - x[i]) for i, j in self._graph.edges ) mdl.maximize(objective) op = from_docplex_mp(mdl) return op
def _draw_result( self, result: Union[OptimizationResult, np.ndarray], pos: Optional[Dict[int, np.ndarray]] = None, ) -> None: """Draw the result with colors Args: result : The calculated result for the problem pos: The positions of nodes """ x = self._result_to_x(result) nx.draw(self._graph, node_color=self._node_color(x), pos=pos, with_labels=True)
[docs] def interpret(self, result: Union[OptimizationResult, np.ndarray]) -> List[List[int]]: """Interpret a result as two lists of node indices Args: result : The calculated result of the problem Returns: Two lists of node indices correspond to two node sets for the Max-cut """ x = self._result_to_x(result) cut = [[], []] # type: List[List[int]] for i, value in enumerate(x): if value == 0: cut[0].append(i) else: cut[1].append(i) return cut
def _node_color(self, x: np.ndarray) -> List[str]: # Return a list of strings for draw. # Color a node with red when the corresponding variable is 1. # Otherwise color it with blue. return ["b" if x[node] == 1 else "r" for node in self._graph.nodes]
[docs] @staticmethod def parse_gset_format(filename: str) -> np.ndarray: """Read graph in Gset format from file. Args: filename: the name of the file. Returns: An adjacency matrix as a 2D numpy array. """ n = -1 with open(filename, encoding="utf8") as infile: header = True m = -1 count = 0 for line in infile: # pylint: disable=unnecessary-lambda v = map(lambda e: int(e), line.split()) if header: n, m = v w = np.zeros((n, n)) header = False else: s__, t__, _ = v s__ -= 1 # adjust 1-index t__ -= 1 # ditto w[s__, t__] = t__ count += 1 assert m == count w += w.T return w
[docs] @staticmethod def get_gset_result(x: np.ndarray) -> Dict[int, int]: """Get graph solution in Gset format from binary string. Args: x: binary string as numpy array. Returns: A graph solution in Gset format. """ return {i + 1: 1 - x[i] for i in range(len(x))}