mis.shared.types

source module mis.shared.types

Classes

• MethodType — The method used to extract the MIS.

• Weighting — The algorithm used by the solver.

• MISInstance

• MISSolution — A solution to a MIS problem.

source enum MethodType()

Bases : str, Enum

The method used to extract the MIS.

Attributes

• EAGER — An eager solver that attempts to extract a MIS in a single shot.

• GREEDY — A greedy solver that decomposes the graph into smaller subgraphs that can benefit from device-specific physical layouts.

source enum Weighting()

Bases : str, Enum

The algorithm used by the solver.

Attributes

• UNWEIGHTED — Unweighted Maximum Independent Set

• WEIGHTED — Weighted Maximum Independent Set

source class MISInstance(graph: networkx.Graph)

Methods

• to_qubo — Convert a MISInstance to a qubo matrix.

• draw — Draw instance graph with highlighted nodes.

• node_index — Return the index for a node in the original graph.

• node_indices — Return the indices for nodes in the original graph.

source method MISInstance.to_qubo(penalty: float | None = None) → np.ndarray

Convert a MISInstance to a qubo matrix.

QUBO formulation

Minimize: Q(x) = -∑{i ∈ V} w_i x_i + λ ∑ x_i x_j

Parameters

• penalty : float, optional — Penalty factor. Defaults to None.

Raises

• ValueError — When penalty is strictly inferior to 2 x max(weight).

Returns

• np.ndarray — The QUBO matrix formulation of MIS.

source method MISInstance.draw(nodes: list[int] | None = None, node_size: int = 600, highlight_color: str = 'darkgreen', font_family: str = 'serif') → None

Draw instance graph with highlighted nodes.

Parameters

• ```

• nodes : list[int] — List of nodes to highlight.

• node_size : int — Size of drawn nodes in drawn graph. (default: 600)

• highlight_color : str — Color to highlight nodes with. (default: "darkgreen")

• ```

Raises

• Exception

source method MISInstance.node_index(node: Any) → int

Return the index for a node in the original graph.

source method MISInstance.node_indices(nodes: list[Any]) → list[int]

Return the indices for nodes in the original graph.

source class MISSolution(instance: MISInstance, nodes: list[int], frequency: float)

A solution to a MIS problem.

Attributes

• instance : MISInstance — The MIS instance to which this class represents a solution.

• size : int — The number of nodes in this solution.

• node_indices : list[int] — The indices of the nodes of instance picked in this solution.

• nodes : list[Any] — The nodes of instance picked in this solution.

• frequency : float — How often this solution showed up in the measures, where 0. represents a solution that never showed up in the meaures and 1. a solution that showed up in all measures.

Methods

• draw — Draw instance graph with solution nodes highlighted.

source method MISSolution.draw(node_size: int = 600, highlight_color: str = 'darkgreen', font_family: str = 'serif') → None

Draw instance graph with solution nodes highlighted.

Parameters

• ```

• node_size : int — Size of drawn nodes in drawn graph. (default: 600)

• highlight_color : str — Color to highlight solution nodes with. (default: "darkgreen")

• font : str — Font type

• ```