Skip to main content

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

cyclepath-classifier-0.2.1.tar.gz (7.7 kB view details)

Uploaded Source

Built Distribution

cyclepath_classifier-0.2.1-py3-none-any.whl (8.7 kB view details)

Uploaded Python 3

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

Hashes for cyclepath-classifier-0.2.1.tar.gz
Algorithm Hash digest
SHA256 1b2cbcea9a9d882d2e78b64643a700420146a8741f23b0dee24fdabb1465932b
MD5 d6c4fb9d3eb940f9afa67a6f94ec880f
BLAKE2b-256 9a5daccc283d09ecd330cbbf57537bde9b9910f9aaf2d827e613ee4eaf7218fa

See more details on using hashes here.

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

Hashes for cyclepath_classifier-0.2.1-py3-none-any.whl
Algorithm Hash digest
SHA256 29ce8e6a4c9f4564eee51a44f91b7e146932e93364aa9f1b6723ab2abd84d9f8
MD5 9a769d95a6c9fa34fea99b72abc98793
BLAKE2b-256 b429710a279bf67e84f105334e70cfe59a28eb3cbdda1a838a3371d11318eec8

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page