{
    "info": {
        "author": "Toon Weyens",
        "author_email": "weyenst@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "License :: OSI Approved :: GNU General Public License v3 (GPLv3)",
            "Operating System :: OS Independent",
            "Programming Language :: Python :: 3"
        ],
        "description": "# Elementary Shortest Path Problem with or without Resource Constraint\nThis module solves the shortest elementary path problem, by which it is meant that each node in a path can only be visited once.\nThe edge weights do not need to be nonnegative.\n\nA general algorithm to solve this problem works by solving the *k-paths* problem, i.e. by solving the nonelementary problem repeatedly and requiring that for the nodes that are present in nonelementary paths multiple (k) paths need to be found.\nThe resulting algorithm finds the elementary shortest paths (ESPP) from a **single source to all destinations** [1].\nHowever, it can be very slow if very large graphs are considered.\nEspecially because the algorithm in [1] is intrinsically flawed and the fix for this makes it much less efficient than expected: See note in ESPP.py.\n\nA more powerful algorithm can be used when additionally there are positive resources associated to each edge in the graph, though this requirement can be relaxed to nonnegative resources if not too many edges have zero resource cost associated to them.\nThe resulting Elementary Resource Constrained Shortest Path Problem (ESPPRC) can then be solved by an algorithm that starts by first preprocessing the graph [2].\nDuring preprocessing, the graph is first pruned by discarding all nodes that cannot be reached from the origin or reach the target without violating the resource limits.\nSubsequently, for each pair in the resulting pruned graph, the least-cost path is sought, which will be used later to incrase so-called *dominance* of paths by other paths.\n\nAfter preprocessing, the ESPPRC is solved by introducing *node-resources* that count how many times a node has been used in a certain path, so that elementarity can be enforced.\nAs this problem can quickly become exponential in nature, it is critical that the numer of resource nodes that have to be introdcuced kept as low as possible.\nIn the algorithm this is done by using a two-fold dominance strategy:\nOn the one hand, paths are only added to the list of possible shortest possible paths, if their resource consumption is not dominated by another path.\nAlso, when a path is added, the other possible paths that are dominated by it, are discarded.\nOn the other hand, *strong dominance* is a mathematical trick that is used to speed up convergence to the shortest path, by artificially incrementing possible node resources of nodes that cannot be reached [2].\nThe resulting algorithm seeks the ESPPRC for **single source to single destination** problems.\n\n\n## Installation\n* `pip install pylgrim`\n* or alternatively\n    * Clone this repository\n    * `pip install -e pylgrim`\n\n### Dependencies\n* numpy\n* networkx\n* logging\n* copy\n* matplotlib (for testing)\n* random (for testing)\n* timeit (for testing)\n\n## Usage\n\n### Getting started\nFirst of all, the directed graph ([`networkx.digraph`](https://networkx.github.io/documentation/stable/reference/classes/digraph.html)) `G` on which to use pylgrim needs to have a attribute `n_res` set through, for example\n```python\nG = nx.DiGraph(n_res=1)\n```\nor\n```python\nG.graph['n_res'] = 1\n```\nif the graph already exists.\n\nAlso, each of the graph edges should have an attribute `weight`, which is what will be minimized along the paths.\n\nFurthermore,\n```python\nfrom pylgrim import tools\n```\nshould be used to *decouple* the directed graph to make sure that the source node from which to calculate elementary shortest paths is certain not to have any in-edges, as this is not allowed by the algorithms:\n```python\ntools.decouple_source(G, source, source_in='source_in')\n```\nduplicates the `source` node to `source_in` and moves all the in-edges to the new node.\nThis operation happens in situ.\n\nAfterwards, the graph can be reverted to its original state using\n```python\ntools.undecouple_source(G, source, source_in=`source_in`)\n```\n\nApart from this,\n```python\nfrom pylgrim import Path\n```\nshould be used to import the `Path` class that inherits from the `networkx.digraph` and that represents a path that can be cyclic, so it contains the information of source node.\nAmong other things, the class provides an iterator for the next edge in the path, pretty printing, etc.\n\nFurthermore it is used to represent the solution path(s) from ESPP and ESPPRC.\n\n### Elementary shortest path\nElementary shortest path can be used by first importing the module through\n```python\nfrom pylgrim import ESPP\n```\n\nThe *Dynamic labelling algorithm* is implemented [1]:\n```python\nreturn paths, costs = DLA(G, source, min_K=1, output_pos = False, max_path_len = -1)\n```\nwhere `G` si the directed graph for which to find the shortest path from the `source` to all other nodes. \n\nOptionally, through `min_K` the minimum number of paths to be returned for every node can be changed, with `output_pos` also positive costs can be returned and through `max_path_len`, the maximum length of a path can be limited, so that the problem becomes easier to solve.\n\n`DLA` outputs in `paths` a dictionary where the keys are the target nodes and for every one of these, a list is returned with the best paths of type `Path`, ordered by lowest cost, of length at least `min_K`. The cost itself is returned in a matching dictionary `costs`.\n\nNote, however, that ESPP should no be used for graphs other than very small ones.\nThe following algorithm should be much faster.\n\n### Elementary shortest path with resource constraints\nElementary shortest path with resource constraints can be used by first importing the module through\n```python\nfrom pylgrim import ESPPRC\n```\n\nThe *General State Space Augmenting Algorithm*, `GSSA` is implemented [2]:\n```python\nbest_path, best_path_label = GSSA(G, source, target, max_res, res_min, res_name='res_cost')\n```\nwhere `G` is the directed graph for which to find the shortest path between `source` and `target` subject to maximum resource usage given in `max_res`, the array of maximum resources that can be consumed on any path, where a value should be given for every resource.\n\nNote, furthermore, the graph `G` must have been preprocessed first so that it is reduced and has the minimal resource information that is to be passed into `res_min`\n```python\nG, res_min = ESPPRC.preprocess(G_no_preprocess, source, target, max_res, res_name='res_cost')\n```\n\nFinally, in these functions, `res_name` can be used to specify the name of the resource that is to be used internally for the edges in the graph.\n\nThe output of `GSSA` is a `best_path` of the `Path` type and a corresponding `best_path_label` that is a 2-tuple with the first element equal to the cost of the best path and the second equal to the array of the resources consumed, less than or equal to `res_max`.\n\n## Testing\n* Run the tests in `/tests` using `python test_[NAME].py` where `[NAME]` is the name of the test.\n* Plot(s) will appear as well as textual output.\n* To debug, change `WARNING` to `INFO` or possibly `DEBUG` in `logging.basicConfig(level=logging.WARNING)` present at the top of the python files.\n\n\n## References\n[1] *On the shortest path problem with negative cost cycles* by Di Puglia Pugliese, Luigi (DOI: 10.1007/s10589-015-9773-1)\n\n[2] *Accelerated label setting algorithms for the elementary resource constrained shortest path problem* by Boland, Natashia (DOI: 10.1016/j.orl.2004.11.011)\n\n## Copyright\nCopyright 2018 Toon Weyens, Daan van Vugt\n\n\n",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/ToonWeyens/pylgrim",
        "keywords": "espp,espprc,shortest-path,graph,python",
        "license": "",
        "maintainer": "",
        "maintainer_email": "",
        "name": "pylgrim",
        "package_url": "https://pypi.org/project/pylgrim/",
        "platform": "",
        "project_url": "https://pypi.org/project/pylgrim/",
        "project_urls": {
            "Homepage": "https://github.com/ToonWeyens/pylgrim"
        },
        "release_url": "https://pypi.org/project/pylgrim/1.0.5/",
        "requires_dist": [
            "networkx",
            "numpy",
            "matplotlib (<3.3)"
        ],
        "requires_python": "",
        "summary": "Elementary shortest path problems, with or without resource constraints",
        "version": "1.0.5"
    },
    "last_serial": 5805391,
    "releases": {
        "1.0.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "7ed7d53ffae0e85ea1b0dd6d0ebfd9ae",
                    "sha256": "d58d3f80a95f46c6f4905847604b32bf6e273ebe313c8aabdd10c163736084d2"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.0-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "7ed7d53ffae0e85ea1b0dd6d0ebfd9ae",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 14402,
                "upload_time": "2018-08-09T19:46:03",
                "url": "https://files.pythonhosted.org/packages/5f/25/ea3d2208187f86ccde6a9975c604376b49cf0761bbbeb475eb9103c46ec8/pylgrim-1.0.0-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "8343a1f005dd9d97da0ab8c6727e4ca5",
                    "sha256": "cbf7d461e1e058e29ae4427206610155cf7d5c5140c0c51f9260afee4b816c64"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.0.tar.gz",
                "has_sig": false,
                "md5_digest": "8343a1f005dd9d97da0ab8c6727e4ca5",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 15214,
                "upload_time": "2018-08-09T19:46:05",
                "url": "https://files.pythonhosted.org/packages/f8/f5/4dc43c5b28f742f95af9c21778344bf845b403d4d86d75288bb59ca81d65/pylgrim-1.0.0.tar.gz"
            }
        ],
        "1.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "8886135859065e538a66ead4092a970a",
                    "sha256": "5a028e6f20d2f91d3835447d1db7ebc37eaeff776c516d9ac7aaa4b0d8c60c7b"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "8886135859065e538a66ead4092a970a",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 14419,
                "upload_time": "2018-08-09T20:07:13",
                "url": "https://files.pythonhosted.org/packages/5f/10/c95ab790e3ba7f4b42f8abe463f19e22ad7582ebb9b3b3c6ac9e71855d87/pylgrim-1.0.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "86bfd4bec39ac4be3c07fcfa988d23db",
                    "sha256": "e32afde6ac22b535bdde4ffe1845a996e7b53e3c42c7bab2d768b69a0adf924b"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "86bfd4bec39ac4be3c07fcfa988d23db",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 15246,
                "upload_time": "2018-08-09T20:07:15",
                "url": "https://files.pythonhosted.org/packages/bc/24/6a18a7533c9528597d930a4d82a5a381844c4b4d0ab757cfddd6d9ba54cd/pylgrim-1.0.1.tar.gz"
            }
        ],
        "1.0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "7258a6ecb0ae07646c8dbfad6192689f",
                    "sha256": "a991a5df813133a07ee96d83eb3690206a2855cc273c6d3a475955b87237504e"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.2-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "7258a6ecb0ae07646c8dbfad6192689f",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 14561,
                "upload_time": "2018-08-14T20:40:11",
                "url": "https://files.pythonhosted.org/packages/1d/cd/cad506ff0f54a4c58a2975b38c61fb5f4ba8c58a64c81dfc810a41740c39/pylgrim-1.0.2-py3-none-any.whl"
            }
        ],
        "1.0.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "24302e80349821bc913ccc1cf7d7593e",
                    "sha256": "6bcda4d0fffe97def17dcb92994de9deb406d53852999e3a9fefdfa831a75e30"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.3-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "24302e80349821bc913ccc1cf7d7593e",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 30432,
                "upload_time": "2018-10-12T11:36:12",
                "url": "https://files.pythonhosted.org/packages/b2/62/d3f6bb0986134b29e8bfa1c5fce12b29a96355ecb2ca2c54017363fec9fc/pylgrim-1.0.3-py3-none-any.whl"
            }
        ],
        "1.0.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "6324e0d398f7ffde02d3995eb804d144",
                    "sha256": "74f5ca37a1599e4bf4e5ca43e39f5fd07aabb6e7f2cc3780112aa7b6a7898e07"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.4-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "6324e0d398f7ffde02d3995eb804d144",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 26866,
                "upload_time": "2019-09-09T20:07:15",
                "url": "https://files.pythonhosted.org/packages/d9/ab/1ec480ce6441b0fce968ce4ceb05f60ff30b0850b6c535e22b6aa322285a/pylgrim-1.0.4-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "4d7d15d496776f50a0cb0428c44b8eb0",
                    "sha256": "b4df3ac37f65bf7e8a4b33271d37163e7df2f7884b03bb5722a177cf89d202b5"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.4.tar.gz",
                "has_sig": false,
                "md5_digest": "4d7d15d496776f50a0cb0428c44b8eb0",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 15380,
                "upload_time": "2019-09-09T20:07:17",
                "url": "https://files.pythonhosted.org/packages/e8/08/22bc881e4f482594958f1e59f67a187505f7552962f965b87da64d699971/pylgrim-1.0.4.tar.gz"
            }
        ],
        "1.0.5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "5e0f99bded3809ea63fa98baf072a667",
                    "sha256": "eb9cc80b8bbb905b020d588f0348827cc189b7071eaa92b7113e9000d21f7b6f"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.5-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "5e0f99bded3809ea63fa98baf072a667",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 26861,
                "upload_time": "2019-09-09T20:15:53",
                "url": "https://files.pythonhosted.org/packages/b3/e5/78b7323ca28e4879e70473465a1477b63fdcdd2e6c9795ac3842cf74eb04/pylgrim-1.0.5-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "501caac069d037ee40dd0a08e4c577c1",
                    "sha256": "7f7094df3ceac4ee25c6be6a786511c12133330508305083bc0d215e02a755c2"
                },
                "downloads": -1,
                "filename": "pylgrim-1.0.5.tar.gz",
                "has_sig": false,
                "md5_digest": "501caac069d037ee40dd0a08e4c577c1",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 15376,
                "upload_time": "2019-09-09T20:15:56",
                "url": "https://files.pythonhosted.org/packages/00/df/ed5ee5d3da2e72ee257b210bf639897636a78ffc6221c921d41e82ddba51/pylgrim-1.0.5.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "5e0f99bded3809ea63fa98baf072a667",
                "sha256": "eb9cc80b8bbb905b020d588f0348827cc189b7071eaa92b7113e9000d21f7b6f"
            },
            "downloads": -1,
            "filename": "pylgrim-1.0.5-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "5e0f99bded3809ea63fa98baf072a667",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 26861,
            "upload_time": "2019-09-09T20:15:53",
            "url": "https://files.pythonhosted.org/packages/b3/e5/78b7323ca28e4879e70473465a1477b63fdcdd2e6c9795ac3842cf74eb04/pylgrim-1.0.5-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "501caac069d037ee40dd0a08e4c577c1",
                "sha256": "7f7094df3ceac4ee25c6be6a786511c12133330508305083bc0d215e02a755c2"
            },
            "downloads": -1,
            "filename": "pylgrim-1.0.5.tar.gz",
            "has_sig": false,
            "md5_digest": "501caac069d037ee40dd0a08e4c577c1",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 15376,
            "upload_time": "2019-09-09T20:15:56",
            "url": "https://files.pythonhosted.org/packages/00/df/ed5ee5d3da2e72ee257b210bf639897636a78ffc6221c921d41e82ddba51/pylgrim-1.0.5.tar.gz"
        }
    ]
}