graphlib2
This is a Rust port of Python's stdlib graphlib. It passes all of the standard libraries tests and is a drop in replacement. This also happens to be Python 3.7 compatible, so it can be used as a backport. Since usage is exactly the same as the standard libraries, please refer to their documentation for usage details.
See this project on GitHub.
Example
from graphlib2 import TopologicalSorter
graph = {0: [1], 1: [2]} # 0 depends on 1, 1 depends on 2
ts = TopologicalSorter(graph)
ts.prepare()
while ts.is_active():
ready_nodes = ts.get_ready()
ts.done(*ready_nodes) # all at a time or one by one
Motivation
This was primarily written for di and for me to learn Rust. In other words: please vet the code yourself before using this.
Differences with the stdlib implementation
- Added
TopologicalSorter.copy()which copies a prepared or unprepared graph so that it can be executed multiple times. - Pretty solid performance improvements (see benchmarks).
- Misc improvements, like working generics without postponed evaluation (
ToplologicalSorter[int]works at runtime).
Performance
The implementation was designed for the specific use case of adding all nodes, calling prepare() then copying and executing in a loop:
from graphlib2 import TopologicalSorter
graph = {0: [1], 1: [2]}
ts = TopologicalSorter(graph)
ts.prepare()
while True: # hot loop
t = ts.copy()
while t.is_active():
ready_nodes = t.get_ready()
t.done(*ready_nodes)
This means that the focus is on the performance of TopologicalSorter.get_ready() and TopologicalSorter.done(), and only minimal effort was put into other methods (prepare(), add() and get_static_order()), although these are still quite performant.
Contributing
- Clone the repo.
- Run
make init - Run
make test - Make your changes
- Push and open a pull request
- Wait for CI to run.
If your pull request gets approved and merged, it will automatically be relased to PyPi (every commit to main is released).
1 maintainer
Metadata
1 maintainer
Release files for graphlib2 0.4.7
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| graphlib2-0.4.7.tar.gz | 390.5 kB | Details |
Built distributions (wheels)
Total release size: 6.7 MB
Release files / graphlib2-0.4.7.tar.gz
| Download URL | graphlib2-0.4.7.tar.gz |
|---|---|
| Size | 390.5 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
a951c18cb4c2c2834eec898b4c75d3f930d6f08beb37496f0e0ce56eb3f571f5
|
|
BLAKE2b-256 checksum How to use checksums |
a4a40dbdce7ad4b0f9b869bb31bad4b7546d586d41879abd9b6060cb309b9368
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 223.3 kB |
| Tags | Linux glibc 2.17+ x86-64 PyPy 3.9 PyPy 3.9 7.3 |
|
SHA-256 checksum How to use checksums |
b16e21e70938132d4160c2591fed59f79b5f8b702e4860c8933111b5fedb55c2
|
|
BLAKE2b-256 checksum How to use checksums |
9a2be11bc30a33e7c06a4e09b656f55585fac403368ef3a40f6c6a3195831bb9
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
| Download URL | graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl |
|---|---|
| Size | 207.1 kB |
| Tags | Linux glibc 2.17+ ARM64 PyPy 3.9 PyPy 3.9 7.3 |
|
SHA-256 checksum How to use checksums |
ee62ff1042fde980adf668e30393eca79aee8f1fa1274ab3b98d69091c70c5e8
|
|
BLAKE2b-256 checksum How to use checksums |
247881545bf65508c8db0f207aa0cad0319c88dc7d8dbe5f43530cec211d1c4d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp39-pypy39_pp73-macosx_10_7_x86_64.whl
| Download URL | graphlib2-0.4.7-pp39-pypy39_pp73-macosx_10_7_x86_64.whl |
|---|---|
| Size | 203.7 kB |
| Tags | PyPy 3.9 PyPy 3.9 7.3 macOS 10.7+ x86-64 |
|
SHA-256 checksum How to use checksums |
853ef22df8e9f695706e0b8556cda9342d4d617f7d7bd02803e824bcc0c30b20
|
|
BLAKE2b-256 checksum How to use checksums |
3248e2182752770bd27495a9ac61b47d39bd1e0ffaa2622c0ffee7baa535194a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 223.3 kB |
| Tags | Linux glibc 2.17+ x86-64 PyPy 3.8 PyPy 3.8 7.3 |
|
SHA-256 checksum How to use checksums |
297c817229501255cd3a744c62c8f91e5139ee79bc550488f5bc765ffa33f7c5
|
|
BLAKE2b-256 checksum How to use checksums |
fddbfc26b664e2cf1605c8ac164b962c4f881339d482947793f4de8582637250
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
| Download URL | graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl |
|---|---|
| Size | 207.4 kB |
| Tags | Linux glibc 2.17+ ARM64 PyPy 3.8 PyPy 3.8 7.3 |
|
SHA-256 checksum How to use checksums |
5873480df8991273bd1585122df232acd0f946c401c254bd9f0d661c72589dcf
|
|
BLAKE2b-256 checksum How to use checksums |
6864c331d4def335767d903d08d8827d4e1fa589d9dfc4cd2ceca82617926c39
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp38-pypy38_pp73-macosx_10_7_x86_64.whl
| Download URL | graphlib2-0.4.7-pp38-pypy38_pp73-macosx_10_7_x86_64.whl |
|---|---|
| Size | 203.8 kB |
| Tags | PyPy 3.8 PyPy 3.8 7.3 macOS 10.7+ x86-64 |
|
SHA-256 checksum How to use checksums |
3ee3a99fc39df948fef340b01254709cc603263f8b176f72ed26f1eea44070a4
|
|
BLAKE2b-256 checksum How to use checksums |
d5de2140cb852f85ad8c25c81a5e7871b4e69f1238370d0b686fccd0eb5038e0
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 225.6 kB |
| Tags | Linux glibc 2.17+ x86-64 PyPy 3.7 PyPy 3.7 7.3 |
|
SHA-256 checksum How to use checksums |
cb4ae9df7ed895c6557619049c9f73e1c2e6d1fbed568010fd5d4af94e2f0692
|
|
BLAKE2b-256 checksum How to use checksums |
74f38fe7a1cf9082fbd6c65858be5a684d2d33b009d74b0f5a973542ba6373ec
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
| Download URL | graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl |
|---|---|
| Size | 209.5 kB |
| Tags | Linux glibc 2.17+ ARM64 PyPy 3.7 PyPy 3.7 7.3 |
|
SHA-256 checksum How to use checksums |
aeecb604d70317c20ca6bc3556f7f5c40146ad1f0ded837e978b2fe6edf3e567
|
|
BLAKE2b-256 checksum How to use checksums |
414b208140a4d04b689108726d6aca2349658882b911ad813e7f19c74cf9160d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-pp37-pypy37_pp73-macosx_10_7_x86_64.whl
| Download URL | graphlib2-0.4.7-pp37-pypy37_pp73-macosx_10_7_x86_64.whl |
|---|---|
| Size | 205.6 kB |
| Tags | PyPy 3.7 PyPy 3.7 7.3 macOS 10.7+ x86-64 |
|
SHA-256 checksum How to use checksums |
9cef08a50632e75a9e11355e68fa1f8c9371d0734642855f8b5c4ead1b058e6f
|
|
BLAKE2b-256 checksum How to use checksums |
3afed134d8e95106068cf24a85ba25f1c0c5d9c39b07978fec1044381e8e2b27
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-win_amd64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-win_amd64.whl |
|---|---|
| Size | 150.5 kB |
| Tags | CPython 3.7 Windows x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
d40935a9da81a046ebcaa0216ad593ef504ae8a5425a59bdbd254c0462adedc8
|
|
BLAKE2b-256 checksum How to use checksums |
8060f17470522a9bdd43ffbdf0d067490e6b3f8083b46b5387a91551e413cea8
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-win32.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-win32.whl |
|---|---|
| Size | 145.1 kB |
| Tags | CPython 3.7 Windows x86-32 abi3 |
|
SHA-256 checksum How to use checksums |
31b40cea537845d80b69403ae306d7c6a68716b76f5171f68daed1804aadefec
|
|
BLAKE2b-256 checksum How to use checksums |
a48dbc4546928353e4e2f30ce9531ee9be2e0fde1efc112181f9de69e2a49cdd
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-musllinux_1_2_x86_64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-musllinux_1_2_x86_64.whl |
|---|---|
| Size | 394.6 kB |
| Tags | CPython 3.7 Linux musl 1.2+ x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
0cb6c4449834077972c3cea4602f86513b4b75fcf2d40b12e4fe4bf1aa5c8da2
|
|
BLAKE2b-256 checksum How to use checksums |
4780c91604bdd85283c9d66a73a42d9d2029a6acd135d4efb206879634fe3765
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-musllinux_1_2_i686.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-musllinux_1_2_i686.whl |
|---|---|
| Size | 419.3 kB |
| Tags | CPython 3.7 Linux musl 1.2+ x86-32 abi3 |
|
SHA-256 checksum How to use checksums |
15a8a6daa28c1fb5c518d387879f3bbe313264fbbc2fab5635b718bc71a24913
|
|
BLAKE2b-256 checksum How to use checksums |
8b39977c9c8a8f77ffa4543fce6caf771c98ed94483a4cecf60b74ede49a3c2a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-musllinux_1_2_armv7l.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-musllinux_1_2_armv7l.whl |
|---|---|
| Size | 475.7 kB |
| Tags | CPython 3.7 Linux musl 1.2+ ARMv7l abi3 |
|
SHA-256 checksum How to use checksums |
13a23fcf07c7bef8a5ad0e04ab826d3a2a2bcb493197005300c68b4ea7b8f581
|
|
BLAKE2b-256 checksum How to use checksums |
5426797f597ce81e2c9c4c51cdbd74df6e1c25d03e7e34a9c72ebae23ecad5af
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-musllinux_1_2_aarch64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-musllinux_1_2_aarch64.whl |
|---|---|
| Size | 387.6 kB |
| Tags | CPython 3.7 Linux musl 1.2+ ARM64 abi3 |
|
SHA-256 checksum How to use checksums |
2de5e32ca5c0b06d442d2be4b378cc0bc335c5fcbc14a7d531a621eb8294d019
|
|
BLAKE2b-256 checksum How to use checksums |
27f473b2b48ac62f10189d9305c4ea1781638870a3cb42ffaa6a566f847b6019
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 223.1 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
3c9ec3a5645bdf020d8bd9196b2665e26090d60e523fd498df29628f2c5fbecc
|
|
BLAKE2b-256 checksum How to use checksums |
92ab604c1cd20f37fff2a53780cb61abc51319041618c606751a4fc8924dfb54
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl |
|---|---|
| Size | 278.2 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ IBM System/390x abi3 |
|
SHA-256 checksum How to use checksums |
b06bed98d42f4e10adfe2a8332efdca06b5bac6e7c86dd1d22a4dea4de9b275a
|
|
BLAKE2b-256 checksum How to use checksums |
7d51376b2a17015adc2893fcf08f913d00137530b10d28647cabf4c3aa1be7f1
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl |
|---|---|
| Size | 311.7 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ PowerPC 64-le abi3 |
|
SHA-256 checksum How to use checksums |
d7cc38b68775cb2cdfc487bbaca2f7991da0d76d42a68f412c2ca61461e6e026
|
|
BLAKE2b-256 checksum How to use checksums |
cc5d176f475be69d6c85e448dae141b455cac78f7bb6f46577240e065131264a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64.manylinux2014_ppc64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64.manylinux2014_ppc64.whl |
|---|---|
| Size | 322.4 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ PowerPC 64-be abi3 |
|
SHA-256 checksum How to use checksums |
6efc6a197a619a97f1b105aea14b202101241c1db9014bd100ad19cf29288cbf
|
|
BLAKE2b-256 checksum How to use checksums |
4429cfd6ff9573bf6f862d5e6e7e4824a59208eed715be185d903029d980d5f2
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl |
|---|---|
| Size | 212.6 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ ARMv7l abi3 |
|
SHA-256 checksum How to use checksums |
624020f6808ee21ffbb2e455f8dd4196bbb37032a35aa3327f0f5b65fb6a35d1
|
|
BLAKE2b-256 checksum How to use checksums |
685bb7e024a4578d7df133dfc81066e47e1dbe2e49c1771c5b6294c83d6a2011
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl |
|---|---|
| Size | 206.9 kB |
| Tags | CPython 3.7 Linux glibc 2.17+ ARM64 abi3 |
|
SHA-256 checksum How to use checksums |
5b19f1b91d0f22ca3d1cfb2965478db98cf5916a5c6cea5fdc7caf4bf1bfbc33
|
|
BLAKE2b-256 checksum How to use checksums |
ccf10966a43c48cc4747181cd1ecac32699c38ffb43566a75250b092d7ce090a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl |
|---|---|
| Size | 247.1 kB |
| Tags | CPython 3.7 Linux glibc 2.5+ x86-32 abi3 |
|
SHA-256 checksum How to use checksums |
824df87f767471febfd785a05a2cc77c0c973e0112a548df827763ca0aa8c126
|
|
BLAKE2b-256 checksum How to use checksums |
5aad4765785902301c6bc0860953fbfe489f50d1cb9f1162ce3cc51c6f097fb4
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl |
|---|---|
| Size | 389.0 kB |
| Tags | CPython 3.7 abi3 macOS 10.9+ universal2 (ARM64, x86-64) macOS 10.9+ x86-64 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
3619c7d3c5aca95e6cbbfc283aa6bf42ffa5b59d7f39c8d0ad615bce65dc406f
|
|
BLAKE2b-256 checksum How to use checksums |
531f5096430835c4649cf0847ec529b09a870548b0258f2e4a8bdeea78db5b57
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
Release files / graphlib2-0.4.7-cp37-abi3-macosx_10_7_x86_64.whl
| Download URL | graphlib2-0.4.7-cp37-abi3-macosx_10_7_x86_64.whl |
|---|---|
| Size | 203.7 kB |
| Tags | CPython 3.7 abi3 macOS 10.7+ x86-64 |
|
SHA-256 checksum How to use checksums |
483710733215783cdc76452ccde1247af8f697685c9c1dfd9bb9ff4f52d990ee
|
|
BLAKE2b-256 checksum How to use checksums |
cded4c5254b064bf80769364855cb31dc9f6bc589ba1b6119acb2ce76111cbac
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.10.7
|
