1"""This module contains the Graph Coloring class."""
2
3import pickle
4import networkx as nx
5from random import randint
6import matplotlib.pyplot as plt
7from quantum_launcher.base import Problem
8
9
[docs]
10class GraphColoring(Problem):
11 """
12 Class for Graph Coloring Problem which is a combinatorial problem involving assigning labels to vertices of the graph such that no two adjacent
13 vertices share the same label.
14
15 Attributes:
16 instance (nx.Graph): The graph for which the coloring problem is to be solved.
17
18
19 """
20
21 def __init__(
22 self,
23 instance: nx.Graph,
24 num_colors: int,
25 instance_name: str = "unnamed",
26 ) -> None:
27 super().__init__(instance=instance, instance_name=instance_name)
28 self.pos = None
29 self.num_colors = num_colors
30
31 @property
32 def setup(self) -> dict:
33 return {"instance_name": self.instance_name}
34
[docs]
35 @staticmethod
36 def from_preset(instance_name: str) -> "GraphColoring":
37 match instance_name:
38 case "default":
39 graph = nx.petersen_graph()
40 gc = GraphColoring(graph, instance_name=instance_name, num_colors=3)
41 gc.pos = nx.shell_layout(gc.instance, nlist=[list(range(5, 10)), list(range(5))])
42 return gc
43 case "small":
44 graph = nx.Graph()
45 graph.add_edges_from([(0, 1), (1, 2), (0, 2), (3, 2)])
46 return GraphColoring(graph, instance_name=instance_name, num_colors=3)
47
[docs]
48 @staticmethod
49 def from_file(path: str) -> "GraphColoring":
50 with open(path, 'rb') as f:
51 graph, num_colors = pickle.load(f)
52 return GraphColoring(graph, instance_name=path, num_colors=num_colors)
53
[docs]
54 def to_file(self, path: str):
55 with open(path, 'wb') as f:
56 pickle.dump((self.instance, self.num_colors), f, pickle.HIGHEST_PROTOCOL)
57
58 def _get_path(self) -> str:
59 return f"{self.name}@{self.instance_name}"
60
[docs]
61 def visualize(self, solution: list[int] | None = None):
62 if self.pos is None:
63 self.pos = nx.spring_layout(self.instance)
64 plt.figure(figsize=(8, 6))
65 if solution is not None:
66 nx.draw_networkx_nodes(self.instance, self.pos, node_size=500, node_color=solution, cmap="Accent")
67 else:
68 nx.draw_networkx_nodes(self.instance, self.pos, node_size=500, node_color="skyblue")
69 nx.draw_networkx_edges(self.instance, self.pos, edge_color="gray")
70 nx.draw_networkx_labels(self.instance, self.pos, font_size=10, font_weight="bold")
71 plt.title("Graph Coloring Problem Instance Visualization")
72 plt.show()
73
[docs]
74 @staticmethod
75 def generate_graph_coloring_instance(num_vertices: int, edge_probability: int, num_colors: int) -> "GraphColoring":
76 graph = nx.gnp_random_graph(num_vertices, edge_probability)
77 return GraphColoring(graph, num_colors=num_colors)
78
[docs]
79 @staticmethod
80 def randomly_choose_a_graph(num_colors: int) -> "GraphColoring":
81 graphs = nx.graph_atlas_g()
82 graph = graphs[randint(0, len(graphs) - 1)]
83 return GraphColoring(graph, num_colors=num_colors)
