We present a new polynomial-time algorithm for determining whether two given graphs are isomorphic or not. We prove that the algorithm is necessary and sufficient for solving the Graph Isomorphism Problem in polynomial-time, thus showing that the Graph Isomorphism Problem is in P.  The semiotic theory for the recognition of graph structure is used to define a canonical form of the sign matrix of a graph. We prove that the canonical form of the sign matrix is uniquely identifiable in polynomial-time for isomorphic graphs. The algorithm is demonstrated by solving the Graph Isomorphism Problem for many of the hardest known examples. We implement the algorithm in C++ and provide a demonstration program for Microsoft Windows [download]. Google Scholar Citations © 2009

The Graph Isomorphism Algorithm and its consequence that Graph Isomorphism is in P were first announced during a special S.E.R.R. seminar at Euroacademy in 2009. The result was subsequently published in the Euroacademy series Baltic Horizons No. 14 (111) in 2010. We are pleased to announce that The Graph Isomorphism Algorithm has also been published by Amazon in 2011. The Endowed Chair of the Institute of Mathematics was bestowed upon Distinguished Professor Ashay Dharwadker in 2012 to honour his fundamental contributions to Mathematics and Natural Sciences.

One of the most fundamental problems in graph theory is the Graph Isomorphism Problem : given two graphs G_A and G_B, are they isomorphic? Graphs G_A and G_B are said to be isomorphic if their vertices can be rearranged so that the corresponding edge structure is exactly the same. To show that graphs G_A and G_B are isomorphic, it suffices to find one such rearrangement of vertices. On the other hand, to show that G_A and G_B are not isomorphic, one must prove that no such rearrangement of vertices can exist. Without a good algorithm, this problem can be very difficult to solve even for relatively small graphs.
 

Figure 1.1. Are graphs G_A and G_B isomorphic?

We present a new polynomial-time GRAPH ISOMORPHISM ALGORITHM for determining whether two given graphs are isomorphic or not. If the given graphs are isomorphic, the algorithm finds an explicit isomorphism function in polynomial-time. In Section 2, we provide precise DEFINITIONS of all the terminology used and introduce the essential concept of a sign matrix according to the semiotic theory for the recognition of graph structure. In Section 3, we present a formal description of the ALGORITHM followed by an example to show how the algorithm works step-by-step. In Section 4, we prove that the algorithm is NECESSARY AND SUFFICIENT for solving the Graph Isomorphism Problem: if graphs G_A and G_B are isomorphic, then the algorithm finds an explicit isomorphism function; if graphs G_A and G_B are not isomorphic, then the algorithm determines that no isomorphism function can exist. In Section 5, we show that the algorithm has polynomial-time COMPLEXITY. Thus, we prove that the Graph Isomorphism Problem is in P. In Section 6, we provide an IMPLEMENTATION of the algorithm as a C++ program, together with demonstration software for Microsoft Windows. In Section 7, we demonstrate the algorithm by solving the Graph Isomorphism Problem for several EXAMPLES of graphs in the hardest known cases. In Section 8, we list the REFERENCES.

To begin with, we present elementary definitions of all the terminology used, following [1]. Thereafter, we introduce the essential concept of a sign matrix according to the semiotic theory for the recognition of graph structure, following [2].

A finite simple graph G consists of a set of vertices V, with |V| = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. The definition of a simple graph G forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite, with |E| = m. We label the vertices of G with the integers 1, 2, ..., n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is adjacent to v and write uv ∈ E. Adjacency is a symmetric relationship: uv ∈ E if and only if vu ∈ E. The degree of a vertex v is the number of vertices that are adjacent to v. A (u, v)-path P in G is a sequence of distinct vertices u = v₁, v₂, ..., v_k = v such that v_iv_i+1 ∈ E for i = 1, 2, ..., k-1. If such a (u, v)-path P exists, then the vertices u and v are said to be connected by a path of length k-1. 

Given any pair of vertices (u, v) in G, we define the distance
 

d(u, v)	=	0, if u = v,
d(u, v)	=	the length of a shortest (u, v)-path, if u and v are connected, and
d(u, v)	=	∞, otherwise.

We now introduce the key ingredients of semiotic theory. For any pair of vertices (u, v) in G, the collateral graph G\uv is defined as follows:

• If uv ∈ E, then G\uv is obtained by deleting the edge uv from G while preserving all the vertices of G. We use the binary sign + to distinguish the distance function in this case.
• If uv ∉ E, then G\uv = G. We use the binary sign − to distinguish the distance function in this case.

The pair graph G_uv for any pair of vertices (u, v) in G is defined as follows: 

• w is a vertex of G_uv if and only if w belongs to a shortest (u, v)-path in G\uv, and
• wx is an edge of G_uv if and only if wx is also an edge of G. 

For any pair of vertices (u, v) in G, we write the (u, v)-sign, denoted by the symbol s_uv, as follows:
 

suv

=

±

duv

.

nuv

.

muv

where

• the leading binary sign is positive if uv ∈ E, or negative if uv ∉ E; 
• d_uv is the distance d(u, v) in the collateral graph G\uv ;
• n_uv is the number of vertices of the pair graph G_uv; 
• m_uv is the number of edges of the pair graph G_uv. 

The sign matrix S of the graph G is written as an n × n array with the (u, v)-sign s_uv as the entry in row u and column v,
 

S

=

[

suv

]

.

The adjacency matrix of G is an n × n matrix with the entry in row u and column v equal to 1 if uv ∈ E and equal to 0 if uv ∉ E. Thus, the adjacency matrix of the graph G can be recovered from the leading binary signs of the entries of the sign matrix S. Note that for a simple graph G, both the adjacency matrix and the sign matrix S are symmetric. 

We shall now define a canonical form S* of the sign matrix by ordering the rows and columns of S in a certain way. First, write the set of all distinct (u, v)-signs s_uv in lexicographic order s₁, s₂, ..., s_r. Then, for each row i of the sign matrix, i = 1, 2, ..., n, compute the sign frequency vector
 

fi

=

(

fi(1), fi(2), ...,  fi(r)

)

where  f_i^(k) is the number of times the sign s_k occurs in row i. Since S is symmetric, the sign frequency vector for column i is the same as the sign frequency vector for row i, for i = 1, 2, ..., n. Now, write the sign frequency vectors f₁, f₂, ..., f_n in lexicographic order  ^fi₁, ^fi₂, ..., ^fi_n. Reorder the rows and columns of the sign matrix according to the permutation i₁, i₂, ..., i_n of the vertices 1, 2, ..., n of G to obtain the canonical form S* of the sign matrix. 

The vertices of G are partitioned into equivalence classes consisting of vertices with the same sign frequency vectors. Thus, the canonical form S* of the sign matrix is uniquely defined only upto permutations of vertices within each equivalence class. 

Graphs G_A and G_B are said to be isomorphic if there exists a bijection
 

φ: VA  → VB

from the vertices of graph G_A to the vertices of  graph G_B, such that uv is an edge in graph G_A if and only if φ(u)φ(v) is an edge in graph G_B. The graph isomorphism problem is to determine whether two given graphs are isomorphic or not.

An algorithm is a problem-solving method suitable for implementation as a computer program. While designing algorithms we are typically faced with a number of different approaches. For small problems, it hardly matters which approach we use, as long as it is one that solves the problem correctly. However, there are many problems for which the only known algorithms take so long to compute the solution that they are practically useless. For instance, the naïve approach of computing all n! possible permutations of the n vertices to show that a pair of graphs G_A and G_B are not isomorphic is impractical even for small inputs. 

A polynomial-time algorithm is one whose number of computational steps is always bounded by a polynomial function of the size of the input. Thus, a polynomial-time algorithm is one that is actually useful in practice. The class of all problems that have polynomial-time algorithms is denoted by P. If graphs G_A and G_B are isomorphic then they must have the same sign frequency vectors in lexicographic order ^fi₁, ^fi₂, ..., ^fi_n and we shall show that our algorithm obtains identical canonical forms of their sign matrices S_A* and S_B* in polynomial-time, thus exhibiting an explicit isomorphism function φ. Conversely, we shall show that our algorithm determines in polynomial-time that the sign matrices S_A* and S_B* cannot be expressed in identical canonical forms if and only if the graphs G_A and G_B are not isomorphic. Thus, we have a polynomial-time algorithm for solving the graph isomorphism problem, showing that the graph isomorphism problem is in P.

We are now ready to present a formal description of the algorithm. After that, the steps of the algorithm will be illustrated by an example. We begin by defining four procedures.

3.1. Procedure. This procedure is Dijkstra's algorithm [3]. Given a graph G and a vertex u, we compute shortest (u, v)-paths to all vertices v of G. Define a(u, v) = 1 if uv ∈ E and a(u, v) = ∞ if uv ∉ E. We maintain a set V_known of vertices to which the shortest (u, v)-path is known and a tentative distance d'(u, w) for each vertex w outside V_known.

