qat.opt.GraphColouring

class qat.opt.GraphColouring(graph, number_of_colours, **kwargs)

Specialization of the QUBO class for Graph Colouring.

Reference: “Ising formulations of many NP problems”, A. Lucas, 2014 - Section 6.1.

import numpy as np
import networkx as nx
from qat.opt import GraphColouring

graph = nx.Graph()
graph.add_nodes_from(np.arange(4))
graph.add_edges_from([(0,1), (0,2), (1,2), (1,3), (2,3)])
number_of_colours = 3

graph_colouring_problem = GraphColouring(graph, number_of_colours)

print("To anneal the problem, the solver would need "
      + str(len(graph.nodes()) * number_of_colours) + " spins.")

To anneal the problem, the solver would need 12 spins.

Parameters

graph (networkx.Graph) – a networkx graph
number_of_colours (int) – the number of colours

get_best_parameters()

Returns

6-key dictionary containing

n_monte_carlo_updates (int) - the number of Monte Carlo updates
n_trotters (int) - the number of “classical replicas” or “Trotter replicas”
gamma_max (double) - the starting magnetic field
gamma_min (double) - the final magnetic field
temp_max (double) - the starting temperature
temp_min (double) - the final temperature

parse_result(result, inverse=False)

Returns the best approximated solution of the Graph Colouring problem from a list of samples

Parameters: result (BatchResult) – BatchResult containing a list of samples
Returns: The best partition among the samples thatrepresents the colour of each node
Return type: GraphPartitioningResult

qat.opt.graph_colouring.produce_q_and_offset(graph, number_of_colours)

Returns the \(Q\) matrix and the offset energy of the problem.

Parameters

graph (networkx.Graph) – a networkx graph
number_of_colours (int) – the number of colours