Suppose I have a list and a notion of what it means for two elements to be isomorphic. I would like to create a subset of the list with exactly one representative from each isomorphism class.

The specific case in which I want to apply this is I have a list of graphs, and I would like to remove isomorphic duplicates. I have a very long list of graphs (~100,000) that I would like to apply this to.

Another example:


And my notion of isomorphism is if the numbers are the same mod 3. In this case, an acceptable output would be


(obviously this is not unique).

What is the most efficient way to do this? For example, one could "greedily" select elements, and at each step compare an element in L with the guys who were already chosen to be part of the output. I don't think this will terminate in a reasonable amount of time in my case.


closed as off-topic by MarcoB, LLlAMnYP, LCarvalho, m_goldberg, garej Jul 12 '17 at 6:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question arises due to a simple mistake such as a trivial syntax error, incorrect capitalization, spelling mistake, or other typographical error and is unlikely to help any future visitors, or else it is easily found in the documentation." – MarcoB, LLlAMnYP, LCarvalho, m_goldberg, garej
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ DeleteDuplicatesBy[{6, 7, 4, 3, 9, 30, 4}, Mod[#, 3] &]? $\endgroup$ – Kuba Jul 11 '17 at 12:13
  • $\begingroup$ This works in the specific example given but not in the case of a list of graphs and graph isomorphism $\endgroup$ – M. Brandt Jul 11 '17 at 12:21
  • 4
    $\begingroup$ DeleteDuplicates[listOfobjects, yourIsomorphism] where yourIsomorphism[obj1, obj2] is True is obj1 and obj2 are isomorphic, False otherwise. $\endgroup$ – kglr Jul 11 '17 at 12:26
  • $\begingroup$ Thank you! This worked. $\endgroup$ – M. Brandt Jul 11 '17 at 12:30

As mentioned in the comments DeleteDuplicates[listOfThings, isomorphicForMeQ] gives the desired result.

graphs = RandomGraph[UniformGraphDistribution[5, 5], 8];
Grid[Partition[graphs, 4]]

enter image description here

Row@DeleteDuplicates[graphs, IsomorphicGraphQ]

enter image description here

Using a made-up graph-isomorphism condition

myIsomorphicGraphQ = Equal @@ (Mean[HITSCentrality[#]] & /@ {##}) &;
Row@DeleteDuplicates[graphs, myIsomorphicGraphQ ]

enter image description here


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