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

  • min_pattern (int) –

    Minimum number of pattern nodes.

  • max_pattern (int) –

    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.

Returns:

Examples:

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