Skip to content

Support Empty E-Classes #11

@saulshanabrook

Description

@saulshanabrook

Currently, e-graphs with empty e-classes cannot be referred to as children in the serialization format.

This is problematic when trying to serialize some edge cases from egglog, that were brought up by @oflatt in egraphs-good/egglog#368, namely:

  1. Using delete to create an empty e-class (example).
  2. Serializing a large e-graph with the max parameters set so that some e-nodes are stripped out to make a more manageable size graph.

There are a few ways we discussed resolving this:

  1. Allowing each child in the children vec to be optional.
  2. Changing the op itself to be optional.

With option 1, you just point to a null node ID if you are looking to represent an e-class that is empty. In option 2, you would point to a node in that e-class that has a null op.

The advantage of option 2 is that you can still represent the e-class. So if two nodes point to the same null e-class that is shown in the serialized format, while in option one, they will both just be null and that won't be clear.

Similarily, with option 2, you can still represent the typ of the empty e-class, because it will have an ID, while in option 1, you can't.

Either way, we should also support this when converting to graphviz. One way to do that might be to make an actual node within a cluster for the empty one, but just make it invisible or small. So you can still see the e-class and the arrows pointing to it, but there is no node inside.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions