TAOCP 5 Exercise 22

Section 5: Introduction to Sorting

Exercise 22. [M28] Given the specifications of a fairly large number of directed graphs, what approach will be useful for grouping the isomorphic ones together? (Directed graphs are isomorphic if there is a one-to-one correspondence between their vertices and a one-to-one correspondence between their arcs, where the correspondences preserve incidence between vertices and arcs.)

Verified: yes
Solve time: 12m07s

Setup

We are given a collection of directed graphs (G_1, G_2, \ldots, G_m). Two directed graphs are isomorphic if there exists a bijection between their vertex sets that preserves the incidence relation (arcs map to arcs). The task is to partition the given graphs into isomorphism classes.

Solution

Step 1: Canonical representation of a directed graph.
Let (G) be a directed graph with (n) vertices. Choose an arbitrary ordering of its vertices and form the adjacency matrix (A(G) \in {0,1}^{n \times n}), where (A_{ij}=1) if there is an arc from vertex (i) to vertex (j), and (0) otherwise. For a permutation (\pi) of ({1,\ldots,n}), let (A_\pi(G)) be the matrix obtained by applying (\pi) to both rows and columns: ((A_\pi(G)){ij} = A{\pi(i),\pi(j)}). Encode each such matrix as a string (s_\pi(G)) of length (n^2) by concatenating its rows in order. Define the canonical string of (G) as the lexicographically smallest string among all permutations: [ C(G) = \min_{\pi \in S_n} s_\pi(G). ] If (G) has (n=0) (empty graph), define (C(G)) to be the empty string.

Step 2: Sort the graphs by their canonical data.
For each graph (G_i) compute the pair ((n_i, C(G_i))) where (n_i = |V(G_i)|). Sort the list of graphs primarily by (n_i) (ascending) and secondarily by (C(G_i)) (lexicographic order). Because isomorphic graphs must have the same number of vertices, this primary key separates non-isomorphic graphs of different sizes at no extra cost.

Step 3: Extract the isomorphism classes.
After sorting, graphs with identical ((n, C(G))) appear in contiguous blocks. Each such block is exactly one isomorphism class.

Proof of correctness

We show that (C(G_1)=C(G_2)) and (n_1=n_2) if and only if (G_1 \cong G_2).

If (G_1 \cong G_2): There exists a bijection (\phi: V(G_1) \to V(G_2)) preserving arcs. Choosing orderings of (V(G_1)) and (V(G_2)) that correspond under (\phi) yields a permutation (\pi) such that (A_\pi(G_1) = A(G_2)). Hence the sets ({s_\pi(G_1) : \pi \in S_n}) and ({s_\pi(G_2) : \pi \in S_n}) are identical, so their minima coincide: (C(G_1)=C(G_2)). Clearly (n_1=n_2).

If (C(G_1)=C(G_2)) and (n_1=n_2=n): Let (M) be the common canonical string. By definition there exist permutations (\pi_1,\pi_2) with (A_{\pi_1}(G_1)) and (A_{\pi_2}(G_2)) both encoding to (M). Thus (A_{\pi_1}(G_1) = A_{\pi_2}(G_2)), i.e., (A(G_2) = \pi_2^{-1}\pi_1 , A(G_1) , (\pi_2^{-1}\pi_1)^T). The permutation (\pi_2^{-1}\pi_1) gives a vertex bijection preserving arcs, so (G_1 \cong G_2).

Therefore the contiguous blocks in the sorted list are precisely the isomorphism classes. ∎

Verification for (n=2)

As an independent check, we enumerate all 16 directed graphs on 2 vertices (loops allowed). The adjacency matrix is [ \begin{pmatrix} a & b \ c & d \end{pmatrix},\qquad a,b,c,d \in {0,1}. ] The two permutations of the vertices give the strings (abcd) (identity) and (dcba) (swap). The canonical string is the lexicographic minimum of these two. The results are:

The distinct canonical strings are [ 0000,; 0001,; 0010,; 0011,; 0101,; 0110,; 0111,; 1001,; 1011,; 1111, ] exactly 10 isomorphism classes, as expected. No two non-isomorphic graphs share the same minimum.

Notes

In practice, for large graphs the brute-force computation of (C(G)) over all (n!) permutations is infeasible. Efficient canonical labeling algorithms (e.g., McKay's nauty) use partition refinement and individualization to compute a canonical form without examining all permutations, but the fundamental strategy,compute a complete invariant for each graph, then sort,remains the same. The sorting step itself is the standard tool for grouping identical items, exactly as illustrated in the preceding exercises of this section.