Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindCanonicalHypergraph

Source Notebook

Find a canonical version of a directed hypergraph

Contributed by: Ed Pegg Jr

ResourceFunction["FindCanonicalHypergraph"][graph]

finds a canonical version of a hypergraph.

Details and Options

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

Examples

Basic Examples (3) 

Find a canonical version of a very simple hypergraph:

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

A more complex case:

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

Hyperedges are sorted by reverse length:

In[3]:=
ResourceFunction[ "FindCanonicalHypergraph"][{{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 a while:

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

Version History

  • 3.0.0 – 17 February 2020
  • 2.0.0 – 19 December 2019
  • 1.0.0 – 17 December 2019

Related Resources

License Information