1
$\begingroup$

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:

L={6,7,4,3,9,30,4}

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

{6,7}

(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.

$\endgroup$

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
1
$\begingroup$

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

SeedRandom[1]
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

$\endgroup$

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