You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Ordered Hypergraph Canonicalization
by Ed Pegg Jr
Synopsis: A canonicalization method for directed hypergraphs is presented. Spoiler: It’s a greedy method.
Graphs, Hypergraphs and Directed Graphs
Graphs, Hypergraphs and Directed Graphs
A graph is a collection of vertices joined in pairs to make edges. For example, the Petersen graph can be represented by vertices 1 to 10 and 15 edge pairs.
In[]:=
octag=Graph[GraphData["OctahedralGraph"],VertexLabels"Name",ImageSizeTiny]
Out[]=
A hypergraph allows more than one vertex per hyperedge. For example, the faces of an octahedron can be considered as a hypergraph.
In[]:=
octa=First/@#&/@FindCycle[octag,{3},All]
Out[]=
{{4,5,6},{3,6,5},{1,5,3},{2,3,6},{2,4,6},{1,3,2},{1,2,4},{1,5,4}}
In a directed graph, the ordering of edges in the graph is important. In the following balanced sink-source graph, all vertices have a total of 7 as inputs and 7 as outputs.
balancedoctahedron={{1,3},{1,4},{2,1},{2,6},{3,2},{3,5},{4,2},{4,5},{5,1},{5,6},{6,3},{6,4}};bog=Graph[DirectedEdge@@@balancedoctahedron,VertexLabels"Name",ImageSizeSmall]
Out[]=
Another property is that all unordered 3-cycles in the undirected graph are also ordered cycles in the directed graph.
In[]:=
First/@#&/@FindCycle[bog,{3},All]
Out[]=
{{4,5,6},{4,2,6},{3,5,6},{3,2,6},{1,4,5},{1,4,2},{1,3,5},{1,3,2}}
Here’s the canonical form of this directed graph. Notice how the first three edges use only 1-3, and the first five only use 1-4. That’s the greedy aspect of this algorithm, new vertices are introduced are frugally as possible.
In[]:=
bogcanon=ResourceFunction["FindCanonicalHypergraph"][balancedoctahedron]
Out[]=
{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}}
The canonical form still has 8 3-cycles.
In[]:=
First/@#&/@FindCycle[Graph[DirectedEdge@@@bogcanon],{3},All]
{{4,5,6},{3,6,4},{2,5,6},{2,3,6},{1,4,5},{1,4,3},{1,2,5},{1,2,3}}
We can mix up the vertices and edge orders of the graph.
In[]:=
mix=Table[RandomSample[bogcanon/.Thread[Range[6]RandomSample[Range[6]]]],{4}]
Out[]=
{{{2,3},{6,4},{1,3},{4,1},{6,5},{3,4},{4,2},{1,6},{2,6},{3,5},{5,1},{5,2}},{{5,4},{1,5},{1,2},{4,3},{2,4},{6,3},{6,1},{3,2},{5,6},{4,1},{3,5},{2,6}},{{1,2},{4,1},{1,6},{6,5},{2,4},{3,2},{6,4},{5,1},{5,3},{4,3},{3,6},{2,5}},{{5,2},{1,5},{6,3},{3,4},{5,3},{2,4},{3,1},{1,6},{4,5},{4,6},{6,2},{2,1}}}
Applying the canonicalizer to these always returns the canonical form of the graph.
In[]:=
ResourceFunction["FindCanonicalHypergraph"][#]&/@mix
Out[]=
{{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}},{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}},{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}},{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}}}
The greedy algorithm starts with all edges in separate lists, then tries adding all remaining edges to each list. Any list that contains more vertices than the others is discarded. As the lists of edges get to length 3, there are only eight possibilities remaining:
In[]:=
Column[Select[Subsets[mix[[4]],{3}],Length[Union[Flatten[#]]]<4&]]
Out[]=
{{5,2},{1,5},{2,1}} |
{{5,2},{2,4},{4,5}} |
{{1,5},{5,3},{3,1}} |
{{6,3},{3,4},{4,6}} |
{{6,3},{3,1},{1,6}} |
{{3,4},{5,3},{4,5}} |
{{2,4},{4,6},{6,2}} |
{{1,6},{6,2},{2,1}} |
Hypergraphs can also canonicalized, such as the faces of an octahedron as directed hyperedges. So long as the hypergraph doesn’t have a combination of extreme symmetry and more than 10 hyperedges, the canonicalization has no problem. The faces of an icosahedron do not currently work with this method.
In[]:=
octa=PolyhedronData["Octahedron","FaceIndices"];ResourceFunction["FindCanonicalHypergraph"][octa]
Out[]=
{{1,2,3},{1,3,4},{1,4,5},{1,5,2},{2,5,6},{2,6,3},{3,6,4},{6,5,4}}
Code From FindCanonicalHypergraph
Code From FindCanonicalHypergraph
Standard Orders and Canonical Rules
Standard Orders and Canonical Rules
Integers >0 in standard order start with 1, then can never be more than 1 higher than all previous integers.
The DelDup function takes the alphabet of a list and maps it to Range[Length[alphabet]], which puts the items of a list into standard order.
DelDup[{{4,5,6},{3,6,4},{2,5,6},{2,3,6},{1,4,5},{1,4,3},{1,2,5},{1,2,3}}]
{{1,2,3},{4,3,1},{5,2,3},{5,4,3},{6,1,2},{6,1,4},{6,5,2},{6,5,4}}
How many standard orders of length 24 exist? The BellB function gives the answer:
BellB[24]
445958869294805289
The MiserTermsInTuples function starts with each single edge in a separate list.
1. Eliminate any list that doesn’t contain the fewest possible vertices.
2. To each list, add one more edge in all possible ways.
3. Repeat
1. Eliminate any list that doesn’t contain the fewest possible vertices.
2. To each list, add one more edge in all possible ways.
3. Repeat
For the balanced octahedron from above, the extreme symmetry means that the greedy step ends up with 24 possibilities:
balancedoctahedron={{1,3},{1,4},{2,1},{2,6},{3,2},{3,5},{4,2},{4,5},{5,1},{5,6},{6,3},{6,4}};equiv=MiserTermsInTuples[balancedoctahedron]
If converted into standard orders, all of these are equivalent. If this function is eventually improved to handle supersymmetry, there may be an intermediary step if there are more that 100 lists after a step and used/unused edges in a list have equivalent standard orders. Since supersymmetry has a measure near 0 in random hypergraphs, I wasn’t worried about it initially.
Tally[DelDup/@equiv]
{{{{1,2},{2,3},{3,1},{1,4},{4,3},{2,5},{4,5},{5,1},{3,6},{5,6},{6,2},{6,4}},24}}
A canonical WolframModel rule is composed of a series of canonical hypergraphs. For example, the following is canonical.
first=MiserTermsInTuples[{{7,7},{7,8},{8,3},{3,5}}]
{{{7,7},{7,8},{8,3},{3,5}}}
If we want the canonical rule for {{7,7},{7,8},{8,3},{3,5}} -> balancedoctahedron, the only vertices in the first part that matter in the second part are 3 and 5, so the canonical rule will pick an example that starts {3.5}
Take[SortBy[Tuples[{first,equiv}],DelDup[#]&],4]
{{{{7,7},{7,8},{8,3},{3,5}},{{3,5},{5,1},{1,3},{3,2},{2,1},{5,6},{2,6},{6,3},{1,4},{6,4},{4,5},{4,2}}},{{{7,7},{7,8},{8,3},{3,5}},{{3,5},{5,6},{6,3},{3,2},{2,6},{5,1},{2,1},{1,3},{6,4},{1,4},{4,5},{4,2}}},{{{7,7},{7,8},{8,3},{3,5}},{{3,2},{2,1},{1,3},{3,5},{5,1},{2,6},{5,6},{6,3},{1,4},{6,4},{4,2},{4,5}}},{{{7,7},{7,8},{8,3},{3,5}},{{3,2},{2,6},{6,3},{3,5},{5,6},{2,1},{5,1},{1,3},{6,4},{1,4},{4,2},{4,5}}}}
Converting to standard orders shows that the first two are equivalent.
DelDup/@Take[SortBy[Tuples[{first,equiv}],DelDup[#]&],4]
{{{{1,1},{1,2},{2,3},{3,4}},{{3,4},{4,5},{5,3},{3,6},{6,5},{4,7},{6,7},{7,3},{5,8},{7,8},{8,4},{8,6}}},{{{1,1},{1,2},{2,3},{3,4}},{{3,4},{4,5},{5,3},{3,6},{6,5},{4,7},{6,7},{7,3},{5,8},{7,8},{8,4},{8,6}}},{{{1,1},{1,2},{2,3},{3,4}},{{3,5},{5,6},{6,3},{3,4},{4,6},{5,7},{4,7},{7,3},{6,8},{7,8},{8,5},{8,4}}},{{{1,1},{1,2},{2,3},{3,4}},{{3,5},{5,6},{6,3},{3,4},{4,6},{5,7},{4,7},{7,3},{6,8},{7,8},{8,5},{8,4}}}}
The canonical rule for {{7,7},{7,8},{8,3},{3,5}} -> balancedoctahedron is the following:
{{1,1},{1,2},{2,3},{3,4}}{{3,4},{4,5},{5,3},{3,6},{6,5},{4,7},{6,7},{7,3},{5,8},{7,8},{8,4},{8,6}}
Why this way? We tried many canonicalization methods and this was the fastest. The key idea “A canonical WolframModel rule is composed of a series of canonical hypergraphs” allowed for a lot of speed increases and simplification.