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

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

    Minimum number of nodes.

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

    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.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_nodes/max_nodes, by default None.

Returns:

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:

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