Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 IsomorphicHypergraphQ

Source Notebook

Determine whether two orderless (undirected) hypergraphs are isomorphic

Contributed by: Jonathan Gorard

ResourceFunction["IsomorphicHypergraphQ"][h1,h2]

yields True if the hypergraphs h1 and h2 are isomorphic, and False otherwise.

Details and Options

Hypergraphs are specified as lists of hyperedges.
Two hypergraphs are isomorphic if there exists a renaming of vertices that makes them identical.
The algorithm used in ResourceFunction["IsomorphicHypergraphQ"] is a direct generalization of Gorard’s uniqueness tree algorithm for standard graph isomorphism: https://arxiv.org/abs/1606.06399.

Examples

Basic Examples (3) 

Determine that two hypergraphs are isomorphic:

In[1]:=
ResourceFunction[ "IsomorphicHypergraphQ"][{{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[ "IsomorphicHypergraphQ"][{{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[ "IsomorphicHypergraphQ"][{{1, 2}, {2, 3}, {3, 4}, {4, 5}}, {{1, 2}, {2, 3}, {3, 4}, {1, 5}}]
Out[3]=

Scope (2) 

IsomorphicHypergraphQ also works for standard undirected graphs:

In[4]:=
ResourceFunction[ "IsomorphicHypergraphQ"][{{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 IsomorphicGraphQ:

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

Furthermore, IsomorphicHypergraphQ supports isomorphism testing on multihypergraphs (i.e. hypergraphs with multihyperedges):

In[6]:=
ResourceFunction[ "IsomorphicHypergraphQ"][{{1, 2}, {1, 2}, {1, 3}, {1, 3}, {2, 4}, {3, 4}, {4, 1}}, {{1, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 4}, {4, 1}}]
Out[6]=

Publisher

Jonathan Gorard

Version History

  • 2.0.0 – 05 December 2019
  • 1.0.0 – 01 November 2019

Source Metadata

  • Citation:

Related Resources

License Information