Source code for qlauncher.problems.problem_initialization.maxcut

 1"""  This module contains the MaxCut class."""
 2import networkx as nx
 3import matplotlib.pyplot as plt
 4
 5from qlauncher.base import Problem
 6
 7

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

[docs]
30    @staticmethod
31    def from_preset(instance_name: str) -> "MaxCut":
32        match instance_name:
33            case 'default':
34                node_list = list(range(6))
35                edge_list = [(0, 1), (0, 2), (0, 5), (1, 3), (1, 4),
36                             (2, 4), (2, 5), (3, 4), (3, 5)]
37        graph = nx.Graph()
38        graph.add_nodes_from(node_list)
39        graph.add_edges_from(edge_list)
40        return MaxCut(graph, instance_name=instance_name)

41
42    def _get_path(self) -> str:
43        return f'{self.name}@{self.instance_name}'
44

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

56

[docs]
57    @staticmethod
58    def generate_maxcut_instance(num_vertices: int, edge_probability: float) -> "MaxCut":
59        graph = nx.gnp_random_graph(num_vertices, edge_probability)
60        return MaxCut(graph, instance_name='Generated')