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