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 Type Description
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:

Name Type Description Default
ax Axes | None

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

 None

Returns:

Type Description
Axes

The axes containing both graphs.

to_string() -> str

Format the data as a human-readable string.

Returns:

Type Description
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:

Name Type Description Default
adjacency_matrix_1 ndarray

Adjacency matrix of graph 1.

 required
adjacency_matrix_2 ndarray

Adjacency matrix of graph 2.

 required
node_names_1 list[int | str]

Node names for graph 1.

 required
node_names_2 list[int | str]

Node names for graph 2.

 required
mapping_weights ndarray | None

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

 None

Returns:

Type Description
LmwcsData

The data instance.

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:

Name Type Description Default
n1 int

Number of nodes in graph 1, by default 4.

 4
n2 int

Number of nodes in graph 2, by default 4.

 4
edge_prob float

Edge probability, by default 0.5.

 0.5
seed int | None

Random seed.

 None

Returns:

Type Description
LmwcsData

Randomly generated instance.

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:

Name Type Description Default
data LmwcsData

The problem data.

 required

Returns:

Type Description
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:

Name Type Description Default
data LmwcsData

The problem data.

 required

Returns:

Type Description
Model

A Luna Model ready to be solved.

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

Extract a LMWCS solution from the solver result.

Parameters:

Name Type Description Default
solution Solution

The solver solution.

 required
data LmwcsData

The original problem data.

 required

Returns:

Type Description
LmwcsSolution

Structured solution.

Raises:

Type Description
NoSolutionFoundError

If the solver did not find any solution.

Solution

Solution model for LMWCS use case.

LmwcsSolution

Bases: UcSolution

Solution for the LMWCS use case.

Attributes:

Name Type Description
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:

Name Type Description Default
data LmwcsData | None

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

 None
ax Axes | None

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

 None

Returns:

Type Description
Axes

The axes containing the combined visualization of both graphs.

Raises:

Type Description
ValueError

If data is None.
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:

Type Description
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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> LmwcsCollection classmethod

Generate random LMWCS instances.

Parameters:

Name Type Description Default
min_nodes int

Minimum number of nodes per graph.

 required
max_nodes int

Maximum number of nodes per graph.

 required
edge_prob float

Edge probability, by default 0.5.

 0.5
num_instances int

Number of instances per size, by default 1.

 1
seed int | None

Random seed, by default None.

 None

Returns:

Type Description
LmwcsCollection

Collection containing generated instances.

Examples:

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