{
    "info": {
        "author": "Mr-Io",
        "author_email": "mrio.dev@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 5 - Production/Stable",
            "Intended Audience :: Developers",
            "Intended Audience :: Science/Research",
            "License :: OSI Approved :: MIT License",
            "Programming Language :: Python :: 3.7",
            "Programming Language :: Python :: 3 :: Only",
            "Topic :: Scientific/Engineering",
            "Topic :: Software Development :: Build Tools"
        ],
        "description": "dset - Fast Disjoint-Set in Python\n==================================\n.. ini-badges\n\n|Python| |Version| |License|\n\n.. |Python| image:: https://img.shields.io/pypi/pyversions/dset.svg\n    :target: https://pypi.org/project/dset/\n\n.. |Version| image:: https://img.shields.io/pypi/v/dset.svg\n    :target: https://pypi.org/project/dset/\n\n.. |License| image:: https://img.shields.io/github/license/Mr-Io/dset.svg\n    :target: https://pypi.org/project/dset/\n\n.. end-badges\n\n**A Disjoint-Set implementation which makes use of the the \"Union by Rank\" and \"Path Compression\" heuristic\noptimizations while being as simple and effective as possible.**\n\nIt support the following operations:\n\n* **Find-Set** in *O(1)* amortized running time\n* **Union** in *O(1)* amortized running time\n\n*Check end notes for additional information about running times*\n\nWhy?\n----\nSometimes, specially  during algorithm competitions, a Union-Find data structure is needed\nto solve a certain problem (e.g. when implementing Kruskal's MST algorithm) In those cases,\nwe usually use whatever off-the-shelf implementation we happen to find in PyPI and, many times,\nwe get the infamous submission fail *Time Limit Exceed(TLE)* because that specific\nDisjoint-Set implementation is not fast enough...\n\nWorry not! A fast and simple enough (you can copy paste the code `here`_) disjoint-set implementation\nis now available:\n\nInstallation\n------------\n.. code-block:: console\n\n    $ pip install dset\n\nUsage\n-----\n.. code-block:: python\n\n    >>> import dset\n    >>> s1 = dset.Set()                 # To create new sets objects (it runs in O(1))\n    >>> s2 = dset.Set()\n    >>> s3 = dset.Set()\n    >>> dset.groups()                   # To check the number of different groups (it runs in O(1))\n    3\n    >>> dset.find(s1) == dset.find(s2)  # To check if two sets are in the same group\n    False\n    >>> dset.union(s1, s2)              # to group s1 and s2 sets together\n    >>> dset.groups()                   # Now there are only 2 groups: s1-s2 and s3\n    2\n    >>> dset.find(s1) == dset.find(s2)  # They are in the same group s1-s2\n    True\n    >>> dset.find(s2) == dset.find(s3)  # They are in distinct groups s1-s2 and s3\n    False\n    >>> dset.union(s2, s1)              # do nothing (no need to check if s1 and s2 belong to the same group)\n    >>> dset.groups()                   # Same as before only 2: s1-s2 and s3\n    2\n    >>> dset.union(s1, s3)              # group s1-s2 and s3 together.\n    >>> dset.groups()                   # Now there is only one group: s1-s2-s3\n    1\n    >>> dset.find(s1) == dset.find(s2)  # All the sets are in the same groups s1-s2-s3\n    ... dset.find(s2) == dset.find(s3)\n    ... dset.find(s1) == dset.find(s3)\n    True\n    True\n    True\n\nFuture improvements\n-------------------\n* Make official Sphinx Documentation. (minor releases)\n* Make test suite. (minor releases)\n* Change to a list-based implementation (major-minor release)\n    * Improve running time (constant terms)\n    * Improve memory space (constant terms)\n\n* Make the package C-based. (major-minor release)\n    * Improve running time (constant terms)\n\n.. _notes:\n\nNotes on Complexity Running Times\n---------------------------------\nSeparately, either \"Union by Rank\" or \"Path Compression\" improves the running time of\nthe operations on disjoint-sets. Alone, \"Union by Rank\" yields a running time\nof *O(m log n)*, where *m* is the number of Union and Find-Set operations and *n* is the number\nof sets.\n\nThe improvement is even greater when we use the two heuristics together; the worst-case running\ntime is *O(m f(n)),*  where *f(n)* is a very slowly growing function, the Inverse Ackermann function\n(e.g. for *n* equal to the number atoms in the universe, *f(n)* is only 4)\nSo for any conceivable application, we can consider the running time of *m* Union + Find-Set operations to be\n*O(m)* and therefore both Union and Find-Set operations have *O(1)* amortized running time in practice.\n\n\n.. _`here`: https://github.com/Mr-Io/dset/blob/master/dset.py\n\n\n",
        "description_content_type": "text/x-rst",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/Mr-Io/dset",
        "keywords": "",
        "license": "",
        "maintainer": "",
        "maintainer_email": "",
        "name": "dset",
        "package_url": "https://pypi.org/project/dset/",
        "platform": "",
        "project_url": "https://pypi.org/project/dset/",
        "project_urls": {
            "Bug Reports": "https://github.com/Mr-Io/dset/issues",
            "Homepage": "https://github.com/Mr-Io/dset",
            "Source": "https://github.com/Mr-Io/dset"
        },
        "release_url": "https://pypi.org/project/dset/0.0.1/",
        "requires_dist": null,
        "requires_python": ">=3.7",
        "summary": "Disjoint-Set implementation with heuristic optimizations (union-by-rank and path-compression)",
        "version": "0.0.1"
    },
    "last_serial": 5720591,
    "releases": {
        "0.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "849984553bdca4cb095a9b41425c79a2",
                    "sha256": "fdca85c0ba033725006a9617383a26f1023230bb8bbca69f4ab25d824599b838"
                },
                "downloads": -1,
                "filename": "dset-0.0.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "849984553bdca4cb095a9b41425c79a2",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": ">=3.7",
                "size": 4012,
                "upload_time": "2019-08-23T12:45:49",
                "url": "https://files.pythonhosted.org/packages/60/a7/97c81486d66cd7ec47d413f128c66dd00dbc51bee32e6165e05310561703/dset-0.0.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "2b47fe2fec195c7b8e85d33cece7b7d3",
                    "sha256": "cd65b3260908a2218dd41252c361021aea7a5da8c72079b2b1672e54faf8e781"
                },
                "downloads": -1,
                "filename": "dset-0.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "2b47fe2fec195c7b8e85d33cece7b7d3",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": ">=3.7",
                "size": 5081,
                "upload_time": "2019-08-23T12:45:52",
                "url": "https://files.pythonhosted.org/packages/5d/64/5aeecb73379149f1a2e53e946d6083c1bed11f489597ca14aaafb3ba5242/dset-0.0.1.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "849984553bdca4cb095a9b41425c79a2",
                "sha256": "fdca85c0ba033725006a9617383a26f1023230bb8bbca69f4ab25d824599b838"
            },
            "downloads": -1,
            "filename": "dset-0.0.1-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "849984553bdca4cb095a9b41425c79a2",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.7",
            "size": 4012,
            "upload_time": "2019-08-23T12:45:49",
            "url": "https://files.pythonhosted.org/packages/60/a7/97c81486d66cd7ec47d413f128c66dd00dbc51bee32e6165e05310561703/dset-0.0.1-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "2b47fe2fec195c7b8e85d33cece7b7d3",
                "sha256": "cd65b3260908a2218dd41252c361021aea7a5da8c72079b2b1672e54faf8e781"
            },
            "downloads": -1,
            "filename": "dset-0.0.1.tar.gz",
            "has_sig": false,
            "md5_digest": "2b47fe2fec195c7b8e85d33cece7b7d3",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.7",
            "size": 5081,
            "upload_time": "2019-08-23T12:45:52",
            "url": "https://files.pythonhosted.org/packages/5d/64/5aeecb73379149f1a2e53e946d6083c1bed11f489597ca14aaafb3ba5242/dset-0.0.1.tar.gz"
        }
    ]
}