iqm.applications.mis

Module containing the MIS problem instance class.

Two solvers for MIS problems are also provided:

• A simple and fast greedy solver.

• Exact solver based on Bron-Kerbosch algorithm to find a graph’s cliques.

Example

from iqm.applications.mis import MISInstance
from iqm.applications.mis import greedy_mis
from iqm.applications.mis import bron_kerbosch

my_mis_instance = MISInstance(my_graph, penalty = 2)  # Problem instance from a graph.
my_mis_instance.constraints_checker("101011000")  # Check if this corresponds to an independent set.

greedy_solution = greedy_mis(my_instance)  # Solution bitstring obtained from greedy.
bk_solution = bron_kerbosch(my_instance)  # Solution bitstring obtained from BK.

Functions

bron_kerbosch(mis_problem)	Bron-Kerbosch algorithm for finding the maximum independent set.
greedy_mis(mis_problem)	Standard greedy algorithm for maximum independent set problem class.

Classes

ISInstance(graph, penalty, objective)	The instance class for independent set problems on a graph with a custom cost function.
MISInstance(graph[, penalty])	The instance class for maximum independent set problems.
MaximumWeightISInstance(graph, penalty)	The instance class for maximum-weight independent set problems.

Inheritance