maxcut_generator

iqm.applications.maxcut.maxcut_generator(n, n_instances, *, graph_family='erdos-renyi', p=0.5, d=3, break_z2=False, seed=None, enforce_connected=False, max_iterations=1000)

The generator function for generating random maxcut problem instances.

The generator yields maxcut 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 maxcut 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.

• break_z2 (bool) – Optional bool indicating whether the \(\mathbb{Z}_2\) symmetry should be explicitly broken in the problem instances.

• seed (int | None) – 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.

Yields:

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

Return type:

Iterator[MaxCutInstance]