Skip to content

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

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

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

    Optional axes to draw graph 1 on. If None, a new figure with both graphs is created.

Returns:

  • Axes –

    The left axes (graph 1).

to_string() -> str

Format the data as a human-readable string.

Returns:

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

  • adjacency_matrix_1 (NDArray[float64]) –

    Adjacency matrix of graph 1.

  • adjacency_matrix_2 (NDArray[float64]) –

    Adjacency matrix of graph 2.

  • node_names_1 (list[int | str]) –

    Node labels for graph 1.

  • node_names_2 (list[int | str]) –

    Node labels for graph 2.

Returns:

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:

  • n_nodes (int, default: 5 ) –

    Number of graph nodes, by default 5.

  • edge_prob (float, default: 0.5 ) –

    Probability of an edge between any two nodes, by default 0.5.

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

    Random seed for reproducibility, by default None.

Returns:

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:

Returns:

  • str –

    Formatted formulation summary.

formulate(data: GraphIsomorphismData) -> Model staticmethod

Build the graph isomorphism optimization model.

Parameters:

Returns:

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

  • solution (Solution) –

    The solution containing variable assignments.

  • data (GraphIsomorphismData) –

    Original problem instance.

Returns:

Raises:

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

  • data (GraphIsomorphismData | None, default: None ) –

    Original problem data.

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

    Optional axes. If provided, only graph 1 is drawn onto the given axes. Otherwise a new figure with two subplots is created.

Returns:

  • tuple[Axes, Axes] –

    Axes containing graph 1 and graph 2.

Raises:

to_string() -> str

Format the solution as a human-readable string.

Returns:

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

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, 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 = GraphIsomorphismCollection.from_random(
...     min_nodes=3,
...     max_nodes=5,
...     num_instances=2,
...     seed=42,
... )