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

DeleteIsoG1[gl_List]:= Module[{},

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]]; 

1 Answer 1


You can use the CanonicalGraph function in concert with DeleteDuplicatesBy:

DeleteIso[gs_List] := DeleteDuplicatesBy[gs, CanonicalGraph]
  • 4
    $\begingroup$ +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. $\endgroup$
    – ybeltukov
    Commented Nov 14, 2015 at 17:26
  • $\begingroup$ @Pillsy Your solution works like a charm! $\endgroup$
    – hxiao
    Commented Nov 15, 2015 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.