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)
