{
    "info": {
        "author": "Mitch LeBlanc",
        "author_email": "supermitch@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 3 - Alpha",
            "Environment :: Console",
            "Intended Audience :: Developers",
            "License :: OSI Approved :: MIT License",
            "Natural Language :: English",
            "Operating System :: OS Independent",
            "Programming Language :: Python",
            "Topic :: Utilities"
        ],
        "description": "# Chinese-Postman Solver\n\nI wrote this program to solve the\n[Chinese Postman problem](http://en.wikipedia.org/wiki/Route_inspection_problem).\n\nDescribed as:\n\n> The **Chinese Postman Problem**, or \"route inspection problem\"\n> is to find a shortest closed circuit that visits every edge of a\n> (connected) undirected graph.\n\n## Inspiration\n\nI was inspired to learn about and solve this problem when I thought it would\nbe cool to follow every trail in\n[Pacific Spirit Park](http://en.wikipedia.org/wiki/Pacific_Spirit_Regional_Park)\nin one run.\n\nGiven that the park contains over 73 km of trail, I need to find the optimum\nEularian Path. Otherwise it's going to be a really, really long run!\n\n\n## The Process\n\nThe solution is roughly a three-step process:\n\n1. Determine if the graph has an\n[Eularian Path](http://en.wikipedia.org/wiki/Eulerian_path)\n    (Very easy)\n2. Make the non-Eularian graph Eularian, at the minimum expense\n    (Not so easy)\n3. Find the fudged Eularian path\n    (Pretty easy)\n\n### Solving Minimum Expense\n\nIn order to convert a non- or semi-Eularian graph to an Eularian one,\nyou must eliminate odd nodes (nodes having an odd number of edges.)\n\nTo eliminate an odd node, you need to add another edge to it (essentially\nretracing your steps.) However, this comes as a cost! The goal then is\nto find out which edges to repeat, that eliminate all the odd nodes, with\nthe minimum cost.\n\n1. Find all possible combinations of pairs of odd nodes\n2. Using Dijkstra's Algorithm, find the cost of the minimum path between\nthose pairs\n3. Find which set of paths (depending on how many odd nodes you have)\nthat results in the least total cost\n4. Modify your graph with these new parallel edges\n\nNow you have an Eularian graph with only even nodes, for which an Eularian\nCircuit can be found.\n\n### Solving the Eularian Circuit\n\nSolving the Eularian Circuit (now that we have one) is relatively easy. At\nfirst, I simply walked the edges randomly until I happened to find a route\nthat either dead-ended, or resulted in a circuit. Then I implemented [Fleury's\nAlgorithm](http://en.wikipedia.org/wiki/Eulerian_path#Fleury.27s_algorithm)\nwhich says always choose a non-bridge over a bridge (for obvious\nreasons). Now it takes very few attempts to solve most circuits.\n\nLater I will implement an alternative circuit finding method (Hierholzer's?)\n\n## To run\n\n    python main.py\n\nIf you want to specify which graph to load, simply add the graph name:\n\n    python main.py north\n\nYou can find all the graph names in the `data` folder.\n\nThis program will run in Python 2.7 and Python 3.4, at least.\n\nThere are unit tests included, in the `tests` directory. You can run these by\ntyping\n\n    python tests/run_tests.py\n\nfrom the root project folder.\n",
        "description_content_type": null,
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/supermitch/Chinese-Postman",
        "keywords": "graph network solver postman chinese",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "chinesepostman",
        "package_url": "https://pypi.org/project/chinesepostman/",
        "platform": "",
        "project_url": "https://pypi.org/project/chinesepostman/",
        "project_urls": {
            "Homepage": "https://github.com/supermitch/Chinese-Postman"
        },
        "release_url": "https://pypi.org/project/chinesepostman/0.0.2/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Chinese-Postman network solver",
        "version": "0.0.2"
    },
    "last_serial": 2427823,
    "releases": {
        "0.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "bc36272c9df69c9c9fe4a1de0543c923",
                    "sha256": "25224f3a672654c172175615fafb2c9d7789b765e21652a9217716e2d79e192c"
                },
                "downloads": -1,
                "filename": "chinesepostman-0.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "bc36272c9df69c9c9fe4a1de0543c923",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 391515,
                "upload_time": "2016-10-28T04:40:14",
                "url": "https://files.pythonhosted.org/packages/95/06/22a81d56eff0157bd2907c53d8cc35c8b3cfa9e9fb9f51aa403b03ff10b4/chinesepostman-0.0.1.tar.gz"
            }
        ],
        "0.0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "56893ae745fbfd06328e9ac54a786ff2",
                    "sha256": "38262c247dbdaf5dffc147efd8c2049e2452244042425993a82ea054189e3d46"
                },
                "downloads": -1,
                "filename": "chinesepostman-0.0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "56893ae745fbfd06328e9ac54a786ff2",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 391703,
                "upload_time": "2016-10-28T04:47:48",
                "url": "https://files.pythonhosted.org/packages/28/b6/ef67af4fe231c7449d82239a886d3289bc2774468bb89ca5e81ad0756878/chinesepostman-0.0.2.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "56893ae745fbfd06328e9ac54a786ff2",
                "sha256": "38262c247dbdaf5dffc147efd8c2049e2452244042425993a82ea054189e3d46"
            },
            "downloads": -1,
            "filename": "chinesepostman-0.0.2.tar.gz",
            "has_sig": false,
            "md5_digest": "56893ae745fbfd06328e9ac54a786ff2",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 391703,
            "upload_time": "2016-10-28T04:47:48",
            "url": "https://files.pythonhosted.org/packages/28/b6/ef67af4fe231c7449d82239a886d3289bc2774468bb89ca5e81ad0756878/chinesepostman-0.0.2.tar.gz"
        }
    ]
}