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 Luna Model 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, max_pattern: int, target_extra: int = 2, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> SubgraphIsomorphismCollection` `classmethod`

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

Examples:

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

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

`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, max_pattern: int, target_extra: int = 2, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> SubgraphIsomorphismCollection` `classmethod`