STABCOL: Graph Isomorphism Testing Based on the Weisfeiler-Leman Algorithm

A coherent algebra is a matrix algebra over the field of the complex numbers which is closed under conjugate transposition and elementwise multiplication of matrices and which contains the identity matrix and the all 1 matrix. This algebraic structure has a variety of important applications. Among others, coherent algebras are an appropriate tool in the design of algorithms for two notoriously hard graph theoretical problems: the problems of deciding whether two graphs are isomorphic and of finding the automorphism partition of a graph. Weisfeiler and Leman stated a polynomial algorithm which computes the coherent algebra which is generated by the adjacency matrix of a graph. However, for almost three decades, no reasonable time bound was known for this method. Very recently, one of the authors established a theoretical time bound of O(n 3 log n) with n denoting the number of vertices in the graph. The aim of this paper is to document a computer implementation of the algorithm of Wei..