Graph Equality

As mentioned before, the adjacency matrix representation is insufficent to determine isomorphism, at least by simple element by element comparison. While there are algorithms to determine graph isomorphism, and perhaps even more efficient algorithms to determine tree isomorphism, development of such an algorithm was not the intent of this project. Rather than implement some algorithm ourselves, we turned to the nauty suite.

Using the command line tools and the simplified dreadnaut format, we can translate graphs to dreadnaut and then use the utility dretog to translate from dreadnaut to graph6 format, which is used by many of the other utilities in nauty. Sending the graph6 representation to labelg we retrieve the canonical label of a graph. Any graphs which are isomorphic share canonical labelings. Thus, by retrieving the canonical labeling of two graphs we can determine whether they are isomorphic, which we will henceforth denote $\mathit{gequal}(G_1, G_2)$.