Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Hypergraph Rewriting
Hypergraph rewriting repeatedly transforms a hypergraph by replacing subhypergraphs that match the left-hand side of a rule with the right-hand side of the rule. Systems of this kind, known as Wolfram models, are studied as models of fundamental physics, and the Hypergraph paclet provides the objects to build, apply, visualize and enumerate such rules.
Rewriting Rules
In[1]:=
rule=
[{{1,2}}],
[{{1,2},{2,3}}]
 | HypergraphRule |
 | Hypergraph |
| Hypergraph |
Out[1]=
The rule displays as a diagram of its input and output sides. Both sides are ordinary objects with all their styling and symmetry options:
In[2]:=
rule["Output"]
Out[2]=
Applying a Rule
Applying a rule to a hypergraph gives one record for every way its input matches:
In[3]:=
matches=
[{{1,2}}],
[{{1,2},{2,3}}]
[{{a,b},{b,c}}];Length[matches]
| HypergraphRule |
 | Hypergraph |
| Hypergraph |
| Hypergraph |
Out[3]=
4
Each record is an association describing one rewrite:
In[4]:=
Keys[First[matches]]
Out[4]=
{Hypergraph,MatchVertices,MatchEdges,MatchEdgePositions,NewVertices,NewEdges,DeletedVertices,RuleVertexMap,Bindings,EdgeArities}
The "Hypergraph" key holds the rewritten hypergraph; newly created vertices get fresh names:
In[5]:=
First[matches]["Hypergraph"]
Out[5]=
Edge Symmetry and Matching
The number of matches depends on the edge symmetry of the hypergraph and the rule. By default hyperedges are unordered, so a single binary pattern edge matches each binary edge in both orientations. With "Ordered" symmetry each edge matches only one way:
In[6]:=
orderedRule=
[{{1,2}},"EdgeSymmetry""Ordered"],
[{{1,2},{2,3}},"EdgeSymmetry""Ordered"];LengthorderedRule
[{{a,b},{b,c}},"EdgeSymmetry""Ordered"]
 | HypergraphRule |
 | Hypergraph |
| Hypergraph |
| Hypergraph |
Out[6]=
2
The rewritten hypergraphs of all ordered matches:
In[7]:=
#["Hypergraph"]&/@orderedRule
[{{a,b},{b,c}},"EdgeSymmetry""Ordered"]
| Hypergraph |
Out[7]=
,
Visualizing Matches
renders every match of a rule inside a hypergraph, highlighting the matched edges and the produced edges:
In[8]:=
 | HighlightRule |
| HypergraphRule |
| Hypergraph |
| Hypergraph |
| Hypergraph |
Out[8]=
,
Evolution
Iterating a rule produces an evolution of hypergraph states. Here each step applies the first available match:
In[9]:=
evolution=NestListFirst
[{{1,2}},"EdgeSymmetry""Ordered"],
[{{1,2},{2,3}},"EdgeSymmetry""Ordered"][#]["Hypergraph"]&,
[{{1,2}},"EdgeSymmetry""Ordered"],4
| HypergraphRule |
| Hypergraph |
| Hypergraph |
| Hypergraph |
The edge counts grow by one at each step:
Applying all matches simultaneously, or exploring every match branch separately, leads to multiway evolution; the per-match records returned by rule application carry enough information ("MatchEdgePositions", "NewEdges", "DeletedVertices") to build either.
Enumerating and Sampling Rules
A small sample of the enumerated rules: