Skip to content

Induced Subgraph Isomorphism API Reference

Data

Data model for Induced Subgraph Isomorphism use case.

InducedSubgraphIsomorphismData

Bases: UcData

Data for the Induced Subgraph Isomorphism use case.

Problem Description

Determines whether a smaller graph (pattern) appears as an induced subgraph of a larger graph (target).

In contrast to standard subgraph isomorphism, an induced embedding requires preservation of both: - edges - non-edges

Formally, for a mapping f : V_P -> V_T: A_P[i,k] == A_T[f(i), f(k)] for all i < k

Attributes:

Name Type Description
name Literal['induced_subgraph_isomorphism']

Identifier for this data type.
adjacency_matrix_pattern BinAdjMatrix

Symmetric binary adjacency matrix of the pattern graph.
adjacency_matrix_target BinAdjMatrix

Symmetric binary adjacency matrix of the target graph.
node_names_pattern list[int | str]

Node identifiers of the pattern graph.
node_names_target list[int | str]

Node identifiers of the target graph.

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

Visualize pattern and target graphs.

If no axes are provided, both graphs are plotted side-by-side for direct comparison.

Parameters:

Name Type Description Default
ax Axes | None

Optional axes object. If provided, only the pattern graph is drawn onto this axis.

 None

Returns:

Type Description
Axes | tuple[Axes, Axes]

Single axis (pattern only) or tuple (pattern, target).

to_string() -> str

Return a compact textual summary of the instance.

Returns:

Type Description
str

Summary including number of nodes and edges.

from_adjacency_matrices(adjacency_matrix_pattern: np.ndarray, adjacency_matrix_target: np.ndarray, node_names_pattern: list[int | str], node_names_target: list[int | str]) -> InducedSubgraphIsomorphismData staticmethod

Construct instance from adjacency matrices.

Parameters:

Name Type Description Default
adjacency_matrix_pattern ndarray

Pattern adjacency matrix.

 required
adjacency_matrix_target ndarray

Target adjacency matrix.

 required
node_names_pattern list[int | str]

Pattern node labels.

 required
node_names_target list[int | str]

Target node labels.

 required

Returns:

Type Description
InducedSubgraphIsomorphismData

Data instance.

