Hypergraph Rewriting System

<img src="screenshot.jpg" width="512">

Run it: https://met4citizen.github.io/Hypergraph/

Hypergraph Rewriting System able to visualize both single-way and multiway evolutions in 3D.

The app uses 3d Force-Directed Graph for representing graph structures, ThreeJS/WebGL for 3D rendering and d3-force-3d for the force engine.

Introduction

A hypergraph is a generalization of a regular graph. Whereas an edge typically connects only two nodes, a hyperedge can join any number of nodes. In a Hypergraph Rewriting System some initial hypergraph is transformed incrementally by making a series of updates that follow some abstract rewriting rule.

As an example, consider an abstract rewriting rule (x,x,y)(y,z,u)->(x,v,u)(y,v,z)(v,v,u). Wherever and whenever a subhypergraph having the form of the left-hand side pattern (x,x,y)(y,z,u) is found in the hypergraph, it is replaced with a new subhypergraph having the form of the right-hand side pattern (x,v,u)(y,v,z)(v,v,u) introducing a new node v.

Sometimes matches overlap. For example, when using the previous rule with the initial state (1,1,2)(2,2,3)(3,3,4) there are two overlapping matches (x=1,y=2,z=2,u=3) and (x=2,y=3,z=3,u=4) (critical pair). One way to resolve the conflict is to pick one of the two according to some ordering scheme and ignore the other (single-way evolution). Another approach is to rewrite both by allowing the system to branch (multiway evolution).

As the multiway system branches and diverges (quantum mechanics), the probability of ending up in some particular end state is related to the number of different evolutionary paths to that state (path counting). However, there can also be rules that make branches merge (critical pair completion). This branching and merging makes certain end states more/less likely (constructive/destructive interference). In the end we (observers) are likely to find ourselves in the part of the system in which the branches always merge (confluence) and the system converges (classical mechanics).

For more information about hypergraph rewriting systems and their potential to represent fundamental physics visit The Wolfram Physics Project website. According to their technical documents certain models reproduce key features of both relativity and quantum mechanics.

If you are interested in quantum mechanics and graph theory, you might also want to take a look at my spin-off projects BigraphQM and CliqueVM. For a philosophical take on these ideas see my blog post The Game of Algorithms.

Rules

Click RULE to modify the rewriting rule, change its settings, and run the rewriting process.

The system supports several rules separated with a semicolon ; or written on separate lines. The two sides of any one-way rule must be separated with an arrow ->. The separator == can be used as a shortcut for a two-way setup in which both directions (the rule and its inverse) are possible.

Hyperedge patterns can be described by using numbers, characters or words. Several types of parentheses are also supported. For example, a rule [{x,y}{x,z}]->[{x,y}{x,w}{y,w}{z,w}] is considered valid and can be validated and converted to the default number format by clicking Scan.

The system also supports a filter/negation \. As an example, the rule (1)(1,2)\(2)->(1)(1,2)(2) is applied only if there is no unary edge (2). If the branchlike interactions are allowed, the check is made relative to all possible branches of history.

A rule without any right-hand side, such as (1,1,1)(1,1,1), is used as the initial graph. An alternative way to define an initial state is to use some predefined function:

Initial graph | Description --- | --- complete(n) | Complete graph with n vertices so that each vertex is connected to every other vertex. grid(d1,d2,...) | Grid with sides of length d1, d2, and so on. The number of parameters defines the dimension of the grid. For example, grid(2,4,5) creates a 3-dimensional 2x4x5 grid. line(n) | Line with n vertices. points(n) | n unconnected unary edges. prerun(n) | Pre-run the current rule for n events in one branch (singleway). The leaves of the result are used as an initial state. random(n,d,nedges) | Random graph with n vertices so that each vertex is sprinkled randomly in d dimensional space and has at least nedges connections. rule('rule',n) | Run rewriting rule rule for maximum n events in one branch (singleway). The leaves of the result are used as an initial state. sphere(n) | Fibonacci sphere with n vertices.

By using options twoway, oneway and/or inverse, each edge produced can be made a two-way edge, sorted or reversed. It is also possible to define some specific branch, or a combination of branches, for the initial state. As an example, (1,1)(1,1)/7, would specify branches 1-3 (the sum of the first three bits 1+2+4). By default, the initial state is set for all the tracked branches.

If the initial state is not specified, the left-hand side pattern of the first rule is used, but with only a single node. For example, a rule (1,2)(1,3)->(1,2)(1,4)(2,4)(3,4) gives an initial state (1,1)(1,1).

The Evolution option defines which kind of evolution is to be simulated:

Evolution | Description --- | --- 1,2,4 | Single-way system with 1/2/4 branches. By default, random event order is used to resolve overlaps for each branch. If the WM option is set, Wolfram model's standard event order is used for branch 1 and its reverse for branch 2. FULL | Full multiway system. All the matches are instantiated and four branches tracked.

The Interactions option defines the possible interactions between hyperedges. Any combination of the three possible interactions can be selected.

Interactions | Description --- | --- SPACE | Allow interactions between spacelike separated hyperedges. Two edges are spacelike separated if their lowest common ancestors are all updating events. In practice this should always be selected, because the nodes in a typical initial state are spacelike separated. TIME | Allow interaction between timelike separated hyperedges. Two edges are timelike separated if either one of them is an ancestors of the other one, that is, inside the other's past causal cone. BRANCH | Allow interaction between branchlike separated hyperedges. Two edges are branchlike separated if any of their lowest common ancestors is a hyperedge.

Other options:

Option | Description --- | --- WM | Wolfram Model. If set, the first branch uses Wolfram Model's standard event order (LeastRecentEdge + RuleOrdering + RuleIndex) and the second branch its reverse. By default the setting is off and all tracked branches use random event ordering. RO | Rule order (index). Regardless of other settings, always try to apply the events in the order in which the rules have been specified. By default the setting is off and the individual rules are allowed to mix. DD | De-duplicate. The overlapping new hyperedges on different branches are de-duplicated at the end of each step. This allows branches to merge. EXPERIMENTAL, FUNCTIONALITY LIKELY TO CHANGE.

Simulation/Observer

Simulation can be run in three different modes: Space, Time or Phase.

• In Space mode the system shows the evolution of the spatial hypergraph. According to the Wolfram Model, the spatial hypergraph represents a spacelike state of the universe with nodes as "atoms of space".
• In Time mode the system builds up the transitive reduction of the causal graph. In this view nodes represent updating events and directed edges their causal relations. According to the Wolfram Model, the flux of causal edges through spacelike and timelike hypersurfaces is related to energy and momentum respectively.
• In Phase mode the hyper-dimensional multiway space is projected in 3D by using Hamming distances and k-NN algorithm (see Appendix A: Coordinatization of Local Multiway System by using Hyper-dimensional Vectors). According to Wolfram Model, positions in so-called "branchial" space are related to quantum phase.

Media buttons let you reset the mode, start/pause the simulation and skip to the end. Whenever the system has branches, the first four branches can be shown separately or in any combination. If Past is selected, the full history of the local multiway system is shown in space mode. By default only the leaf edges of the system are visible.

The two sliders change the visual appearance of the graph by tuning the parameters of the underlying force engine. Note: Changing the viewpoint or the forces do not in any way change the multiway system itself only how it is visualized on the screen.

Highlighting

Subhypergraphs can be highlighted by clicking RED/BLUE and using one or more of the following commands:

Command | Highlighted | Status Bar --- | --- | --- curv(x,y) | Two n-dimensional balls of radius one and the shortest path between their centers. | Curvature based on Ollivier-Ricci (1-Wasserstein) distance. dim([x],[radius]) | N-dimensional ball with an origin x (random, if not specified) and radius r (automatically scaled if not specified). | The effective dimension d based on nearby n-ball volumes fitted to r^d. geodesic(x,y,[dir],[rev],[all])<br/><br/>dir = directed edges<br/>rev = reverse direction<br/>all = all shortest paths | Shortest path(s) between two nodes.<br/><br/> | Path distance as the number of edges. lightcone(x,length) | Lightcone centered at node x with size length. TIME mode only. | Size of the cones as the number of edg