{ "info": { "author": "Duvvuri Surya Rahul", "author_email": "dsrahul@outlook.com", "bugtrack_url": null, "classifiers": [], "description": "========================\n Christofides Algorithm\n========================\n\nThis package(Christofides) provides a way to implement Christofides algorithm\nfor solving Travelling Saleman Problem(TSP) to obtain an approximate solution\non an undirected graph(Distance Matrix) provided as an upper Triangular matrix.\nThe Distance from a node on to itself is assumed 0.\n\nUsage\n======\n\nUse the compute() function which takes as input a distance_matrix and returns a Christofides solution as follows::\n\n\tfrom Christofides import christofides\n\tTSP = christofides.compute(distance_matrix)\n\nor::\n\n\timport Christofides\n\tTSP = Christofides.christofides.compute(distance_matrix)\n\t\nThe Distance Matrix is an upper Triangular matrix with distance from a node on to itself 0, since Christofides algorithm \ncould only be applied for undirected graphs. Also the distance between a node on to itself is practically 0.\nExample for distance_matrix is as follows,\ndistance_matrix = ::\n\n\t[[0,45,65,15],\n\t [0,0,56,12],\n\t [0,0,0,89],\n\t [0,0,0,0]] \n\t \nThe above distance_matrix should be provided as an input to christofides.compute(), when we want to calculate TSP for\ndistance = ::\n\t\n\t[[0,45,65,15],\n\t[45,0,56,12],\n\t[65,56,0,89],\n\t[15,12,89,0]]\n\t\nchristofides.compute(distance_matrix) returns a Dictionary with following Keys:\n\tChristofides_Solution, \n\tTravel_Cost,\n\tMST, \n\tOdd_Vertices\n\tIndexes, \n\tMultigraph, \n\tEuler_Tour\n\t\t\n* Christofides_Solution: A list consisting of approximate tour for TSP.\n\tUse: TSP['Chistofides_Solution']\n* Travel_Cost: The cost of TSP tour generated.\n\tUse: TSP['Travel_Cost']\n* MST: The minimum spanning tree generated during the Christofides algorithm.\n\tUse: TSP['MST']\n* Odd_Vertices: A list of odd vertices of minimum spanning tree.\n\tUse: TSP['Odd_Vertices']\n* Indexes: List of edges from minimum cost perfect matching of odd vertices.\n\tUse: TSP['Indexes']\n* Multigraph: Edges of multigraph formed after Indexing.\n\tUse: TSP['Multigraph']\n* Euler_Tour: The Euler Tour of the Multigraph.\n\tUse: TSP['Euler_Tour']\n\t\t\nSupport Functions in christofides\n=================================\n\n- _csr_gen_triples(csr_matrix)\n- _odd_vertices_of_MST(distance_matrix, number_of_nodes)\n- min_Munkres(distance_matrix, bipartitie_graphs)\n- Munkres_cost(indexes, bipartite_graph)\n- bipartite_Graph(distance_matrix, bipartite_set, odd_vertices)\n- create_Multigraph(distance_matrix, MST, indexes, odd_vertices)\n- Euler_Tour(multigraph)\n- shortcut_Euler_Tour(tour)\n- cost(christofides_tour, distance_matrix)\n\t\nInstall\n=======\n\npython setup.py install\n\t\nAdditional Packages\n===================\n\nscipy, numpy, networkx, munkres", "description_content_type": null, "docs_url": "https://pythonhosted.org/Christofides/", "download_url": "UNKNOWN", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "http://pypi.python.org/pypi/Christofides/", "keywords": null, "license": "LICENSE.txt", "maintainer": null, "maintainer_email": null, "name": "Christofides", "package_url": "https://pypi.org/project/Christofides/", "platform": "UNKNOWN", "project_url": "https://pypi.org/project/Christofides/", "project_urls": { "Download": "UNKNOWN", "Homepage": "http://pypi.python.org/pypi/Christofides/" }, "release_url": "https://pypi.org/project/Christofides/1.0.1/", "requires_dist": null, "requires_python": null, "summary": "Christofides Algorithm for TSP.", "version": "1.0.1", "yanked": false, "yanked_reason": null }, "last_serial": 6013511, "releases": { "0.1.0": [], "0.2.0": [], "1.0.0": [ { "comment_text": "", "digests": { "md5": "259f92cfb6c098219ad3ab8dd982ad66", "sha256": "2c0f3287e3f7e6eb31525b52c2af74a5a56c4b926067d009b0be6af519d313a2" }, "downloads": -1, "filename": "Christofides-1.0.0.tar.gz", "has_sig": false, "md5_digest": "259f92cfb6c098219ad3ab8dd982ad66", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5609, "upload_time": "2016-01-08T05:36:13", "upload_time_iso_8601": "2016-01-08T05:36:13.672010Z", "url": "https://files.pythonhosted.org/packages/f5/91/3cc3881ca08ad06d002b513650ed5bccafbc1c2b545601f98e16e2a57502/Christofides-1.0.0.tar.gz", "yanked": false, "yanked_reason": null } ], "1.0.1": [ { "comment_text": "", "digests": { "md5": "6d1b367624f576474d80b5f567db4bf4", "sha256": "411696f665cdffec63e709f3f4cd4338fd2014ffd5420f4ba1bfb5aca94dafd6" }, "downloads": -1, "filename": "Christofides-1.0.1.tar.gz", "has_sig": false, "md5_digest": "6d1b367624f576474d80b5f567db4bf4", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5850, "upload_time": "2017-04-16T03:46:10", "upload_time_iso_8601": "2017-04-16T03:46:10.311627Z", "url": "https://files.pythonhosted.org/packages/0f/6e/93158e316b513d06515442cebdf096b7ad13e6b4204f0cf0950f8279f3ff/Christofides-1.0.1.tar.gz", "yanked": false, "yanked_reason": null } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "6d1b367624f576474d80b5f567db4bf4", "sha256": "411696f665cdffec63e709f3f4cd4338fd2014ffd5420f4ba1bfb5aca94dafd6" }, "downloads": -1, "filename": "Christofides-1.0.1.tar.gz", "has_sig": false, "md5_digest": "6d1b367624f576474d80b5f567db4bf4", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5850, "upload_time": "2017-04-16T03:46:10", "upload_time_iso_8601": "2017-04-16T03:46:10.311627Z", "url": "https://files.pythonhosted.org/packages/0f/6e/93158e316b513d06515442cebdf096b7ad13e6b4204f0cf0950f8279f3ff/Christofides-1.0.1.tar.gz", "yanked": false, "yanked_reason": null } ], "vulnerabilities": [] }