Graph Isomorphism API Reference

Data

Data model for Graph Isomorphism use case.

`GraphIsomorphismData`

Bases: UcData

Data for the Graph Isomorphism use case.

Determines whether two graphs are isomorphic, i.e., whether there exists a bijection between their node sets that preserves adjacency.

Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists a bijection:

f : V1 -> V2

such that for all node pairs (i,k):

(i,k) in E1  <=>  (f(i), f(k)) in E2

Attributes:

Name	Type	Description
`name`	`Literal['graph_isomorphism']`	Identifier for this data type.
`adjacency_matrix_1`	`BinAdjMatrix`	Symmetric binary adjacency matrix of graph 1.
`adjacency_matrix_2`	`BinAdjMatrix`	Symmetric binary adjacency matrix of graph 2.
`node_names_1`	`list[int \| str]`	Node identifiers for graph 1.
`node_names_2`	`list[int \| str]`	Node identifiers for graph 2.

Notes

Graphs are assumed to be undirected.
Graph isomorphism requires both graphs to have the same number of nodes.

`model_post_init(__context: object) -> None`

Validate graph dimensions after initialization.

Raises:

Type	Description
`ValueError`	If graph sizes or node counts are inconsistent.

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

Plot both graphs side by side with a vertical divider.

If ax is provided, only graph 1 is drawn onto it. Otherwise a new figure with both graphs is created.

Parameters:

Name	Type	Description	Default
`ax`	`Axes \| None`	Optional axes to draw graph 1 on. If `None`, a new figure with both graphs is created.	`None`

Returns:

Type	Description
`Axes`	The left axes (graph 1).

`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_1: NDArray[np.float64], adjacency_matrix_2: NDArray[np.float64], node_names_1: list[int | str], node_names_2: list[int | str]) -> GraphIsomorphismData` `staticmethod`

Create data from adjacency matrices.

Parameters:

Name	Type	Description	Default
`adjacency_matrix_1`	`NDArray[float64]`	Adjacency matrix of graph 1.	required
`adjacency_matrix_2`	`NDArray[float64]`	Adjacency matrix of graph 2.	required
`node_names_1`	`list[int \| str]`	Node labels for graph 1.	required
`node_names_2`	`list[int \| str]`	Node labels for graph 2.	required

Returns:

