Metadata-Version: 2.1
Name: rooted-tree-classifier
Version: 0.1.6
Summary: A command-line tool for automatically classifying LCL problems on rooted trees.
Home-page: https://github.com/jendas1/rooted-tree-classifier
Author: Jan Studeny
Author-email: jendas1@yahoo.com
License: Unlicense
Platform: UNKNOWN
Classifier: License :: OSI Approved :: The Unlicense (Unlicense)
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Description-Content-Type: text/markdown
Requires-Dist: networkx


## 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

1. Install dependencies by `pip3 install -r requirements.txt`.

2. 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
```


