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
- 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.