If I have a list of graphs, and the nodes are colored, is there a way to split the list such that each element of the list contains a groups of isomorphic graph of the original list? other than run graph iseomorphic pairwise, if there a more efficient way? Thanks so much!
I don’t have the time to write a code example right now, but generally, the approach is to group graphs based on a canonical form. For example, compute the canonical_permutation() of each graph, permute the graph accordingly, then convert the graph into some object that is easy to compare, and use as a basis of groupings. In Mathematica, I would use the adjacency matrix and a list of vertex colours. I’m not sure quite sure what is easiest to work with in R, as I don’t often use that language.
This approach is linear in the number of graphs, as opposed to pairwise comparisons, which would be quadratic.
Thanks so much! Have came up with a way to efficiently compute this task yesterday and I was right using the idea of canonical grouping. Thanks for sharing, I did not know there is a term ‘canonical form’ for graph before!