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 | None = None, max_pattern: int | None = None, target_extra: int = 2, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> InducedSubgraphIsomorphismCollection classmethod

Generate random Induced Subgraph Isomorphism instances.

Parameters:

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

    Minimum number of pattern nodes.

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

    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.

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

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

Returns:

Examples:

>>> collection = InducedSubgraphIsomorphismCollection.from_random(
...     min_pattern=3,
...     max_pattern=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: