Tutorial 4 - Graph Coloring Solver¶

In this notebook, we are going to implement a graph coloring algorithm based on a MIS solver for a practical problem of sharing a bandwidth of frequencies for a network of antennas.

In [1]:

Copied!





# imports
from mis.coloring import GraphColoringSolver
from mis.data import DataLoader
from pathlib import Path
from mis.pipeline.config import SolverConfig
from mis.shared.types import MethodType
from mis.pipeline.backends import QutipBackend
# imports
from mis.coloring import GraphColoringSolver
from mis.data import DataLoader
from pathlib import Path
from mis.pipeline.config import SolverConfig
from mis.shared.types import MethodType
from mis.pipeline.backends import QutipBackend

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.

In [2]:

Copied!

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

---------------------------------------------------------------------------
FileNotFoundError                         Traceback (most recent call last)
Cell In[2], line 2
      1 loader = DataLoader()
----> 2 loader.load_from_csv_coordinates(Path('./datasets/coloring/antenna_Paris.csv'))

File ~/work/maximum-independent-set/maximum-independent-set/mis/data/dataloader.py:45, in DataLoader.load_from_csv_coordinates(self, file_path)
     43 # error handling with a try-except block
     44 if not file_path.exists():
---> 45     raise FileNotFoundError(f"The file {file_path} does not exist.")
     46 if not file_path.is_file():
     47     raise ValueError(f"The path {file_path} is not a file.")

FileNotFoundError: The file datasets/coloring/antenna_Paris.csv does not exist.

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.

In [3]:

Copied!

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

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[3], line 1
----> 1 instance = loader.build_mis_instance_from_coordinates(antenna_range=1.2)

File ~/work/maximum-independent-set/maximum-independent-set/mis/data/dataloader.py:82, in DataLoader.build_mis_instance_from_coordinates(self, antenna_range, antennas)
     68 def build_mis_instance_from_coordinates(
     69     self, antenna_range: float, antennas: set[int] = None
     70 ) -> MISInstance:
     71     """
     72     Build a Maximum Independent Set (MIS) instance from the loaded coordinates.
     73     The function creates a graph where nodes represent antennas and edges represent
   (...)
     80         MISInstance: An instance of the Maximum Independent Set problem represented as a graph.
     81     """
---> 82     if self.coordinates_dataset is None:
     83         raise ValueError(
     84             "Coordinates dataset is not loaded. Please load the dataset using load_from_csv_coordinates method."
     85         )
     87     if antennas is None:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

Let's visualize our dataset :

In [4]:

Copied!

instance.draw()
instance.draw()

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[4], line 1
----> 1 instance.draw()

NameError: name 'instance' is not defined

Solving the Graph Coloring Problem¶

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

The algorithm starts with a set $S$ 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 $S$, colors all of the nodes of the MIS in the same color, then removes them from $S$. The operation is repeated until $S$ is empty.

Using a classical solver¶

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

In [5]:

Copied!





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}")
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}")

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[5], line 8
      1 from mis.pipeline.kernelization import Kernelization
      4 solver = GraphColoringSolver(loader, 1.2, SolverConfig(
      5     method = MethodType.EAGER,
      6     max_iterations=1,
      7 ))
