Subgraph Isomorphism API Reference

Data

Data model for Subgraph Isomorphism use case.

`SubgraphIsomorphismData`

Bases: UcData

Data for the Subgraph Isomorphism use case.

Determines whether a smaller graph (pattern) can be found as a subgraph of a larger graph (target), preserving edges.

Attributes:

Name	Type	Description
`name`	`Literal['subgraph_isomorphism']`	Identifier for this data type.
`adjacency_matrix_pattern`	`BinAdjMatrix`	Symmetric binary adjacency matrix of the pattern (smaller) graph.
`adjacency_matrix_target`	`BinAdjMatrix`	Symmetric binary adjacency matrix of the target (larger) graph.
`node_names_pattern`	`list[int \| str]`	Node identifiers for the pattern graph.
`node_names_target`	`list[int \| str]`	Node identifiers for the target graph.

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

Plot the pattern graph.

Parameters:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

`to_string() -> str`

Format the data as a human-readable string.

Returns:

Type	Description
`str`	String representation of the data.

`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]) -> SubgraphIsomorphismData` `staticmethod`

Create data from pattern and target adjacency matrices.

Parameters:

Name	Type	Description	Default
`adjacency_matrix_pattern`	`ndarray`	Adjacency matrix of the pattern graph.	required
`adjacency_matrix_target`	`ndarray`	Adjacency matrix of the target graph.	required
`node_names_pattern`	`list[int \| str]`	Node identifiers for the pattern graph.	required
`node_names_target`	`list[int \| str]`	Node identifiers for the target graph.	required

Returns:

Type	Description
`SubgraphIsomorphismData`	The data instance.

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

Generate a random instance with guaranteed subgraph.

Creates a target graph and embeds the pattern as a subgraph.

Parameters:

Name	Type	Description	Default
`n_pattern`	`int`	Number of pattern nodes, by default 3.	`3`
`n_target`	`int`	Number of target nodes, by default 5.	`5`
`edge_prob`	`float`	Edge probability for extra target edges, by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed, by default None.	`None`

Returns:

Type	Description
`SubgraphIsomorphismData`	A randomly generated data instance.

Examples:

>>> data = SubgraphIsomorphismData.generate_random(seed=42)

Formulation

Formulation for Subgraph Isomorphism use case.

`SubgraphIsomorphismFormulation`

Bases: UcFormulation[SubgraphIsomorphismData, SubgraphIsomorphismSolution]

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

Mathematical Formulation

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

Decision Variables:
    x[i,j] in {0,1} -- 1 if pattern node i maps to target node j.

Objective:
    None (feasibility problem)

Constraints:
    1. Each pattern node maps i to exactly one target node j:
       sum_j x[i,j] == 1

    2. Each target node mapped from at most one pattern node:
       sum_i x[i,j] <= 1

    3. Edge preservation (undirected):
       For each edge (i,k) in the pattern with i < k and each non-edge (j,m)
       in the target with j < m:

           x[i,j] + x[k,m] <= 1

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

Format the formulation as a string.

Parameters:

Name	Type	Description	Default
`data`	`SubgraphIsomorphismData`	The problem data.	required

Returns:

Type	Description
`str`	Formatted description of the formulation.

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

Formulate the Subgraph Isomorphism problem (undirected graphs).

Parameters:

Name	Type	Description	Default
`data`	`SubgraphIsomorphismData`	The problem data.	required

Returns:

Type	Description
`Model`	A LunaModel ready to be solved.

`interpret(solution: Solution, data: SubgraphIsomorphismData) -> SubgraphIsomorphismSolution` `staticmethod`

Extract a Subgraph Isomorphism solution from the solver result.

Solution

Solution model for Subgraph Isomorphism use case.

`SubgraphIsomorphismSolution`

Bases: UcSolution

Solution for the Subgraph Isomorphism use case.

Attributes:

Name	Type	Description
`name`	`Literal['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 subgraph isomorphism.

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

Plot the subgraph isomorphism mapping.

Parameters:

Name	Type	Description	Default
`data`	`SubgraphIsomorphismData \| 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 SubgraphIsomorphism use case.

`SubgraphIsomorphismInstance`

Bases: UcInstance[SubgraphIsomorphismData, SubgraphIsomorphismFormulation, SubgraphIsomorphismSolution]

Instance combining data and formulation for SubgraphIsomorphism.

Collection

Collection of Subgraph Isomorphism instances.

`SubgraphIsomorphismCollection`

Bases: UcInstanceCollection[SubgraphIsomorphismInstance]

Collection of 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) -> SubgraphIsomorphismCollection` `classmethod`

Generate random 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
`SubgraphIsomorphismCollection`	Collection containing generated instances.

Examples:

>>> collection = SubgraphIsomorphismCollection.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.

Subgraph Isomorphism API Reference

Data

SubgraphIsomorphismData

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]) -> SubgraphIsomorphismData staticmethod

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

Formulation

SubgraphIsomorphismFormulation

to_string(data: SubgraphIsomorphismData) -> str staticmethod

formulate(data: SubgraphIsomorphismData) -> Model staticmethod

interpret(solution: Solution, data: SubgraphIsomorphismData) -> SubgraphIsomorphismSolution staticmethod

Solution

SubgraphIsomorphismSolution

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

to_string() -> str

Instance

SubgraphIsomorphismInstance

Collection

SubgraphIsomorphismCollection

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) -> SubgraphIsomorphismCollection classmethod

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

`SubgraphIsomorphismData`

`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]) -> SubgraphIsomorphismData` `staticmethod`

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

`SubgraphIsomorphismFormulation`

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

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

`interpret(solution: Solution, data: SubgraphIsomorphismData) -> SubgraphIsomorphismSolution` `staticmethod`

`SubgraphIsomorphismSolution`

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

`to_string() -> str`

`SubgraphIsomorphismInstance`

`SubgraphIsomorphismCollection`

`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) -> SubgraphIsomorphismCollection` `classmethod`

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