Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindHypergraphIsomorphism

Source Notebook

Find all isomorphisms between two orderless (undirected) hypergraphs

Contributed by: Jonathan Gorard

ResourceFunction["FindHypergraphIsomorphism"][h1,h2]

finds all possible isomorphisms that map the hypergraph h1 to h2 by renaming vertices.

Details and Options

Hypergraphs are specified as lists of hyperedges.
ResourceFunction["FindHypergraphIsomorphism"] gives an association of the form Association[v1→{w1,…},v2→{w2,…}], where vi are vertices in h1 and wj are corresponding vertices in h2.
ResourceFunction["FindHypergraphIsomorphism"] gives an empty association if no isomorphism can be found.
Two hypergraphs are isomorphic if there exists a renaming of vertices that makes them identical.
The algorithm used in ResourceFunction["FindHypergraphIsomorphism"] is a direct generalization of Gorard’s uniqueness tree algorithm for standard graph isomorphism: https://arxiv.org/abs/1606.06399.

Examples

Basic Examples (3) 

Find all isomorphisms between two hypergraphs:

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

Determine that two hypergraphs are not isomorphic:

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

Lists of hyperedges that are isomorphic as orderless hypergraphs may not be isomorphic as ordered hypergraphs:

In[3]:=
ResourceFunction[ "FindHypergraphIsomorphism"][{{1, 2}, {2, 3}, {3, 4}, {4, 5}}, {{1, 2}, {2, 3}, {3, 4}, {1, 5}}]
Out[3]=

Scope (2) 

FindHypergraphIsomorphism also works for standard undirected graphs:

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

In this case, it is functionally equivalent to FindGraphIsomorphism[…,All]:

In[5]:=
FindGraphIsomorphism[Graph[{a <-> d, d <-> c, c <-> b, b <-> a}], Graph[{2 <-> 4, 4 <-> 1, 1 <-> 3, 3 <-> 2}], All]
Out[5]=

Publisher

Jonathan Gorard

Version History

  • 1.0.0 – 01 November 2019

Source Metadata

  • Citation:

Related Resources

License Information