Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindOrderedHypergraphIsomorphism

Source Notebook

Find isomorphisms between two ordered (directed) hypergraphs

Contributed by: Jonathan Gorard

ResourceFunction["FindOrderedHypergraphIsomorphism"][h1,h2]

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

Details and Options

Hypergraphs are specified as lists of edges.
ResourceFunction["FindOrderedHypergraphIsomorphism"] 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["FindOrderedHypergraphIsomorphism"] gives an empty association if no isomorphism can be found.
Two ordered hypergraphs are isomorphic if there exists a renaming of vertices that makes them identical.
The algorithm used in ResourceFunction["FindOrderedHypergraphIsomorphism"] 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 ordered hypergraphs:

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

Scope (2) 

FindOrderedHypergraphIsomorphism also works for standard directed graphs:

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