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(adjacency_matrix)

Bases: object

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

property adjacency_matrix: ndarray: Returns the adjacency matrix 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]

classmethod from_random_uniform(num_vertices, density, seed=0)

Instantiate a new MIS problem, based on a random uniform graph sampled with the given paramters.

Parameters:

num_vertices (int) – Number of vertices of the random graph.
density (float) – Density of the random adjacency matrix.
seed (int) – Seed for random graph generation.

Return type:

MISProblem

classmethod from_watts_strogatz(num_vertices, num_neighbors, connection_prob, seed=0)

Instantiate a new MIS problem, based on a random Watts-Strogatz graph sampled with the given parameters.

Parameters:

num_vertices (int) – Number of vertices of the random graph.
num_neighbors (int) – Each node is joined with its k nearest neighbors.
connection_prob (float) – Connection probability between different vertices.
seed (int) – Seed for random graph generation.

Return type:

MISProblem

get_as_qubo(w_diag=1, w_off=4)

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_qubo_matrix(w_diag=1, w_off=4)

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_edges: int: Returns the number of edges in the graph.

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