A command-line tool for automatically classifying LCL problems on rooted trees.
Project description
Description
This folder contains a program that decides round complexity of homogenous LCL problems on (binary) trees.
The program uses three subroutines to determines a problem's complexity.
- constant_decider
- decides whether a problem is O(1) solvable or it is inherently harder
- log_decider
- decides whether a problem is log(n) solvable or it is inherently harder
- log_star_decider
- decides whether a problem is log*(n) solvable or it is inherently harder
Usage
-
Install dependencies by
pip3 install -r requirements.txt
. -
Run
python -m rooted_tree_classifier
and describe (on standard input) constraints of a problem. For example:
Note that one needs to first run the classifier (python -m rooted_tree_classifier
) and only afterwards provide an input
on a separate line.
python -m rooted_tree_classifier
111
Expected output is O(1)
python -m rooted_tree_classifier
112 121 122
Expected output is O(1)
python -m rooted_tree_classifier
121 131 212 323
Expected output is O(log*n)
python -m rooted_tree_classifier
112 121
Expected output is Θ(log n)
python -m rooted_tree_classifier
112 123 131
Expected output is Θ(log n)
python -m rooted_tree_classifier
121 212
Expected output is Ω(n)
Tests
To execute tests, run the following from the root directory:
python -m unittest discover
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for rooted-tree-classifier-0.1.5.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbda35354bfb52a85f91d5d6d72cde32deb4d8711f4b58b2e0ee2ced6ffca507 |
|
MD5 | c8adfdfe42b81e3de1223625d0dfe19c |
|
BLAKE2b-256 | 6d8ea8371bce247966f3d3129a4b151568721be2e0d8a6ab6cb72468a70773ce |
Hashes for rooted_tree_classifier-0.1.5-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 84e2a2fd997c1dacff557428b61c14879ca9cb1a9c4456c1a3c225486b410e75 |
|
MD5 | 3c2097812bcbca1008ae9866b828aac7 |
|
BLAKE2b-256 | 504f4ab5620e38f8d3be04f6ce2f021567b37a8e9e52a55f09fa27824470145b |