Source code for qlauncher.problems.optimization.maxcut

 1"""This module contains the MaxCut class."""
 2
 3from typing import Literal
 4
 5import matplotlib.pyplot as plt
 6import networkx as nx
 7import numpy as np
 8
 9from qlauncher import hampy, models
10from qlauncher.base import Problem
11
12

[docs]
13class MaxCut(Problem):
14    """
15    Class for MaxCut Problem.
16
17    This class represents MaxCut Problem which is a combinatorial optimization problem that involves partitioning the
18    vertices of a graph into two sets such that the number of edges between the two sets is maximized. The class contains
19    an instance of the problem, so it can be passed into QLauncher.
20
21    Args:
22            instance (nx.Graph): The graph instance representing the problem.
23
24    """
25
26    def __init__(self, instance: nx.Graph, instance_name: str = 'unnamed'):
27        self.instance: nx.Graph
28        super().__init__(instance, instance_name)
29
30    @property
31    def setup(self) -> dict:
32        return {'instance_name': self.instance_name}
33

[docs]
34    @staticmethod
35    def from_preset(instance_name: Literal['default'], **kwargs) -> 'MaxCut':
36        match instance_name:
37            case 'default':
38                node_list = list(range(6))
39                edge_list = [(0, 1), (0, 2), (0, 5), (1, 3), (1, 4), (2, 4), (2, 5), (3, 4), (3, 5)]
40        graph = nx.Graph()
41        graph.add_nodes_from(node_list)
42        graph.add_edges_from(edge_list)
43        return MaxCut(graph, instance_name=instance_name)

44

[docs]
45    def visualize(self, bitstring: str | None = None) -> None:
46        pos = nx.spring_layout(self.instance, seed=42)
47        plt.figure(figsize=(8, 6))
48        cmap = 'skyblue' if bitstring is None else ['crimson' if bit == '1' else 'skyblue' for bit in bitstring]
49        nx.draw(self.instance, pos, with_labels=True, node_color=cmap, node_size=500, edge_color='gray', font_size=10, font_weight='bold')
50        plt.title('Max-Cut Problem Instance Visualization')
51        plt.show()

52

[docs]
53    @staticmethod
54    def generate_maxcut_instance(num_vertices: int, edge_probability: float) -> 'MaxCut':
55        graph = nx.gnp_random_graph(num_vertices, edge_probability)
56        return MaxCut(graph, instance_name='Generated')

57

[docs]
58    def to_qubo(self) -> models.QUBO:
59        n = len(self.instance)
60        Q = np.zeros((n, n))
61        for i, j in self.instance.edges:
62            Q[i, i] += -1
63            Q[j, j] += -1
64            Q[i, j] += 1
65            Q[j, i] += 1
66
67        return models.QUBO(Q, 0)

68

[docs]
69    def to_hamiltonian(self) -> models.Hamiltonian:
70        size = self.instance.number_of_nodes()
71        hamiltonian = hampy.Equation(size)
72        for edge in self.instance.edges():
73            hamiltonian += ~hampy.one_in_n(list(edge), size)
74        if hamiltonian is None:
75            raise TypeError
76        return models.Hamiltonian(hamiltonian)