Directed Hypergraph Path

[maxitg]

The problem

Directed Hypergraphs

The edges of a directed hypergraph consist of two unordered sets of vertices, in other words,

<|1, 2, 3|> -> <|a, b, c|>

Here, the order in the sets <|1, 2, 3|> and <|a, b, c|> does not matter, but it matters that <|1, 2, 3|> preceeds <|a, b, c|>, in other words, <|a, b, c|> -> <|1, 2, 3|> is a different hyperedge. This is a generalization of directed (binary) graphs, in which the sets on each side only have one element each.

Composite Properties

To allow composite properties in the SetReplace type system, we need the smallest path algorithm on these directed hypergraphs.

One can think of the SetReplace type graph #621 as a directed hypergraph where vertices are types or properties, and edges are the implementations. Translation and raw property implementations only have one input (a type) and one output (either another type or a property), so one does not need directed hypergraphs for those. However, composite properties can take multiple other properties as an input, and hence they will correspond to edges with multiple inputs (all of which are required) and a single output.

We need an algorithm that, given an input type and an output property, will compute a subhypergraph of the type graph such that the final property can be computed within it, and that subgraph has as few edges as possible.

Possible solution

The situation where there might be multiple ways to compute a composite property might be rare, and it's not clear how efficient of an algorithm we really need here.

If we can only come up with a quadratic algorithm and have many properties in the future, we might want to do a C++ implementation.

If even a quadratic algorithm is not possible, and there are many branches in the ways to compute properties, we might want to abandon the idea of computing the most efficient path and use some heuristics to compute a reasonable one.

In any case, we might want to cache the path-searching result (unless the algorithm is linear) so that we don't keep recomputing it for the same property that's called multiple times.

Alternative solutions

It's not clear if we should start with a WL implementation or go directly to C++. If the WL implementation performs reasonably well for a few tens of types/properties, we might want to use it for the time being.

I'd say < 0.1 seconds with caching (so, the subsequent calls are instantaneous) should be ok.

Additional context

We might want to have support for optional arguments to composite properties in the future. It's not clear if the optional arguments should affect the path searching, but having as many of them available as possible might be a reasonable optimization criterion in addition to the path size.