Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CanonicalHypergraph

Source Notebook

Find a canonical version of a directed hypergraph

Contributed by: Ed Pegg Jr

ResourceFunction["CanonicalHypergraph"][graph]

finds a canonical version of a hypergraph.

Details and Options

The canonicalization follows several rules:
1.Tuples are sorted by length with longest tuples occuring first
2.Tuples of the same length are considered a rule part
3.A rule part with 3 tuples of length 2 has signature 32
4.Rule parts are ordered so that new alphabet terms are introduced with maximal frugality
ResourceFunction["CanonicalHypergraph"] uses a heuristic method and may not give a complete canonical form in all cases.

Examples

Basic Examples (3) 

Canonicalize a very simple hypergraph:

In[1]:=
ResourceFunction["CanonicalHypergraph"][{{5, 7}, {1, 2}}]
Out[1]=

A more complex case:

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

Hyperedges are sorted by reverse length:

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

Possible Issues (1) 

Hypergraphs with many edges and extreme symmetry will take awhile:

In[4]:=
highsymmetry = {#} & /@ Range[8]; ResourceFunction["CanonicalHypergraph"][highsymmetry]
Out[4]=

Version History

  • 1.0.0 – 25 March 2020

Related Resources

License Information