{
    "info": {
        "author": "Andrew Brooks",
        "author_email": "andrewbrooks@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 2 - Pre-Alpha",
            "License :: OSI Approved :: MIT License",
            "Topic :: Scientific/Engineering :: Mathematics",
            "Topic :: Scientific/Engineering :: Visualization"
        ],
        "description": ".. image:: https://travis-ci.org/brooksandrew/postman_problems.svg?branch=master\n    :target: https://travis-ci.org/brooksandrew/postman_problems\n\n.. image:: https://badge.fury.io/py/postman_problems.svg\n    :target: https://badge.fury.io/py/postman_problems\n\n.. image:: http://coveralls.io/repos/github/brooksandrew/postman_problems/badge.svg?branch=master\n    :target: https://coveralls.io/github/brooksandrew/postman_problems?branch=master\n\n.. image:: https://landscape.io/github/brooksandrew/postman_problems/master/landscape.svg?style=flat\n   :target: https://landscape.io/github/brooksandrew/postman_problems/master\n   :alt: Code Health\n\n*Note to those reading this on PyPI: For a better reading experience, checkout the README on GitHub*\n`here <https://github.com/brooksandrew/postman_problems/blob/master/README.rst>`__.  *GitHub and PyPI are not\ncooperating on rendering SVGs*.\n\n\n\n.. sectnum::\n\n.. contents:: **Table of Contents:**\n   :depth: 2\n\n\nContents\n========\n\nThis package contains implementations to solve the suite of `Postman Problems`_ from graph theory.\n\nAlgorithms currently implemented:\n\n- Chinese Postman\n- Rural Postman (partial)\n\nThe Rural Postman implementation is currently restricted to a subset of problems.  Specifically to graphs where\nthe required edges form a single connected component when the optional edges are removed.\n\nInstall\n=======\n\nBasic\n-----\n\n**Option 1. Install from PyPI:** Stable release.\n\n.. code:: bash\n\n   pip install postman_problems\n\n**Option 2. Install from GitHub:**  As this project develops, GitHub will have the most recent features, but no\nguarantees they'll be stable.\n\n\n1. Clone the repo.\n\n   .. code::\n\n      git clone https://github.com/brooksandrew/postman_problems.git\n      cd postman_problems\n\n2. Install with pip.  Builds are tested on Python 2.7, 3.3, 3.4, 3.5, 3.6.\n\n   .. code::\n\n      pip install .\n\n\nViz\n---\n\n``postman_problems`` leverages `Graphviz`_ for visualization which unlocks more robust visualizations than just NetworkX\nand matplotlib.  However, this also comes with several dependencies.  These are managed separately from the\nbase package, so users can optimize graphs to their heart's content unencumbered from the weight and hassle of\ninstalling viz dependencies, if they so choose.\n\n1. Install optional Python visualization libraries.\n\n   .. code::\n\n      pip install postman_problems[viz]\n\n\n2. Install Graphviz.  You need this underlying software application in addition to the `graphviz python package`_ which\n   wraps around it.  Checkout the `Graphviz Download page`_ for the best way to install on your OS.\n\n   For Mac, this should be as easy as:\n\n   .. code::\n\n      brew install graphviz\n\n   For Linux,\n\n   .. code::\n\n      sudo apt-get install graphviz\n\n   These are the installs I'm currently using on my builds for the `tests on TravisCI`_.  YMMV.  For Windows users and\n   for those where these methods fail, I defer to the Graphviz download docs.\n\n\nUsage\n=====\n\nCLI\n---\n\nThe easiest way to start is with the command line using the entry points installed with this package: `chinese_postman`\nand `rural_postman`.\n\nArguments: edgelist\n~~~~~~~~~~~~~~~~~~~\n\nThere are several optional command line arguments, but the only one required is ``--edgelist``:\n\n**Description:** Filename of edgelist.  Expected to be comma delimited text file readable with pandas.read_csv.  The first two columns\nshould be the \"from\" and \"to\" node names.  Additional columns can be provided for edge attributes.  The first row\nshould be the edge attribute names.\n\nA note on some edge attributes:\n\n- ``required``: must be provided for the RPP.  0 is used for optional edges, 1 for required.\n- ``distance``: default edge attribute used for shortest path computations.  Can be overridden with ``edge_weight``.\n- ``id``: recommended to not include, but will be used if provided.  This will be generated automatically to assist with\n  computation of parallel edges.  If provided, it should be unique to ensure stable computation.\n\nArguments: others\n~~~~~~~~~~~~~~~~~\n\nFor the complete list of optional arguments run one of the following:\n\n.. code::\n\n   chinese_postman --help\n   rural_postman --help\n\nThe big ones are ``--viz`` and ``--animation``, which when present will create the static (single visualization) and\nanimation of the postman problem solution.  Most of the other arguments modify the default values used for the\nvisualizations.\n\nSimple example\n~~~~~~~~~~~~~~\n\nBelow we solve the CPP on the `Seven Bridges of Konigsberg`_ network.  The edgelist is provided in this repo, but you\ncan swap this out for any comma delimited text file where the first two columns represent the node pairs in your network.\n\n.. code::\n\n   chinese_postman --edgelist postman_problems/examples/seven_bridges/edgelist_seven_bridges.csv\n\n\nIf the ``chinese_postman`` entry point is not working for whatever reason, you can run the script directly with:\n\n.. code::\n\n   python postman_problems/chinese_postman.py --edgelist postman_problems/examples/seven_bridges/edgelist_seven_bridges.csv\n\n\nYou should see output that describes the CPP route solution (Eulerian circuit through each edge).  Something like this:\n\n.. code ::\n\n        ('A', 'C', 1, {'trail': 'd', 'distance': 10, 'id': 3})\n        ('C', 'D', 0, {'trail': 'g', 'distance': 3, 'id': 6, 'augmented': True})\n        ('D', 'C', 0, {'trail': 'g', 'distance': 3, 'id': 6})\n        ('C', 'A', 0, {'trail': 'c', 'distance': 2, 'id': 2})\n        ('A', 'D', 0, {'trail': 'e', 'distance': 1, 'id': 4})\n        ('D', 'B', 0, {'trail': 'f', 'distance': 9, 'id': 5})\n        ('B', 'A', 0, {'trail': 'a', 'distance': 3, 'id': 0, 'augmented': True})\n        ('A', 'B', 1, {'trail': 'b', 'distance': 5, 'id': 1})\n        ('B', 'A', 0, {'trail': 'a', 'distance': 3, 'id': 0})\n\n\nThe first two values of each tuple are the \"from\" and the \"to\" node respectively for each edge in the circuit.\n\nThe third value indicates the key of the edge on the MultiGraph.  These will be 0 unless there are parallel edges.\n\nThe fourth value contains the edge attributes for each edge walked.  These are mostly grabbed from the starting graph,\nwith two exceptions:\n\n- ``augmented`` is added to edges after their first walk (double backing... the thing we want to minimize)\n- ``id`` is generated to aid computation in the case of parallel edges.  This can generally be ignored.\n\nA summary report of the solution should be printed.  Something like this:\n\n.. code ::\n\n    Solution summary stats:\n    distance_walked : 39\n    distance_doublebacked : 6\n    distance_walked_once : 33\n    distance_walked_optional : 0\n    distance_walked_required : 39\n    edges_walked : 9\n    edges_doublebacked : 2\n    edges_walked_once : 7\n    edges_walked_optional : 0\n    edges_walked_required : 9\n\n\nPython\n------\n\nThe postman solvers are modules that can also be imported and run within a Python environment.  This might interest you\nif solving the CPP/RPP is just one step in your problem, you'd like to poke and prod at the output, or you'd like to tweak\nthe visualization or optimization parameters beyond what's provided from the CLI.\n\nThe snippet below should produce exactly the same output as printed above in `CLI`_.\n\n.. code:: python\n\n   from postman_problems.solver import cpp\n   from postman_problems.stats import calculate_postman_solution_stats\n\n   # find CPP solution\n   circuit, graph = cpp(edgelist_filename='postman_problems/examples/seven_bridges/edgelist_seven_bridges.csv', start_node='D')\n\n   # print solution route\n   for e in circuit:\n       print(e)\n\n   # print solution summary stats\n   for k, v in calculate_postman_solution_stats(circuit).items():\n       print(k, v)\n\n\nExamples\n========\n\nThree examples are included in ``postman_problems`` which demonstrate end-to-end usage: raw edgelist & nodelist =>\noptimization and visualization.\n\nExamples are added as entry points and pre-configured arguments, so they can be executed with the single commands below.\n\nNote, the visualization step will write a GIF and a series of PNGs to your filesystem.  The paths are locked into\n*postman_problems/examples/[example_name]/output/*.\n\nAn expected exception will be thrown if you don't have the visualization dependencies.  But no worries,\nthe output is prepackaged into ``/examples`` and images are embedded below.\n\nEach example will produce the following file types:\n\n- ``cpp_graph``: representation of ``cpp_graph.svg`` in the `DOT`_ graph description language.  This is provided mostly\n  for reference, or for tweaking.\n- ``cpp_graph.svg``: static image with edge attributes annotating the walk sequence.\n- ``cpp_graph.gif``: animation highlighting each edge in the Euler circuit (solution route) as it's walked.\n- ``png/img*.png``: PNGs generated for each frame of the GIF (omitted from package, but will hit your filesystem when\n  you run the examples).\n\n\nCPP: Seven Bridges of Konigsberg\n--------------------------------\n\nThe Seven Bridges of Konigsberg is rather simple network with just 4 nodes and 7 edges.  Although small, it does contain\n2 parallel edges which introduce some complexity to the CPP computation.\n\nThis was the graph with which Leonhard Euler famously postulated in 1736 that there exists a path which visits each edge\nexactly once if all nodes have even degree. Although this wasn't proven until the 1870s by Carl Hierholzer, Euler was\nright and this property is a key part of solving the Postman Problems.\n\nThis contrived example has been bundled and parameterized into a script that can be run with:\n\n.. code::\n\n   chinese_postman_seven_bridges\n\n\nThe example can also be run using the verbose method below which allows you to parameterize more pieces.\nMany of the options provided below are defaults and can be excluded in practice. They are included here simply to convey\nwhat the possibilities are:\n\n.. code::\n\n    chinese_postman --edgelist postman_problems/examples/seven_bridges/edgelist_seven_bridges.csv \\\n    --viz \\\n    --viz_filename 'postman_problems/examples/seven_bridges/output/cpp_graph.svg' \\\n    --viz_engine 'dot' \\\n    --animation \\\n    --animation_filename 'postman_problems/examples/seven_bridges/output/cpp_graph.gif' \\\n    --animation_images_dir 'postman_problems/examples/seven_bridges/output/img' \\\n    --animation_engine 'dot' \\\n    --animation_format 'png' \\\n    --fps 2\n\n\n``base_cpp_graph.svg``: This is the starting graph.  Edges are annotated by distance.\n\n.. image:: ./postman_problems/examples/seven_bridges/output/base_cpp_graph.svg\n\n\n``cpp_graph.svg``: Edges are annotated with the order in which they are walked, starting at 0.  Edges walked more than\nonce are annotated by a sequence of numbers (walk order) and **bolded**.\n\n.. image:: ./postman_problems/examples/seven_bridges/output/cpp_graph.svg\n\n\n``cpp_graph.gif``: The nodes and edges in red indicate the current direction.\n\n.. image:: ./postman_problems/examples/seven_bridges/output/cpp_graph.gif\n\n\n``cpp_graph``: dot representation of the graph is also provided.  This is mostly for reference, but in rare cases you may\nwant to tweak graphviz parameters directly here.\n\n.. code ::\n\n    graph {\n\tgraph [forcelabels=true \"strict\"=false]\n\tC [label=C]\n\tD [label=D]\n\tA [label=A]\n\tB [label=B]\n\t\tC -- D [label=9 decorate=true distance=3 id=6 penwidth=1 trail=g]\n\t\tC -- A [label=\"6, 8\" augmented=True decorate=true distance=2 id=2 penwidth=4 trail=c]\n\t\tC -- A [label=7 decorate=true distance=10 id=3 penwidth=1 trail=d]\n\t\tD -- A [label=\"0, 3\" augmented=True decorate=true distance=1 id=4 penwidth=4 trail=e]\n\t\tD -- B [label=4 decorate=true distance=9 id=5 penwidth=1 trail=f]\n\t\tA -- B [label=\"2, 5\" augmented=True decorate=true distance=3 id=0 penwidth=4 trail=a]\n\t\tA -- B [label=1 decorate=true distance=5 id=1 penwidth=1 trail=b]\n    }\n\n\n\nRPP: Star\n---------\n\nThis is a simple example that demonstrates the power of the RPP vs CPP.\n\nRun with:\n\n.. code::\n\n    rural_postman_star\n\n\n``base_rpp_graph.svg``: Required edges are solid. Optional edges are dotted.  Simply showing the edge distances here.\n\n.. image:: ./postman_problems/examples/star/output/base_rpp_graph.svg\n\n``cpp_graph_req.svg``: If we solve this with the CPP and only only consider the required edges, we get the pretty inefficient solution below\ndoubling back on every single edge.\n\n.. image:: ./postman_problems/examples/star/output/cpp_graph_req.svg\n\n``cpp_graph_opt.svg``: If we recognize the optional edges, and apply the the CPP again (where the optional edges are treated\nas required edges), we get a slightly better solution:\n\n.. image:: ./postman_problems/examples/star/output/cpp_graph_opt.svg\n\n``rpp_graph.svg``: When we recognize the optional edges as truly optional and employ the RPP, we get the optimal solution\nwhere we walk all required edges exactly once and only use a subset of optional edges:\n\n.. image:: ./postman_problems/examples/star/output/rpp_graph.svg\n\n``rpp_graph.gif``: Same information as above, but in an animation... because flashy moving pictures are fun.\n\n.. image:: https://gist.githubusercontent.com/brooksandrew/d24560e674fccd1ab78f9d2588769e86/raw/4e477121ea698431ce294c6e1b17ad7e415eb396/rpp_star_example_for_postman_problems.gif\n\n\n\nRPP: Sleeping Giant\n-------------------\n\nThis example is near and dear to my heart and the motivation for this project in the first place.\n\n`Sleeping Giant`_ is a state park near my hometown in Hamden CT with a little challenge called the `Giant Master Program`_.\nThose who hike every trail (see `trail map`_) are awarded the honor of Giantmaster Marathoner and earn themselves a\nspot on the `Giantmaster roster`_ and the glory of a red highlight on their name.\n\nThat's all I'll say here.  I wrote more about the personal motivation and Sleeping Giant specific data/problem in a\n`DataCamp tutorial`_ which also helped motivate this project.\n\nRun this example with:\n\n.. code::\n\n   rural_postman_sleeping_giant\n\n\n``postman_problems/examples/sleeping_giant/rpp_graph.svg``:\n\nThe optional edges are marked with a dotted line.  You'll notice that not all of them are utilized (no edge label\nannotating their order in the route).\n\n.. image:: ./postman_problems/examples/sleeping_giant/output/rpp_graph.svg\n\n``postman_problems/examples/sleeping_giant/rpp_graph.gif`` (omitted from package due to size):  Can be viewed\n`here <https://gist.github.com/brooksandrew/64bacaff6d3004e3601ec14c41382fc3>`__.\n\nHere are the solution summary stats.\n\n.. code ::\n\n    RPP Solution summary stats:\n\n    Solution summary stats:\n    distance_walked : 32.119999999999976\n    distance_doublebacked : 6.11\n    distance_walked_once : 26.009999999999977\n    distance_walked_optional : 0.68\n    distance_walked_required : 31.439999999999976\n    edges_walked : 151\n    edges_doublebacked : 30\n    edges_walked_once : 121\n    edges_walked_optional : 2\n    edges_walked_required : 149\n\nA CPP example is also provided with entry point ``chinese_postman_sleeping_giant``.  The solution is very similar,\nso it is omitted here.\n\nFor a base of comparison on RPP vs CPP, selected stats are printed below for the CPP.  the RPP shortens the CPP solution\nroute by about 1 mile.\n\n.. code ::\n\n    CPP Solution summary stats:\n\n    distance_walked : 33.24999999999998\n    distance_doublebacked : 7.240000000000001\n    distance_walked_once : 26.009999999999977\n    edges_walked : 155\n    edges_doublebacked : 34\n    edges_walked_once : 121\n\n\nDevelopers\n==========\n\nIf you'd like to fork or contribute directly to this project (PRs welcome), or simply want run the tests, here's how:\n\n0. Clone/Fork repo\n\n1. Full install with test and viz dependencies.\n\n   .. code::\n\n       pip install .[test,viz]\n\n   Or do an editable install from the beginning.  This is my typical approach when developing.\n\n   .. code::\n\n       pip install -e .[test,viz]\n\n2. Run tests\n\n   .. code::\n\n       python -m pytest\n       pytest --cov\n\n   Some tests take quite a while to run.  Namely the examples that write visualizations to the filesystem for large networks.\n\n   As I have limited patience while developing, but am too cautious to drop them completely, I've kept and marked them with the ``@slow`` and ``@long`` decorators.  ``conftest.py`` is configured to exclude them by default with a simple run of ``pytest`` or ``python -m pytest``, but the full test suite can be run by:\n\n   .. code::\n\n       python -m pytest --runslow\n       pytest --cov --runslow\n\n\nRelease Notes\n=============\n\nCheckout the release notes in Gitub `here <https://github.com/brooksandrew/postman_problems/releases>`__.\n\nIf I'm doing a good job of keeping PyPI updated, each release should also be available\n`here <https://pypi.org/project/postman_problems/#history>`__.\n\n\nLicense\n=======\n\nReleased under the MIT License (see `LICENSE.txt`_).\n\nCopyright (C) 2017 Andrew Brooks.\n\n\n.. _`Postman Problems`: https://en.wikipedia.org/wiki/Route_inspection_problem\n.. _`Seven Bridges of Konigsberg`: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg\n.. _`Graphviz python package`: https://pypi.python.org/pypi/graphviz\n.. _`Graphviz Download page`: http://www.graphviz.org/Download..php\n.. _`Graphviz`: http://www.graphviz.org/\n.. _`Tests on TravisCI`: https://github.com/brooksandrew/postman_problems/blob/master/.travis.yml\n.. _`Sleeping Giant`: http://www.sgpa.org/\n.. _`Giant Master Program`: http://www.sgpa.org/hikes/masters.html\n.. _`trail map`: http://www.ct.gov/deep/lib/deep/stateparks/maps/sleepgiant.pdf\n.. _`Giantmaster roster`: http://www.sgpa.org/hikes/master-list.htm\n.. _`Datacamp tutorial`: https://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial\n.. _`DOT`: https://en.wikipedia.org/wiki/DOT_(graph_description_language)\n.. _`LICENSE.txt`: https://github.com/brooksandrew/postman_problems/blob/master/LICENSE.txt\n",
        "description_content_type": "",
        "docs_url": null,
        "download_url": "https://github.com/brooksandrew/postman_problems/archive/v0.3.tar.gz",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/brooksandrew/postman_problems",
        "keywords": "chinese postman problem networkx optimization network graph arc routing",
        "license": "MIT License",
        "maintainer": "",
        "maintainer_email": "",
        "name": "postman_problems",
        "package_url": "https://pypi.org/project/postman_problems/",
        "platform": "",
        "project_url": "https://pypi.org/project/postman_problems/",
        "project_urls": {
            "Download": "https://github.com/brooksandrew/postman_problems/archive/v0.3.tar.gz",
            "Homepage": "https://github.com/brooksandrew/postman_problems"
        },
        "release_url": "https://pypi.org/project/postman_problems/0.3/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Solutions to Postman graph optimization problems: Chinese and Rural Postman problems",
        "version": "0.3"
    },
    "last_serial": 3858965,
    "releases": {
        "0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "ba3933f2fcc3f8d372cf70f7f08b62e9",
                    "sha256": "13adc2bdb73567caaf3b503dfda0854800ffa21a2091ad2fca51be78bf60b590"
                },
                "downloads": -1,
                "filename": "postman_problems-0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "ba3933f2fcc3f8d372cf70f7f08b62e9",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 25711,
                "upload_time": "2017-09-18T03:52:51",
                "url": "https://files.pythonhosted.org/packages/47/71/818f9969ed9e1cc69b28adf9906a896f9d9bacb9b607ed1ae837b75607b5/postman_problems-0.1.tar.gz"
            }
        ],
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a97c186b8f1cf4a67b3479bfbdd75004",
                    "sha256": "d53c78bff5487770bf479c5fd00d37c0e8db6f843559a5e26f223f92b3c43fe7"
                },
                "downloads": -1,
                "filename": "postman_problems-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "a97c186b8f1cf4a67b3479bfbdd75004",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 25685,
                "upload_time": "2017-09-24T04:12:03",
                "url": "https://files.pythonhosted.org/packages/17/49/83e6b592d10e18386ea3fd83dbb5c873238dfa50740680cfa33a76b992fb/postman_problems-0.1.1.tar.gz"
            }
        ],
        "0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "066c27b9b61fde0a0ecb764210618b01",
                    "sha256": "35a1b3b712ecccc495afc2262879b47343821f9025d0ad325862ce5d7a7faec8"
                },
                "downloads": -1,
                "filename": "postman_problems-0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "066c27b9b61fde0a0ecb764210618b01",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 33793,
                "upload_time": "2017-10-05T05:19:11",
                "url": "https://files.pythonhosted.org/packages/5d/26/76dd3332b945e6934b7dfbfd1edc861f5b2081cd3c5b6b95b33e9b274aa9/postman_problems-0.2.tar.gz"
            }
        ],
        "0.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "2eb0cfa8fb65ef4df6a7a65412e99b4f",
                    "sha256": "87de7c4674e88129bb03a8e1826c46bcd858393ca675f8de8f6921f2893afa6a"
                },
                "downloads": -1,
                "filename": "postman_problems-0.3.tar.gz",
                "has_sig": false,
                "md5_digest": "2eb0cfa8fb65ef4df6a7a65412e99b4f",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 34393,
                "upload_time": "2018-05-13T18:35:00",
                "url": "https://files.pythonhosted.org/packages/e7/4e/f05d557c8818cd52f566c369cbede2cd8c7de05650c20589e58be8b4920f/postman_problems-0.3.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "2eb0cfa8fb65ef4df6a7a65412e99b4f",
                "sha256": "87de7c4674e88129bb03a8e1826c46bcd858393ca675f8de8f6921f2893afa6a"
            },
            "downloads": -1,
            "filename": "postman_problems-0.3.tar.gz",
            "has_sig": false,
            "md5_digest": "2eb0cfa8fb65ef4df6a7a65412e99b4f",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 34393,
            "upload_time": "2018-05-13T18:35:00",
            "url": "https://files.pythonhosted.org/packages/e7/4e/f05d557c8818cd52f566c369cbede2cd8c7de05650c20589e58be8b4920f/postman_problems-0.3.tar.gz"
        }
    ]
}