• Initialization: Set V_known = {u}, d(u, u) = 0 and d'(u, w) = a(u, w) for each vertex w outside V_known.
• Iteration: Select a vertex w_min outside V_known such that d'(u, w_min) is a minimum. Add w_min to V_known and update the tentative distance d'(u, w) = min{d'(u, w), d(u, w)+a(u, w)} for each vertex w outside V_known.
• Termination: Iterate until V_known contains all the vertices of G or until d'(u, w) = ∞ for each vertex w outside V_known. In the later case, no further vertex can be selected and the remaining vertices are not connected to the vertex u.

3.2. Procedure. Given a graph G and vertices u and v, we compute the distance d(u, v) in the collateral graph G\uv and the pair graph G_uv.

• Using Procedure 3.1, compute shortest (u, x)-paths to all vertices x of G\uv.
• Using Procedure 3.1, compute shortest (v, y)-paths to all vertices y of G\uv.
• In particular, the length of any shortest (u, v)-path in G\uv is the distance d(u, v).
• If u = u₁, u₂, ..., u_r and v = v₁, v₂, ..., v_s are shortest paths found above such that u_r = v_s and the sum of the lengths of the two paths is the distance d(u, v) in the collateral graph G\uv, then the union of  vertices of the two paths are vertices of the pair graph G_uv. Every vertex w of the pair graph G_uv is obtained this way, because any shortest (u, v)-path containing w is obtained by connecting some shortest (u, w)-path with some shortest (w, v)-path in G\uv. Thus, at least one pair of shortest paths found above must satisfy u_r = v_s = w, for each vertex w of the pair graph G_uv.

3.3. Procedure. Given a graph G, we compute the sign matrix S and its canonical form S*.

• Using Procedure 3.2, for every pair of vertices u and v, we compute the distance d(u, v) in the collateral graph G\uv and the pair graph G_uv.
• The entry in row u and column v of the sign matrix S is s_uv = ± d_uv.n_uv.m_uv, where the leading binary sign is positive if uv ∈ E, and negative if uv ∉ E; d_uv is the distance d(u, v) in the collateral graph G\uv; n_uv is the number of vertices of the pair graph G_uv; and m_uv is the number of edges of the pair graph G_uv.
• Write the set of all distinct signs s_uv in lexicographic order s₁, s₂, ..., s_r.
• For each row i of the sign matrix S, i = 1, 2, ..., n, compute the sign frequency vector f_i = ( f_i⁽¹⁾, f_i⁽²⁾, ...,  f_i^(r)), where  f_i^(k) is the number of times the sign s_k occurs in row i. Since S is symmetric, the sign frequency vector for column i is the same as the sign frequency vector for row i, for i = 1, 2, ..., n.
• Write the sign frequency vectors f₁, f₂, ..., f_n in lexicographic order  ^fi₁, ^fi₂, ..., ^fi_n.
• Reorder the rows and columns of the sign matrix according to the permutation i₁, i₂, ..., i_n of the vertices 1, 2, ..., n of G to obtain the canonical form S*.

3.4. Procedure. Given graphs G_A and G_B such that the sign frequency vectors in lexicographic order for S_A* and S_B* are the same, (  ^f_Ai₁, ^f_Ai₂, ..., ^f_Ai_n ) = (  ^f_Bi'₁, ^f_Bi'₂, ..., ^f_Bi'_n ), we compute a reordering i''₁, i''₂, ..., i''_n of the vertices of G_B such that either the first entry of S_B* that does not match the corresponding entry of S_A* occurs at the greatest possible index in row major order or S_A* = S_B*.

• Set A = S_A* and  B = S_B*.
• Read the matrices A and B in row major order (read each row from left to right and read the rows from top to bottom). If all corresponding entries A_ij and B_ij of A and B match, then stop. Else, find the first entry B_ij in B that does not match the corresponding entry A_ij in A. Find k > i such that interchanging rows (k, j) and columns (k, j) of B ensures that the first mismatch occurs later than B_ij in row major order (or there is no mismatch at all). If no such k exists, then stop. Repeat this process until the corresponding k cannot be found or all corresponding entries of A and B match.
• We obtain a reordering i''₁, i''₂, ..., i''_n of the vertices of G_B such that either the first entry of B that does not match the corresponding entry of A occurs at the greatest possible index in row major order or A = B.

3.5. Algorithm. Given graphs G_A and G_B, we determine whether G_A and G_B are isomorphic or not. If G_A and G_B are isomorphic, we exhibit an explicit isomorphism function.

• Using Procedure 3.3, we compute the canonical forms of the sign matrices S_A* and S_B*. If the sign frequency vectors in lexicographic order for S_A* and S_B* are different, then G_A and G_B are not isomorphic and we stop.
• Else, the sign frequency vectors in lexicographic order for S_A* and S_B* are the same, (  ^f_Ai₁, ^f_Ai₂, ..., ^f_Ai_n ) = (  ^f_Bi'₁, ^f_Bi'₂, ..., ^f_Bi'_n ).
• For k = 1, 2, ..., n :
• Set A = S_A* and  B = S_B*.
• Interchange rows (1, k) and columns (1, k) of B.
• Using Procedure 3.4, if A = B then stop. Else, start with the next value of k. If k = n then stop.
• If A  ≠  B, then G_A and G_B are not isomorphic. Else A = B, G_A and G_B are isomorphic and the reordering i''₁, i''₂, ..., i''_n of the vertices of G_B to obtain S_B* = B provides an explicit isomorphism function φ(i₁) = i''₁, φ(i₂) = i''₂, ..., φ(i_n) = i''_n.

3.6. Example. We demonstrate the steps of the algorithm with an example. The input consists of Turán [4] graphs G_A and G_B, with vertices labeled V_A = {1, 2, 3, 4, 5, 6, 7, 8} and V_B = {1, 2, 3, 4, 5, 6, 7, 8} as shown below in Figure 3.6.1.
 

Figure 3.6.1. An example to demonstrate the steps of the algorithm : input

The algorithm first computes all the pair graphs of G_A. To see how this is done, let us explicitly compute the pair graph G₁₂ for the pair of vertices (1, 2). First, Procedure 3.2 computes the shortest paths from vertex 1 in G_A\12 as (1), (1, 7, 2), (1, 7, 3), (1, 7), (1, 8), (1, 4), (1, 5) and (1, 6). Then, Procedure 3.2 computes the shortest paths from vertex 2 in G_A\12 as (2), (2, 7, 1), (2, 7, 3), (2, 7), (2, 8), (2, 4), (2, 5) and (2, 6). The distance d(1, 2) = 2 is given by the length of any shortest (1, 2)-path found in G_A\12 so far. Now, Procedure 3.2 obtains the shortest (1, 2)-paths (1, 7, 2), (1, 8, 2), (1, 4, 2), (1, 5, 2) and (1, 6, 2) whose union gives the 7 vertices of the pair graph {1, 2, 4, 5, 6, 7, 8}. The pair graph has 16 edges {1,7}, {1,8}, {1,4}, {1,5}, {1,6}, {2,7}, {2,8}, {2,4}, {2,5}, {2,6}, {7,4}, {7,5}, {8,4}, {8,5}, {4,6} and {5,6}. Since {1, 2} is not an edge in G_A, the leading binary sign is negative and Procedure 3.3 computes the sign s₁₂ = -2.7.16. Similarly, Procedure 3.3 computes all the signs s_ij for i, j = 1, 2, 3, 4, 5, 6, 7, 8. Note that for i = j the sign is always -0.1.0. Thus, Procedure 3.3 computes the sign matrix S_A. Then, Procedure 3.3 counts the number of times each sign occurs in a column of S_A and obtains the sign frequency vectors for each column of S_A. Finally, Procedure 3.3 reorders the rows and columns of S_A  according to the lexicographic order of the sign frequency vectors, to obtain the canonical form of the sign matrix S_A*. We use the following convention to display the sign matrix : the row and column headers show the vertex labels and the equivalence classes of vertices are distinguished by different shades of blue; the sign frequency vectors, vertex degrees and equivalence class numbers are displayed along the column footers. 
 

SA*	4	5	1	2	3	7	8	6
4	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
5	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
1	+2.5.7	+2.5.7	-0.1.0	-2.7.16	-2.7.16	+2.4.5	+2.4.5	+2.4.5
2	+2.5.7	+2.5.7	-2.7.16	-0.1.0	-2.7.16	+2.4.5	+2.4.5	+2.4.5
3	+2.5.7	+2.5.7	-2.7.16	-2.7.16	-0.1.0	+2.4.5	+2.4.5	+2.4.5
7	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-0.1.0	-2.7.16	-2.7.16
8	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-0.1.0	-2.7.16
6	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-2.7.16	-0.1.0
Signs	4	5	1	2	3	7	8	6
-2.7.16.	0	0	2	2	2	2	2	2
-2.8.21.	1	1	0	0	0	0	0	0
-0.1.0.	1	1	1	1	1	1	1	1
+2.4.5.	0	0	3	3	3	3	3	3
+2.5.7.	6	6	2	2	2	2	2	2
Degrees	6	6	5	5	5	5	5	5
Classes	1	1	2	2	2	2	2	2

Similarly, Procedure 3.3 obtains the canonical form of the sign matrix S_B* :
 

SB*	1	8	7	2	3	4	5	6
1	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
8	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
7	+2.5.7	+2.5.7	-0.1.0	+2.4.5	-2.7.16	+2.4.5	+2.4.5	-2.7.16
2	+2.5.7	+2.5.7	+2.4.5	-0.1.0	+2.4.5	-2.7.16	-2.7.16	+2.4.5
3	+2.5.7	+2.5.7	-2.7.16	+2.4.5	-0.1.0	+2.4.5	+2.4.5	-2.7.16
4	+2.5.7	+2.5.7	+2.4.5	-2.7.16	+2.4.5	-0.1.0	-2.7.16	+2.4.5
5	+2.5.7	+2.5.7	+2.4.5	-2.7.16	+2.4.5	-2.7.16	-0.1.0	+2.4.5
6	+2.5.7	+2.5.7	-2.7.16	+2.4.5	-2.7.16	+2.4.5	+2.4.5	-0.1.0
Signs	1	8	7	2	3	4	5	6
-2.7.16.	0	0	2	2	2	2	2	2
-2.8.21.	1	1	0	0	0	0	0	0
-0.1.0.	1	1	1	1	1	1	1	1
+2.4.5.	0	0	3	3	3	3	3	3
+2.5.7.	6	6	2	2	2	2	2	2
Degrees	6	6	5	5	5	5	5	5
Classes	1	1	2	2	2	2	2	2

Next, the algorithm checks that the sign frequency vectors in lexicographic order for S_A* and S_B* are the same, ( ^f_A4, ^f_A5, ^f_A1, ^f_A2, ^f_A3, ^f_A7, ^f_A8, ^f_A6 ) = (  ^f_B1, ^f_B8, ^f_B7, ^f_B3, ^f_B6, ^f_B4, ^f_B5, ^f_B2) = (01106, 01106, 20132, 20132, 20132, 20132, 20132, 20132). Finally, the algorithm runs through the loop k = 1, 2, 3, 4, 5, 6, 7, 8 to find an explicit isomorphism if it exists. Starting with k = 1, set A = S_A* and B = S_B* :
 

Matrix A	4	5	1	2	3	7	8	6
4	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
5	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
1	+2.5.7	+2.5.7	-0.1.0	-2.7.16	-2.7.16	+2.4.5	+2.4.5	+2.4.5
2	+2.5.7	+2.5.7	-2.7.16	-0.1.0	-2.7.16	+2.4.5	+2.4.5	+2.4.5
3	+2.5.7	+2.5.7	-2.7.16	-2.7.16	-0.1.0	+2.4.5	+2.4.5	+2.4.5
7	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-0.1.0	-2.7.16	-2.7.16
8	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-0.1.0	-2.7.16
6	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-2.7.16	-0.1.0

 

Matrix B	1	8	7	2	3	4	5	6
1	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
8	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
7	+2.5.7	+2.5.7	-0.1.0	+2.4.5	-2.7.16	+2.4.5	+2.4.5	-2.7.16
2	+2.5.7	+2.5.7	+2.4.5	-0.1.0	+2.4.5	-2.7.16	-2.7.16	+2.4.5
3	+2.5.7	+2.5.7	-2.7.16	+2.4.5	-0.1.0	+2.4.5	+2.4.5	-2.7.16
4	+2.5.7	+2.5.7	+2.4.5	-2.7.16	+2.4.5	-0.1.0	-2.7.16	+2.4.5
5	+2.5.7	+2.5.7	+2.4.5	-2.7.16	+2.4.5	-2.7.16	-0.1.0	+2.4.5
6	+2.5.7	+2.5.7	-2.7.16	+2.4.5	-2.7.16	+2.4.5	+2.4.5	-0.1.0

Since k = 1, there is no initial interchange of rows and columns of B. Now, the algorithm uses Procedure 3.4. The entries of A and B are read in row major order. The first mismatch is found in the third row and fourth column, shown underlined. The algorithm finds that exchanging the fourth column with the fifth column (and the fourth row with the fifth row) of B will push the first mismatch further along the row major order:
 

Matrix B	1	8	7	3	2	4	5	6
1	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
8	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
7	+2.5.7	+2.5.7	-0.1.0	-2.7.16	+2.4.5	+2.4.5	+2.4.5	-2.7.16
3	+2.5.7	+2.5.7	-2.7.16	-0.1.0	+2.4.5	+2.4.5	+2.4.5	-2.7.16
2	+2.5.7	+2.5.7	+2.4.5	+2.4.5	-0.1.0	-2.7.16	-2.7.16	+2.4.5
4	+2.5.7	+2.5.7	+2.4.5	+2.4.5	-2.7.16	-0.1.0	-2.7.16	+2.4.5
5	+2.5.7	+2.5.7	+2.4.5	+2.4.5	-2.7.16	-2.7.16	-0.1.0	+2.4.5
6	+2.5.7	+2.5.7	-2.7.16	-2.7.16	+2.4.5	+2.4.5	+2.4.5	-0.1.0

The first mismatch is found in the third row and fifth column, shown underlined. The algorithm finds that exchanging the fifth column with the eighth column (and the fifth row with the eighth row) of B will push the first mismatch further along the row major order:
 

Matrix B	1	8	7	3	6	4	5	2
1	-0.1.0	-2.8.21	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
8	-2.8.21	-0.1.0	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7	+2.5.7
7	+2.5.7	+2.5.7	-0.1.0	-2.7.16	-2.7.16	+2.4.5	+2.4.5	+2.4.5
3	+2.5.7	+2.5.7	-2.7.16	-0.1.0	-2.7.16	+2.4.5	+2.4.5	+2.4.5
6	+2.5.7	+2.5.7	-2.7.16	-2.7.16	-0.1.0	+2.4.5	+2.4.5	+2.4.5
4	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-0.1.0	-2.7.16	-2.7.16
5	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-0.1.0	-2.7.16
2	+2.5.7	+2.5.7	+2.4.5	+2.4.5	+2.4.5	-2.7.16	-2.7.16	-0.1.0

Now there is no mismatch, A = B. The algorithm exits the final loop and reports that an isomorphism has been found. The explicit isomorphism φ is given by reading the vertex labels of A and B in this order:
 

Graph GA	Graph GB
4	1
5	8
1	7
2	3
3	6
7	4
8	5
6	2

If the graphs G_A and G_B are redrawn with vertices ordered in this way, the isomorphism φ is easy to visualize. 
 

Here we prove that the algorithm is necessary and sufficient for solving the Graph Isomorphism Problem: 

• if graphs G_A and G_B are isomorphic, then the algorithm finds an explicit isomorphism function; 
• if graphs G_A and G_B are not isomorphic, then the algorithm determines that no isomorphism function can exist.

4.1. Proposition. If graphs G_A and G_B are isomorphic, then the algorithm finds an isomorphism.

Proof. Suppose graphs G_A and G_B are isomorphic and let φ: V_A → V_B be an isomorphism from the vertices of G_A to the vertices of G_B. Note that distances are preserved bijectively under the isomorphism,
 

d(u, v)

=

d(φ(u), φ(v))

for all vertices u, v of G_A. Thus, all the corresponding pair graphs are isomorphic and the signs
 

suv

=

sφ(u)φ(v)

are also preserved bijectively under the isomorphism for all vertices u, v of G_A. Hence, the sign frequency vectors in lexicographic order for the canonical sign matrices S_A* and S_B* are the same,
 

(  fAi1, fAi2, ..., fAin )

=

(  fBi'1, fBi'2, ..., fBi'n ).

Since φ is surjective, the algorithm finds a value of k such that if vertex v₁ is the label of row 1 and column 1 of A = S_A* then vertex φ(v₁) is the label of row k and column k of B = S_B*. Then, rows (1, k) and columns (1, k) of B are interchanged. We now use induction on the rows of B to show that Procedure 3.4 matches each row of B with the corresponding row of A. For the base of the induction, consider row 1 of B. Since vertex v₁ is the label of row 1 of A and φ(v₁) is the label of row 1 of B, the corresponding sign frequency vectors are equal. By counting sign frequencies, as long as there is a mismatch in row 1, it is always possible to interchange the columns of B such that row 1 of A and row 1 of B are perfectly matched by Procedure 3.4. For the induction hypothesis, assume that rows 1, ..., t of A and B have been perfectly matched by Procedure 3.4 such that the vertex labels for the rows 1, ..., t of A are v₁, ..., v_t and the vertex labels for the rows 1, ..., t of B are φ(v₁) = v'₁, ..., φ(v_t) = v'_t respectively. Since the sign matrices are symmetric, Procedure 3.4 also ensures that the columns 1, ..., t of A and B are perfectly matched with the same vertex labels as the rows. Thus, the first entry B_ij in B that does not match the corresponding entry A_ij in A must now occur in row i = t+1 and column j  ≥  t+1. By the induction hypothesis, the subgraph G_A^t of G_A with vertices {v₁, ..., v_t} and the subgraph G_B^t of G_B with vertices {φ(v₁) = v'₁, ..., φ(v_t) = v'_t} are isomorphic under φ. Thus, there must be a vertex v_t+1 of G_A outside the subgraph G_A^t such that the corresponding vertex φ(v_t+1) of G_B is outside the subgraph G_B^t. Since there is a mismatch at the entry B_ij, the vertex φ(v_t+1) must be the label for a column j' > j. Hence, Procedure 3.4 will always interchange rows ( j, j' ) and columns ( j, j' ) of B and repeat the process until rows i = t+1 of A and B are perfectly matched and the vertex label for row t+1 of B is φ(v_t+1) = v'_t+1. This completes the induction, showing that Procedure 3.4 matches each row of B with the corresponding row of A. Thus, the algorithm finds an explicit isomorphism function φ(v₁) = v'₁, ..., φ(v_n) = v'_n. ☐

4.2. Proposition. If graphs G_A and G_B are not isomorphic, then the algorithm determines that there cannot be an isomorphism.

Proof. Suppose graphs G_A and G_B are not isomorphic. The algorithm first computes the canonical forms of the sign matrices S_A* and S_B*. If the sign frequency vectors in lexicographic order for S_A* and S_B* are different, then the algorithm concludes that G_A and G_B are not isomorphic. If the sign frequency vectors in lexicographic order for S_A* and S_B* are the same, (  ^f_Ai₁, ^f_Ai₂, ..., ^f_Ai_n ) = (  ^f_Bi'₁, ^f_Bi'₂, ..., ^f_Bi'_n ), then the algorithm runs through the final loop for k = 1, 2, ..., n and cannot find any isomorphism. By Proposition 4.1, if G_A and G_B were isomorphic, then the algorithm would have found an explicit isomorphism for some value of k. Therefore, the algorithm concludes that there cannot be an isomorphism. ☐

From Propositions 4.1 and 4.2, we have

4.3. Theorem. The algorithm solves the Graph Isomorphism Problem. ☐

We shall now show that the algorithm terminates in polynomial-time, by specifying a polynomial of the larger of the two number of vertices n of the input graphs, that is an upper bound on the total number of computational steps performed by the algorithm. Note that we consider 

• checking whether a given pair of vertices is connected by an edge in G_A or G_B, and 
• comparing whether a given integer is less than another given integer 

to be elementary computational steps. Thus, we shall show that the Graph Isomorphism Problem is in P.

5.1. Proposition. Given a graph G with n vertices, Procedure 3.1 takes at most 3n² + 3n steps to find shortest paths from an initial vertex u to all other vertices.

Proof. Initialization takes at most 3n steps. To find the minimum distance of an unknown vertex from the initial vertex u takes at most n steps and to update the tentative distances takes at most n steps. There are at most n iterations until all the vertices are known. Finally, it takes at most n² steps to recover the vertices of the shortest paths. Thus, Procedure 3.1 terminates after at most 3n + n(n + n) + n² = 3n² + 3n steps. ☐

5.2. Proposition. Given a graph G with n vertices, Procedure 3.2 takes at most 7n² + 7n steps to compute the distance d(u, v) in the collateral graph G\uv and the pair graph G_uv for a given pair of vertices u and v.

Proof. The graph G\uv also has n vertices. By Proposition 5.1, Procedure 3.1 takes at most 3n² + 3n steps to find shortest paths from the initial vertex u to all other vertices and at most 3n² + 3n steps to find shortest paths from the initial vertex v to all other vertices. Then it takes at most n steps to determine the distance d(u, v). Finally, it takes at most n² steps to run through pairs of shortest paths to find the vertices of the pair graph G_uv. Thus, Procedure 3.2 terminates after at most 3n² + 3n + 3n² + 3n + n + n² = 7n² + 7n steps. ☐

5.3. Proposition. Given a graph G with n vertices, Procedure 3.3 takes at most 7n⁴ + 7n³ + 2n² steps to compute the canonical form of the sign matrix S*.

Proof. By Proposition 5.2, for each pair of vertices it takes at most 7n² + 7n steps to compute the sign s_uv. Since there are n² signs, it takes at most n²(7n² + 7n) = 7n⁴ + 7n³ steps to compute the sign matrix S. Then it takes at most n² steps to compute the sign frequency vector and at most n² steps to sort it in lexicographic order. Thus, Procedure 3.3 terminates after at most 7n⁴ + 7n³ + n²+ n² = 7n⁴ + 7n³ + 2n² steps. ☐

5.4. Proposition. Given a sign matrices S_A* and S_B* such that the sign frequency vectors in lexicographic order (  ^f_Ai₁, ^f_Ai₂, ..., ^f_Ai_n ) = (  ^f_Bi'₁, ^f_Bi'₂, ..., ^f_Bi'_n ), Procedure 3.4 takes at most 2n⁴ steps to terminate.

Proof. Since there are n² entries in S_B*, it takes at most n² steps to find a mismatch (i, j) with the corresponding entry in S_A* in row major order. Then, it takes at most n² steps along the row i to find a column j' such that interchanging rows ( j, j' ) and columns ( j, j' ) leads to a mismatch later in the row major order. This may be repeated at most n² times until either the corresponding interchange column j' cannot be found or all the entries in the sign matrices are perfectly matched. Thus, Procedure 3.4 terminates after at most n²(n² + n²) = 2n⁴ steps. ☐

5.5. Proposition. Given graphs G_A and G_B with n vertices, the algorithm takes at most 2n⁵ + 14n⁴ + 14n³ + 4n² steps to terminate.

Proof. By Proposition 5.3, Procedure 3.3 takes at most 2(7n⁴ + 7n³ + 2n²) = 14n⁴ + 14n³ + 4n² steps to compute the canonical forms of the sign matrices S_A* and S_B*. If the sign frequency vectors in lexicographic order (  ^f_Ai₁, ^f_Ai₂, ..., ^f_Ai_n ) = (  ^f_Bi'₁, ^f_Bi'₂, ..., ^f_Bi'_n ) are the same, then by Proposition 5.4 the final loop for k = 1, 2, ..., n takes at most n(2n⁴) = 2n⁵ steps. Thus, the algorithm terminates after at most 2n⁵ + 14n⁴ + 14n³ + 4n² steps. ☐

From Theorem 4.3 and Proposition 5.5, we have

5.6. Theorem. The Graph Isomorphism Problem is in P. ☐

We provide a demonstration program for the Graph Isomorphism Algorithm written in C++ for Microsoft Windows. The input consists of the files Graph A.txt and Graph B.txt containing the adjacency matrices of graph G_A and graph G_B respectively. The program computes the sign matrices S_A* and S_B* in canonical form and determines whether G_A and G_B are isomorphic or not, in polynomial-time.
 

Figure 6.1. A demonstration program for Microsoft Windows [download]

We show how to write the input for the computation performed in Example 3.6:
 

Graph A.txt 8  0 0 0 1 1 1 1 1   0 0 0 1 1 1 1 1   0 0 0 1 1 1 1 1   1 1 1 0 0 1 1 1   1 1 1 0 0 1 1 1   1 1 1 1 1 0 0 0   1 1 1 1 1 0 0 0   1 1 1 1 1 0 0 0  Graph B.txt 8  0 1 1 1 1 1 1 0   1 0 1 0 0 1 1 1   1 1 0 1 1 0 0 1   1 0 1 0 0 1 1 1   1 0 1 0 0 1 1 1   1 1 0 1 1 0 0 1   1 1 0 1 1 0 0 1   0 1 1 1 1 1 1 0

Figure 6.2. Input for the demonstration program

The C++ program is shown below:

#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 
#include <map> 
#include <set> 
#include <algorithm> 
using namespace std; 

vector<vector<int> > dijkstra(vector<vector<int> > graph); 
vector<vector<int> > reindex(vector<vector<int> > graph, vector<int> index); 
vector<int> inv(vector<int> index); 
vector<int> transform(map<vector<int>,vector<int> > signmatrixA,  
map<vector<int>,vector<int> > signmatrixB, vector<int> vertexA,  
vector<int> vertexB, vector<int> isoB); 
ifstream infileA("graphA.txt"); 
ifstream infileB("graphB.txt"); 
ofstream outfile("result.txt"); 

int main() 
{ 
cout<<"The Graph Isomorphism Algorithm"<<endl; 
cout<<"by Ashay Dharwadker and John-Tagore Tevet"<<endl; 
cout<<"http://www.dharwadker.org/tevet/isomorphism/"<<endl; 
cout<<"Copyright (c) 2009"<<endl; 

//Process Graph A 
cout<<"Computing the Sign Matrix of Graph A..."<<endl; 
int i, j, k, q, N1, N2, nA; infileA>>nA; 
//Read adjacency matrix of graph A from graphA.txt 
vector< vector<int> > rgraphA; int valA; 
for(i=0; i<nA; i++) 
{ 
vector<int> rowA; 
for(j=0; j<nA; j++) 
{ 
infileA>>valA; 
rowA.push_back(valA); 
} 
rgraphA.push_back(rowA); 
} 
//End reading 

//Initial sorting 
vector<vector<int> > distanceA; 
vector<vector<int> > neighborA; 
for(i=0; i<rgraphA.size(); i++) 
{ 
vector<int> rowdistanceA, rowneighborA;  
for(j=0; j<rgraphA[i].size(); j++) 
{ 
if(rgraphA[i][j]==1) rowneighborA.push_back(j); 
vector<int> indexdA; 
for(k=0; k<rgraphA.size(); k++) indexdA.push_back(k); 
indexdA[0]=i; indexdA[i]=0; 
vector<vector<int> > dgraphA=reindex(rgraphA,indexdA); 
vector<vector<int> > dpathA=dijkstra(dgraphA); 
int ddA=-1; 
for(k=0; k<dpathA.size(); k++) 
if(inv(indexdA)[dpathA[k][dpathA[k].size()-1]]==j) 
{ddA=dpathA[k].size()-1; break;} 
rowdistanceA.push_back(ddA);  
}  
distanceA.push_back(rowdistanceA); 
neighborA.push_back(rowneighborA); 
} 

vector<vector<int> > sequenceA; 
for(i=0; i<rgraphA.size(); i++) 
{ 
vector<int> mutualdistanceA; 
for(j=0; j<neighborA[i].size()-1; j++) 
for(k=j+1; k<neighborA[i].size(); k++) 
mutualdistanceA.push_back(distanceA[neighborA[i][j]][neighborA[i][k]]);  
sort(mutualdistanceA.begin(), mutualdistanceA.end()); 
vector<int> tmutualA; 
for(k=0; k<nA*nA-1-mutualdistanceA.size(); k++) tmutualA.push_back(0); 
for(k=0; k<mutualdistanceA.size(); k++) tmutualA.push_back(mutualdistanceA[k]); 
sequenceA.push_back(tmutualA);  
} 

map<vector<int>,int> sorterA; 
for(i=0; i<sequenceA.size(); i++) sorterA[sequenceA[i]]=i; 
vector<int> mainindexA; 
map<vector<int>,int>::iterator sitA=sorterA.begin(); 
while(sitA!=sorterA.end()) 
{ 
vector<int>vsitA=sitA->first; 
for(i=0; i<sequenceA.size(); i++) 
if(sequenceA[i]==vsitA) mainindexA.push_back(i); 
sitA++;  
} 

vector< vector<int> > graphA=reindex(rgraphA,mainindexA); 

//Compute degree sequence 
vector<int> degA; 
int sumA; 
for(i=0; i<nA; i++) 
{ 
sumA=0; 
for(j=0; j<nA; j++) 
{ 
if(graphA[i][j]==1) sumA++; 
} 
degA.push_back(sumA); 
} 
vector<int> sorted_degA=degA; 
sort(sorted_degA.begin(),sorted_degA.end()); 

//Pair graphs 
map<vector<int>,set<int> > PA; 
map<vector<int>,int> dA; 
map<vector<int>,int> ntA; 
map<vector<int>,int> eA; 

for(N1=0; N1<graphA.size(); N1++) 
for(N2=0; N2<graphA[N1].size(); N2++) 
{ 
int signA=-1; 
vector<vector<int> > tgraphA=graphA; 
if(graphA[N1][N2]!=0) {tgraphA[N1][N2]=0; tgraphA[N2][N1]=0; signA=1;} 
//Compute shortest paths from vertex 1  
vector<vector<int> > shortest_path1A; 
vector<int> index1A; for(q=0; q<nA; q++) index1A.push_back(q);  
index1A[0]=N1; index1A[N1]=0;  
vector< vector<int> > temp_graph1A=reindex(tgraphA, index1A);  
vector< vector<int> > p1A=dijkstra(temp_graph1A); 
for(i=0; i<p1A.size(); i++) 
{ 
vector<int> tpath1A; 
for(j=0; j<p1A[i].size(); j++) {tpath1A.push_back(inv(index1A)[p1A[i][j]]);} 
shortest_path1A.push_back(tpath1A); 
} 
//Compute shortest paths from vertex 2  
vector<vector<int> > shortest_path2A; 
vector<int> index2A; for(q=0; q<nA; q++) index2A.push_back(q);  
index2A[0]=N2; index2A[N2]=0;  
vector< vector<int> > temp_graph2A=reindex(tgraphA, index2A);  
vector< vector<int> > p2A=dijkstra(temp_graph2A); 
for(i=0; i<p2A.size(); i++) 
{ 
vector<int> tpath2A; 
for(j=0; j<p2A[i].size(); j++) {tpath2A.push_back(inv(index2A)[p2A[i][j]]);} 
shortest_path2A.push_back(tpath2A); 
} 
//Compute distance between vertex 1 and vertex 2 
int DA=0; 
for(i=0; i<shortest_path1A.size(); i++) 
if(shortest_path1A[i][shortest_path1A[i].size()-1]==N2) 
{DA=shortest_path1A[i].size()-1; break;}  
//Compute shortest paths between vertex1 and vertex 2 
vector<vector<int> > shortest_path12A; 
for(i=0; i<shortest_path1A.size(); i++) 
for(j=0; j<shortest_path2A.size(); j++) 
{ 
if(shortest_path1A[i][shortest_path1A[i].size()-1]== 
shortest_path2A[j][shortest_path2A[j].size()-1]) 
{ 
vector<int> temppathA=shortest_path1A[i]; 
for(k=shortest_path2A[j].size()-2; k>=0; k--)  
temppathA.push_back(shortest_path2A[j][k]); 
if(temppathA.size()-1==DA)  
shortest_path12A.push_back(temppathA); 
}  
} 
//Pair graph for vertex 1 and vertex 2 
bool checkA=false; 
set<int> SA; 
for(i=0; i<shortest_path12A.size(); i++) 
{ 
if(shortest_path12A[i][0]==N1 &&  
shortest_path12A[i][shortest_path12A[i].size()-1]==N2) 
{ 
checkA=true; 
for(j=0; j<shortest_path12A[i].size(); j++) 
SA.insert(shortest_path12A[i][j]); 
} 
} 
vector<int> VA; VA.push_back(N1); VA.push_back(N2); 
PA[VA]=SA; 
//Distance between vertex 1 and vertex 2 
if(checkA) dA[VA]=signA*DA; 
else dA[VA]=signA; 
//Count number of vertices in pair graph 
ntA[VA]=SA.size(); 
//Count number of edges in pair graph 
int countA=0; 
for(i=0; i<nA; i++) 
for(j=i+1; j<nA; j++) 
{ 
bool findpairA=false; 
set<int>::iterator i1A,i2A; 
i1A=SA.find(i); i2A=SA.find(j); 
if(i1A!=SA.end() && i2A!=SA.end()) findpairA=true; 
if(findpairA && graphA[i][j]!=0) countA++; 
} 
eA[VA]=countA;  
} 

//Make frequency table (sign frequency vectors) 
map<vector<int>,int>::iterator itA; 
map<vector<int>, vector<int> > frequencyA; 
vector<int> dummyA; for(i=0; i<nA; i++) dummyA.push_back(0); 
for(i=0; i<nA; i++) 
{  
for(j=0; j<nA; j++) 
{ 
vector<int> vecA; 
vector<int> indA; indA.push_back(i); indA.push_back(j); 
itA=dA.find(indA); 
vecA.push_back(itA->second); 
itA=ntA.find(indA);  
vecA.push_back(itA->second); 
itA=eA.find(indA);  
vecA.push_back(itA->second); 
frequencyA[vecA]=dummyA; 
} 
} 

map<vector<int>,vector<int> >::iterator ittA=frequencyA.begin(); 
while(ittA!=frequencyA.end()) 
{ 
for(i=0; i<nA; i++) 
{  
int fA=0; 
for(j=0; j<nA; j++) 
{ 
vector<int> vecA; 
vector<int> indA; indA.push_back(i); indA.push_back(j); 
itA=dA.find(indA); 
vecA.push_back(itA->second); 
itA=ntA.find(indA);  
vecA.push_back(itA->second); 
itA=eA.find(indA);  
vecA.push_back(itA->second); 
if(vecA==ittA->first) fA++; 
} 
ittA->second[i]=fA; 
} 
ittA++; 
} 

//Transpose and sort (canonical form of sign matrix) 
vector<vector<int> > vssA; 
ittA=frequencyA.begin(); 
while(ittA!=frequencyA.end()) 
{ 
vector<int> vsA=ittA->second; 
vssA.push_back(vsA); 
ittA++;  
} 
vector<vector<int> > tvssA; 
vector<int> rowA; 
for(i=0; i<vssA.size(); i++) rowA.push_back(0); 
for(j=0; j<vssA[0].size(); j++) tvssA.push_back(rowA); 
for(i=0; i<vssA.size(); i++) 
for(j=0; j<vssA[0].size(); j++) 
tvssA[j][i]=vssA[i][j]; 
for(i=0; i<tvssA.size(); i++) tvssA[i].push_back(i); 
sort(tvssA.begin(),tvssA.end()); 


//Determine equivalence classes k 
vector<int> classA;  
vector<int> clA, dlA; 
int cA=0; 
int icA=0; 
dlA=tvssA[icA]; dlA.pop_back(); 
while(icA<nA) 
{ 
clA=tvssA[icA]; clA.pop_back(); 
if(clA==dlA) classA.push_back(cA); 
else {dlA=clA; cA++; classA.push_back(cA);} 
icA++;  
} 

//Final Vertices 
vector<int> vertexA; 
for(i=0; i<nA; i++) 
vertexA.push_back(tvssA[i][tvssA[i].size()-1]); 

//Final Sign Matrix 
map<vector<int>,vector<int> > signmatrixA; 
for(i=0; i<nA; i++) 
for(j=0; j<nA; j++) 
{ 
vector<int> indA;  
indA.push_back(vertexA[i]);  
indA.push_back(vertexA[j]);  
vector<int> siA; 
itA=dA.find(indA); siA.push_back(itA->second); 
itA=ntA.find(indA); siA.push_back(itA->second); 
itA=eA.find(indA); siA.push_back(itA->second); 
signmatrixA[indA]=siA; 
} 


//Process Graph B 
cout<<"Computing the Sign Matrix of Graph B..."<<endl; 
int nB; infileB>>nB; 
//Read adjacency matrix of graph B from graphB.txt 
vector< vector<int> > rgraphB; int valB; 
for(i=0; i<nB; i++) 
{ 
vector<int> rowB; 
for(j=0; j<nB; j++) 
{ 
infileB>>valB; 
rowB.push_back(valB); 
} 
rgraphB.push_back(rowB); 
} 
//End reading 

//Initial sorting 
vector<vector<int> > distanceB; 
vector<vector<int> > neighborB; 
for(i=0; i<rgraphB.size(); i++) 
{ 
vector<int> rowdistanceB, rowneighborB;  
for(j=0; j<rgraphB[i].size(); j++) 
{ 
if(rgraphB[i][j]==1) rowneighborB.push_back(j); 
vector<int> indexdB; 
for(k=0; k<rgraphB.size(); k++) indexdB.push_back(k); 
indexdB[0]=i; indexdB[i]=0; 
vector<vector<int> > dgraphB=reindex(rgraphB,indexdB); 
vector<vector<int> > dpathB=dijkstra(dgraphB); 
int ddB=-1; 
for(k=0; k<dpathB.size(); k++) 
if(inv(indexdB)[dpathB[k][dpathB[k].size()-1]]==j) 
{ddB=dpathB[k].size()-1; break;} 
rowdistanceB.push_back(ddB);  
}  
distanceB.push_back(rowdistanceB); 
neighborB.push_back(rowneighborB); 
} 

vector<vector<int> > sequenceB; 
for(i=0; i<rgraphB.size(); i++) 
{ 
vector<int> mutualdistanceB; 
for(j=0; j<neighborB[i].size()-1; j++) 
for(k=j+1; k<neighborB[i].size(); k++) 
mutualdistanceB.push_back(distanceB[neighborB[i][j]][neighborB[i][k]]);  
sort(mutualdistanceB.begin(), mutualdistanceB.end()); 
vector<int> tmutualB; 
for(k=0; k<nB*nB-1-mutualdistanceB.size(); k++) tmutualB.push_back(0); 
for(k=0; k<mutualdistanceB.size(); k++) tmutualB.push_back(mutualdistanceB[k]); 
sequenceB.push_back(tmutualB);  
} 

map<vector<int>,int> sorterB; 
for(i=0; i<sequenceB.size(); i++) sorterB[sequenceB[i]]=i; 
vector<int> mainindexB; 
map<vector<int>,int>::iterator sitB=sorterB.begin(); 
while(sitB!=sorterB.end()) 
{ 
vector<int>vsitB=sitB->first; 
for(i=0; i<sequenceB.size(); i++) 
if(sequenceB[i]==vsitB) mainindexB.push_back(i); 
sitB++;  
} 

vector< vector<int> > graphB=reindex(rgraphB,mainindexB); 

//Compute degree sequence 
vector<int> degB; 
int sumB; 
for(i=0; i<nB; i++) 
{ 
sumB=0; 
for(j=0; j<nB; j++) 
{ 
if(graphB[i][j]==1) sumB++; 
} 
degB.push_back(sumB); 
} 
vector<int> sorted_degB=degB; 
sort(sorted_degB.begin(),sorted_degB.end()); 

//Pair graphs 
map<vector<int>,set<int> > PB; 
map<vector<int>,int> dB; 
map<vector<int>,int> ntB; 
map<vector<int>,int> eB; 

for(N1=0; N1<graphB.size(); N1++) 
for(N2=0; N2<graphB[N1].size(); N2++) 
{ 
int signB=-1; 
vector<vector<int> > tgraphB=graphB; 
if(graphB[N1][N2]!=0) {tgraphB[N1][N2]=0; tgraphB[N2][N1]=0; signB=1;} 
//Compute shortest paths from vertex 1  
vector<vector<int> > shortest_path1B; 
vector<int> index1B; for(q=0; q<nB; q++) index1B.push_back(q);  
index1B[0]=N1; index1B[N1]=0;  
vector< vector<int> > temp_graph1B=reindex(tgraphB, index1B);  
vector< vector<int> > p1B=dijkstra(temp_graph1B); 
for(i=0; i<p1B.size(); i++) 
{ 
vector<int> tpath1B; 
for(j=0; j<p1B[i].size(); j++) {tpath1B.push_back(inv(index1B)[p1B[i][j]]);} 
shortest_path1B.push_back(tpath1B); 
} 
//Compute shortest paths from vertex 2  
vector<vector<int> > shortest_path2B; 
vector<int> index2B; for(q=0; q<nB; q++) index2B.push_back(q);  
index2B[0]=N2; index2B[N2]=0;  
vector< vector<int> > temp_graph2B=reindex(tgraphB, index2B);  
vector< vector<int> > p2B=dijkstra(temp_graph2B); 
for(i=0; i<p2B.size(); i++) 
{ 
vector<int> tpath2B; 
for(j=0; j<p2B[i].size(); j++) {tpath2B.push_back(inv(index2B)[p2B[i][j]]);} 
shortest_path2B.push_back(tpath2B); 
} 
//Compute distance between vertex 1 and vertex 2 
int DB=0; 
for(i=0; i<shortest_path1B.size(); i++) 
if(shortest_path1B[i][shortest_path1B[i].size()-1]==N2) 
{DB=shortest_path1B[i].size()-1; break;}  
//Compute shortest paths between vertex 1 and vertex 2 
vector<vector<int> > shortest_path12B; 
for(i=0; i<shortest_path1B.size(); i++) 
for(j=0; j<shortest_path2B.size(); j++) 
{ 
if(shortest_path1B[i][shortest_path1B[i].size()-1]== 
shortest_path2B[j][shortest_path2B[j].size()-1]) 
{ 
vector<int> temppathB=shortest_path1B[i]; 
for(k=shortest_path2B[j].size()-2; k>=0; k--)  
temppathB.push_back(shortest_path2B[j][k]); 
if(temppathB.size()-1==DB)  
shortest_path12B.push_back(temppathB); 
}  
} 
//Pair graph for vertex 1 and vertex 2 
bool checkB=false; 
set<int> SB; 
for(i=0; i<shortest_path12B.size(); i++) 
{ 
if(shortest_path12B[i][0]==N1 &&  
shortest_path12B[i][shortest_path12B[i].size()-1]==N2) 
{ 
checkB=true; 
for(j=0; j<shortest_path12B[i].size(); j++) 
SB.insert(shortest_path12B[i][j]); 
} 
} 
vector<int> VB; VB.push_back(N1); VB.push_back(N2); 
PB[VB]=SB; 
//Distance between vertex 1 and vertex 2 
if(checkB) dB[VB]=signB*DB; 
else dB[VB]=signB; 
//Count number of vertices in pair graph 
ntB[VB]=SB.size(); 
//Count number of edges in pair graph 
int countB=0; 
for(i=0; i<nB; i++) 
for(j=i+1; j<nB; j++) 
{ 
bool findpairB=false; 
set<int>::iterator i1B,i2B; 
i1B=SB.find(i); i2B=SB.find(j); 
if(i1B!=SB.end() && i2B!=SB.end()) findpairB=true; 
if(findpairB && graphB[i][j]!=0) countB++; 
} 
eB[VB]=countB;  
} 

//Make frequency table (sign frequency vectors) 
map<vector<int>,int>::iterator itB; 
map<vector<int>, vector<int> > frequencyB; 
vector<int> dummyB; for(i=0; i<nB; i++) dummyB.push_back(0); 
for(i=0; i<nB; i++) 
{  
for(j=0; j<nB; j++) 
{ 
vector<int> vecB; 
vector<int> indB; indB.push_back(i); indB.push_back(j); 
itB=dB.find(indB); 
vecB.push_back(itB->second); 
itB=ntB.find(indB);  
vecB.push_back(itB->second); 
itB=eB.find(indB);  
vecB.push_back(itB->second); 
frequencyB[vecB]=dummyB; 
} 
} 

map<vector<int>,vector<int> >::iterator ittB=frequencyB.begin(); 
while(ittB!=frequencyB.end()) 
{ 
for(i=0; i<nB; i++) 
{  
int fB=0; 
for(j=0; j<nB; j++) 
{ 
vector<int> vecB; 
vector<int> indB; indB.push_back(i); indB.push_back(j); 
itB=dB.find(indB); 
vecB.push_back(itB->second); 
itB=ntB.find(indB);  
vecB.push_back(itB->second); 
itB=eB.find(indB);  
vecB.push_back(itB->second); 
if(vecB==ittB->first) fB++; 
} 
ittB->second[i]=fB; 
} 
ittB++; 
} 

//Transpose and sort (canonical form of sign matrix) 
vector<vector<int> > vssB; 
ittB=frequencyB.begin(); 
while(ittB!=frequencyB.end()) 
{ 
vector<int> vsB=ittB->second; 
vssB.push_back(vsB); 
ittB++;  
} 
vector<vector<int> > tvssB; 
vector<int> rowB; 
for(i=0; i<vssB.size(); i++) rowB.push_back(0); 
for(j=0; j<vssB[0].size(); j++) tvssB.push_back(rowB); 
for(i=0; i<vssB.size(); i++) 
for(j=0; j<vssB[0].size(); j++) 
tvssB[j][i]=vssB[i][j]; 
for(i=0; i<tvssB.size(); i++) tvssB[i].push_back(i); 
sort(tvssB.begin(),tvssB.end()); 

//Determine equivalence classes k 
vector<int> classB;  
vector<int> clB, dlB; 
int cB=0; 
int icB=0; 
dlB=tvssB[icB]; dlB.pop_back(); 
while(icB<nB) 
{ 
clB=tvssB[icB]; clB.pop_back(); 
if(clB==dlB) classB.push_back(cB); 
else {dlB=clB; cB++; classB.push_back(cB);} 
icB++;  
} 

//Final Vertices 


vector<int> vertexB; 
for(i=0; i<nB; i++) 
vertexB.push_back(tvssB[i][tvssB[i].size()-1]); 

//Final Sign Matrix 
map<vector<int>,vector<int> > signmatrixB; 
for(i=0; i<nB; i++) 
for(j=0; j<nB; j++) 
{ 
vector<int> indB;  
indB.push_back(vertexB[i]);  
indB.push_back(vertexB[j]);  
vector<int> siB; 
itB=dB.find(indB); siB.push_back(itB->second); 
itB=ntB.find(indB); siB.push_back(itB->second); 
itB=eB.find(indB); siB.push_back(itB->second); 
signmatrixB[indB]=siB; 
} 

//Isomorphism Index 
vector<int> fixisoB, isoB;  
for(i=0; i<nB; i++) fixisoB.push_back(i); isoB=fixisoB; 
bool isomorphic = false; 
bool possibly_isomorphic = false; 
if(sorted_degA==sorted_degB){ 
vector<vector<int> > checksignA; 
ittA=frequencyA.begin(); 
while(ittA!=frequencyA.end()) 
{ 
vector<int> checksignrowA; 
vector<int> wsA=ittA->first; 
for(i=0; i<wsA.size(); i++) checksignrowA.push_back(wsA[i]); 
vector<int> vsA=ittA->second; 
for(i=0; i<vsA.size(); i++) checksignrowA.push_back(vsA[vertexA[i]]); 
checksignA.push_back(checksignrowA); 
ittA++;  
} 
vector<vector<int> > checksignB; 
ittB=frequencyB.begin(); 
while(ittB!=frequencyB.end()) 
{ 
vector<int> checksignrowB; 
vector<int> wsB=ittB->first; 
for(i=0; i<wsB.size(); i++) checksignrowB.push_back(wsB[i]); 
vector<int> vsB=ittB->second; 
for(i=0; i<vsB.size(); i++) checksignrowB.push_back(vsB[vertexB[i]]); 
checksignB.push_back(checksignrowB); 
ittB++;  
} 
if(checksignA==checksignB) {possibly_isomorphic=true;} 
} 

if(possibly_isomorphic) 
{ 
//Find isomorphism 
for(int J=0; J<nB; J++) 
{ 
if(isomorphic) break; 
isoB=fixisoB; isoB[0]=fixisoB[J]; isoB[J]=fixisoB[0];  
for(int I=0; I<nB*nB; I++) 
{ 
vector<int> oldisoB=isoB; 
isoB=transform(signmatrixA,signmatrixB,vertexA,vertexB, isoB); 


bool quit=false, mismatch=false; 
for(int ii=0; ii<nB; ii++) 
{ 
if(quit) break;  
for(int jj=ii+1; jj<nB; jj++) 
{ 
vector<int> tindA, ta;  
tindA.push_back(vertexA[ii]); tindA.push_back(vertexA[jj]); 
vector<int> tindB, tb;  
tindB.push_back(vertexB[isoB[ii]]);  
tindB.push_back(vertexB[isoB[jj]]);  
ittA=signmatrixA.find(tindA); ta=ittA->second;  


ittB=signmatrixB.find(tindB); tb=ittB->second;  
if(ta!=tb) {mismatch=true; quit=true; break;} 
}  
}  
if(isoB==oldisoB) 
{ 
if(!mismatch) isomorphic=true; 
break; 
} 
} 
} 

} 

if(!possibly_isomorphic)  
{ 
outfile<<"Graph A and Graph B cannot be isomorphic because " 
<<"they have different sign frequency vectors in lexicographic order." 
<<endl;  
cout<<"Graph A and Graph B cannot be isomorphic because " 
<<"they have different sign frequency vectors in lexicographic order." 
<<endl; 
} 
if(possibly_isomorphic && !isomorphic)  
{ 
outfile<<"Graph A and Graph B have the same sign frequency vectors " 
<<"in lexicographic order but cannot be isomorphic."<<endl;  
cout<<"Graph A and Graph B have the same sign frequency vectors " 
<<"in lexicographic order but cannot be isomorphic."<<endl; 
} 
if(possibly_isomorphic && isomorphic)  
{ 
outfile<<"Graph A and Graph B are isomorphic."<<endl<<endl;  
cout<<"Graph A and Graph B are isomorphic."<<endl; 
outfile<<"Isomorphism f:V(A)->V(B);"<<endl<<endl; 
for(int i=0; i<nA; i++)  
{  
outfile<<"f("<<inv(mainindexA)[vertexA[i]]+1<<")\t=\t";  
outfile<<inv(mainindexB)[vertexB[isoB[i]]]+1<<endl; 
}  
} 

cout<<"See result.txt for details."<<endl; 
return 0; 
} 



//Functions 

vector<vector<int> > dijkstra(vector<vector<int> > graph) 
{ 
vector<vector<int> > table; 
int i, j, k, n=graph.size();  
//Initialize Table 
const int infinity=n; 
vector<bool> known; 
for(i=0; i<n; i++) known.push_back(false); 
vector<int> d; 
d.push_back(0); 
for(i=1; i<n; i++) d.push_back(infinity); 
vector<int> p; 
for(i=0; i<n; i++) p.push_back(-1); 
//End initialization 

//Iteration 
for(k=0; k<n; k++) 
{ 
//Find min of d for unknown vertices 
int min=0; 
while(known[min]==true)min++; 
for(i=0; i<n; i++) 
if(known[i]==false && d[i]<d[min])min=i; 
//End find 
//Update Table 
known[min]=true; 
for(j=0; j<n; j++) 
{ 
if(graph[min][j]!=0 && d[j]>d[min]+graph[min][j] && known[j]==false) 
{ 
d[j]=d[min]+graph[min][j]; 
p[j]=min; 
} 
} 
//End update 
} 
table.push_back(d); 
table.push_back(p); 
vector<vector<int> > path; 
for(i=0; i<n; i++) 
{ 
vector<int> temp_path; 
vector<int> temp; 
k=i; 
while(k!=-1) 
{ 
temp.push_back(k); 
k=table[1][k]; 
} 
temp_path.push_back(temp[temp.size()-1]); 
for(j=temp.size()-2; j>=0; j--) 
{ 
temp_path.push_back(temp[j]); 
} 
path.push_back(temp_path); 
}  
return path;  
} 

vector<vector<int> > reindex(vector<vector<int> > graph, vector<int> index) 
{ 
vector<vector<int> > temp_graph=graph; 
for(int i=0; i<graph.size(); i++) 
for(int j=0; j<graph[i].size(); j++) 
temp_graph[index[i]][index[j]]=graph[i][j]; 
return temp_graph;  
} 

vector<int> inv(vector<int> index) 
{ 
vector<int> inverse=index; 
for(int i=0; i<index.size(); i++) 
inverse[index[i]]=i; 
return inverse;  
} 

vector<int> transform(map<vector<int>,vector<int> > signmatrixA,  
  map<vector<int>,vector<int> > signmatrixB,  
  vector<int> vertexA, vector<int> vertexB,  
  vector<int> isoB) 
{ 
vector<int> iso=isoB; 
map<vector<int>,vector<int> >::iterator it; 
int k, n=iso.size(); 
bool found=false; 
bool check=true; 
for(int i=0; i<n; i++) 
{ 
if(found) break; 
for(int j=i+1; j<n; j++) 
{ 
vector<int> indA, a;  
indA.push_back(vertexA[i]); indA.push_back(vertexA[j]); 
vector<int> indB, b;  

indB.push_back(vertexB[isoB[i]]);  
indB.push_back(vertexB[isoB[j]]);  
it=signmatrixA.find(indA); a=it->second;  
it=signmatrixB.find(indB); b=it->second;  
if(a!=b) 
{ 
k=j;  
vector<int> temp_ind=indB; 
while(k<n-1 && check==true) 
{ 
k++;  
temp_ind[1]=vertexB[isoB[k]]; 
it=signmatrixB.find(temp_ind); b=it->second;  
//check 
if(a==b) 
{ 
vector<int> temp_iso=isoB; 
temp_iso[j]=isoB[k];  temp_iso[k]=isoB[j]; 
int ti=-1, tj=-1;  
bool quit=false; 
for(int ii=0; ii<n; ii++) 
{ 
if(quit) break;  
for(int jj=ii+1; jj<n; jj++) 
{ 
vector<int> tindA, ta;  
tindA.push_back(vertexA[ii]); tindA.push_back(vertexA[jj]); 
vector<int> tindB, tb;  
tindB.push_back(vertexB[temp_iso[ii]]);  
tindB.push_back(vertexB[temp_iso[jj]]);  
it=signmatrixA.find(tindA); ta=it->second;  
it=signmatrixB.find(tindB); tb=it->second;  
if(ta!=tb) {ti=ii; tj=jj; quit=true; break;} 
if(k==n-1 && ti==-1) {check=false; quit=true; break;} 
}  
} 
if(ti==-1 || ti>i || (ti==i && tj>j)) check=false; 
} 
//end check  
} 
if(!check){found=true; iso[j]=isoB[k]; iso[k]=isoB[j];  
break;} 
if(check) return iso; 
}  
} 
} 
return iso;  
}

The output of the program for the input in Figure 6.2 is shown in Example 3.6. The next section shows many more examples of input/output files. The download package also contains a visualizer for drawing graphs according to the output of the demonstration program.

We now demonstrate the Graph Isomorphism Algorithm for several examples. The first set of examples 7.1-7.5 consists of isomorphic graphs whose vertices have been permuted randomly so that the isomorphism is well and truly hidden. The second set of examples 7.6-7.9 consists of graphs that are not isomorphic and yet have a very similar structure, hence deciding that they are not isomorphic in polynomial-time demonstrates the power of the algorithm. 

7.1. Example. We run the program on isomorphic Petersen [5] graphs A and B as input:
 

Graph A

10   0 1 0 0 1 0 1 0 0 0   1 0 1 0 0 0 0 1 0 0   0 1 0 1 0 0 0 0 1 0   0 0 1 0 1 0 0 0 0 1   1 0 0 1 0 1 0 0 0 0   0 0 0 0 1 0 0 1 1 0   1 0 0 0 0 0 0 0 1 1   0 1 0 0 0 1 0 0 0 1   0 0 1 0 0 1 1 0 0 0   0 0 0 1 0 0 1 1 0 0

 

Graph B

10  0 0 0 1 0 1 0 0 0 1   0 0 0 1 1 0 1 0 0 0   0 0 0 0 0 0 1 1 0 1   1 1 0 0 0 0 0 1 0 0  0 1 0 0 0 0 0 0 1 1   1 0 0 0 0 0 1 0 1 0   0 1 1 0 0 1 0 0 0 0   0 0 1 1 0 0 0 0 1 0   0 0 0 0 1 1 0 1 0 0   1 0 1 0 1 0 0 0 0 0

The algorithm finds an explicit isomorphism, shown below.
 

Figure 7.1. The Petersen graphs are isomorphic

7.2. Example. We run the program on isomorphic Icosahedron [6] graphs A and B as input:
 

Graph A

12  0 1 1 0 0 1 1 1 0 0 0 0   1 0 1 1 1 1 0 0 0 0 0 0   1 1 0 1 0 0 0 1 1 0 0 0   0 1 1 0 1 0 0 0 1 1 0 0   0 1 0 1 0 1 0 0 0 1 1 0   1 1 0 0 1 0 1 0 0 0 1 0   1 0 0 0 0 1 0 1 0 0 1 1   1 0 1 0 0 0 1 0 1 0 0 1   0 0 1 1 0 0 0 1 0 1 0 1   0 0 0 1 1 0 0 0 1 0 1 1   0 0 0 0 1 1 1 0 0 1 0 1   0 0 0 0 0 0 1 1 1 1 1 0

 

Graph B

12  0 0 1 0 0 1 0 0 1 1 0 1   0 0 0 1 1 0 0 1 1 0 0 1   1 0 0 0 0 1 0 1 1 0 1 0   0 1 0 0 1 0 1 1 0 0 1 0   0 1 0 1 0 0 1 0 0 1 0 1   1 0 1 0 0 0 1 0 0 1 1 0   0 0 0 1 1 1 0 0 0 1 1 0   0 1 1 1 0 0 0 0 1 0 1 0   1 1 1 0 0 0 0 1 0 0 0 1   1 0 0 0 1 1 1 0 0 0 0 1   0 0 1 1 0 1 1 1 0 0 0 0   1 1 0 0 1 0 0 0 1 1 0 0

The algorithm finds an explicit isomorphism, shown below. 
 

Figure 7.2. The Icosahedron graphs are isomorphic

7.3. Example. We run the program on isomorphic Ramsey [7] graphs A and B as input:
 

Graph A

17  0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1   1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1   1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0   0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1   1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0   0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0  0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0   0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1   1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1   1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0   0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0   0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0   0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1   1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0   0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1   1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1   1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0

 

Graph B

17  0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0   0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0   0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0   0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1   0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0   1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0   0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1   1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0   1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1   0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1   1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1   0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1   1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1   1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0   1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1   1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0   0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0

The algorithm finds an explicit isomorphism, shown below. 
 

Figure 7.3. The Ramsey graphs are isomorphic

7.4. Example. We run the program on isomorphic Dodecahedron [6] graphs A and B as input:
 

Graph A

20  0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0   1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0   0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0   0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0  1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0   0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0   0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0   0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1   1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0   0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1   0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0   0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1   0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0

 

Graph B

20  0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0   0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0   0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0   0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0   1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0   1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0   0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0   0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1   0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0   0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0   1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0   0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1   0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0   0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0

The algorithm finds an explicit isomorphism, shown below.
 

Figure 7.4. The Dodecahedron graphs are isomorphic

7.5. Example. We run the program on isomorphic Coxeter [8] graphs A and B as input:
 

Graph A

30  0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1   1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0   0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0   0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0   0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0  0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1   0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0   0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0   0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0   0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0   0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0

 

Graph B

30  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0   0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0   0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0   0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0   0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0   0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0   0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0   1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1   0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1   0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0   0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0   0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0   0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0   1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0

The algorithm finds an explicit isomorphism, shown below.
 

Figure 7.5. The Coxeter graphs are isomorphic

7.6. Example. We run the program on nonisomorphic Praust [9] graphs A and B as input:
 

Graph A

20  0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0   1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0   1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0   1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0   1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0   0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0   0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0   1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0   0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0   0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0   0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1   0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0   0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0   0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1   0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0   0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1   0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1   0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1   0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0

 

Graph B

20  0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0   1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0   1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0   1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0   1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0   0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1   0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0   0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0   1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0  0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0   0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0   0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0   0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1   0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0   0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1   0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0   0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0   0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1   0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1   0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0

Graph A and Graph B have the same sign frequency vectors in lexicographic order, so their structure is very similar. The algorithm determines that the graphs are not isomorphic, shown below.
 

Figure 7.6. The Praust graphs are not isomorphic

7.7. Example. We run the program on nonisomorphic Mathon [10] graphs A and B as input:
 

Graph A

25  0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1   0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1   0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0   0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1  0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1   0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0   1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 

Graph B

25  0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0   0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1   0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1   0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0   0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1   0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1   0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0  1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Graph A and Graph B have the same sign frequency vectors in lexicographic order, so their structure is very similar. The algorithm determines that the graphs are not isomorphic, shown below.
 

Figure 7.7. The Mathon graphs are not isomorphic

7.8. Example. We run the program on nonisomorphic Weisfeiler [11] graphs A and B as input:
 

Graph A

25  0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0   1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0   1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1   1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0   1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0   1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1   1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1   1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1   1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0   1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1   1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0   1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0   1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1   0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1   0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0   0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1   0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1   0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0   0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0   0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0   0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1   0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0   0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1  0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1   0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

 

Graph B

25  0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0   1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0   1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1   1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0   1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0   1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1   1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1   1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1   1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1   1 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0  1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0   1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0   1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1   0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1   0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0   0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1   0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1   0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0   0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0   0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0   0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0   0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1   0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1   0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1   0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0

Graph A and Graph B have different sign frequency vectors in lexicographic order. The algorithm determines that the graphs are not isomorphic, shown below.
 

Figure 7.8. The Weisfeiler graphs are not isomorphic

7.9. Example. We run the program on nonisomorphic Siberian [12] graphs A and B as input:
 

Graph A

40  0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1   0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1   0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1   0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 1  0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0   1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0  0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0   0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0   0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0  1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1   1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0   0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1   0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1   0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0   0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0   1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0   0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0   0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1   0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0   0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1   0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0   1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0   0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0   0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0   0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0   0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0   0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1   1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0   1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0   0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0   0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0   0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0   1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0   1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1   0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0   1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0   0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1   1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0   1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0

 

Graph B

40  0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1  1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0   0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0   0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0  0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1   0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0   0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0   0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1   0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1   1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0   0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0   1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0   0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0  0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0   0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0   0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1   0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0   0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0   1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1   0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1   1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1   1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0   1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0   0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1   0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0   0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0   0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0   0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0   1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0   0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0   0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0   0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0   1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0   0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1   0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1   0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1   1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0   1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0   1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0

Graph A and Graph B have the same sign frequency vectors in lexicographic order, so their structure is very similar. The algorithm determines that the graphs are not isomorphic, shown below.