Enumeration of Hypergraphs and Hypergraph Rules

[maxitg]

The project goal

We currently don't have any way to enumerate ordered hypergraphs or HypergraphSubstitutionSystem rules in SetReplace. The closest thing we have is a RandomHypergraph function and a resource function (which being a WFR function is difficult to use).

This project is mostly a software engineering project to implement the enumeration as a SetReplace function.

The algorithm from WFR can be used. However, it will need to be carefully tested. There are also some improvements that can be made. For example, we can allow flat enumeration based on complexity (similar to a single argument version of RandomHypergraph). If possible, it will also be nice to have a numbering scheme that will assign (not necessarily unique) short codes to rules and produce the rule given the code.

Expected deliverables:

• A function to enumerate ordered hypergraphs, and, time permitting, HypergraphSubstitutionSystem rules.
• A documentation page for that function, which can also be turned into a community post.

Motivations

Any systematic study of HypergraphSubstitutionSystem rules will require a reliable enumeration algorithm. This project will be a foundation for that.

External prerequisites

• Familiarity with graphs and graph algorithms.
• Experience with C++ or Wolfram Language.

SetReplace prerequisites

• Understanding of HypergraphSubstitutionSystem (aka WolframModel).

Difficulty

It should be fairly straightforward to port the WFR function to SetReplace. However, implementing additional features, especially the short codes, might be quite hard.

Potential instructors

@maxitg

Existing work

• RandomHypergraph function.
• EnumerateWolframModelRules WFR function.
• EnumerateHypergraphs WFR function.

Required future SetReplace features

No additional features are required. The rules can be used with WolframModel already.