Skip to content

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

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

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Format the data as a human-readable string.

Returns:

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

  • adjacency_matrix_pattern (ndarray) –

    Adjacency matrix of the pattern graph.

  • adjacency_matrix_target (ndarray) –

    Adjacency matrix of the target 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.

Returns:

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:

  • n_pattern (int, default: 3 ) –

    Number of pattern nodes, by default 3.

  • n_target (int, default: 5 ) –

    Number of target nodes, by default 5.

  • edge_prob (float, default: 0.5 ) –

    Edge probability for extra target edges, by default 0.5.

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

    Random seed, by default None.

Returns:

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:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: SubgraphIsomorphismData) -> Model staticmethod

Formulate the Subgraph Isomorphism problem (undirected graphs).

Parameters:

Returns:

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

  • data (SubgraphIsomorphismData | 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 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:

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

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