{ "info": { "author": "Nelson Uhan", "author_email": "nelson@uhan.me", "bugtrack_url": null, "classifiers": [], "description": "bellmanford\n===========\n\nThis package provides a few small extensions of the Bellman-Ford\nroutines in `NetworkX `__, primarily for\nconvenience.\n\nInstallation\n------------\n\n``bellmanford`` is available on PyPI:\n\n.. code:: bash\n\n pip install bellmanford\n\nUsage\n-----\n\nbellman_ford\n~~~~~~~~~~~~\n\n.. code:: python\n\n length, nodes, negative_cycle = bellman_ford(G, source, target, weight='weight')\n\nCompute shortest path and shortest path lengths between a source node\nand target node in weighted graphs using the Bellman-Ford algorithm.\n\nParameters\n^^^^^^^^^^\n\n- ``G`` : NetworkX graph\n- ``pred`` : dict - Keyed by node to predecessor in the path\n- ``dist`` : dict - Keyed by node to the distance from the source\n- ``source``: node label - Source node\n- ``target``: node label - Target node\n- ``weight`` : string - Edge data key corresponding to the edge weight\n\nReturns\n^^^^^^^\n\n- ``length`` : numeric - Length of a negative cycle if one exists.\n Otherwise, length of a shortest path. Length is ``inf`` if ``source``\n and ``target`` are not connected.\n- ``nodes`` : list - Nodes in a negative edge cycle (in order) if one\n exists. Otherwise nodes in a shortest path. List is empty if\n ``source`` and ``target`` are not connected.\n- ``negative_cycle`` : bool - ``True`` if a negative edge cycle exists,\n otherwise ``False``.\n\nExamples\n^^^^^^^^\n\n.. code:: python\n\n >>> import networkx as nx\n >>> G = nx.path_graph(5, create_using = nx.DiGraph())\n >>> bf.bellman_ford(G, source=0, target=4)\n (3, [1, 2, 3, 4], False)\n\nnegative_edge_cycle\n~~~~~~~~~~~~~~~~~~~\n\n.. code:: python\n\n length, nodes, negative_cycle = negative_edge_cycle(G, weight='weight')\n\nIf there is a negative edge cycle anywhere in ``G``, returns ``True``.\nAlso returns the total weight of the cycle and the nodes in the cycle.\n\n.. _parameters-1:\n\nParameters\n^^^^^^^^^^\n\n- ``G`` : NetworkX graph\n- ``weight`` : string, optional (default = ``'weight'``) - Edge data\n key corresponding to the edge weight\n\n.. _returns-1:\n\nReturns\n^^^^^^^\n\n- ``length`` : numeric - Length of a negative edge cycle if one exists,\n otherwise ``None``.\n- ``nodes`` : list - Nodes in a negative edge cycle (in order) if one\n exists, otherwise ``None``.\n- ``negative_cycle`` : bool - ``True`` if a negative edge cycle exists,\n otherwise ``False``.\n\n.. _examples-1:\n\nExamples\n^^^^^^^^\n\n.. code:: python\n\n >>> import networkx as nx\n >>> import bellmanford as bf\n >>> G = nx.cycle_graph(5, create_using = nx.DiGraph())\n >>> print(bf.negative_edge_cycle(G))\n (None, [], False)\n >>> G[1][2]['weight'] = -7\n >>> print(bf.negative_edge_cycle(G))\n (-3, [4, 0, 1, 2, 3, 4], True)", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/nelsonuhan/bellmanford", "keywords": "", "license": "BSD", "maintainer": "", "maintainer_email": "", "name": "bellmanford", "package_url": "https://pypi.org/project/bellmanford/", "platform": "", "project_url": "https://pypi.org/project/bellmanford/", "project_urls": { "Homepage": "https://github.com/nelsonuhan/bellmanford" }, "release_url": "https://pypi.org/project/bellmanford/0.2.1/", "requires_dist": null, "requires_python": "", "summary": " Small extensions of the Bellman-Ford routines in NetworkX, primarily for convenience (https://networkx.github.io). ", "version": "0.2.1" }, "last_serial": 3841934, "releases": { "0.1": [ { "comment_text": "", "digests": { "md5": "97cc584367644644906acec486c53c3f", "sha256": "8a8a3c40d86b933303378b2fb7c34697a8146432c6d5a643c31a49fb4b0d7890" }, "downloads": -1, "filename": "bellmanford-0.1.tar.gz", "has_sig": false, "md5_digest": "97cc584367644644906acec486c53c3f", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5053, "upload_time": "2017-01-12T22:05:02", "url": "https://files.pythonhosted.org/packages/4b/af/07382b36d58ee96c633ac5cc01ccce9e2ebc0abc684cb49500f204735396/bellmanford-0.1.tar.gz" } ], "0.1.1": [ { "comment_text": "", "digests": { "md5": "021a6783ab23fb40c1e61ed2eb2b41ce", "sha256": "33816d2b26201ba1b64e1d76dc02bf6c2b0b83881b76dbedad8a13d8f5d5320c" }, "downloads": -1, "filename": "bellmanford-0.1.1.tar.gz", "has_sig": false, "md5_digest": "021a6783ab23fb40c1e61ed2eb2b41ce", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5066, "upload_time": "2017-01-26T20:32:06", "url": "https://files.pythonhosted.org/packages/f4/9c/4dd8ec8ddcfca70f2a315819b5db6dadc50dc4249bf1407f5f230738a033/bellmanford-0.1.1.tar.gz" } ], "0.1.2": [ { "comment_text": "", "digests": { "md5": "63d5c3c4f621866eb7c74e1370d27fc9", "sha256": "48ef649f921ecbc345e986a1e603664fc949727d7ec26200522be648a1a27e49" }, "downloads": -1, "filename": "bellmanford-0.1.2.tar.gz", "has_sig": false, "md5_digest": "63d5c3c4f621866eb7c74e1370d27fc9", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5080, "upload_time": "2017-08-03T20:01:30", "url": "https://files.pythonhosted.org/packages/76/f8/a3ddd7ef16abcf0ca1361d483da2a26b0c41400012412ce23ee3f745719c/bellmanford-0.1.2.tar.gz" } ], "0.2.1": [ { "comment_text": "", "digests": { "md5": "1ec12aee1d21f0260699dc4a3f60b58b", "sha256": "29e4975df1b1c8353d6e495f214e23a470e8eb7021c7a3c0db7c24c78599d39e" }, "downloads": -1, "filename": "bellmanford-0.2.1.tar.gz", "has_sig": false, "md5_digest": "1ec12aee1d21f0260699dc4a3f60b58b", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5233, "upload_time": "2018-05-07T19:38:17", "url": "https://files.pythonhosted.org/packages/ea/2b/2c483bdd3c07af70e5ae1a85183f40c980e25b98ac16eb122202cc9a8b18/bellmanford-0.2.1.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "1ec12aee1d21f0260699dc4a3f60b58b", "sha256": "29e4975df1b1c8353d6e495f214e23a470e8eb7021c7a3c0db7c24c78599d39e" }, "downloads": -1, "filename": "bellmanford-0.2.1.tar.gz", "has_sig": false, "md5_digest": "1ec12aee1d21f0260699dc4a3f60b58b", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5233, "upload_time": "2018-05-07T19:38:17", "url": "https://files.pythonhosted.org/packages/ea/2b/2c483bdd3c07af70e5ae1a85183f40c980e25b98ac16eb122202cc9a8b18/bellmanford-0.2.1.tar.gz" } ] }