Graph Coloring

This page explains how to solve the graph coloring problem using Amplify.

Formulation of Graph Coloring Problem

The graph coloring problem is a problem of assigning colors to the vertices of a certain graph under some constraints. The most typical problem is to assign colors to vertices so that every pair of adjacent vertices has different colors.

https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/200px-Petersen_graph_3-coloring.svg.png

In a plane graph (map), the four color theorem states that four colors are enough to color any map so that all adjacent regions in the map have distinct colors. However, it is not obvious how to implement such coloring.

Several application examples are known for the graph coloring problem, such as scheduling problems related to allocation of conference rooms, machines, tasks, etc., register allocation by a compiler, frequency allocation in a mobile phone network. Here, we demonstrate a way to solve a graph coloring problem using an Ising machine by coloring the prefectures in Japan.

In order to use an Ising machine, we consider how to express the states of the coloring of the graph in terms of binary variables. It can be expressed by assigning \(0\) or \(1\) to each region using four variables as follows:

Region

Red

Green

Blue

Yellow

1

0

0

1

0

2

0

1

0

0

3

0

0

1

0

4

1

0

0

0

This example means assigning blue to region to \(1\), green to region \(2\), blue to region \(3\), and red to region \(4\). We will represent each variable in the above table as \(q_{i,c}\) using the region index \(i\) and the color index \(c\). Therefore, given the number of regions as \(N\) and the number of colors as \(C\), the number of variables required is \(NC\).

The following constraints are imposed on the variables accordingly to the definition of the coloring problem.

  • Paint one region with one color

  • Adjacent regions must have distinct colors

The formulation of this problem is expressed in the following way.

Constraints

\[\begin{split}&\sum_{c = 0}^{C-1}{ q_{i,c} } = 1 \quad i \in \left\{0, 1, \cdots, N - 1 \right\} \\ &\sum_{\left(i, j \right) \in E}{ q_{i,c} q_{j,c} } = 0\end{split}\]

Here, \(E\) represents a set of pairs of adjacent regions on the graph. Please note that the variable index starts at \(0\) for the convenience of programming later.

Construction of a Problem

We use Python’s japanmap module to work with the map of Japan. Using the prefecture code (\(1\) - \(47\)), the prefecture names, adjacency information, etc. can be obtained.

First, we define the colors and prepare the variable table.

from amplify import BinaryPoly, gen_symbols
import japanmap as jm

colors = ["red", "green", "blue", "yellow"]
num_colors = len(colors)
num_region = len(jm.pref_names) - 1  # Obtained the number of prefectures

q = gen_symbols(BinaryPoly, num_region, num_colors)
>>> q
[[q_0, q_1, q_2, q_3], [q_4, q_5, q_6, q_7], [q_8, q_9, q_10, q_11], [q_12, q_13, q_14, q_15],
 [q_16, q_17, q_18, q_19], [q_20, q_21, q_22, q_23], [q_24, q_25, q_26, q_27], [q_28, q_29, q_30, q_31],
 [q_32, q_33, q_34, q_35], [q_36, q_37, q_38, q_39], [q_40, q_41, q_42, q_43], [q_44, q_45, q_46, q_47],
 [q_48, q_49, q_50, q_51], [q_52, q_53, q_54, q_55], [q_56, q_57, q_58, q_59], [q_60, q_61, q_62, q_63],
 [q_64, q_65, q_66, q_67], [q_68, q_69, q_70, q_71], [q_72, q_73, q_74, q_75], [q_76, q_77, q_78, q_79],
 [q_80, q_81, q_82, q_83], [q_84, q_85, q_86, q_87], [q_88, q_89, q_90, q_91], [q_92, q_93, q_94, q_95],
 [q_96, q_97, q_98, q_99], [q_100, q_101, q_102, q_103], [q_104, q_105, q_106, q_107],
 [q_108, q_109, q_110, q_111], [q_112, q_113, q_114, q_115], [q_116, q_117, q_118, q_119],
 [q_120, q_121, q_122, q_123], [q_124, q_125, q_126, q_127], [q_128, q_129, q_130, q_131],
 [q_132, q_133, q_134, q_135], [q_136, q_137, q_138, q_139], [q_140, q_141, q_142, q_143],
 [q_144, q_145, q_146, q_147], [q_148, q_149, q_150, q_151], [q_152, q_153, q_154, q_155],
 [q_156, q_157, q_158, q_159], [q_160, q_161, q_162, q_163], [q_164, q_165, q_166, q_167],
 [q_168, q_169, q_170, q_171], [q_172, q_173, q_174, q_175], [q_176, q_177, q_178, q_179],
 [q_180, q_181, q_182, q_183], [q_184, q_185, q_186, q_187]]

Note

Since all the coefficients appearing in the constraint polynomials are integers, it is possible to use BinaryIntPoly instead of BinaryPoly.

