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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphIsomorphismCollection` `classmethod`

Generate random Graph Isomorphism instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int`	Minimum number of nodes.	required
`max_nodes`	`int`	Maximum number of nodes.	required
`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`

Returns:

Type	Description
`GraphIsomorphismCollection`	Collection containing generated instances.

Examples:

>>> collection = GraphIsomorphismCollection.from_random(
...     min_nodes=3,
...     max_nodes=5,
...     num_instances=2,
...     seed=42,
... )

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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphIsomorphismCollection classmethod

`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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> GraphIsomorphismCollection` `classmethod`