# efficient way to find isomorphic graph in a list

**URL:** <https://igraph.discourse.group/t/efficient-way-to-find-isomorphic-graph-in-a-list/1751>\
**Category:** Usage\
**Tags:** R\
**Created:** [15 February 2024 21:48 UTC](https://igraph.discourse.group/t/efficient-way-to-find-isomorphic-graph-in-a-list/1751 "2024-02-15T21:48:37Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Huimin721](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/huimin721/32/1007_2.png) [@Huimin721](https://igraph.discourse.group/u/Huimin721)\
**Post date:** [15 February 2024 21:48 UTC](https://igraph.discourse.group/t/efficient-way-to-find-isomorphic-graph-in-a-list/1751/1 "2024-02-15T21:48:37Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [16 February 2024 08:38 UTC](https://igraph.discourse.group/t/efficient-way-to-find-isomorphic-graph-in-a-list/1751/2 "2024-02-16T08:38:46Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Huimin721](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/huimin721/32/1007_2.png) [@Huimin721](https://igraph.discourse.group/u/Huimin721)\
**Post date:** [16 February 2024 16:55 UTC](https://igraph.discourse.group/t/efficient-way-to-find-isomorphic-graph-in-a-list/1751/3 "2024-02-16T16:55:10Z")

</div>

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!