lava.lib.optimization.utils.generators

lava.lib.optimization.utils.generators.mis

Inheritance diagram of lava.lib.optimization.utils.generators.mis
class lava.lib.optimization.utils.generators.mis.MISProblem(num_vertices, connection_prob, seed=None)

Bases: object

Utility class to instantiate Maximum Independent Set problems and convert them to a QUBO formulation.

property connection_prob: float

Returns the connection probability of the graph.

Return type

float

find_maximum_independent_set()

Find and return the maximum independent set of a graph based on its adjacency matrix.

*Please note that this function addresses the maximum and not just the maximal independent set. A maximal independent set is an independent set that is not a subset of any other independent set. The largest of these sets is the maximum independent set, which is determined by the present function.*Uses Networkx to solve the equivalent maximum clique problem.

Get a graph whose maximum clique corresponds to the maximum independent set of that defined by the input connectivity matrix. The maximum independent set for the graph G={V,E} is equivalent to the maximum-clique of the graph H={V,E_c}, where E_c is the complement of E.

Returns

solution – Vector of length equal to the number of vertices in the graph. The ith entry of the vector determines if the ith vertex is a member of the MIS.

Return type

Array[binary]

get_as_qubo(w_diag, w_off)

Creates a QUBO whose solution corresponds to the maximum independent set (MIS) of the graph defined by the input adjacency matrix.

The goal of the QUBO is to minimize the cost

min x^T * Q * x ,

where the vector x is defined as:

x_i = 1 if vertex i is part of the MIS x_i = 0 if vertex i is not part of the MIS,

and the QUBO matrix is given by

Q_ii = w_diag Q_ij = w_off (for i!=j) .

Return type

QUBO

get_complement_graph()

Returns the complement graph in networkx format.

Return type

Graph

get_complement_graph_matrix()

Returns the adjacency matrix of the complement graph.

Return type

ndarray

get_graph()

Returns the graph in networkx format.

Return type

Graph

get_graph_matrix()

Returns the adjacency matrix of the graph.

Return type

ndarray

get_qubo_matrix(w_diag, w_off)

Creates a QUBO whose solution corresponds to the maximum independent set (MIS) of the graph defined by the input adjacency matrix.

The goal of the QUBO is to minimize the cost

min x^T * Q * x ,

where the vector x is defined as:

x_i = 1 if vertex i is part of the MIS x_i = 0 if vertex i is not part of the MIS,

and the QUBO matrix is given by

Q_ii = w_diag Q_ij = w_off (for i!=j) .

Return type

ndarray

property num_vertices: int

Returns the number of vertices in the graph.

Return type

int

property seed

Returns the seed used for generating the graph.