Graph Structure as Instruction Strings
IsalGraph encodes graph topology as instruction strings over a 9-character alphabet using a circular doubly linked list with two mobile pointers. The canonical string is a complete graph invariant — two graphs are isomorphic if and only if their canonical strings are identical.
Complete Invariant
The canonical string uniquely identifies a graph up to isomorphism.
Graph Distance
Levenshtein distance between canonical strings
String edit distance provides a polynomial-time proxy for graph edit distance.
9-Character Alphabet
Movement, node creation, edge creation, and no-op instructions encode any finite simple graph.
By the Numbers
Empirical results across 5 benchmark datasets. See full benchmarks →
Compression Ratio
Peak compression vs. GED standard model. IsalGraph wins on 100% of graphs in 4 of 5 datasets.
GED Correlation
Peak Spearman rank correlation between IsalGraph distance and graph edit distance.
Greedy Encoding
Empirical time complexity of the greedy single-start encoder on synthetic graphs.
Benchmark Datasets
IAM Letter (LOW, MED, HIGH), LINUX kernel, and AIDS molecular graphs.