Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 IsomorphicOrderedHypergraphQ

Source Notebook

Determine whether two ordered (directed) hypergraphs are isomorphic

Contributed by: Jonathan Gorard

ResourceFunction["IsomorphicOrderedHypergraphQ"][h1,h2]

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

Details and Options

Hypergraphs are specified as lists of hyperedges.
Two ordered hypergraphs are isomorphic if there exists a renaming of vertices that makes them identical.
The algorithm used in ResourceFunction["IsomorphicOrderedHypergraphQ"] 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 ordered hypergraphs are isomorphic:

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

Determine that two ordered hypergraphs are not isomorphic:

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

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

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

Scope (2) 

IsomorphicOrderedHypergraphQ also works for standard directed graphs:

In[4]:=
ResourceFunction[ "IsomorphicOrderedHypergraphQ"][{{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, IsomorphicOrderedHypergraphQ supports isomorphism testing on ordered multihypergraphs (i.e. hypergraphs with ordered multihyperedges):

In[6]:=
ResourceFunction[ "IsomorphicOrderedHypergraphQ"][{{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