6
$\begingroup$

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]];
|improve this question
$\endgroup$
8
$\begingroup$

You can use the CanonicalGraph function in concert with DeleteDuplicatesBy:

DeleteIso[gs_List] := DeleteDuplicatesBy[gs, CanonicalGraph]
|improve this answer
$\endgroup$
  • 2
    $\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 Nov 14 '15 at 17:26
  • $\begingroup$ @Pillsy Your solution works like a charm! $\endgroup$ – Han Xiao Nov 15 '15 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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