Wolfram Research

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

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

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]=

Resource History

Source Metadata

Related Resources

License Information