generate_random(n_pattern: int = 3, n_target: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> InducedSubgraphIsomorphismData staticmethod

Generate a random instance with guaranteed induced embedding.

Construction strategy: 1. Generate a random pattern graph. 2. Embed it into the first n_pattern nodes of the target. 3. Add edges ONLY involving nodes outside the embedded pattern.

This guarantees: The induced subgraph on the embedded nodes is identical to the pattern graph.

Parameters:

Name Type Description Default
n_pattern int

Number of pattern nodes.

 3
n_target int

Number of target nodes.

 5
edge_prob float

Probability of edge creation in the pattern graph.

 0.5
seed int | None

Random seed.

 None

Returns:

Type Description
InducedSubgraphIsomorphismData

Random instance with guaranteed solution.

Formulation

Formulation for Induced Subgraph Isomorphism use case.

InducedSubgraphIsomorphismFormulation

Bases: UcFormulation[InducedSubgraphIsomorphismData, InducedSubgraphIsomorphismSolution]

Constraint-based formulation for Induced Subgraph Isomorphism (undirected graphs).

Problem Description

Given a pattern graph G_P = (V_P, E_P) and a target graph G_T = (V_T, E_T), determine whether G_P is isomorphic to an induced subgraph of G_T.

An induced subgraph isomorphism is an injective mapping:

f : V_P -> V_T

such that for all node pairs (i,k) with i < k:

(i,k) in E_P  <=>  (f(i), f(k)) in E_T

That is, both edges and non-edges must be preserved.

Mathematical Formulation

Index: i, k -- pattern node indices with i < k j, m -- target node indices with j < m

Decision Variables: x[i,j] in {0,1} x[i,j] = 1 if pattern node i is mapped to target node j

Objective: None (feasibility problem)

Constraints: 1. Node assignment (total mapping): sum_j x[i,j] == 1 for all i

2. Injectivity:
    sum_i x[i,j] <= 1    for all j

3. Edge preservation:
    For each edge (i,k) in pattern and each non-edge {j,m} in target:
        x[i,j] + x[k,m] <= 1
        x[i,m] + x[k,j] <= 1

4. Non-edge preservation (induced constraint):
    For each non-edge (i,k) in pattern and each edge (j,m) in target:

        x[i,j] + x[k,m] <= 1
Notes
  • The formulation assumes undirected graphs.
  • Only pairs with j < m are considered to avoid duplicate constraints.
  • This is a pure feasibility problem; no objective function is required.

to_string(data: InducedSubgraphIsomorphismData) -> str staticmethod

Format the formulation as a human-readable string.

Parameters:

Name Type Description Default
data InducedSubgraphIsomorphismData

The problem data.

 required

Returns:

Type Description
str

Description of the model size and structure.

formulate(data: InducedSubgraphIsomorphismData) -> Model staticmethod

Build the optimization model.

Parameters:

Name Type Description Default
data InducedSubgraphIsomorphismData

Problem instance.

 required

Returns:

Type Description
Model

Configured Luna optimization model.

interpret(solution: Solution, data: InducedSubgraphIsomorphismData) -> InducedSubgraphIsomorphismSolution staticmethod

Extract a structured solution from solver output.

Parameters:

Name Type Description Default
solution Solution

Solver output.

 required
data InducedSubgraphIsomorphismData

Original problem instance.

 required

Returns:

Type Description
InducedSubgraphIsomorphismSolution

Mapping and validity flag.

Raises:

Type Description
NoSolutionFoundError

If no solution was found.

Solution

Solution model for Induced Subgraph Isomorphism use case.

InducedSubgraphIsomorphismSolution

Bases: UcSolution

Solution for the Induced Subgraph Isomorphism use case.

Attributes:

Name Type Description
name Literal['induced_subgraph_isomorphism']

Identifier.
mapping dict[int | str, int | str]

Mapping from pattern nodes to target nodes.
is_valid bool

Whether the mapping is a valid induced subgraph isomorphism.

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

Plot the induced subgraph isomorphism mapping.

Parameters:

Name Type Description Default
data InducedSubgraphIsomorphismData | None

Problem data. Required.

 None
ax Axes | None

Matplotlib axes to draw on.

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

to_string() -> str

Format the solution as a human-readable string.

Returns:

Type Description
str

String representation of the solution.

Instance

Instance model for InducedSubgraphIsomorphism use case.

InducedSubgraphIsomorphismInstance

Bases: UcInstance[InducedSubgraphIsomorphismData, InducedSubgraphIsomorphismFormulation, InducedSubgraphIsomorphismSolution]

Instance combining data and formulation for InducedSubgraphIsomorphism.

Collection

Collection of Induced Subgraph Isomorphism instances.

InducedSubgraphIsomorphismCollection

Bases: UcInstanceCollection[InducedSubgraphIsomorphismInstance]

Collection of Induced Subgraph Isomorphism instances.

Provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_pattern: int, max_pattern: int, target_extra: int = 2, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> InducedSubgraphIsomorphismCollection classmethod

Generate random Induced Subgraph Isomorphism instances.

Parameters:

Name Type Description Default
min_pattern int

Minimum number of pattern nodes.

 required
max_pattern int

Maximum number of pattern nodes.

 required
target_extra int

Extra nodes in target beyond pattern size, by default 2.

 2
edge_prob float

Edge probability for pattern graph, by default 0.5.

 0.5
num_instances int

Number of instances per size, by default 1.

 1
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
InducedSubgraphIsomorphismCollection

Collection containing generated instances.

Examples:

>>> collection = InducedSubgraphIsomorphismCollection.from_random(
...     min_pattern=3,
...     max_pattern=5,
...     num_instances=2,
...     seed=42,
... )