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 evaluateion (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.0.tar.gz (186.4 kB view details)

Uploaded Source

Built Distributions

graphlib2-0.4.0-pp38-pypy38_pp73-win_amd64.whl (143.6 kB view details)

Uploaded PyPy Windows x86-64

graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (209.7 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (193.0 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.4.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (193.9 kB view details)

Uploaded PyPy macOS 10.9+ x86-64

graphlib2-0.4.0-pp37-pypy37_pp73-win_amd64.whl (143.6 kB view details)

Uploaded PyPy Windows x86-64

graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (209.8 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (193.0 kB view details)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.4.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (193.9 kB view details)

Uploaded PyPy macOS 10.9+ x86-64

graphlib2-0.4.0-cp37-abi3-win_amd64.whl (143.7 kB view details)

Uploaded CPython 3.7+ Windows x86-64

graphlib2-0.4.0-cp37-abi3-musllinux_1_1_x86_64.whl (243.0 kB view details)

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

graphlib2-0.4.0-cp37-abi3-musllinux_1_1_aarch64.whl (227.9 kB view details)

Uploaded CPython 3.7+ musllinux: musl 1.1+ ARM64

graphlib2-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (210.0 kB view details)

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

graphlib2-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (193.2 kB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARM64

graphlib2-0.4.0-cp37-abi3-macosx_10_9_x86_64.whl (194.3 kB view details)

Uploaded CPython 3.7+ macOS 10.9+ x86-64

File details

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

File metadata

  • Download URL: graphlib2-0.4.0.tar.gz
  • Upload date:
  • Size: 186.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0.tar.gz
Algorithm Hash digest
SHA256 2e11f67319539f80f29ed25a0afb58074f93f606544b216e7c6cf2ec5dda7199
MD5 f94f7b41fd2f445a2bb229c412747b41
BLAKE2b-256 9ad6891c785d4820da530a6e3718f684fcb45778a2792cd33f01c5a8053f1a86

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-pp38-pypy38_pp73-win_amd64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-pp38-pypy38_pp73-win_amd64.whl
  • Upload date:
  • Size: 143.6 kB
  • Tags: PyPy, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp38-pypy38_pp73-win_amd64.whl
Algorithm Hash digest
SHA256 08703a3ea234cfedaac54f71e1230cc9198d6cf34e6de8d1508a84bf7716f6e0
MD5 1a6286b22efa3129981ffeb3d915d0ff
BLAKE2b-256 1a6fb165c3dcb411168e170f158fc373d5a9705a9a87c192369038097505ccbe

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
  • Upload date:
  • Size: 209.7 kB
  • Tags: PyPy, manylinux: glibc 2.17+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 022e4aa65b3d846574dead894046f79c96447824b293dfd79469137bfbb13077
MD5 a756078cbf6d5d2834fda59b02e089c1
BLAKE2b-256 0157059f2ef69e7a99fb4b519921b5bb656b7a833b46dfcafadcd337db043a6c

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
  • Upload date:
  • Size: 193.0 kB
  • Tags: PyPy, manylinux: glibc 2.17+ ARM64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 2a8ade22c5fe5d44d81b61497b894c24f4ddbc42fe212152baed91ef236192bf
MD5 c35bdb1915ffe8bc9d84accb66508a98
BLAKE2b-256 2d26c79b07c4d6c9d1fdfc13cfd4557d393dd06fdae0b8c5961c1faabc9b1e63

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 193.9 kB
  • Tags: PyPy, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 28e91991bc2b9473473f4a0a913f5e8de03816e75654ce56477c8dd2c1765881
MD5 5155a3be6114ac3918b385ee278083d8
BLAKE2b-256 88faea3ec152592fab7e2676282f0f6f7a37af38bc7a407e39e5d5d435b7131a

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-pp37-pypy37_pp73-win_amd64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-pp37-pypy37_pp73-win_amd64.whl
  • Upload date:
  • Size: 143.6 kB
  • Tags: PyPy, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp37-pypy37_pp73-win_amd64.whl
Algorithm Hash digest
SHA256 3c819c23ac29503b834999d791d579a39adb76fd2d4505fac86e411d20331d95
MD5 5acb0167805bbd83e01535dc2e2807b2
BLAKE2b-256 58cc12158939f0f51127124a72ea14514e78278680e62ef31d9c67b802404075

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
  • Upload date:
  • Size: 209.8 kB
  • Tags: PyPy, manylinux: glibc 2.17+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 e31b600213e64f4213de71980e81f0f043faaab0ad5fc01982785ed1d7a8bdf1
MD5 33a3a935b003b932669efd08c8baaabc
BLAKE2b-256 b1b5d7edfbe324bd41d58a610cf85aa1235eac912a51b421b7b5e1eef8521c63

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
  • Upload date:
  • Size: 193.0 kB
  • Tags: PyPy, manylinux: glibc 2.17+ ARM64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 a17183e2650c967bddacb84f3e9dfb249438109746b196f9b2f3819122a0bf77
MD5 3b0b02848661c69a63d1125b0f2cba56
BLAKE2b-256 e14493c3cc0b718bb2fc16d98422d4dd4f7625980c61a9c9abedfaf84ec46e01

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 193.9 kB
  • Tags: PyPy, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 15b5d7a7f1d1d29cd87647598f52c80849c572f5f6d9bb49fa1d96eb08179805
MD5 fbdef8acb4c371086e609a62cae06e7b
BLAKE2b-256 be6acf7b27fb799093a7f54df96b789d16e3e65c5ededfdd391c1073bd64f292

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-win_amd64.whl
  • Upload date:
  • Size: 143.7 kB
  • Tags: CPython 3.7+, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 8f1b4b3d14bd82ffe5153c6a255fa0c616012f09ad75dab55b3f7b3ef3275977
MD5 2c6c47163816e2877f2d3b3846f9ef6c
BLAKE2b-256 d8f818c2a3f9b0808d22f47e9ef8026ebd286e0cd118965adbc03abb0f63878a

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-cp37-abi3-musllinux_1_1_x86_64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-musllinux_1_1_x86_64.whl
  • Upload date:
  • Size: 243.0 kB
  • Tags: CPython 3.7+, musllinux: musl 1.1+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-musllinux_1_1_x86_64.whl
Algorithm Hash digest
SHA256 ab09ffd45c360f3809934bd61c8734ce737a8dbac8547492513b382ca4167671
MD5 ec919b7d5589b56f9ce15b67606832d3
BLAKE2b-256 8e7ed3fddaa45cfcbdfc245412d5c975437eea476d12ab873a725516e2229cca

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-cp37-abi3-musllinux_1_1_aarch64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-musllinux_1_1_aarch64.whl
  • Upload date:
  • Size: 227.9 kB
  • Tags: CPython 3.7+, musllinux: musl 1.1+ ARM64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-musllinux_1_1_aarch64.whl
Algorithm Hash digest
SHA256 0c16b12ab887e74fee800f601f07048523dd89f0b5bfbcb00a9dae668587c8f5
MD5 f0c2dcb84d87a896846fc33a93378271
BLAKE2b-256 24d8896c07c97e7891940ee98c89ed1639a700e55ebf729af4a87e03a57bdf41

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
  • Upload date:
  • Size: 210.0 kB
  • Tags: CPython 3.7+, manylinux: glibc 2.17+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 a133ddc87974b36298879c032408a40981364c6f0fde294f5471f0e302e7218b
MD5 431955688846a122d233609875cf538c
BLAKE2b-256 f8cbfdde596d2edc51dfabae594b754dbb31daad84e1583d1bfaf1fb9f43de5a

See more details on using hashes here.

Provenance

File details

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

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
  • Upload date:
  • Size: 193.2 kB
  • Tags: CPython 3.7+, manylinux: glibc 2.17+ ARM64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 02b5bfdf84971a2973fcdb91f58f974e058a6b6fa0bfb3894fc7e8ea6f731f40
MD5 5f98fbdcf7f68412161d0447a508e3c2
BLAKE2b-256 f4cd43bc01ed34cabba5156f29e56fa802ad76defc2e4fb05147e3560b742c95

See more details on using hashes here.

Provenance

File details

Details for the file graphlib2-0.4.0-cp37-abi3-macosx_10_9_x86_64.whl.

File metadata

  • Download URL: graphlib2-0.4.0-cp37-abi3-macosx_10_9_x86_64.whl
  • Upload date:
  • Size: 194.3 kB
  • Tags: CPython 3.7+, macOS 10.9+ x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/33.0 requests/2.27.1 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.63.0 importlib-metadata/4.11.2 keyring/23.5.0 rfc3986/2.0.0 colorama/0.4.4 CPython/3.10.2

File hashes

Hashes for graphlib2-0.4.0-cp37-abi3-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 8d777b11e1d56402f442d147721a9cc0b218be66e3c7131813d14c637217479b
MD5 30ffe939d29216128b5f29e92c84a4a8
BLAKE2b-256 a0536c466a3a19b915efbf941537a649cc950ecbb80cb6f82f62f5add4c45e0e

See more details on using hashes here.

Provenance

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