Type	Description
`GraphIsomorphismData`	Constructed data instance.

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> GraphIsomorphismData` `staticmethod`

Generate a random isomorphic graph pair.

Creates a random graph and a randomly permuted copy, guaranteeing graph isomorphism.

Parameters:

Name	Type	Description	Default
`n_nodes`	`int`	Number of graph nodes, by default 5.	`5`
`edge_prob`	`float`	Probability of an edge between any two nodes, by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`GraphIsomorphismData`	Random isomorphic graph instance.

Examples:

>>> data = GraphIsomorphismData.generate_random(n_nodes=4, seed=42)

Formulation

Formulation for Graph Isomorphism use case.

`GraphIsomorphismFormulation`

Bases: UcFormulation[GraphIsomorphismData, GraphIsomorphismSolution]

Formulation for Graph Isomorphism.

Problem Description

Given two undirected graphs:

G1 = (V1, E1)
G2 = (V2, E2)

determine whether they are isomorphic.

A graph isomorphism is a bijection:

f : V1 -> V2

such that for all node pairs:

(i,k) in E1
iff
(f(i), f(k)) in E2

Equivalently, adjacency must be preserved exactly.

Mathematical Formulation

Index:
    i, k -- graph 1 node indices with i < k
    j, m -- distinct graph 2 node indices with j != m

Decision Variables:
    x[i,j] in {0,1}

        x[i,j] = 1
        iff graph 1 node i is mapped
        to graph 2 node j

Objective:
    None (feasibility problem)

Constraints:
    1. Total mapping:
        Every graph 1 node maps to exactly one graph 2 node.

            sum_j x[i,j] == 1

    2. Bijectivity:
        Every graph 2 node is mapped from exactly one graph 1 node.

            sum_i x[i,j] == 1

    3. Edge preservation:
        Pattern edges may not map to graph 2 non-edges.

        For every edge (i,k) in G1 and every non-edge (j,m) in G2:

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

    4. Non-edge preservation:
        Pattern non-edges may not map to graph 2 edges.

        For every non-edge (i,k) in G1 and every edge (j,m) in G2:

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

Notes

Graphs are assumed to be undirected.
Both edge and non-edge preservation are required.
The formulation uses ordered target pairs (j,m) with j != m to correctly forbid both mapping orientations.
This is a pure feasibility problem.

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

Format the formulation as a human-readable string.

Parameters:

Name	Type	Description	Default
`data`	`GraphIsomorphismData`	Problem instance.	required

Returns:

Type	Description
`str`	Formatted formulation summary.

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

Build the graph isomorphism optimization model.

Parameters:

Name	Type	Description	Default
`data`	`GraphIsomorphismData`	Problem instance.	required

Returns:

Type	Description
`Model`	A Luna optimization model representing the graph isomorphism problem.

`interpret(solution: Solution, data: GraphIsomorphismData) -> GraphIsomorphismSolution` `staticmethod`

Extract a structured solution from solver output.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solution containing variable assignments.	required
`data`	`GraphIsomorphismData`	Original problem instance.	required

Returns:

Type	Description
`GraphIsomorphismSolution`	Structured mapping solution with validity check.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find a solution.

Solution

Solution model for Graph Isomorphism use case.

`GraphIsomorphismSolution`

Bases: UcSolution

Solution for the Graph Isomorphism use case.

Represents a bijective node mapping between two graphs.

Attributes:

Name	Type	Description
`name`	`Literal['graph_isomorphism']`	Identifier for this solution type.
`mapping`	`dict[int \| str, int \| str]`	Mapping from graph 1 nodes to graph 2 nodes.
`is_valid`	`bool`	Whether the mapping is a valid graph isomorphism.

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

Plot both graphs and visualize the node mapping.

Graph 1 and graph 2 are shown side-by-side. Corresponding mapped nodes share the same color to visually highlight the isomorphism.

Parameters:

Name	Type	Description	Default
`data`	`GraphIsomorphismData \| None`	Original problem data.	`None`
`ax`	`Axes \| None`	Optional axes. If provided, only graph 1 is drawn onto the given axes. Otherwise a new figure with two subplots is created.	`None`

Returns:

Type	Description
`tuple[Axes, Axes]`	Axes containing graph 1 and graph 2.

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 Graph Isomorphism use case.

`GraphIsomorphismInstance`

Bases: UcInstance[GraphIsomorphismData, GraphIsomorphismFormulation, GraphIsomorphismSolution]

Instance combining data and formulation for Graph Isomorphism.

Collection

Collection of Graph Isomorphism instances.

`GraphIsomorphismCollection`

Bases: UcInstanceCollection[GraphIsomorphismInstance]

Collection of Graph Isomorphism instances.

Provides methods to generate benchmark instances with various characteristics for testing and evaluation.

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphIsomorphismCollection` `classmethod`

Generate random Graph Isomorphism instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes.	`None`
`max_nodes`	`int \| None`	Maximum number of nodes.	`None`
`edge_prob`	`float`	Edge probability, 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_nodes`/`max_nodes`, by default None.	`None`

Returns:

Type	Description
`GraphIsomorphismCollection`	Collection containing generated instances.

Examples:

>>> collection = GraphIsomorphismCollection.from_random(
...     min_nodes=3,
...     max_nodes=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.

Graph Isomorphism API Reference

Data

GraphIsomorphismData

model_post_init(__context: object) -> None

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

to_string() -> str

from_adjacency_matrices(adjacency_matrix_1: NDArray[np.float64], adjacency_matrix_2: NDArray[np.float64], node_names_1: list[int | str], node_names_2: list[int | str]) -> GraphIsomorphismData staticmethod

generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> GraphIsomorphismData staticmethod

Formulation

GraphIsomorphismFormulation

to_string(data: GraphIsomorphismData) -> str staticmethod

formulate(data: GraphIsomorphismData) -> Model staticmethod

interpret(solution: Solution, data: GraphIsomorphismData) -> GraphIsomorphismSolution staticmethod

Solution

GraphIsomorphismSolution

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

to_string() -> str

Instance

GraphIsomorphismInstance

Collection

GraphIsomorphismCollection

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphIsomorphismCollection classmethod

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

`GraphIsomorphismData`

`model_post_init(__context: object) -> None`

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

`to_string() -> str`

`from_adjacency_matrices(adjacency_matrix_1: NDArray[np.float64], adjacency_matrix_2: NDArray[np.float64], node_names_1: list[int | str], node_names_2: list[int | str]) -> GraphIsomorphismData` `staticmethod`

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> GraphIsomorphismData` `staticmethod`

`GraphIsomorphismFormulation`

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

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

`interpret(solution: Solution, data: GraphIsomorphismData) -> GraphIsomorphismSolution` `staticmethod`

`GraphIsomorphismSolution`

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

`to_string() -> str`

`GraphIsomorphismInstance`

`GraphIsomorphismCollection`

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GraphIsomorphismCollection` `classmethod`

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