Causal cones in data sibling graphs

[cqc-alec]

At one point we discussed requiring Order edges from the Input node into nodes having no data inputs, and similarly for outputs.

This may make analysis of causal relations and convexity a bit easier.

It doesn't seem to be in the spec at the moment.

If we do have this requirement then either the SimpleReplace API needs updating so that such edges are inserted, or the user has to explicitly specify them.

Another possible objection is that such edges prevent us from moving nodes out of the graph. Arguably Order edges should only exist when there is an actual order requirement.

[acl-cqc]

Looks like validation checks we have a causal cone:
https://github.com/CQCL-DEV/hugr/blob/8c53d0b267ef2eb8ded30298d6633d9fa0b35c95/src/hugr/validate.rs#L326-L357

[acl-cqc]

("single source and source" => "single source and sink"; "inter-graph" => "non-local"; "constant or state order edges" => "static and order edges")

[cqc-alec]

I originally thought this property would make convexity checking easier, but I'm not convinced now. @lmondada do you agree? Whether we have this property or not, it isn't the case that every convex subgraph has the property.

And as for specification of a convex subgraph, again I think it makes no difference: we can specify the subgraph by its set of minimal nodes (nodes having no predecessors in the set) and its set of maximal nodes (nodes having no successors in the set).

[lmondada]

Just thinking about this for 10min, I can't think of a way to use that additional information. At least not in the way we are checking convexity at the moment.

For now, I agree with your conclusion Alec that less edges are better. Also makes the rewriting logic simpler. At some point we might need to revisit how we check for convexity if it turns out to be expensive in practice, but even then, my feeling is that state order edges won't be the answer.

[lmondada]

As a bonus, just writing down a note here that came up in my short reasoning about it: convexity is a non-local property, i.e. in a graph with $n$ vertices, you might in the worst case have to traverse all $n$ vertices to check convexity. Unless you can come up with some smart preprocessing.

Example

graph TD
  subgraph "subgraph"
  0-->n
  end
  0-->2
  2-->|...| n-1
  n-1-->n

Loading

Right now we are using a topsort heuristic to (hopefully) early exit when a subgraph is non-convex, we will soon see if that is good enough.

[cqc-alec]

So leaning towards not requiring this on the grounds that fewer edges is good.

[acl-cqc]

Think this has been solved now and we decided not to require causal cone (right @cqc-alec? I can't find the PR!)

[cqc-alec]

Yeah I think so, not sure the requirement was ever in the spec though?

[acl-cqc]

Possibly not, so the code had diverged from the spec and we fixed the code

[acl-cqc]

Might have been closed by #468 ?

[cqc-alec]

Yes, that looks right.