Crate network_isomorphism_solver 

Network Isomorphism Solver using Links Theory

This library provides algorithms for determining if two networks (represented as links) are isomorphic, meaning they are structurally identical via node relabeling.

Based on Links Theory, this implementation uses doublet-links (ordered pairs of references) as the fundamental data structure, replacing traditional graph theory concepts of vertices and edges with a unified link concept where “a link connects links”.

This library uses the links-notation crate for parsing Links Notation (LiNo) format, which is the standard notation for describing link structures.

Real-World Applications

• Drug Discovery: Compare molecular structures to identify similar compounds
• Circuit Verification: Check if two electronic circuit designs are equivalent
• Computer Vision: Match patterns in image structures for object recognition
• Social Network Analysis: Detect isomorphic substructures in user networks
• Cryptography: Zero-knowledge proofs relying on graph isomorphism hardness

Links Notation (LiNo) Examples

Networks can be described using Links Notation from the links-notation library:

// Doublet format (source target)
(1 2) (2 3) (3 1)

// Named links
(bond1: C1 C2) (bond2: C2 C3)

// Nested structures
((A B) (B C) (C A))

Example

use network_isomorphism_solver::{LinkNetwork, is_isomorphic};

let mut network1 = LinkNetwork::new();
network1.add_link(1, 2);
network1.add_link(2, 3);
network1.add_link(3, 1);

let mut network2 = LinkNetwork::new();
network2.add_link(10, 20);
network2.add_link(20, 30);
network2.add_link(30, 10);

assert!(is_isomorphic(&network1, &network2));

Re-exports

pub use links_notation;

Structs

DoubletLink

A doublet-link representing a connection between two link references. This is the fundamental building block in Links Theory: L → L²

IsomorphismResult

Result of an isomorphism check, containing the mapping if isomorphic.

LinkNetwork

A network of links representing interconnected structures.

Constants

VERSION

Package version (matches Cargo.toml version).

Functions

check_isomorphism

Checks if two link networks are isomorphic and returns the mapping.

contains_subnetwork

Checks if a network contains a subnetwork isomorphic to the pattern.

find_automorphisms

Finds all automorphisms of a network.

is_isomorphic

Checks if two link networks are isomorphic.

Type Aliases

LinkId

A unique identifier for a link in the network. In Links Theory, each link has its own reference enabling cross-references.