A command-line tool for automatically classifying LCL problems on rooted trees.
Project description
Description
This folder contains two programs that partially a round complexity of homogenous LCL problem on (binary) trees.
- 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
. -
Run
python3 log_decider.py
orpython3 log_star_decider.py
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(log*n)
python -m rooted_tree_classifier
112 121 122
Expected output is O(log*n)
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.3.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3ee7d38fed05e5f8c7e805f7cc5068eaf833cc5cb240bb94252fc3860756056 |
|
MD5 | 001c262e6bd74b698f3b426519ff8522 |
|
BLAKE2b-256 | 0530a51e450497a52a02daa3d141c4f8691c552f914be950c59d5ac4c2cd8c9f |
Hashes for rooted_tree_classifier-0.1.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | adb3f9a1c0595b65a237dd98bbd9aee08eb0c63ea75c55342d105ebacf5d3732 |
|
MD5 | ee22ded7971e98c4b132b8b30274f226 |
|
BLAKE2b-256 | 3a73bd91512e1c02a18c5c0d8057b39e971415b4337998776281c29bacf008fe |