# Deleting isomorphic graphs efficiently

I'm trying to delete isomorphic graphs from a large list. My solution is as follows:

DeleteIsoG1[gl_List]:= Module[{},
DeleteDuplicates[gl,IsomorphicGraphQ]];


Unfortunately, it turns out very inefficient. I'm aware that graph isomorphism problem belongs to NP. I just need a relatively fast implementation in Mma.

Any comments or suggestions are welcome.

Update: I searched the forum. It looks that the performance can be improved by using other functions like DeleteDuplicatesBy or GatherBy instead of DeleteDuplicates. But according to the observation of @Mr.Wizard link, the behaviour of GatherBy is NOT a pairwise comparison. Hence it seems that we need a new method to get around here. The following is an implementation by using Gather. But it is slower than the one using DeleteDuplicates.

DeleteIsoG2[gl_List] := Module[{},
First /@ Gather[gl, IsomorphicGraphQ]];


You can use the CanonicalGraph function in concert with DeleteDuplicatesBy:
DeleteIso[gs_List] := DeleteDuplicatesBy[gs, CanonicalGraph]

• +1 Indeed, from docs: CanonicalGraph is often used to compare and match a graph to a large collection of graphs; isomorphic graphs have the same canonical graph. – ybeltukov Nov 14 '15 at 17:26