Skip to content

LMWCS API Reference

Data

Data model for LMWCS use case.

LmwcsData

Bases: UcData

Data for the Largest Maximum Weighted Common Subgraph use case.

Finds the largest weighted common subgraph between two graphs, where each possible node mapping has an associated weight.

Attributes:

  • name (Literal['largest_mapping_of_weighted_common_subgraph']) –

    Identifier.

  • adjacency_matrix_1 (SymMatrix) –

    Symmetric adjacency matrix of graph 1.

  • adjacency_matrix_2 (SymMatrix) –

    Symmetric adjacency matrix of graph 2.

  • node_names_1 (list[int | str]) –

    Node identifiers for graph 1.

  • node_names_2 (list[int | str]) –

    Node identifiers for graph 2.

  • mapping_weights (NumPyArray) –

    Weight matrix (n1 x n2) for mapping node i to node j.

plot(*, ax: Axes | None = None) -> Axes

Plot both graphs on a single axes.

Parameters:

  • ax (Axes | None, default: None ) –

    The axes to draw on. If None, a new figure is created.

Returns:

  • Axes –

    The axes containing both graphs.

to_string() -> str

Format the data as a human-readable string.

Returns:

  • str –

    String representation.

from_adjacency_matrices(adjacency_matrix_1: np.ndarray, adjacency_matrix_2: np.ndarray, node_names_1: list[int | str], node_names_2: list[int | str], mapping_weights: np.ndarray | None = None) -> LmwcsData staticmethod

Create data from adjacency matrices and optional weights.

Parameters:

  • adjacency_matrix_1 (ndarray) –

    Adjacency matrix of graph 1.

  • adjacency_matrix_2 (ndarray) –

    Adjacency matrix of graph 2.

  • node_names_1 (list[int | str]) –

    Node names for graph 1.

  • node_names_2 (list[int | str]) –

    Node names for graph 2.

  • mapping_weights (ndarray | None, default: None ) –

    Weight for mapping node i to j. Defaults to ones.

Returns:

generate_random(n1: int = 4, n2: int = 4, edge_prob: float = 0.5, seed: int | None = None) -> LmwcsData staticmethod

Generate a random LMWCS instance.

Creates two random graphs with some shared structure.

Parameters:

  • n1 (int, default: 4 ) –

    Number of nodes in graph 1, by default 4.

  • n2 (int, default: 4 ) –

    Number of nodes in graph 2, by default 4.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, by default 0.5.

  • seed (int | None, default: None ) –

    Random seed.

Returns:

Examples:

>>> data = LmwcsData.generate_random(seed=42)

Formulation

Formulation for LMWCS use case.

LmwcsFormulation

Bases: UcFormulation[LmwcsData, LmwcsSolution]

Constraint-based formulation for LMWCS.

This formulation finds a non-induced subgraph embedding of G1 into G2: G1 is embedded into G2, meaning every edge in G1 must be preserved in G2, but G2 may contain additional edges between mapped nodes that do not exist in G1. As a result, mapped nodes in G2 can have higher degrees than their counterparts in G1.

Mathematical Formulation 
Decision Variables:
    x[i,j] in {0, 1} -- G1 node i mapped to G2 node j.

Objective:
    maximize sum_{i,j} w[i,j] * x[i,j]

Constraints:
    1. Each G1 node at most one mapping: sum_j x[i,j] <= 1
    2. Each G2 node at most one mapping: sum_i x[i,j] <= 1
    3. Non-induced edge consistency: for each edge (i,k) in G1, the
       corresponding G2 nodes must also be connected. Extra edges in G2
       between mapped nodes are permitted.
       For edge (i,k) in G1, non-edge (j,m) in G2: x[i,j] + x[k,m] <= 1

Note:
    This is a non-induced embedding (G1 -> G2), not a classical common
    subgraph isomorphism. In an induced formulation, edges in G2 between
    mapped nodes would also be required to exist in G1. Here, isolated
    nodes in G1 may be mapped to high-degree nodes in G2, and the
    solution may therefore look asymmetric when visualized.

to_string(data: LmwcsData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description.

formulate(data: LmwcsData) -> Model staticmethod

Formulate the LMWCS problem as a non-induced subgraph embedding.

G1 is embedded into G2: every edge in G1 must map to an edge in G2, but additional edges in G2 between mapped nodes are permitted.

Parameters:

Returns:

  • Model –

    A LunaModel ready to be solved.

interpret(solution: Solution, data: LmwcsData) -> LmwcsSolution staticmethod

Extract a LMWCS solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (LmwcsData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for LMWCS use case.

LmwcsSolution

Bases: UcSolution

Solution for the LMWCS use case.

Attributes:

  • name (Literal['largest_mapping_of_weighted_common_subgraph']) –

    Identifier.

  • mapping (list[tuple[int | str, int | str]]) –

    Matched node pairs (G1 node, G2 node).

  • total_weight (float) –

    Sum of mapping weights.

  • is_valid (bool) –

    Whether the mapping preserves edges.

plot(data: LmwcsData | None = None, *, ax: Axes | None = None) -> Axes

Plot the LMWCS solution on a single axes with both graphs side by side.

Both input graphs (G1 and G2) are embedded into a shared coordinate system using a spring layout and horizontally separated for visual comparison. Nodes that are part of the mapping are highlighted, and their labels are augmented to show the corresponding matched node in the other graph.

Parameters:

  • data (LmwcsData | None, default: None ) –

    Problem data containing adjacency matrices and node names for both graphs. Required.

  • ax (Axes | None, default: None ) –

    The axes to draw on. If None, a new figure and axes are created.

Returns:

  • Axes –

    The axes containing the combined visualization of both graphs.

Raises:

Notes
  • G1 is rendered on the left, G2 on the right, separated by a vertical line.
  • Node colors indicate whether a node is part of the LMWCS mapping.
  • Node labels are extended to show correspondences (e.g. u→v).
  • The layout is deterministic due to a fixed random seed.
  • Axes and ticks are hidden since the layout has no physical meaning.

to_string() -> str

Format the solution as a human-readable string.

Returns:

  • str –

    String representation.

Instance

Instance model for LMWCS use case.

LmwcsInstance

Bases: UcInstance[LmwcsData, LmwcsFormulation, LmwcsSolution]

Instance combining data and formulation for LMWCS.

Collection

Collection of LMWCS instances.

LmwcsCollection

Bases: UcInstanceCollection[LmwcsInstance]

Collection of LMWCS instances.

Provides methods to generate benchmark instances.

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> LmwcsCollection classmethod

Generate random LMWCS instances.

Parameters:

  • min_nodes (int | None, default: None ) –

    Minimum number of nodes per graph.

  • max_nodes (int | None, default: None ) –

    Maximum number of nodes per graph.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, by default 0.5.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed, by default None.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_nodes/max_nodes, by default None.

Returns:

Examples:

>>> collection = LmwcsCollection.from_random(
...     min_nodes=3,
...     max_nodes=5,
...     num_instances=2,
...     seed=42,
... )

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: