Rust port of the Python stdlib graphlib modules

Navigation

Verified details

These details have been verified by PyPI
Maintainers
Avatar for adriangb from gravatar.com adriangb

Unverified details

These details have not been verified by PyPI
Meta
  • License: MIT License (MIT)
  • Author: Adrian Garcia Badaracco
  • Requires: Python >=3.7
Classifiers

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

Verified details

These details have been verified by PyPI
Maintainers
Avatar for adriangb from gravatar.com adriangb

Unverified details

These details have not been verified by PyPI
Meta
  • License: MIT License (MIT)
  • Author: Adrian Garcia Badaracco
  • Requires: Python >=3.7
Classifiers

Release history Release notifications | RSS feed

0.4.7

0.4.6

0.4.5

0.4.4

0.4.3

0.4.2

0.4.1

0.4.0

0.3.0

0.2.18

This version

0.2.16

0.2.15

0.2.14

0.2.13

0.2.12

0.2.11

0.2.10

0.2.9

0.2.7

0.2.5

0.2.4

0.2.2

0.2.1

0.2.0

0.1.2

0.1.1

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.2.16.tar.gz (180.2 kB view hashes)

Uploaded Source

Built Distributions

graphlib2-0.2.16-pp38-pypy38_pp73-win_amd64.whl (145.2 kB view hashes)

Uploaded PyPy Windows x86-64

graphlib2-0.2.16-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (214.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.2.16-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (197.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.2.16-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (240.8 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

graphlib2-0.2.16-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (197.9 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

graphlib2-0.2.16-pp37-pypy37_pp73-win_amd64.whl (145.2 kB view hashes)

Uploaded PyPy Windows x86-64

graphlib2-0.2.16-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (214.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

graphlib2-0.2.16-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (197.5 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

graphlib2-0.2.16-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (240.8 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

graphlib2-0.2.16-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (197.9 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

graphlib2-0.2.16-cp37-abi3-win_amd64.whl (145.0 kB view hashes)

Uploaded CPython 3.7+ Windows x86-64

graphlib2-0.2.16-cp37-abi3-musllinux_1_1_x86_64.whl (247.4 kB view hashes)

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

graphlib2-0.2.16-cp37-abi3-musllinux_1_1_i686.whl (266.3 kB view hashes)

Uploaded CPython 3.7+ musllinux: musl 1.1+ i686

graphlib2-0.2.16-cp37-abi3-musllinux_1_1_aarch64.whl (231.9 kB view hashes)

Uploaded CPython 3.7+ musllinux: musl 1.1+ ARM64

graphlib2-0.2.16-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (214.9 kB view hashes)

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

graphlib2-0.2.16-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (197.3 kB view hashes)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARM64

graphlib2-0.2.16-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (240.7 kB view hashes)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

graphlib2-0.2.16-cp37-abi3-macosx_10_9_x86_64.whl (198.1 kB view hashes)

Uploaded CPython 3.7+ macOS 10.9+ x86-64

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