hugr icon indicating copy to clipboard operation
hugr copied to clipboard

Allow non-convex SiblingSubgraph

Open lmondada opened this issue 4 months ago • 1 comments

It should be straightforward to generalise SiblingSubgraph to allow for any induced subgraph (including non-convex ones). The convexity check would be deferred to SimpleReplacement-creation time.

Proposal: SiblingSubgraph::create_simple_replacement would take an additional Option<ConvexChecker> argument. It would check whether the replacement is well-defined, (i.e. is guaranteed to not introduce a cycle) by performing the following checks in this order:

  1. Use portgraph::boundary::PortOrdering to see if the right hand side of the replacement is compatible with the left hand side; if the RHS port ordering is compatible, then the replacement is valid
  2. Use the convex checker provided as argument, if it is not None, to check for convexity of the LHS. If so, the replacement is valid.
  3. Compute a convex checker from scratch.

This would be strictly more powerful than the current status of requiring SiblingSubgraph to be convex, as check 1 can be satisfied in some cases for a non-convex LHS. Check 1 would also be cheaper than convexity checking in most cases.

lmondada avatar Aug 17 '25 14:08 lmondada

I have started work on this on branch lm/nonconvex-sibsub

lmondada avatar Aug 17 '25 14:08 lmondada