perf: Only check partial convexity for SimpleReplacement subgraphs.
#1869
Comments
github-merge-queue bot
pushed a commit
that referenced
this issue
Jan 20, 2025
The new portgraph release comes with some perf improvements. We require this update for #1869. Closes #1872. I added a benchmark variation for subgraphs with few nodes as a drive-by. This got improved by the new portgraph (skipping a full graph traversal), but the runtime is still mostly the `O(n)` full-graph traversal required for the convexity checking when building the subgraph. BREAKING CHANGE: Bumped public dependency `portgraph` to breaking version `0.13`.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See discussion #1656 ("Can we avoid the convexity work altogether?").
Requires CQCL/portgraph#161 to be published in portgraph.Requires #1872.
SiblingSubgraphcurrently requires the subgraph to be convex. This is no longer needed for doing replacements if we can prove that the new node boundary orders are no stricter than the original ones. We should only need to check this if the new port pairs inPortOrdering::missing_pairshad an external reverse dependency before.The text was updated successfully, but these errors were encountered: