Skip to content
Pasqal Documentation

Tutorial 4 - Graph Coloring Solver

# imports
from mis.coloring import GraphColoringSolver
from mis.data import DataLoader
from pathlib import Path
from mis import MethodType, SolverConfig

Importing our dataset

Section titled “Importing our dataset”

The practical dataset of interest is the placement of 5G antennas in Paris that can be found in the antenna_Paris.csv file. A set of antennas are distributed over the city with a specific coverage range. Therefore, some antennas will be in range of each other and cannot share the same frequency.

loader = DataLoader()
loader.load_from_csv_coordinates(Path('./datasets/coloring/antenna_Paris.csv'))

Representing our problem instance

Section titled “Representing our problem instance”

The first step is to represent the problem by a graph. In this case, each node represents an antenna, with an edge between two if they are in the range of each other. For the sake of simplicity, we will reduce the graph size by considering only antennas within a constant range R, set to 1.2 km.

instance = loader.build_mis_instance_from_coordinates(antenna_range=1.2)
instance.draw()

Solving the Graph Coloring Problem

Section titled “Solving the Graph Coloring Problem”

We will use the greedy heuristic algorithm described in Appendix A (external) to find a coloring of the graph using MIS output.

The algorithm starts with a set SS of all the nodes in the graph, and at each iteration it searches for a maximum independent set of nodes of the subgraph formed by the nodes currently in SS, colors all of the nodes of the MIS in the same color, then removes them from SS. The operation is repeated until SS is empty.

Using a classical solver

Section titled “Using a classical solver”

We will first solve the coloring problem using the standard classical and heuristic MIS solver in Networkx (external). As it is heuristic and non-deterministic, this solver does not guarantee an optimal solution.

from mis.pipeline.kernelization import Kernelization




solver = GraphColoringSolver(loader, 1.2, SolverConfig(
    method = MethodType.EAGER,
    max_iterations=1,
))
solver.solve()
solver.visualize_solution()
print(solver.colors)
print(f"Number of colors used: {solver.colors_count}")

Using the quantum SDK QuTiP

Section titled “Using the quantum SDK QuTiP”

We will now use a quantum solver to solve the MIS instances used by our coloring algorithm, please refer to tutorial 1a for more details about the solver.

from mis.pipeline.maximization import Maximization
from mis import BackendConfig, BackendType


backend_config = BackendConfig(
    backend = BackendType.QUTIP
)


solver = GraphColoringSolver(loader, 1.2, SolverConfig(
    method = MethodType.EAGER,
    backend = backend_config,
    max_iterations=1
))
solver.solve()
solver.visualize_solution()
print(solver.colors)
print(f"Number of colors used: {solver.colors_count}")

Applying Pre and Post Processors

Section titled “Applying Pre and Post Processors”

Performs optimizations before and after running the Quantum solver in order to enhance the quality of the results given by the algorithm.

solver = GraphColoringSolver(loader, 1.2, SolverConfig(
    method = MethodType.EAGER,
    backend = backend_config,
    max_iterations = 1,
    preprocessor = lambda config, graph: Kernelization(config, graph),
    postprocessor = lambda config: Maximization(config)
))
solver.solve()
solver.visualize_solution()
print(solver.colors)
print(f"Number of colors used: {solver.colors_count}")

Enhancing our algorithm

Section titled “Enhancing our algorithm”

We now explore further improvements to the MIS-based coloring algorithm.

Color Reduction

Section titled “Color Reduction”

Note that the approach we are using is a greedy heuristic algorithm, that does not necessarily give the optimal solution, let's look at an example where it is more obvious.

loader_2 = DataLoader()
loader_2.load_from_csv_coordinates(Path('./datasets/coloring/counterexample_1.csv'))
instance = loader_2.build_mis_instance_from_coordinates(antenna_range=112)
instance.draw()
solver_2 = GraphColoringSolver(loader_2, 112, SolverConfig(
    method = MethodType.EAGER,
    max_iterations=1
))
solver_2.solve()
solver_2.visualize_solution()
print(solver_2.colors)
print(f"Number of colors used: {solver_2.colors_count}")
solver_2.reduce_colors()
solver_2.visualize_solution()
print(solver_2.colors)
print(f"Number of colors used: {solver_2.colors_count}")
solver.reduce_colors()
solver.visualize_solution()
print(solver.colors)
print(f"Number of colors used: {solver.colors_count}")

Node Degree Segmentation

Section titled “Node Degree Segmentation”

Let's try to improve more the algorithm, by preprocessing the graph. We first split the antennas into two groups, those with many antennas in the their range, and those with less. More formally, we will after fixing a threshold, split the nodes of the graph those with a degree higher than the threshold, and the others, then solve the coloring problem on each set, and finally join the results with the reduce_colors method.

solver_3 = GraphColoringSolver(loader, 1.2, SolverConfig(
    method = MethodType.EAGER,
    max_iterations=1
))
sets = solver_3.split_antennas_by_degree(2) # setting the threshold to 2
solver_3.solve(antennas=sets[0])
solver_3.solve(antennas=sets[1], is_second_coloring=True)
solver_3.reduce_colors()
solver_3.visualize_solution()
print(solver_3.colors)
print(f"Number of colors used: {solver_3.colors_count}")
print(solver_3.check_solution())