1"""  This module contains the EC class."""
  2import ast
  3from collections import defaultdict
  4from typing import List, Optional, Set
  5import networkx as nx
  6import matplotlib.pyplot as plt
  7
  8from quantum_launcher.base import Problem
  9
 10

[docs]
 11class EC(Problem):
 12    """
 13    Class for exact cover problem.
 14
 15    The exact cover problem is a combinatorial optimization problem that involves finding a subset of a given set
 16    of elements such that the subset covers all elements and the number of elements in the subset is minimized.
 17    The class contains an instance of the problem, so it can be passed into Quantum Launcher.
 18
 19    Attributes:
 20        onehot (str): The one-hot encoding used for the problem.
 21        instance (any): The instance of the problem.
 22        instance_name (str | None): The name of the instance.
 23        instance_path (str): The path to the instance file.
 24
 25    """
 26
 27    def __init__(self, instance: List[Set[int]] = None, instance_name: str = 'unnamed') -> None:
 28        super().__init__(instance=instance, instance_name=instance_name)
 29
 30    @property
 31    def setup(self) -> dict:
 32        return {
 33            'instance_name': self.instance_name
 34        }
 35
 36    def _get_path(self) -> str:
 37        return f'{self.name}@{self.instance_name}'
 38

[docs]
 39    @staticmethod
 40    def from_preset(instance_name: str, **kwargs) -> "EC":
 41        match instance_name:
 42            case 'micro':
 43                instance = [{1, 2},
 44                            {1}]
 45            case 'toy':
 46                instance = [{1, 4, 7},
 47                            {1, 4},
 48                            {4, 5, 7},
 49                            {3, 5, 6},
 50                            {2, 3, 6, 7},
 51                            {2, 7}]
 52        return EC(instance=instance, instance_name=instance_name, **kwargs)

 53

[docs]
 54    @classmethod
 55    def from_file(cls, path: str, **kwargs) -> "EC":
 56        with open(path, 'r', encoding='utf-8') as file:
 57            read_file = file.read()
 58        instance = ast.literal_eval(read_file)
 59        return EC(instance, **kwargs)

 60

[docs]
 61    def read_instance(self, instance_path: str):
 62        with open(instance_path, 'r', encoding='utf-8') as file:
 63            read_file = file.read()
 64        self.instance = ast.literal_eval(read_file)

 65

[docs]
 66    def visualize(self, marked: Optional[str] = None):
 67        G = nx.Graph()
 68        size = len(self.instance)
 69        ec = list(map(lambda x: set(map(str, x)), self.instance))
 70        names = set.union(*ec)
 71        for i in range(len(ec)):
 72            G.add_node(i)
 73        for i in sorted(names):
 74            G.add_node(i)
 75        covered = defaultdict(int)
 76        for node, edges in enumerate(ec):
 77            for goal_node in edges:
 78                G.add_edge(node, goal_node)
 79
 80        edge_colors = []
 81        for goal_node in G.edges():
 82            node, str_node = goal_node
 83            if marked is None:
 84                edge_colors.append('black')
 85                continue
 86            if marked[node] == '1':
 87                edge_colors.append('red')
 88                covered[str_node] += 1
 89            else:
 90                edge_colors.append('gray')
 91        color_map = []
 92        for node in G:
 93            if isinstance(node, int):
 94                color_map.append('lightblue')
 95            elif covered[node] == 0:
 96                color_map.append('yellow')
 97            elif covered[node] == 1:
 98                color_map.append('lightgreen')
 99            else:
100                color_map.append('red')
101        pos = nx.bipartite_layout(G, nodes=range(size))
102        nx.draw(G, pos, node_color=color_map, with_labels=True,
103                edge_color=edge_colors)
104        plt.title('Exact Cover Problem Visualization')
105        plt.show()

106

[docs]
107    @staticmethod
108    def generate_ec_instance(n: int, m: int, p: float = 0.5, **kwargs) -> "EC":
109        graph = nx.bipartite.random_graph(n, m, p)
110        right_nodes = [n for n, d in graph.nodes(data=True) if d["bipartite"] == 0]
111        instance = [set() for _ in right_nodes]
112        for left, right in graph.edges():
113            instance[left].add(right)
114        return EC(instance=instance, **kwargs)