Title: [BUG] Inefficient pop(0) queue operations and IndexError on sparse vertex IDs in graphs/kahns_algorithm_topo.py · Issue #15071 · TheAlgorithms/Python · GitHub
Open Graph Title: [BUG] Inefficient pop(0) queue operations and IndexError on sparse vertex IDs in graphs/kahns_algorithm_topo.py · Issue #15071 · TheAlgorithms/Python
X Title: [BUG] Inefficient pop(0) queue operations and IndexError on sparse vertex IDs in graphs/kahns_algorithm_topo.py · Issue #15071 · TheAlgorithms/Python
Description: Repository commit 11d2a47 Python version (python --version) Python 3.11.7 Dependencies version (pip freeze) pytest>=8.4.1 pytest-cov>=6 Expected behavior topological_sort in graphs/kahns_algorithm_topo.py should perform BFS queue operati...
Open Graph Description: Repository commit 11d2a47 Python version (python --version) Python 3.11.7 Dependencies version (pip freeze) pytest>=8.4.1 pytest-cov>=6 Expected behavior topological_sort in graphs/kahns_algorithm_...
X Description: Repository commit 11d2a47 Python version (python --version) Python 3.11.7 Dependencies version (pip freeze) pytest>=8.4.1 pytest-cov>=6 Expected behavior topological_sort in graphs/kahns_algo...
Opengraph URL: https://github.com/TheAlgorithms/Python/issues/15071
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"[BUG] Inefficient pop(0) queue operations and IndexError on sparse vertex IDs in graphs/kahns_algorithm_topo.py","articleBody":"### Repository commit\n\n11d2a47cc1d71df2b116e333fdca6d7c3d9a8d9d\n\n### Python version (python --version)\n\nPython 3.11.7\n\n### Dependencies version (pip freeze)\n\npytest>=8.4.1\npytest-cov>=6\n\n\n### Expected behavior\n\n1. `topological_sort` in `graphs/kahns_algorithm_topo.py` should perform BFS queue operations in $O(1)$ time using `collections.deque.popleft()`, maintaining the algorithm's overall time complexity of $O(V + E)$.\n2. `topological_sort` should handle valid graphs with sparse/non-contiguous integer vertex IDs (e.g., `{10: [20], 20: []}`) without crashing and return the correct topological ordering `[10, 20]`.\n\n\n### Actual behavior\n\n1. **$O(N)$ Dequeue Performance**: Line 43 uses `vertex = queue.pop(0)` on a Python `list`. Deleting from the front of a list takes $O(N)$ time, degrading Kahn's algorithm from $O(V + E)$ to $O(V^2 + E)$.\n2. **Crash on Non-Contiguous/Sparse Vertex IDs**: Line 26 initializes `indegree = [0] * len(graph)`, assuming vertex IDs are contiguous integers starting at 0 (`0..N-1`). Passing sparse vertex IDs like `{10: [20], 20: []}` results in `indegree` having size 2 (`[0, 0]`), causing line 34 (`indegree[i] += 1`) to crash with:\n\n```text\nIndexError: list index out of range\n","author":{"url":"https://github.com/Kanika0306","@type":"Person","name":"Kanika0306"},"datePublished":"2026-08-22T21:18:44Z","url":"https://github.com/TheAlgorithms/Python/issues/15071"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react-reconciler,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@d5750093facf |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:304ae44b-3f8e-d61b-f948-f61c1c3d2142 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | E256:3ED756:9AEB95:D943CC:6AFB732F |
| html-safe-nonce | f2dd939891a2dfec084d7d70946c5648c2abfab71f58cf8569ec6465e44d2bbc |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFMjU2OjNFRDc1Njo5QUVCOTU6RDk0M0NDOjZBRkI3MzJGIiwidmlzaXRvcl9pZCI6IjM4Mzk5Njc3NTY3NjU4NTI0NjMiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 08f8de2dec8f1a2084db52f397ff34ae91173c1b92768d893d87ad1cf46b33ca |
| hovercard-subject-tag | issue:5223983693 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/TheAlgorithms/Python/15071/issue_layout |
| twitter:image | https://opengraph.githubassets.com/f84c09abc8bd5b96c9618e4df6e1b77cd2b3d82f2e91c1b95021dea1b0657f08/TheAlgorithms/Python/issues/15071 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/f84c09abc8bd5b96c9618e4df6e1b77cd2b3d82f2e91c1b95021dea1b0657f08/TheAlgorithms/Python/issues/15071 |
| og:image:alt | Repository commit 11d2a47 Python version (python --version) Python 3.11.7 Dependencies version (pip freeze) pytest>=8.4.1 pytest-cov>=6 Expected behavior topological_sort in graphs/kahns_algorithm_... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | Kanika0306 |
| hostname | github.com |
| expected-hostname | github.com |
| None | 0e29e7974fdda2feeaf5c891efd4b23b0734b23480232b62c7bdef13f40b5b48 |
| turbo-cache-control | no-preview |
| go-import | github.com/TheAlgorithms/Python git https://github.com/TheAlgorithms/Python.git |
| octolytics-dimension-user_id | 20487725 |
| octolytics-dimension-user_login | TheAlgorithms |
| octolytics-dimension-repository_id | 63476337 |
| octolytics-dimension-repository_nwo | TheAlgorithms/Python |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 63476337 |
| octolytics-dimension-repository_network_root_nwo | TheAlgorithms/Python |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 2e8872b770cc4d5d0cc1f2026afab747a268e2ce |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width