lava.lib.optimization.utils.generators

lava.lib.optimization.utils.generators.mis

digraph inheritance33f7a9aa01 { bgcolor=transparent; rankdir=TB; size=""; "MISProblem" [URL="../lava-lib-optimization/lava.lib.optimization.utils.generators.html#lava.lib.optimization.utils.generators.mis.MISProblem",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Utility class to instantiate Maximum Independent Set problems and"]; }

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.

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.

Return type:: QUBO

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

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.

Return type:: ndarray

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

property num_vertices: int: Returns the number of vertices in the graph.

property seed: Returns the seed used for generating the graph.