# Isomorphism Testing in Multigraphs Using Canonical Forms

**URL:** <https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116>\
**Category:** Usage\
**Tags:** Mathematica\
**Created:** [7 May 2025 10:46 UTC](https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116 "2025-05-07T10:46:43Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [7 May 2025 10:46 UTC](https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116/1 "2025-05-07T10:46:44Z")

</div>

None of the three algorithms in IGraphM support canonical forms for isomorphism testing.  
Are there any algorithms that handle isomorphism testing for unlabeled-edge multigraphs or edge-colored multigraphs using canonical forms?  
I’ve searched but haven’t been able to find any relevant information on this.  
Thanks for your help.

---

<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:** [7 May 2025 11:29 UTC](https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116/2 "2025-05-07T11:29:46Z")

</div>

> [@anhnha](#):
>
> None of the three algorithms in IGraphM support canonical forms for isomorphism testing.

Bliss is based on canonical forms, but it only supports simple graphs (with loops) with vertex colours. Multigraphs and edge colours are not supported.

> [@anhnha](#):
>
> Are there any algorithms that handle isomorphism testing for unlabeled-edge multigraphs or edge-colored multigraphs using canonical forms?

I don’t know. If you find a ready-made tool that does this, let us know.

The usual recommendation is to encode the edge-coloured multigraphs into a simple vertex-coloured graph, usually by subdividing edges and using a separate colour set for divider vertices vs. original vertices. This is quite a bit of work and requires careful attention.

[This](https://math.stackexchange.com/q/2844546/12384) refers to section 14 (“Variations”) of the nauty manual which is worth checking out.

---

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [7 May 2025 12:13 UTC](https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116/3 "2025-05-07T12:13:46Z")

</div>

Thank you very much for the detailed information.  
I’ll read through the references you mentioned, and I’ll let you know if I come across any tool.

---

<div class="post-metadata">

**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\
**Post date:** [9 May 2025 04:44 UTC](https://igraph.discourse.group/t/isomorphism-testing-in-multigraphs-using-canonical-forms/2116/4 "2025-05-09T04:44:57Z")

</div>

A post was split to a new topic: [Memory usage many multigraphs](https://igraph.discourse.group/t/memory-usage-many-multigraphs/2119)