How It Works

IsalGraph converts between graphs and strings using a circular doubly linked list (CDLL) with two mobile pointers. Explore both directions interactively below.

The Core Idea

Any finite simple graph can be encoded as a string over a 9-character alphabet Σ = {N, n, P, p, V, v, C, c, W} . The encoding is reversible: given the string, the original graph can be reconstructed exactly.

The process uses an auxiliary Circular Doubly Linked List (CDLL) that keeps track of visited vertices. Two pointers — a π (primary) and σ (secondary) — traverse this list. Instructions either move the pointers, create new nodes with edges, or add edges between existing nodes.

The Instruction Set

Instruction	Category	Effect
N	Movement	Move primary pointer π forward (next) in the CDLL
P	Movement	Move primary pointer π backward (prev) in the CDLL
n	Movement	Move secondary pointer σ forward (next) in the CDLL
p	Movement	Move secondary pointer σ backward (prev) in the CDLL
V	Node Creation	Create new vertex, add edge from π's vertex, insert into CDLL after π
v	Node Creation	Create new vertex, add edge from σ's vertex, insert into CDLL after σ
C	Edge Creation	Add edge from π's vertex to σ's vertex
c	Edge Creation	Add edge from σ's vertex to π's vertex
W	No-op	Do nothing (wait/padding)

String → Graph (Decoding): Walkthrough

Let's decode the string VVPnC step by step to produce a triangle (K&sub3;). The initial state has a single vertex (node 0) with both pointers π and σ on it.

Step	Instruction	Action	State After
0	—	Initial state	Nodes: {0}. Edges: none. CDLL: [0]. π→0, σ→0
1	V	Create node 1, add edge {0,1}, insert 1 into CDLL after π	Nodes: {0,1}. Edges: {0,1}. CDLL: [0,1]. π→0, σ→0
2	V	Create node 2, add edge {0,2}, insert 2 into CDLL after π	Nodes: {0,1,2}. Edges: {0,1}, {0,2}. CDLL: [0,2,1]. π→0, σ→0
3	P	Move π backward (prev) in CDLL	π moves from CDLL node 0 to prev = node 1 (graph vertex 1). σ stays at 0
4	n	Move σ forward (next) in CDLL	σ moves from CDLL node 0 to next = node 2 (graph vertex 2). π→1, σ→2
5	C	Add edge from π's vertex (1) to σ's vertex (2)	Edges: {0,1}, {0,2}, {1,2}. Triangle complete!

Try it yourself

The best way to understand IsalGraph is to experiment with it interactively. Use the Playground to enter any instruction string and watch the graph being built step by step, with full CDLL state and action log at each step.

Open Playground →

Graph → String (Encoding): Walkthrough

Now let's go in the other direction: encode the triangle (K&sub3;) back into an instruction string using the greedy G2S algorithm. The algorithm starts from a chosen vertex and greedily searches for the cheapest pointer displacement that enables inserting a new node (via V/v) or a new edge (via C/c).

Input graph: K&sub3; with nodes {0, 1, 2} and edges {0–1, 0–2, 1–2}. Starting vertex: node 0.

Step	Pair (a, b)	Operation	String	State After
0	—	Initial state	`""`	G_out: {0}. Edges: none. CDLL: [0]. π→0, σ→0. 2 nodes + 1 edge still to insert.
1	(0, 0)	Cost 0. Uninserted neighbor of π's node found (node 1). Emit V.	V	G_out: {0, 1}. Edges: {0–1}. CDLL: [0, 1]. π→0, σ→0. 1 node + 1 edge remain.
2	(0, 0)	Cost 0. Uninserted neighbor of π's node found (node 2). Emit V.	VV	G_out: {0, 1, 2}. Edges: {0–1, 0–2}. CDLL: [0, 2, 1]. π→0, σ→0. 0 nodes + 1 edge remain.
3	(−1, +1)	Cost 2. All nodes inserted; search for edge operation. Pairs (0,0) through (−1,0) fail (edges exist or self-loop). At (−1,+1): π prev→node 1, σ next→node 2. Edge 1–2 not in G_out but in input. Emit PnC.	VVPnC	G_out: {0, 1, 2}. Edges: {0–1, 0–2, 1–2}. Triangle complete! π→1, σ→2. All done.

Observation

The greedy G2S algorithm produced the string VVPnC — exactly the same string we decoded in the S2G walkthrough above! This is the round-trip property in action: encoding a graph and decoding the result produces a graph isomorphic to the original. For this triangle, the G2S output from every starting vertex is identical (VVPnC), confirming its canonical string.

Try it yourself

Use the Playground in G2S mode to encode any graph and watch the greedy algorithm choose displacement pairs step by step. Try different starting vertices and observe how the resulting strings differ.

Open Playground →

Mathematical Foundations

Theorem (Round-Trip)

For any valid IsalGraph string w and any starting vertex s:

That is, encoding a decoded graph and decoding the result produces a graph isomorphic to the original.

Theorem (Complete Invariant)

The canonical string is defined as the lexicographically smallest among the shortest strings produced over all starting vertices:

This is a complete graph invariant:

Two graphs are isomorphic if and only if their canonical strings are identical.

Corollary (IsalGraph Distance is a Metric)

The IsalGraph graph distance is defined as the Levenshtein distance between canonical strings:

This defines a metric on the space of isomorphism classes of finite, simple, connected graphs, providing a polynomial-time computable distance that correlates with graph edit distance.

Critical Invariants

CDLL indices ≠ graph node indices. Pointers are CDLL node indices. Use cdll.getValue(ptr) to get the graph node.
Pointer immobility after V/v. The pointer does NOT advance after a node insertion.
Displacement pairs sorted by |a| + |b| (total cost), not by a + b (algebraic sum).
Greedy G2S ≠ canonical string. Different starting vertices may produce different strings. The canonical string requires trying all starting vertices.

Full Mathematical Treatment

For complete formal definitions, algorithm pseudocode, proofs of completeness and metric properties, and the full theoretical foundation of IsalGraph, see the dedicated Math Foundations page.

Math Foundations →