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 (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:

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

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

Returns:

  • Axes | tuple[Axes, Axes] –

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

to_string() -> str

Return a compact textual summary of the instance.

Returns:

  • 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:

  • adjacency_matrix_pattern (ndarray) –

    Pattern adjacency matrix.

  • adjacency_matrix_target (ndarray) –

    Target adjacency matrix.

  • node_names_pattern (list[int | str]) –

    Pattern node labels.

  • node_names_target (list[int | str]) –

    Target node labels.

Returns:

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:

  • n_pattern (int, default: 3 ) –

    Number of pattern nodes.

  • n_target (int, default: 5 ) –

    Number of target nodes.

  • edge_prob (float, default: 0.5 ) –

    Probability of edge creation in the pattern graph.

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

    Random seed.

Returns:

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:

Returns:

  • str –

    Description of the model size and structure.

formulate(data: InducedSubgraphIsomorphismData) -> Model staticmethod

Build the optimization model.

Parameters:

Returns:

  • Model –

    Configured Luna optimization model.

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

Extract a structured solution from solver output.

Parameters:

Returns:

Raises:

Solution

Solution model for Induced Subgraph Isomorphism use case.

InducedSubgraphIsomorphismSolution

Bases: UcSolution

Solution for the Induced Subgraph Isomorphism use case.

Attributes:

  • 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:

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

    Problem data. Required.

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

    Matplotlib axes to draw on.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Format the solution as a human-readable string.

Returns:

  • 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:

  • min_pattern (int) –

    Minimum number of pattern nodes.

  • max_pattern (int) –

    Maximum number of pattern nodes.

  • target_extra (int, default: 2 ) –

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

  • edge_prob (float, default: 0.5 ) –

    Edge probability for pattern graph, by default 0.5.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

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