A simple Python package for Graph Series-Parallel-ization.
Your SP: no sync nodes, can be dups
- Does not have sync nodes, can only have nodes as int. If coming from a graph with dupes, the nodes are simply deduplicated (so from NodeDup to int). Technically, SP can only hold PureNodes, but for simplicity we'll have Node.
Your graph: sync nodes, cannot be dups
-
Can have sync nodes or not (and can freely switch between one another)
-
Can either have no duplicates (so all the nodes are simply int) or have duplicates (in which case they are NodeDups). You can frely switch between graph and SP.
-
Algorithms must take in a DAG that is made up of ints and that is TTSP, and return an SPD of only ints.
-
In general: all graph utilities should apply to SPG, all SP utilities should apply to SPD.
- Have in the algo_utils, rapidcheck style property checkers:
- is_valid_spization
- sp remains sp
- transitive reduction leaves it unchanged
- algorithm A is strictly better than B
- Add the diagram with the various classes
To enter the venv: poetry shell
For testing: pytest
For codecov: pytest --cov=spization --cov-report=term-missing:skip-covered
For linting: ruff check --fix/ruff format
For type checking: mypy .
To run benchmarking: benchmark