{
    "info": {
        "author": "D. S. Rahul",
        "author_email": "dsrahul@outlook.com",
        "bugtrack_url": null,
        "classifiers": [],
        "description": "========================\r\n Christofides Algorithm\r\n========================\r\n\r\nThis package(Christofides) provides a way to implement Christofides algorithm\r\nfor solving Travelling Saleman Problem(TSP) to obtain an approximate solution\r\non an undirected graph(Distance Matrix) provided as an upper Triangular matrix.\r\nThe Distance from a node on to itself is assumed 0.\r\n\r\nUsage\r\n======\r\n\r\nUse the compute() function which takes as input a distance_matrix and returns a Christofides solution as follows::\r\n\r\n\tfrom pyChristofides import christofides\r\n\tTSP = christofides.compute(distance_matrix)\r\n\t\r\nThe Distance Matrix is an upper Triangular matrix with distance from a node on to itself 0, since Christofides algorithm \r\ncould only be applied for undirected graphs. Also the distance between a node on to itself is practically 0.\r\nExample for distance_matrix is as follows,\r\ndistance_matrix = ::\r\n\r\n\t[[0,45,65,15],\r\n\t [0,0,56,12],\r\n\t [0,0,0,89],\r\n\t [0,0,0,0]] \r\n\t \r\nThe above distance_matrix should be provided as an input to christofides.compute(), when we want to calculate TSP for\r\ndistance = ::\r\n\t\r\n\t[[0,45,65,15],\r\n\t[45,0,56,12],\r\n\t[65,56,0,89],\r\n\t[15,12,89,0]]\r\n\t\r\nchristofides.compute(distance_matrix) returns a Dictionary with following Keys:\r\n\tChristofides_Solution,  \r\n\tTravel_Cost,\r\n\tMST, \r\n\tOdd_Vertices\r\n\tIndexes, \r\n\tMultigraph, \r\n\tEuler_Tour\r\n\t\t\r\n* Christofides_Solution: A list consisting of approximate tour for TSP.\r\n\tUse: TSP['Chistofides_Solution']\r\n* Travel_Cost: The cost of TSP tour generated.\r\n\tUse: TSP['Travel_Cost']\r\n* MST: The minimum spanning tree generated during the Christofides algorithm.\r\n\tUse: TSP['MST']\r\n* Odd_Vertices: A list of odd vertices of minimum spanning tree.\r\n\tUse: TSP['Odd_Vertices']\r\n* Indexes: List of edges from minimum cost perfect matching of odd vertices.\r\n\tUse: TSP['Indexes']\r\n* Multigraph: Edges of multigraph formed after Indexing.\r\n\tUse: TSP['Multigraph']\r\n* Euler_Tour: The Euler Tour of the Multigraph.\r\n\tUse: TSP['Euler_Tour']\r\n\t\t\r\nSupport Functions in christofides\r\n=================================\r\n\r\n- _csr_gen_triples(csr_matrix)\r\n- _odd_vertices_of_MST(distance_matrix, number_of_nodes)\r\n- min_Munkres(distance_matrix, bipartitie_graphs)\r\n- Munkres_cost(indexes, bipartite_graph)\r\n- bipartite_Graph(distance_matrix, bipartite_set, odd_vertices)\r\n- create_Multigraph(distance_matrix, MST, indexes, odd_vertices)\r\n- Euler_Tour(multigraph)\r\n- shortcut_Euler_Tour(tour)\r\n- cost(christofides_tour, distance_matrix)\r\n\t\r\nInstall\r\n=======\r\n\r\nDownload the Package and use::\r\n\tpython setup.py install\r\n\t\r\nor::\r\n\tpip install python-christofides\r\n\t\r\nAdditional Packages\r\n===================\r\n\r\nscipy, numpy, networkx, munkres",
        "description_content_type": null,
        "docs_url": null,
        "download_url": "UNKNOWN",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "http://pypi.python.org/pypi/python-christofides/",
        "keywords": "",
        "license": "LICENSE.txt",
        "maintainer": "",
        "maintainer_email": "",
        "name": "python-christofides",
        "package_url": "https://pypi.org/project/python-christofides/",
        "platform": "UNKNOWN",
        "project_url": "https://pypi.org/project/python-christofides/",
        "project_urls": {
            "Download": "UNKNOWN",
            "Homepage": "http://pypi.python.org/pypi/python-christofides/"
        },
        "release_url": "https://pypi.org/project/python-christofides/0.1.2/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "Implementation of Christofides Algorithm for TSP in python.",
        "version": "0.1.2"
    },
    "last_serial": 2806441,
    "releases": {
        "0.1.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "5cab6b8ea7f81b052f37188501f8e236",
                    "sha256": "a5062c9e2373d7c9a4b400f63480ef156af8f78ba8f9b328534cf65bb93ba70e"
                },
                "downloads": -1,
                "filename": "python-christofides-0.1.0.tar.gz",
                "has_sig": false,
                "md5_digest": "5cab6b8ea7f81b052f37188501f8e236",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5633,
                "upload_time": "2016-01-08T05:11:50",
                "url": "https://files.pythonhosted.org/packages/2c/89/6fa9de713dfa6c1bbece5fa1b06ceeb8b9387b1709c5e4ea96c0379b4422/python-christofides-0.1.0.tar.gz"
            }
        ],
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "c9aaa7f9620a35deee4c50d28b0c3d12",
                    "sha256": "3c292fafcc75744d95ff3f4b169873aa73ae9053bd7888a66163880f86f37366"
                },
                "downloads": -1,
                "filename": "python-christofides-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "c9aaa7f9620a35deee4c50d28b0c3d12",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5634,
                "upload_time": "2016-01-08T05:12:50",
                "url": "https://files.pythonhosted.org/packages/d5/9b/e0b7a7e89dcb5b42bc4667c0e3ad46d0cdbdc58c14bd0f076b39cab620d2/python-christofides-0.1.1.tar.gz"
            }
        ],
        "0.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "c5ef18c5439dab68629a1f1656b2b007",
                    "sha256": "8998232479023bac850ff3d6fdc1b929d5a4c791cdcf6f7f2479bdc9649cb05f"
                },
                "downloads": -1,
                "filename": "python-christofides-0.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "c5ef18c5439dab68629a1f1656b2b007",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5914,
                "upload_time": "2017-04-16T04:06:59",
                "url": "https://files.pythonhosted.org/packages/bb/08/2dc1c0dd3130b1cf034d50047aa287d740b2e530fc5d8c86db884374e069/python-christofides-0.1.2.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "c5ef18c5439dab68629a1f1656b2b007",
                "sha256": "8998232479023bac850ff3d6fdc1b929d5a4c791cdcf6f7f2479bdc9649cb05f"
            },
            "downloads": -1,
            "filename": "python-christofides-0.1.2.tar.gz",
            "has_sig": false,
            "md5_digest": "c5ef18c5439dab68629a1f1656b2b007",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 5914,
            "upload_time": "2017-04-16T04:06:59",
            "url": "https://files.pythonhosted.org/packages/bb/08/2dc1c0dd3130b1cf034d50047aa287d740b2e530fc5d8c86db884374e069/python-christofides-0.1.2.tar.gz"
        }
    ]
}