Next, we express constraint conditions. equal_to() function is used for expressing One-hot constraints. If we know that the minimum value of a constraint condition is 0, penalty() function can be used.

from amplify import sum_poly
from amplify.constraint import equal_to, penalty

# Constraints on each area
reg_constraints = [
    equal_to(sum_poly([q[i][c] for c in range(num_colors)]), 1)
    for i in range(num_region)
]

# Constraints between adjacent regions
adj_constraints = [
    # Note that the prefecture code and the array index are off by one
    penalty(q[i][c] * q[j - 1][c])
    for i in range(num_region)
    for j in jm.adjacent(i + 1)  # j: Adjacent prefecture code
    if i + 1 < j
    for c in range(num_colors)
]

constraints = sum(reg_constraints) + sum(adj_constraints)

Adjacent information can be obtained by entering the prefecture code in the japanmap.adjacent() function. Note that the index for q and the prefecture code differ by \(1\).

Note

For the constraints that take the minimum value \(0\), it is equivalent to first summing all the conditions and then creating a single constraint object. You can also write the constraints between adjacent regions as follows:

# Constraints between adjacent regions
adj_constraints = [
    # Note that the prefecture code and the array index are off by one
    penalty(sum_poly(q[i][c] * q[j - 1][c]) for c in range(num_colors))
    for i in range(num_region)
    for j in jm.adjacent(i + 1)  # j: Adjacent prefecture code
    if i + 1 < j
]

Now we completed the preparation for the formulation.

Execution of Ising Machine

We create a client for the Ising machine and set the parameters. We then create a solver by setting the configured client.

from amplify import Solver
from amplify.client import FixstarsClient

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 5000  # Timeout is 5 seconds

solver = Solver(client)

We create a logical model from the constraints, execute the Ising machine as follows, and obtain the result.

from amplify import BinaryQuadraticModel

model = BinaryQuadraticModel(constraints)
result = solver.solve(model)
if len(result) == 0:
    raise RuntimeError("Some of the constraints are not satisfied.")

values = result[0].values

Note

If the length of the result object is 0, it means that no solution that satisfies the constraint conditions was obtained. In this case, it is necessary to change the parameters of the Ising machine.

Analysis of Results

values is a dictionary that represents the mapping between input variables and solution values. Since it is difficult to handle it as it is, we decode it into the same format as the variable table q as follows.

from amplify import decode_solution

q_values = decode_solution(q, values, 1)
>>> q_values
[[0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0],
 [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], [1, 0, 0, 0],
 [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0],
 [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0],
 [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0],
 [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], [1, 0, 0, 0],
 [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 0, 1],
 [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]]

We convert the result to {prefecture name: color} format. First, we obtain the index with the value of 1 in each row of q_values, by using a numpy function as shown below. After that, japanmap.pref_names is used to convert the row indices to prefecture names, and we create a dictionary by paring them with the corresponding colors.

import numpy as np
color_indices = np.where(np.array(q_values) == 1)[1]
color_map = {jm.pref_names[i + 1]: colors[color_indices[i]] for i in range(len(color_indices))}
>>> color_map
{'Hokkaido': 'green', 'Aomori': 'green', 'Iwate': 'yellow', 'Miyagi': 'green', 'Akita': 'red',
 'Yamagata': 'yellow', 'Fukushima': 'blue', 'Ibaraki': 'green', 'Tochigi': 'red', 'Gunma': 'green',
 'Saitama': 'blue', 'Chiba': 'yellow', 'Tokyo': 'red', 'Kanagawa': 'yellow', 'Niigata': 'red',
 'Toyama': 'blue', 'Ishikawa': 'green', 'Fukui': 'blue', 'Yamanashi': 'green', 'Nagano': 'yellow',
 'Gifu': 'red', 'Shizuoka': 'red', 'Aichi': 'blue', 'Mie': 'green', 'Shiga': 'yellow',
 'Kyoto': 'red', 'Osaka': 'yellow', 'Hyogo': 'green', 'Nara': 'blue', 'Wakayama': 'red',
 'Tottori': 'blue', 'Shimane': 'green', 'Okayama': 'yellow', 'Hiroshima': 'red', 'Yamaguchi': 'blue',
 'Tokushima': 'green', 'Kagawa': 'yellow', 'Ehime': 'red', 'Kochi': 'blue', 'Fukuoka': 'yellow',
 'Saga': 'blue', 'Nagasaki': 'red', 'Kumamoto': 'green', 'Oita': 'red', 'Miyazaki': 'yellow',
 'Kagoshima': 'red', 'Okinawa': 'red'}

Finally we display the colored map. It is plotted as follows:

import matplotlib.pyplot as plt

plt.rcParams["figure.figsize"] = 6, 6
plt.imshow(jm.picture(color_map))
plt.show()
_images/coloring_figure1.png