----> 8 solver.solve()
      9 solver.visualize_solution()
     10 print(solver.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:65, in GraphColoringSolver.solve(self, antennas, is_second_coloring)
     51 """
     52 Solve the graph coloring problem by finding a maximum independent set
     53 for the given antenna range and coloring the antennas accordingly.
   (...)
     62     Execution[list[MISSolution]]: An execution object containing the nodes of each color in the solution.
     63 """
     64 if antennas is None:
---> 65     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
     67 res = []
     68 if not is_second_coloring:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

The array solver.colors represents the group assigned to each antenna by the algorithm, such that all the antennas of the same group can share the same frequency without interfering with each other.

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.

In [6]:

Copied!





from mis.pipeline.maximization import Maximization


solver = GraphColoringSolver(loader, 1.2, SolverConfig(
    method = MethodType.EAGER,
    backend = QutipBackend(),
    max_iterations=1
))
solver.solve()
solver.visualize_solution()
print(solver.colors)   
print(f"Number of colors used: {solver.colors_count}")
from mis.pipeline.maximization import Maximization


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

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[6], line 9
      1 from mis.pipeline.maximization import Maximization
      4 solver = GraphColoringSolver(loader, 1.2, SolverConfig(
      5     method = MethodType.EAGER,
      6     backend = QutipBackend(),
      7     max_iterations=1
      8 ))
----> 9 solver.solve()
     10 solver.visualize_solution()
     11 print(solver.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:65, in GraphColoringSolver.solve(self, antennas, is_second_coloring)
     51 """
     52 Solve the graph coloring problem by finding a maximum independent set
     53 for the given antenna range and coloring the antennas accordingly.
   (...)
     62     Execution[list[MISSolution]]: An execution object containing the nodes of each color in the solution.
     63 """
     64 if antennas is None:
---> 65     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
     67 res = []
     68 if not is_second_coloring:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

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.

In [7]:

Copied!





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


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

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[7], line 8
      1 solver = GraphColoringSolver(loader, 1.2, SolverConfig(
      2     method = MethodType.EAGER,
      3     backend = QutipBackend(),
   (...)
      6     postprocessor = lambda : Maximization()
      7 ))
----> 8 solver.solve()
      9 solver.visualize_solution()
     10 print(solver.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:65, in GraphColoringSolver.solve(self, antennas, is_second_coloring)
     51 """
     52 Solve the graph coloring problem by finding a maximum independent set
     53 for the given antenna range and coloring the antennas accordingly.
   (...)
     62     Execution[list[MISSolution]]: An execution object containing the nodes of each color in the solution.
     63 """
     64 if antennas is None:
---> 65     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
     67 res = []
     68 if not is_second_coloring:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

Enhancing our algorithm¶

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

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.

In [8]:

Copied!





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()
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()

---------------------------------------------------------------------------
FileNotFoundError                         Traceback (most recent call last)
Cell In[8], line 2
      1 loader_2 = DataLoader()
----> 2 loader_2.load_from_csv_coordinates(Path('./datasets/coloring/counterexample_1.csv'))
      3 instance = loader_2.build_mis_instance_from_coordinates(antenna_range=112)
      4 instance.draw()

File ~/work/maximum-independent-set/maximum-independent-set/mis/data/dataloader.py:45, in DataLoader.load_from_csv_coordinates(self, file_path)
     43 # error handling with a try-except block
     44 if not file_path.exists():
---> 45     raise FileNotFoundError(f"The file {file_path} does not exist.")
     46 if not file_path.is_file():
     47     raise ValueError(f"The path {file_path} is not a file.")

FileNotFoundError: The file datasets/coloring/counterexample_1.csv does not exist.

In [9]:

Copied!





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 = 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}")

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[9], line 5
      1 solver_2 = GraphColoringSolver(loader_2, 112, SolverConfig(
      2     method = MethodType.EAGER,
      3     max_iterations=1
      4 ))
----> 5 solver_2.solve()
      6 solver_2.visualize_solution()
      7 print(solver_2.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:65, in GraphColoringSolver.solve(self, antennas, is_second_coloring)
     51 """
     52 Solve the graph coloring problem by finding a maximum independent set
     53 for the given antenna range and coloring the antennas accordingly.
   (...)
     62     Execution[list[MISSolution]]: An execution object containing the nodes of each color in the solution.
     63 """
     64 if antennas is None:
---> 65     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
     67 res = []
     68 if not is_second_coloring:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

Actually, the previous graph is bipartite as it has no odd cycles, hence allowing a coloring with only two colors. It follows that our previous coloring is not optimal. We can actually improve the result of the solver using some post-processing, which involves trying to recolor every antenna of some color with an already existing colors, and if succesful, will reduce the numeber of colors.

In [10]:

Copied!





solver_2.reduce_colors()
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}")

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[10], line 1
----> 1 solver_2.reduce_colors()
      2 solver_2.visualize_solution()
      3 print(solver_2.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:118, in GraphColoringSolver.reduce_colors(self)
    111 def reduce_colors(self) -> list[int]:
    112     """
    113     Attempts to reduce the number of colors used in the solution
    114     by trying to reassign every node of some color.
    115     Returns :
    116         list[int]: A list of colors for each antenna, where the index represents the antenna.
    117     """
--> 118     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
    119     graph = self.loader.build_mis_instance_from_coordinates(self.antenna_range, antennas).graph
    120     new_colors = deepcopy(self.colors)

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

It seems that this approach successfully worked in this case, what about our original dataset ?

In [11]:

Copied!





solver.reduce_colors()
solver.visualize_solution()
print(solver.colors)   
print(f"Number of colors used: {solver.colors_count}")
solver.reduce_colors()
solver.visualize_solution()
print(solver.colors)   
print(f"Number of colors used: {solver.colors_count}")

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[11], line 1
----> 1 solver.reduce_colors()
      2 solver.visualize_solution()
      3 print(solver.colors)   

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:118, in GraphColoringSolver.reduce_colors(self)
    111 def reduce_colors(self) -> list[int]:
    112     """
    113     Attempts to reduce the number of colors used in the solution
    114     by trying to reassign every node of some color.
    115     Returns :
    116         list[int]: A list of colors for each antenna, where the index represents the antenna.
    117     """
--> 118     antennas = set([x for x in range(len(self.loader.coordinates_dataset))])
    119     graph = self.loader.build_mis_instance_from_coordinates(self.antenna_range, antennas).graph
    120     new_colors = deepcopy(self.colors)

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'

We can see that it worked, reducing indeed the total number of colors to 8.

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.

In [12]:

Copied!





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())
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())

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[12], line 5
      1 solver_3 = GraphColoringSolver(loader, 1.2, SolverConfig(
      2     method = MethodType.EAGER,
      3     max_iterations=1
      4 ))
----> 5 sets = solver_3.split_antennas_by_degree(2) # setting the threshold to 2
      6 solver_3.solve(antennas=sets[0])
      7 solver_3.solve(antennas=sets[1], is_second_coloring=True)

File ~/work/maximum-independent-set/maximum-independent-set/mis/coloring/coloring.py:99, in GraphColoringSolver.split_antennas_by_degree(self, threshold)
     87 def split_antennas_by_degree(self, threshold: int) -> list[set[int]]:
     88     """
     89     Splits the antennas into two sets based on a threshold of the degree of the node.
     90     Antennas with a degree less than or equal to the threshold will be grouped together.
   (...)
     97         less than or equal to the threshold, and the second set contains the rest.
     98     """
---> 99     graph = self.loader.build_mis_instance_from_coordinates(self.antenna_range).graph
    100     low_degree_antennas = set()
    101     high_degree_antennas = set()

File ~/work/maximum-independent-set/maximum-independent-set/mis/data/dataloader.py:82, in DataLoader.build_mis_instance_from_coordinates(self, antenna_range, antennas)
     68 def build_mis_instance_from_coordinates(
     69     self, antenna_range: float, antennas: set[int] = None
     70 ) -> MISInstance:
     71     """
     72     Build a Maximum Independent Set (MIS) instance from the loaded coordinates.
     73     The function creates a graph where nodes represent antennas and edges represent
   (...)
     80         MISInstance: An instance of the Maximum Independent Set problem represented as a graph.
     81     """
---> 82     if self.coordinates_dataset is None:
     83         raise ValueError(
     84             "Coordinates dataset is not loaded. Please load the dataset using load_from_csv_coordinates method."
     85         )
     87     if antennas is None:

AttributeError: 'DataLoader' object has no attribute 'coordinates_dataset'