Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindCanonicalHypergraphIsomorphism

Source Notebook

Find a canonical isomorphism between hypergraphs

Contributed by: Nikolay Murzin

ResourceFunction["FindCanonicalHypergraphIsomorphism"][hg1, hg2]

find a canonical isomorphism between hypergraphs hg1 and hg2 if it exists.

ResourceFunction["FindCanonicalHypergraphIsomorphism"][hg]

find an isomorphism from hypergraph hg to its canonical representation.

Details and Options

Canonicalization follows the definition and implementation of the resource function CanonicalHypergraph.
ResourceFunction["FindCanonicalHypergraphIsomorphism"] returns an association with vertex replacements, similar to FindGraphIsomorphism.
With "IncludePermutation"→True, a permutation of hyperedges is also included in output as {permutation, isomorphism}.

Examples

Basic Examples (3) 

Find a canonical isomorphism between two hypergraphs:

In[1]:=
ResourceFunction[ "FindCanonicalHypergraphIsomorphism"][{{a, e, d}, {d, c}, {c, b}, {b, a}}, {{2, 4}, {4, 5, 1}, {1, 3}, {3, 2}}]
Out[1]=

Find an isomorphism to hypergraph's canonical representation:

In[2]:=
ResourceFunction[ "FindCanonicalHypergraphIsomorphism"][{{a, e, d}, {d, c}, {c, b}, {b, a}}]
Out[2]=

Transform from one hypergraph to another if isomorphism exists:

In[3]:=
h1 = {{a, e, d}, {d, c}, {c, b}, {b, a}}; h2 = {{2, 4}, {4, 5, 1}, {1, 3}, {3, 2}};
In[4]:=
ResourceFunction["FindCanonicalHypergraphIsomorphism"][h1, h2]
Out[4]=
In[5]:=
Sort[h1 /. %] === Sort[h2]
Out[5]=

Scope (1) 

If no isomorphism exists, $Failed is returned:

In[6]:=
ResourceFunction[ "FindCanonicalHypergraphIsomorphism"][{{a, e, d}, {d, c}, {c, b}, {b, a}}, {{2, 4}, {4, 3, 1}, {1, 3}, {5, 2}}]
Out[6]=

Options (1) 

IncludePermutation (1) 

Include a permutation of hyperedges in the output:

In[7]:=
h1 = {{a, e, d}, {d, c}, {c, b}, {b, a}}; h2 = {{2, 4}, {4, 5, 1}, {1, 3}, {3, 2}};
In[8]:=
{perm, iso} = ResourceFunction["FindCanonicalHypergraphIsomorphism"][h1, h2, "IncludePermutation" -> True]
Out[8]=
In[9]:=
Permute[h1 /. iso, perm] === h2
Out[9]=

Properties and Relations (1) 

The result of the resource function CanonicalHypergraph can be reproduced by combining an isomorphism with a permutation:

In[10]:=
h = ResourceFunction[ "RandomHypergraph"][{7, {{1, 2}, {2, 3}, {3, 4}, {4, 5}}}]
Out[10]=
In[11]:=
{perm, iso} = ResourceFunction["FindCanonicalHypergraphIsomorphism"][h, "IncludePermutation" -> True]
Out[11]=
In[12]:=
Permute[h /. iso, perm] === ResourceFunction["CanonicalHypergraph"][h]
Out[12]=

Version History

  • 1.0.0 – 09 May 2022

Related Resources

License Information