{
    "info": {
        "author": "James Langbein",
        "author_email": "james.langbein@protonmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 4 - Beta",
            "License :: OSI Approved :: MIT License",
            "Programming Language :: Python",
            "Programming Language :: Python :: 3",
            "Programming Language :: Python :: 3.6"
        ],
        "description": "# Open TSP\n\n---\nThis library is designed to make it as easy as possible to generate and test TSP instances against hypotheses, as well as solving them with brute force for comparison.  \nThis is my first major project, having learnt Python over the last six months, so if you have style suggestions I'd love to hear them.\n\nThe goal is to make this an easy library to work with, please feel free to email me with any functionality you feel would help.\n\nIf you want to contribute implementations of algorithms for solving then I'd love to hear from you! Currently I have implemented *brute-force* and *convex-hull*. However, there is a long list of algorithms I'd love to include in the library, such as *christofides* and *branch and bound*. I don't have the knowledge to implement these myself though.  \nThis is why I'm making *opentsp* an open-source library, in the hopes that others who find it useful will add to it. If you have suggestions or code, please create a pull request on the Github page, which I'll put the link up for soon.\n\n## Getting started\n\n---\nTo install *opentsp* in your local environment with pip:\n```\npip install opentsp\n```\n\nThen, at the top of your module:\n```\nfrom opentsp.objects import Generator\n```\n\n\n\n### Creating a TSP Instance\n\nTo create a random TSP instance with eight nodes, using your console:\n```\n>>> from opentsp.objects import Generator\n>>> gen = Generator()\n>>> instance = gen.new_instance(8)\n```\n\nIf you want to get the same values as in these examples, then use the below input:\n```\n>>> instance = gen.new_instance(8, source='seed', seed=1234) \n```\n\nTo see what this creates:\n```\n>>> instance\nSeed: 1234\nNode count: 8\nEdge count: 56\nNodes: {1: (47, 83), 2: (38, 53), 3: (76, 24), 4: (15, 49), 5: (23, 26), 6: (30, 43), 7: (30, 26), 8: (58, 92)}\nEdges: {1: ((47, 83), (38, 53), None, False, 0, good, 0), 2: ((47, 83), (76, 24), None, False, 0, good, 0), 3:...}\nDistance matrix: None\nSolve time: None\nResults: None\n```\n\nIt has a seed, which is used to generate the random nodes. The number of nodes and edges are not object attributes, they come from two class methods, I've found it handy to have that information as part of the printed representation.  \nThen it shows the actual nodes and edges, the distance matrix (if generated), the solve time (if brute-forced), and the results.\nResults is dictionary of algorithms and their results as a path of nodes.\nSomething to note here is that edge lengths are only calculated when first needed, and only calculated once. So you can see a 'None' value in the edges, because the lengths haven't been calculated yet. I'll address the Edge class attributes in more detail later.\n\n\nThe instance has a bunch of methods for accessing different properties of a TSP problem, such as: \n\n- the number of nodes\n```\n>>> instance.num_nodes\n8\n```\n\n- number of edges\n```\n>>> instance.num_edges\n56\n```\n\n- the *x* and *y* values, for instance:\n```\n>>> instance.x_values\n[47, 38, 76, 15, 23, 30, 30, 58]\n```\n\n- the edge lengths:\n```\n>>> instance.edge_lengths_as_list\n[7.0, 7.0, 12.806248474865697, 12.806248474865697, 14.212670...]\n```\n\n- the *n* shortest edges:\n```\n>>> instance.n_shortest_edges_of_instance(1)\n((23, 26), (30, 26), 7.0, False, 0, good, 0)\n```\n\n- etc\n\nThe instance can also be solved, currently the default solve method is brute force.\nYou can then print the instance's `results` dictionary to look at the results.\n```\n>>> instance.solve()\n'Brute force completed.'\n>>> instance.results\n{'convex_hull': [(15, 49), (23, 26), (76, 24), (58, 92), (47, 83), (15, 49)], 'brute_force': ((58, 92), (76, 24), (30, 26), (23, 26), (15, 49), (30, 43), (38, 53), (47, 83), (58, 92))}\n```\n\nInstances can be generated from a variety of sources, currently these are:  \n* **Random**  \n   A random eight digit seed is generated for the instance, and nodes with random values are generated from this seed.\n* **Seed**  \n   Pass in an integer to use as a seed. This is primarily helpful when you want to reproduce a series of random instances. When passing in your own seed make sure to set `source=seed`, otherwise the seed you pass will be ignored.  \n   E.g. `inst = generate.Generator.new_instance(5, source='seed', seed=123)`\n* **CSV**  \n   Currently this takes a CSV with two columns of values for the *x* and *y* coordinates. The top row must have the titles 'x' and 'y'.\n\nAny instance can also be viewed via *matplotlib*, try the two commands below:\n```\n>>> instance.view(nodes=True, edges=True)\n>>> instance.view(result='brute_force')  # must have solved the problem already\n```\n(The string passed in the result argument above should match a key in the `instance.results` dictionary of the instance. If the problem was solved without need for brute force, then the 'brute_force' key won't be present. However, the 'optimal_solution' key is always present if a solution has been found.)\n\n---\n### Example Hypothesis-test Algorithm\n\nHere is an example algorithm, making use of open-tsp's features to generate and test many instances against a hypothesis:\n```\nimport open-tsp as ot\n\n# hypothesis: the shortest edge is always used in the optimal solution\n\ndef hyp_test():\n\n    loop = True\n    loops = 0\n    start = time.time()\n\n    while loop is True and loops < 1000000:\n        loopstr = f\"Failed on loop: {loops}\"\n        p = ot.classes.Generator.new_instance(6, solve=True)\n        shortest_edge = p.n_shortest_edges_of_instance(1)\n        edge_path = p.solution_as_edges\n\n        if shortest_edge in edge_path:\n            loops += 1\n\n        else:\n            loop = False\n            p.view(plot_se=True)\n\n    end = time.time()\n    total_time = end - start\n    print(loopstr)\n    print(\"Took {0}'s to run.\".format(total_time))\n    print(\"Finished\")\n```\nThis function will generate up to a million instances, testing each one to see if the shortest edge is in the solution or not using the `if` test on line 13: `if shortest_edge in edge_path:`.  \nWhen the test fails, it shows the instance that failed with *matplotlib* and highlights the shortest edge `p.view(plot_se=True)`.  \nAs you can see, in 19 lines of code it's possible to test a hypothesis, with only a few lines actually concerned with generating the tsp instance and getting it's properties.  \nAlso, as in the example above, you can solve the instance as part of generating it with `solve=True`. Keep in mind that is most likely going to be a brute force solution, so trying to do this with a 20 node problem will take a fairly long while unless you are running your code on a very powerful supercomputer.\n\n---\n### Using Your Own Algorithms\n\nTo use your own algorithm, define a function with an appropriate name, and make `instance` an argument.  \n```\ndef brute_force(instance):\n```\nWrite your algorithm within the function.\n\nThen, within the function, you can pass in the instance being worked with and use any of it's attributes or properties.  \n\nFor instance, in my brute force algorithm:\n```\n# store the last node to a variable, this will be used to complete the loops\nlast_elem = instance.nodes[len(instance.nodes)]\n```\n\nTo check out the full brute force algorithm, look at the `Solvers` class in the Github repo.\n\n### Overview of Classes\n\n#### Node\n\nBasic point-type class for defining nodes.\n\nI refer to the points in a tsp as 'nodes' rather than 'cities'. Cities is too specific for me, it could just as easily be towns, or cats, really. I prefer the more abstract 'nodes'.\n\nNecessary arguments: *x, y*\n\n#### Edge\n\nDefines the edges as having two nodes and a length. The two nodes inherently bound the length.\n\nNecessary arguments: *node_one, node_two*\n\n#### Path\n\nA path is a series of nodes, and has methods to find the length of the path, etc.\n\nNecessary arguments: *a list of node objects*\n\n#### Instance\n\nEach instance is essentially a container for the nodes, edges and algorithm results.\n\nNecessary arguments: *none*  \n\nThis class is not really meant to be created directly as that requires a lot of code, especially for generating the edges, and it would defeat the whole purpose of this library if you had to write all of that. So, the `Generator` class is used to create instances through the `new_instance` method, which contains all of that functionality.\n\n#### Generator\n\nContains the main method for creating an instance - `new_instance`.\n\nThe only required argument for `new_instance` is the number of nodes. In this case, the default is to generate random nodes.\n\n#### Solver\n\nContains methods for solving instances.\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": "",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "opentsp",
        "package_url": "https://pypi.org/project/opentsp/",
        "platform": "",
        "project_url": "https://pypi.org/project/opentsp/",
        "project_urls": null,
        "release_url": "https://pypi.org/project/opentsp/1.1.3/",
        "requires_dist": [
            "matplotlib",
            "numpy"
        ],
        "requires_python": "",
        "summary": "Generate TSP instances and test hypotheses on them",
        "version": "1.1.3"
    },
    "last_serial": 4689764,
    "releases": {
        "1.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "cd392b2465d3b0c1d873e4f3c9f3c12c",
                    "sha256": "fb4794a93ed523880f81d64b6a40da45d70a3a55d62d44d62d01f7a5c145ad05"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "cd392b2465d3b0c1d873e4f3c9f3c12c",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 18622,
                "upload_time": "2019-01-10T20:17:37",
                "url": "https://files.pythonhosted.org/packages/d7/3e/564b259ee3c5c69fc09eff3536537fdb07ef0d087829c470515db9cdf62f/opentsp-1.1.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "8d5d5fd44580877a63dc01eaf31e831d",
                    "sha256": "5c0e6fed6f0f0b532e1c7fa7726962da0531438eadd3c60dcbadd8dbc896439e"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "8d5d5fd44580877a63dc01eaf31e831d",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 17579,
                "upload_time": "2019-01-10T20:17:39",
                "url": "https://files.pythonhosted.org/packages/72/93/11362c4f95fac38ca6b1fead25dd16cc050d789d059e6969781154ad231e/opentsp-1.1.1.tar.gz"
            }
        ],
        "1.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "918cf3a0b6f4fc6c85fd31bc4ee75f77",
                    "sha256": "913b5e8336f87f7cac75ad92c9a7b7638aa5ca453f08049073fc9670ed6c4c7f"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.2-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "918cf3a0b6f4fc6c85fd31bc4ee75f77",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 18628,
                "upload_time": "2019-01-10T20:49:26",
                "url": "https://files.pythonhosted.org/packages/c8/6d/e9b311eba707439a8bdaf41bfcf5ba5ea1ae9e706399ab7b63878489bd9e/opentsp-1.1.2-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "8f5d828dba34183bd75d0e63263f1948",
                    "sha256": "dd54a7f8513029f0fc1f3afc859ba826c725f485d57532f00db237c46ef56b33"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "8f5d828dba34183bd75d0e63263f1948",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 17582,
                "upload_time": "2019-01-10T20:49:36",
                "url": "https://files.pythonhosted.org/packages/85/6b/45de6000cbca776d1b287bbf8d9341bf3542b1c8340f973e2d6ddc84e2e1/opentsp-1.1.2.tar.gz"
            }
        ],
        "1.1.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "f86b609033abec025311d3580ace9768",
                    "sha256": "b2febc80491fb9321d23c3069566c7e3aac3fea85f9d86dd920279e3f944174c"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.3-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "f86b609033abec025311d3580ace9768",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 19074,
                "upload_time": "2019-01-12T01:25:56",
                "url": "https://files.pythonhosted.org/packages/a7/41/a4d192745415be02163160bd529f46202b36c102d063e9a857b9ab8ca1b0/opentsp-1.1.3-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "dfec2e14ffce77967aeb23dec4fe5fe3",
                    "sha256": "8e5f1a1efd6f8b50339ce0899a9f44ca3a2fddcdcd7d31a2f31c4a37a92b0c67"
                },
                "downloads": -1,
                "filename": "opentsp-1.1.3.tar.gz",
                "has_sig": false,
                "md5_digest": "dfec2e14ffce77967aeb23dec4fe5fe3",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 18001,
                "upload_time": "2019-01-12T01:25:57",
                "url": "https://files.pythonhosted.org/packages/fd/ca/3938361c6bba7ed7d1a1d439045c0587b0e6a05baf47b293f8d9e975f3a3/opentsp-1.1.3.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "f86b609033abec025311d3580ace9768",
                "sha256": "b2febc80491fb9321d23c3069566c7e3aac3fea85f9d86dd920279e3f944174c"
            },
            "downloads": -1,
            "filename": "opentsp-1.1.3-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "f86b609033abec025311d3580ace9768",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 19074,
            "upload_time": "2019-01-12T01:25:56",
            "url": "https://files.pythonhosted.org/packages/a7/41/a4d192745415be02163160bd529f46202b36c102d063e9a857b9ab8ca1b0/opentsp-1.1.3-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "dfec2e14ffce77967aeb23dec4fe5fe3",
                "sha256": "8e5f1a1efd6f8b50339ce0899a9f44ca3a2fddcdcd7d31a2f31c4a37a92b0c67"
            },
            "downloads": -1,
            "filename": "opentsp-1.1.3.tar.gz",
            "has_sig": false,
            "md5_digest": "dfec2e14ffce77967aeb23dec4fe5fe3",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 18001,
            "upload_time": "2019-01-12T01:25:57",
            "url": "https://files.pythonhosted.org/packages/fd/ca/3938361c6bba7ed7d1a1d439045c0587b0e6a05baf47b293f8d9e975f3a3/opentsp-1.1.3.tar.gz"
        }
    ]
}