{"payload":{"feedbackUrl":"https://github.com/orgs/community/discussions/53140","repo":{"id":428886520,"defaultBranch":"main","name":"retworkx","ownerLogin":"Da-Fi","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2021-11-17T02:46:19.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/75712980?v=4","public":true,"private":false,"isOrgOwned":true},"refInfo":{"name":"","listCacheKey":"v0:1637117186.629882","currentOid":""},"activityList":{"items":[{"before":"8dd39a42e4384834b22a4a114e41917062c3dd46","after":"783f30c8f8987099883b5f2a4440abda2e27ea54","ref":"refs/heads/main","pushedAt":"2024-04-07T04:11:48.000Z","pushType":"push","commitsCount":345,"pusher":{"login":"rmourey26","name":"Robert Mourey Jr","path":"/rmourey26","primaryAvatarUrl":"https://avatars.githubusercontent.com/u/20747769?s=80&v=4"},"commit":{"message":"Add node-removal methods linear in node degree (#1083)\n\n* Add node-removal methods linear in node degree\n\nThe existing method, `PyDiGraph.remove_node_retain_edges` is quadratic\nin node degree, because the ``condition`` function takes in pairs of\nedges.  This poses a problem for extreme-degree nodes (for example\nmassive barriers in Qiskit).\n\nThis commit adds two methods based on making edge-retention decisions by\nhashable keys, making it linear in the degree of the node (at least;\nthe MIMO broadcasting can make it quadratic again if all edges have the\nsame key, but that's fundamental to the output, rather than the\nalgorithm).\n\nThe ideal situation (for performance) is that the edges can be\ndisambiguated by Python object identity, which doesn't require\nPython-space calls to retrieve or hash, so can be in pure Rust.  This is\n`remove_node_retain_edges_by_id`.\n\nThe more general situation is that the user wants to supply a Python key\nfunction, which naturally returns a Python object that we need to use\nPython hashing and equality semantics for.  This means using Python\ncollections to do the tracking, which impacts the performance (very\ncasual benchmarking using the implicit identity function as the key\nshows it's about 2x slower than using the identity).  This method is\n`remove_node_retain_edges_by_key`.\n\n* Format\n\n* Update conversion actions to be by `Bound` reference\n\nThis is partly a PyO3 0.21 upgrade, partly fixing a dodgy `extract` in\nfavour of `downcast`.\n\n* Update out-of-date comment\n\n---------\n\nCo-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>","shortMessageHtmlLink":"Add node-removal methods linear in node degree (<a class=\"issue-link js-issue-link\" data-error-text=\"Failed to load title\" data-id=\"2125426694\" data-permission-text=\"Title is private\" data-url=\"https://github.com/Qiskit/rustworkx/issues/1083\" data-hovercard-type=\"pull_request\" data-hovercard-url=\"/Qiskit/rustworkx/pull/1083/hovercard\" href=\"https://github.com/Qiskit/rustworkx/pull/1083\">Qiskit#1083</a>)"}}],"hasNextPage":false,"hasPreviousPage":false,"activityType":"all","actor":null,"timePeriod":"all","sort":"DESC","perPage":30,"startCursor":"Y3Vyc29yOnYyOpK7MjAyNC0wNC0wN1QwNDoxMTo0OC4wMDAwMDBazwAAAAQp7UFm","endCursor":"Y3Vyc29yOnYyOpK7MjAyNC0wNC0wN1QwNDoxMTo0OC4wMDAwMDBazwAAAAQp7UFm"}},"title":"Activity · Da-Fi/retworkx"}