1"""This module contains the Graph Coloring class."""
2
3import pickle
4from itertools import product
5from random import randint
6from typing import Literal
7
8import matplotlib.pyplot as plt
9import networkx as nx
10import numpy as np
11from pyqubo import Array, Binary
12
13from qlauncher import models
14from qlauncher.base import Problem
15from qlauncher.hampy import Equation
16
17
[docs]
18class GraphColoring(Problem):
19 """
20 Class for Graph Coloring Problem which is a combinatorial problem involving assigning labels to vertices of the graph such that no two adjacent vertices share the same label.
21
22 Attributes:
23 instance (nx.Graph): The graph for which the coloring problem is to be solved.
24
25
26 """
27
28 def __init__(
29 self,
30 instance: nx.Graph,
31 num_colors: int,
32 instance_name: str = 'unnamed',
33 ) -> None:
34 super().__init__(instance=instance, instance_name=instance_name)
35 self.pos = None
36 self.num_colors = num_colors
37
38 @property
39 def setup(self) -> dict:
40 return {'instance_name': self.instance_name}
41
[docs]
42 @staticmethod
43 def from_preset(instance_name: Literal['default', 'small'], **kwargs) -> 'GraphColoring':
44 match instance_name:
45 case 'default':
46 graph = nx.petersen_graph()
47 gc = GraphColoring(graph, instance_name=instance_name, num_colors=3)
48 gc.pos = nx.shell_layout(gc.instance, nlist=[list(range(5, 10)), list(range(5))])
49 return gc
50 case 'small':
51 graph = nx.Graph()
52 graph.add_edges_from([(0, 1), (1, 2), (0, 2), (3, 2)])
53 return GraphColoring(graph, instance_name=instance_name, num_colors=3)
54 case _:
55 raise ValueError(f'Preset f{instance_name} not defined')
56
[docs]
57 @classmethod
58 def from_file(cls: type['GraphColoring'], path: str) -> 'Problem':
59 with open(path, 'rb') as f:
60 graph, num_colors = pickle.load(f)
61 return cls(graph, instance_name=path, num_colors=num_colors)
62
63 # def to_file(self, path: str) -> None:
64 # with open(path, 'wb') as f:
65 # pickle.dump((self.instance, self.num_colors), f, pickle.HIGHEST_PROTOCOL)
66
67 def _get_path(self) -> str:
68 return f'{self.name}@{self.instance_name}'
69
[docs]
70 def visualize(self, solution: list[int] | None = None) -> None:
71 if self.pos is None:
72 self.pos = nx.spring_layout(self.instance, seed=42) # set seed for same node graphs in plt
73 plt.figure(figsize=(8, 6))
74 if solution is not None:
75 nx.draw_networkx_nodes(self.instance, self.pos, node_size=500, node_color=solution, cmap='Accent')
76 colors = []
77 for n1, n2 in self.instance.edges:
78 if solution[n1] == solution[n2]:
79 colors.append('r')
80 else:
81 colors.append('gray')
82 nx.draw_networkx_edges(self.instance, self.pos, edge_color=colors, width=4)
83 else:
84 nx.draw_networkx_nodes(self.instance, self.pos, node_size=500, node_color='skyblue')
85 nx.draw_networkx_edges(self.instance, self.pos, edge_color='gray')
86 nx.draw_networkx_labels(self.instance, self.pos, font_size=10, font_weight='bold')
87 plt.title(f'Graph {self.num_colors}-Coloring Problem Instance Visualization')
88 plt.show()
89
[docs]
90 @staticmethod
91 def generate_graph_coloring_instance(num_vertices: int, edge_probability: int, num_colors: int) -> 'GraphColoring':
92 graph = nx.gnp_random_graph(num_vertices, edge_probability)
93 return GraphColoring(graph, num_colors=num_colors)
94
[docs]
95 @staticmethod
96 def randomly_choose_a_graph(num_colors: int) -> 'GraphColoring':
97 graphs = nx.graph_atlas_g()
98 graph = graphs[randint(0, len(graphs) - 1)]
99 return GraphColoring(graph, num_colors=num_colors)
100
101 # Penalty for assigning the same colors to neighboring vertices
102 def _color_duplication_hamiltonian(self, num_qubits: int, color_bit_length: int) -> Equation:
103 eq = Equation(num_qubits)
104 for node1, node2 in self.instance.edges:
105 for ind, comb in enumerate(product(range(2), repeat=color_bit_length)):
106 if ind >= self.num_colors:
107 break
108 eq_inner = Equation(num_qubits)
109 for i in range(color_bit_length):
110 qubit1 = eq[node1 * color_bit_length + i]
111 qubit2 = eq[node2 * color_bit_length + i]
112 exp = qubit1 & qubit2 if comb[i] else ~qubit1 & ~qubit2
113 eq_inner &= exp
114 eq += eq_inner
115 return eq
116
117 # Penalty for using excessive colors
118 def _excessive_colors_use_hamiltonian(self, num_qubits: int, color_bit_length: int) -> Equation:
119 eq = Equation(num_qubits)
120 for node in self.instance.nodes:
121 for ind, comb in enumerate(product(range(2), repeat=color_bit_length)):
122 if ind < self.num_colors:
123 continue
124 eq_inner = Equation(num_qubits)
125 for i in range(color_bit_length):
126 qubit = eq[node * color_bit_length + i]
127 exp = qubit if comb[i] else ~qubit
128 eq_inner &= exp
129 eq += eq_inner
130 return eq
131
[docs]
132 def to_hamiltonian(self, constraints_weight: float = 1, costs_weight: float = 1) -> models.Hamiltonian:
133 color_bit_length = int(np.ceil(np.log2(self.num_colors)))
134 num_qubits = self.instance.number_of_nodes() * color_bit_length
135
136 eq = self._color_duplication_hamiltonian(num_qubits, color_bit_length)
137 eq2 = self._excessive_colors_use_hamiltonian(num_qubits, color_bit_length)
138
139 return models.Hamiltonian(eq * costs_weight + eq2 * constraints_weight)
140
[docs]
141 def to_bqm(self) -> models.BQM:
142 """Returns BQM"""
143 x = Array.create('x', shape=(self.instance.number_of_nodes(), self.num_colors), vartype='BINARY')
144 qubo: Binary = 0
145 for n1, n2 in self.instance.edges:
146 for c in range(self.num_colors):
147 qubo += x[n1, c] * x[n2, c]
148 for node in self.instance.nodes:
149 expression: Binary = 1 - sum(x[node, i] for i in range(self.num_colors))
150 qubo += expression * expression
151 return models.BQM(qubo.compile())
152
[docs]
153 def to_qubo(self) -> models.QUBO:
154 return self.to_bqm().to_qubo()
