Skip to main content

Rust port of the Python stdlib graphlib modules

Project description

graphlib2

CI

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

  1. Added TopologicalSorter.copy() which copies a prepared or unprepared graph so that it can be executed multiple times.
  2. Pretty solid performance improvements (see benchmarks).
  3. 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

  1. Clone the repo.
  2. Run make init
  3. Run make test
  4. Make your changes
  5. Push and open a pull request
  6. 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).

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

graphlib2-0.4.7.tar.gz (390.5 kB view details)

Uploaded Source

Built Distributions

graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (223.3 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (207.1 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.4.7-pp39-pypy39_pp73-macosx_10_7_x86_64.whl (203.7 kB view details)

Uploaded PyPy macOS 10.7+ x86-64

graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (223.3 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (207.4 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.4.7-pp38-pypy38_pp73-macosx_10_7_x86_64.whl (203.8 kB view details)

Uploaded PyPy macOS 10.7+ x86-64

graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (225.6 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (209.5 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.4.7-pp37-pypy37_pp73-macosx_10_7_x86_64.whl (205.6 kB view details)

Uploaded PyPy macOS 10.7+ x86-64

graphlib2-0.4.7-cp37-abi3-win_amd64.whl (150.5 kB view details)

Uploaded CPython 3.7+ Windows x86-64

graphlib2-0.4.7-cp37-abi3-win32.whl (145.1 kB view details)

Uploaded CPython 3.7+ Windows x86

graphlib2-0.4.7-cp37-abi3-musllinux_1_2_x86_64.whl (394.6 kB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ x86-64

graphlib2-0.4.7-cp37-abi3-musllinux_1_2_i686.whl (419.3 kB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ i686

graphlib2-0.4.7-cp37-abi3-musllinux_1_2_armv7l.whl (475.7 kB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ ARMv7l

graphlib2-0.4.7-cp37-abi3-musllinux_1_2_aarch64.whl (387.6 kB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ ARM64

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (223.1 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ x86-64

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl (278.2 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ s390x

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (311.7 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ppc64le

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64.manylinux2014_ppc64.whl (322.4 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ppc64

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (212.6 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARMv7l

graphlib2-0.4.7-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (206.9 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARM64

graphlib2-0.4.7-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl (247.1 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.5+ i686

graphlib2-0.4.7-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl (389.0 kB view details)

Uploaded CPython 3.7+ macOS 10.9+ universal2 (ARM64, x86-64) macOS 10.9+ x86-64 macOS 11.0+ ARM64

graphlib2-0.4.7-cp37-abi3-macosx_10_7_x86_64.whl (203.7 kB view details)

Uploaded CPython 3.7+ macOS 10.7+ x86-64

File details

Details for the file graphlib2-0.4.7.tar.gz.

File metadata

  • Download URL: graphlib2-0.4.7.tar.gz
  • Upload date:
  • Size: 390.5 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.10.7

File hashes

Hashes for graphlib2-0.4.7.tar.gz
Algorithm Hash digest
SHA256 a951c18cb4c2c2834eec898b4c75d3f930d6f08beb37496f0e0ce56eb3f571f5
MD5 3d516e055cac0ec447ca423934edc07d
BLAKE2b-256 a4a40dbdce7ad4b0f9b869bb31bad4b7546d586d41879abd9b6060cb309b9368

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 b16e21e70938132d4160c2591fed59f79b5f8b702e4860c8933111b5fedb55c2
MD5 8a4fb3247e513f07f6be3ac06a52e370
BLAKE2b-256 9a2be11bc30a33e7c06a4e09b656f55585fac403368ef3a40f6c6a3195831bb9

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 ee62ff1042fde980adf668e30393eca79aee8f1fa1274ab3b98d69091c70c5e8
MD5 a49f7d9947666342320d2f9b3a939e15
BLAKE2b-256 247881545bf65508c8db0f207aa0cad0319c88dc7d8dbe5f43530cec211d1c4d

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp39-pypy39_pp73-macosx_10_7_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp39-pypy39_pp73-macosx_10_7_x86_64.whl
Algorithm Hash digest
SHA256 853ef22df8e9f695706e0b8556cda9342d4d617f7d7bd02803e824bcc0c30b20
MD5 5991fa816d37f8a567df80cb2f10ca4d
BLAKE2b-256 3248e2182752770bd27495a9ac61b47d39bd1e0ffaa2622c0ffee7baa535194a

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 297c817229501255cd3a744c62c8f91e5139ee79bc550488f5bc765ffa33f7c5
MD5 8ce8eb6ecc22ceabf0aa2747cdfc9a64
BLAKE2b-256 fddbfc26b664e2cf1605c8ac164b962c4f881339d482947793f4de8582637250

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 5873480df8991273bd1585122df232acd0f946c401c254bd9f0d661c72589dcf
MD5 d4fcb8950e743a2f50a098e132c0d1c2
BLAKE2b-256 6864c331d4def335767d903d08d8827d4e1fa589d9dfc4cd2ceca82617926c39

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp38-pypy38_pp73-macosx_10_7_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp38-pypy38_pp73-macosx_10_7_x86_64.whl
Algorithm Hash digest
SHA256 3ee3a99fc39df948fef340b01254709cc603263f8b176f72ed26f1eea44070a4
MD5 f72298628af91392e1dad1970061ed40
BLAKE2b-256 d5de2140cb852f85ad8c25c81a5e7871b4e69f1238370d0b686fccd0eb5038e0

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 cb4ae9df7ed895c6557619049c9f73e1c2e6d1fbed568010fd5d4af94e2f0692
MD5 5f913777d8bcd594b5c1fe1f388d0b46
BLAKE2b-256 74f38fe7a1cf9082fbd6c65858be5a684d2d33b009d74b0f5a973542ba6373ec

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 aeecb604d70317c20ca6bc3556f7f5c40146ad1f0ded837e978b2fe6edf3e567
MD5 dff4428c58062551d04831505c4edc09
BLAKE2b-256 414b208140a4d04b689108726d6aca2349658882b911ad813e7f19c74cf9160d

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-pp37-pypy37_pp73-macosx_10_7_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-pp37-pypy37_pp73-macosx_10_7_x86_64.whl
Algorithm Hash digest
SHA256 9cef08a50632e75a9e11355e68fa1f8c9371d0734642855f8b5c4ead1b058e6f
MD5 4257291da50a5663bd0d2ec76c7d234c
BLAKE2b-256 3afed134d8e95106068cf24a85ba25f1c0c5d9c39b07978fec1044381e8e2b27

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-win_amd64.whl.

File metadata

  • Download URL: graphlib2-0.4.7-cp37-abi3-win_amd64.whl
  • Upload date:
  • Size: 150.5 kB
  • Tags: CPython 3.7+, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.10.7

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 d40935a9da81a046ebcaa0216ad593ef504ae8a5425a59bdbd254c0462adedc8
MD5 5404b9274d4933f810229ed59bd493a5
BLAKE2b-256 8060f17470522a9bdd43ffbdf0d067490e6b3f8083b46b5387a91551e413cea8

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-win32.whl.

File metadata

  • Download URL: graphlib2-0.4.7-cp37-abi3-win32.whl
  • Upload date:
  • Size: 145.1 kB
  • Tags: CPython 3.7+, Windows x86
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.10.7

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-win32.whl
Algorithm Hash digest
SHA256 31b40cea537845d80b69403ae306d7c6a68716b76f5171f68daed1804aadefec
MD5 82eb9d251bb2769406b9aae8935758b0
BLAKE2b-256 a48dbc4546928353e4e2f30ce9531ee9be2e0fde1efc112181f9de69e2a49cdd

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 0cb6c4449834077972c3cea4602f86513b4b75fcf2d40b12e4fe4bf1aa5c8da2
MD5 a79e7ba99b8cb4cd44b7d6b3809a9c83
BLAKE2b-256 4780c91604bdd85283c9d66a73a42d9d2029a6acd135d4efb206879634fe3765

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-musllinux_1_2_i686.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-musllinux_1_2_i686.whl
Algorithm Hash digest
SHA256 15a8a6daa28c1fb5c518d387879f3bbe313264fbbc2fab5635b718bc71a24913
MD5 59b4f5846b4cb2ccace2bd35e40d2532
BLAKE2b-256 8b39977c9c8a8f77ffa4543fce6caf771c98ed94483a4cecf60b74ede49a3c2a

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-musllinux_1_2_armv7l.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-musllinux_1_2_armv7l.whl
Algorithm Hash digest
SHA256 13a23fcf07c7bef8a5ad0e04ab826d3a2a2bcb493197005300c68b4ea7b8f581
MD5 19324a1118b1b383d93ae50c34bceccb
BLAKE2b-256 5426797f597ce81e2c9c4c51cdbd74df6e1c25d03e7e34a9c72ebae23ecad5af

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-musllinux_1_2_aarch64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-musllinux_1_2_aarch64.whl
Algorithm Hash digest
SHA256 2de5e32ca5c0b06d442d2be4b378cc0bc335c5fcbc14a7d531a621eb8294d019
MD5 fdde8b15f3f8261b569892685fba8164
BLAKE2b-256 27f473b2b48ac62f10189d9305c4ea1781638870a3cb42ffaa6a566f847b6019

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 3c9ec3a5645bdf020d8bd9196b2665e26090d60e523fd498df29628f2c5fbecc
MD5 3a8d781930b2a9fc49db0d3ea9074e9b
BLAKE2b-256 92ab604c1cd20f37fff2a53780cb61abc51319041618c606751a4fc8924dfb54

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Algorithm Hash digest
SHA256 b06bed98d42f4e10adfe2a8332efdca06b5bac6e7c86dd1d22a4dea4de9b275a
MD5 d51cde642b4f793d972defd913f7ce65
BLAKE2b-256 7d51376b2a17015adc2893fcf08f913d00137530b10d28647cabf4c3aa1be7f1

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Algorithm Hash digest
SHA256 d7cc38b68775cb2cdfc487bbaca2f7991da0d76d42a68f412c2ca61461e6e026
MD5 64d231e364e186abd48e4316539d4272
BLAKE2b-256 cc5d176f475be69d6c85e448dae141b455cac78f7bb6f46577240e065131264a

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64.manylinux2014_ppc64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_ppc64.manylinux2014_ppc64.whl
Algorithm Hash digest
SHA256 6efc6a197a619a97f1b105aea14b202101241c1db9014bd100ad19cf29288cbf
MD5 6cdbc1c38ce946ea515506bfda7b5939
BLAKE2b-256 4429cfd6ff9573bf6f862d5e6e7e4824a59208eed715be185d903029d980d5f2

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Algorithm Hash digest
SHA256 624020f6808ee21ffbb2e455f8dd4196bbb37032a35aa3327f0f5b65fb6a35d1
MD5 55a861f51d6799027c0b12eb2880cc6b
BLAKE2b-256 685bb7e024a4578d7df133dfc81066e47e1dbe2e49c1771c5b6294c83d6a2011

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 5b19f1b91d0f22ca3d1cfb2965478db98cf5916a5c6cea5fdc7caf4bf1bfbc33
MD5 e32464ede2ef558e81c65126745f7148
BLAKE2b-256 ccf10966a43c48cc4747181cd1ecac32699c38ffb43566a75250b092d7ce090a

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl
Algorithm Hash digest
SHA256 824df87f767471febfd785a05a2cc77c0c973e0112a548df827763ca0aa8c126
MD5 3a2f972fe6f60c1951a8457f1ecb526c
BLAKE2b-256 5aad4765785902301c6bc0860953fbfe489f50d1cb9f1162ce3cc51c6f097fb4

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 3619c7d3c5aca95e6cbbfc283aa6bf42ffa5b59d7f39c8d0ad615bce65dc406f
MD5 df72ffae738d5d32494d5b6992359902
BLAKE2b-256 531f5096430835c4649cf0847ec529b09a870548b0258f2e4a8bdeea78db5b57

See more details on using hashes here.

File details

Details for the file graphlib2-0.4.7-cp37-abi3-macosx_10_7_x86_64.whl.

File metadata

File hashes

Hashes for graphlib2-0.4.7-cp37-abi3-macosx_10_7_x86_64.whl
Algorithm Hash digest
SHA256 483710733215783cdc76452ccde1247af8f697685c9c1dfd9bb9ff4f52d990ee
MD5 b531d7e2bb517ae4e4f17ff7b01d705d
BLAKE2b-256 cded4c5254b064bf80769364855cb31dc9f6bc589ba1b6119acb2ce76111cbac

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page