mis_generator

Contents

mis_generator#

iqm.applications.mis.mis_generator(n, n_instances, *, graph_family='erdos-renyi', p=0.5, d=3, seed=None, enforce_connected=False, max_iterations=1000, penalty=1)[source]#

The generator function for generating random MIS problem instances.

The generator yields MIS problem instances using random graphs, created according to the input parameters. If enforce_connected is set to True, then the resulting graphs are checked for connectivity and regenerated if the check fails. In that case, the output graphs are not strictly speaking Erdős–Rényi or uniformly random regular graphs anymore.

Parameters:

  • n (int) – The number of nodes of the graph.

  • n_instances (int) – The number of MIS instances to generate.

  • graph_family (Literal['regular', 'erdos-renyi']) – A string describing the random graph family to generate. Possible graph families include ‘erdos-renyi’ and ‘regular’.

  • p (float) – For the Erdős–Rényi graph, this is the edge probability. For other graph families, it’s ignored.

  • d (int) – For the random regular graph, this is the degree of each node in the graph. For other graph families, it’s ignored.

  • seed (int | None | Generator) – Optional random seed for generating the problem instances.

  • enforce_connected (bool) – True iff it is required that the random graphs are connected.

  • max_iterations (int) – In case enforce_connected is True, the function generates random graphs in a while loop until it finds a connected one. If it doesn’t find a connected one after max_iterations, it raises an error.

  • penalty (int) – The penalty to the energy for violating the independence constraint.

Yields:

Problem instances of MISInstance randomly constructed in accordance to the input parameters.

Return type:

Iterator[MISInstance]

Contents