lava.lib.optimization.utils.generators

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.