maxcut_generator

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, weighted=False, distribution_of_weights='uniform', maximum=1.0)[source]#

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

  • weighted (bool) – True iff we want to generate weighted maxcut instances (as opposed to unweighted maxcut).

  • distribution_of_weights (Literal['uniform', 'integers']) – A string describing the distribution of the random weights in case weighted maxcu is generated. Otherwise ignored.

  • maximum (int | float) – A parameter of the distribution used if the distribution is “uniform” or “integers”, otherwise it’s ignored.

Yields:

Problem instances of MaxCutInstance randomly constructed in accordance to the input parameters. Or instances of WeightedMaxCutInstance if weighted is True.

Return type:

Iterator[MaxCutInstance | WeightedMaxCutInstance]

Contents