A command-line tool for automatically calculating round complexity of LCL problems in cycles and paths based on their description in the node-edge-checkable formalism
Project description
Cyclepath classifier
A command-line tool for automatically calculating round complexity of LCL problems in cycles and paths based on their description in the node-edge-checkable formalism. It also reports the number of solvable/unsolvable instances of a problem when classifying it (see examples below).
The tool is based on the techniques described in this paper.
Requirements
- Python 3.8.3 or later version
Getting started
Run the tool specifying node and edge constraints of a problem in the node-edge-checkable formalism.
The required parameters are -t
or --type
, -n
or --node-constr
and -e
or --edge-constr
.
There are also optional parameters specifying start and end constraints: --start-constr
and --end-constr
--type
accepts 3 values: dir
, undir
and tree
for directed cyclepath, undirected cyclepath and a rooted tree respectively.
Unless the type is tree
, the tool will assume that the problem is defined for a path if either --start-constr
or --end-constr
is specified. Otherwise, cycle setting is assumed.
Examples
$ python3 -m cyclepath_classifier -t undir -n "{ 11, 22, 33 }" -e "{ 12, 21, 13, 31, 23, 32 }"
Round complexity of the problem is Θ(log* n)
There are infinitely many solvable instances
There are finitely many unsolvable instances
$ python3 -m cyclepath_classifier -t undir -n "{ 12, 21 }" -e "{ 11, 22 }"
Round complexity of the problem is Θ(n)
There are infinitely many solvable instances
There are infinitely many unsolvable instances
$ python3 -m cyclepath_classifier -t undir -n "{00, 1M}" -e "{01, 10, 11, MM}" --start-constr "{ 1 }" --end-constr "{ 1 }"
A problem cannot be of 'undirected' type if its constraints are asymmetric. Otherwise it is not well-defined.
$ python3 -m cyclepath_classifier -t dir -n "{00, 1M}" -e "{01, 10, 11, MM}" --start-constr "{ 1 }" --end-constr "{ 1 }"
Round complexity of the problem is O(1)
There are finitely many solvable instances
There are infinitely many unsolvable instances
$ python3 -m cyclepath_classifier -t tree -e "{ 11, 22 }"
Round complexity of the problem is O(1)
There are infinitely many solvable instances
There are finitely many unsolvable instances
python3 -m cyclepath_classifier -t tree -e "{ 12, 13, 23, 21, 31, 32 }"
Round complexity of the problem is Θ(log* n)
There are infinitely many solvable instances
There are finitely many unsolvable instances
Tests
Run tests with python -m unittest discover
. See the tests/test.py
file for details.
Project details
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
File details
Details for the file cyclepath-classifier-0.2.1.tar.gz
.
File metadata
- Download URL: cyclepath-classifier-0.2.1.tar.gz
- Upload date:
- Size: 7.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.3.0 pkginfo/1.7.0 requests/2.25.1 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.48.2 CPython/3.8.3
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b2cbcea9a9d882d2e78b64643a700420146a8741f23b0dee24fdabb1465932b |
|
MD5 | d6c4fb9d3eb940f9afa67a6f94ec880f |
|
BLAKE2b-256 | 9a5daccc283d09ecd330cbbf57537bde9b9910f9aaf2d827e613ee4eaf7218fa |
File details
Details for the file cyclepath_classifier-0.2.1-py3-none-any.whl
.
File metadata
- Download URL: cyclepath_classifier-0.2.1-py3-none-any.whl
- Upload date:
- Size: 8.7 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.3.0 pkginfo/1.7.0 requests/2.25.1 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.48.2 CPython/3.8.3
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 29ce8e6a4c9f4564eee51a44f91b7e146932e93364aa9f1b6723ab2abd84d9f8 |
|
MD5 | 9a769d95a6c9fa34fea99b72abc98793 |
|
BLAKE2b-256 | b429710a279bf67e84f105334e70cfe59a28eb3cbdda1a838a3371d11318eec8 |