A Rust library for determining network isomorphism using Links Theory concepts. This solver can check if two networks are structurally identical (isomorphic), find all automorphisms (symmetries), and detect subnetwork patterns.
Network isomorphism is a fundamental problem in computer science with applications across many domains:
- Drug Discovery: Comparing molecular structures to find similar compounds
- Circuit Verification: Checking if two circuit designs are functionally equivalent
- Computer Vision: Pattern matching in image recognition
- Social Network Analysis: Detecting community structures and fraud patterns
- Cryptography: Zero-knowledge proofs and graph-based cryptographic systems
This library uses Links Theory concepts where networks are represented as collections of doublet-links (ordered pairs of source and target nodes), following the L → L² formula where "a link connects links".
- Isomorphism Detection: Check if two networks have identical structure
- Mapping Discovery: Find the exact node-to-node correspondence between isomorphic networks
- Automorphism Analysis: Discover all symmetries within a network
- Subnetwork Matching: Find if one network contains another as a pattern
- Links Notation (LiNo) Support: Parse networks using the standard
links-notationcrate - Weisfeiler-Lehman Algorithm: Efficient canonical labeling for pruning the search space
Add to your Cargo.toml:
[dependencies]
network-isomorphism-solver = "0.2.0"use network_isomorphism_solver::{LinkNetwork, check_isomorphism};
// Create two networks using Links Notation
let benzene1 = LinkNetwork::from_notation("
C1 connects C2
C2 connects C3
C3 connects C4
C4 connects C5
C5 connects C6
C6 connects C1
");
let benzene2 = LinkNetwork::from_notation("
A connects B
B connects C
C connects D
D connects E
E connects F
F connects A
");
// Check if they are isomorphic
let result = check_isomorphism(&benzene1, &benzene2);
if result.is_isomorphic {
println!("Networks are isomorphic!");
if let Some(mapping) = result.mapping {
println!("Node mapping: {:?}", mapping);
}
}This library integrates with the links-notation crate for parsing standard LiNo format:
use network_isomorphism_solver::{LinkNetwork, is_isomorphic};
// Parse LiNo doublet format: (source target)
let network1 = LinkNetwork::from_lino("(1 2) (2 3) (3 1)").unwrap();
let network2 = LinkNetwork::from_lino("(A B) (B C) (C A)").unwrap();
assert!(is_isomorphic(&network1, &network2));
// Parse named links with identifiers
let named = LinkNetwork::from_lino("(bond1: C1 C2) (bond2: C2 C3) (bond3: C3 C1)").unwrap();
assert!(is_isomorphic(&network1, &named));
// Parse triplet format: (source relation target)
let triplet = LinkNetwork::from_lino("(A connects B) (B connects C) (C connects A)").unwrap();
assert!(is_isomorphic(&network1, &triplet));The from_lino method provides proper parsing using the official LiNo grammar from the link-foundation/links-notation repository.
A link connecting two nodes (source → target).
pub struct DoubletLink {
pub source: LinkId,
pub target: LinkId,
}A network represented as a collection of doublet-links.
impl LinkNetwork {
/// Create an empty network
pub fn new() -> Self;
/// Parse from simple text notation (legacy)
pub fn from_notation(notation: &str) -> Self;
/// Parse from Links Notation (LiNo) using the links-notation crate
pub fn from_lino(lino: &str) -> Result<Self, ParseError>;
/// Add a link between two nodes
pub fn add_link(&mut self, source: LinkId, target: LinkId);
/// Get node and link counts
pub fn node_count(&self) -> usize;
pub fn link_count(&self) -> usize;
/// Get degree of a node
pub fn degree(&self, node: LinkId) -> usize;
/// Get sorted degree sequence
pub fn degree_sequence(&self) -> Vec<usize>;
}Result of an isomorphism check.
pub struct IsomorphismResult {
pub is_isomorphic: bool,
pub mapping: Option<HashMap<LinkId, LinkId>>,
}Quick check if two networks are isomorphic.
use network_isomorphism_solver::{LinkNetwork, is_isomorphic};
let net1 = LinkNetwork::from_notation("A connects B, B connects C");
let net2 = LinkNetwork::from_notation("X connects Y, Y connects Z");
assert!(is_isomorphic(&net1, &net2));Check isomorphism and return the node mapping if found.
use network_isomorphism_solver::{LinkNetwork, check_isomorphism};
let result = check_isomorphism(&net1, &net2);
if let Some(mapping) = result.mapping {
// mapping: {A: X, B: Y, C: Z}
}Find all automorphisms (symmetries) of a network.
use network_isomorphism_solver::{LinkNetwork, find_automorphisms};
// Square has 8 automorphisms (rotations + reflections)
let square = LinkNetwork::from_notation("
A connects B, B connects C, C connects D, D connects A
");
let autos = find_automorphisms(&square);
assert_eq!(autos.len(), 8);Check if a network contains another as a subnetwork pattern.
use network_isomorphism_solver::{LinkNetwork, contains_subnetwork};
let molecule = LinkNetwork::from_notation("
C1 connects C2, C2 connects C3, C3 connects C4,
C4 connects C5, C5 connects C6, C6 connects C1,
C1 connects O
");
let ring = LinkNetwork::from_notation("
A connects B, B connects C, C connects D,
D connects E, E connects F, F connects A
");
assert!(contains_subnetwork(&molecule, &ring));Compare molecular structures to find similar compounds:
let aspirin = LinkNetwork::from_notation("
benzene connects carboxyl
carboxyl connects acetyl
");
let candidate = LinkNetwork::from_notation("
ring connects acid
acid connects ester
");
if is_isomorphic(&aspirin, &candidate) {
println!("Potential drug candidate found!");
}Verify that optimized circuits maintain functional equivalence:
let original = LinkNetwork::from_notation("
input1 connects gate
input2 connects gate
gate connects output
");
let optimized = LinkNetwork::from_notation("
A connects X
B connects X
X connects Y
");
assert!(is_isomorphic(&original, &optimized));Detect fraud patterns in transaction networks:
let fraud_pattern = LinkNetwork::from_notation("
hub connects node1
hub connects node2
hub connects node3
");
if contains_subnetwork(&transaction_graph, &fraud_pattern) {
println!("Potential fraud detected!");
}The solver uses a combination of techniques:
- Quick Rejection: Compare node counts, link counts, and degree sequences
- Weisfeiler-Lehman Refinement: Compute canonical node signatures for pruning
- Backtracking Search: Systematically explore valid node mappings
- Constraint Propagation: Use degree and adjacency constraints to prune search
The Weisfeiler-Lehman algorithm iteratively refines node labels based on neighborhood structure, creating signatures that help identify potentially equivalent nodes.
This library is inspired by Links Theory, which represents all data as doublet-links following the formula L → L² (a link connects links).
Key concepts:
- Doublet-Link: An ordered pair (source, target) representing a connection
- Link Network: A collection of doublet-links forming a structure
- Links Notation (LiNo): Human-readable format for describing networks
This library uses and integrates with the Link Foundation ecosystem:
- links-notation - Parser for Links Notation (LiNo) format, available in Rust, JavaScript, Python, C#, Go, and Java
- link-cli - CLI tool for manipulating links with query-based operations
- links-client - Client library for doublet-links database access
- doublets-rs - Rust implementation of associative doublet storage (requires nightly Rust)
# Run all tests
cargo test
# Run with verbose output
cargo test -- --nocapture
# Run specific test module
cargo test drug_discovery
cargo test circuit_verification# Format code
cargo fmt
# Run lints
cargo clippy --all-targets --all-features
# Run all checks
cargo fmt --check && cargo clippy --all-targets --all-features && cargo testContributions are welcome! Please see CONTRIBUTING.md for guidelines.
Unlicense - Public Domain
- Inspired by Links Theory by Konstantin Encyclopedist
- Uses concepts from the Weisfeiler-Lehman graph isomorphism test
- Related projects: links-notation, links-client