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

Name	Type	Description	Default
`min_pattern`	`int \| None`	Minimum number of pattern nodes.	`None`
`max_pattern`	`int \| None`	Maximum number of pattern nodes.	`None`
`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`
`sizes`	`Sequence[int] \| None`	Explicit sizes to generate, e.g. `[10, 50, 100]`, instead of a range. Mutually exclusive with `min_pattern`/`max_pattern`, 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,
... )

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

Name	Type	Description	Default
`max_runtime`	`float`	SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.	`3600`
`quiet`	`bool`	Suppress the SCIP solver output.	`True`

Returns:

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

Type	Description
`ValueError`	If `max_runtime` is not positive.

Induced Subgraph Isomorphism API Reference

Data

InducedSubgraphIsomorphismData

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

to_string() -> str

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

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

Formulation

InducedSubgraphIsomorphismFormulation

to_string(data: InducedSubgraphIsomorphismData) -> str staticmethod

formulate(data: InducedSubgraphIsomorphismData) -> Model staticmethod

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

Solution

InducedSubgraphIsomorphismSolution

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

to_string() -> str

Instance

InducedSubgraphIsomorphismInstance

Collection

InducedSubgraphIsomorphismCollection

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

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

`InducedSubgraphIsomorphismData`

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

`to_string() -> str`

`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`

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

`InducedSubgraphIsomorphismFormulation`

`to_string(data: InducedSubgraphIsomorphismData) -> str` `staticmethod`

`formulate(data: InducedSubgraphIsomorphismData) -> Model` `staticmethod`

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

`InducedSubgraphIsomorphismSolution`

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

`to_string() -> str`

`InducedSubgraphIsomorphismInstance`

`InducedSubgraphIsomorphismCollection`

`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`

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