{ "info": { "author": "Brian Clapper", "author_email": "bmc@clapper.org", "bugtrack_url": null, "classifiers": [ "Intended Audience :: Developers", "Intended Audience :: Science/Research", "License :: OSI Approved :: BSD License", "Operating System :: OS Independent", "Programming Language :: Python", "Programming Language :: Python :: 3", "Topic :: Scientific/Engineering :: Mathematics", "Topic :: Software Development :: Libraries :: Python Modules" ], "description": "Introduction\n============\n\nThe Munkres module provides an implementation of the Munkres algorithm\n(also called the Hungarian algorithm or the Kuhn-Munkres algorithm),\nuseful for solving the Assignment Problem.\n\nAssignment Problem\n==================\n\nLet *C* be an *n*\\ x\\ *n* matrix representing the costs of each of *n* workers\nto perform any of *n* jobs. The assignment problem is to assign jobs to\nworkers in a way that minimizes the total cost. Since each worker can perform\nonly one job and each job can be assigned to only one worker the assignments\nrepresent an independent set of the matrix *C*.\n\nOne way to generate the optimal set is to create all permutations of\nthe indexes necessary to traverse the matrix so that no row and column\nare used more than once. For instance, given this matrix (expressed in\nPython)::\n\n matrix = [[5, 9, 1],\n [10, 3, 2],\n [8, 7, 4]]\n\nYou could use this code to generate the traversal indexes::\n\n def permute(a, results):\n if len(a) == 1:\n results.insert(len(results), a)\n\n else:\n for i in range(0, len(a)):\n element = a[i]\n a_copy = [a[j] for j in range(0, len(a)) if j != i]\n subresults = []\n permute(a_copy, subresults)\n for subresult in subresults:\n result = [element] + subresult\n results.insert(len(results), result)\n\n results = []\n permute(range(len(matrix)), results) # [0, 1, 2] for a 3x3 matrix\n\nAfter the call to permute(), the results matrix would look like this::\n\n [[0, 1, 2],\n [0, 2, 1],\n [1, 0, 2],\n [1, 2, 0],\n [2, 0, 1],\n [2, 1, 0]]\n\nYou could then use that index matrix to loop over the original cost matrix\nand calculate the smallest cost of the combinations::\n\n n = len(matrix)\n minval = sys.maxint\n for row in range(n):\n cost = 0\n for col in range(n):\n cost += matrix[row][col]\n minval = min(cost, minval)\n\n print minval\n\nWhile this approach works fine for small matrices, it does not scale. It\nexecutes in O(*n*!) time: Calculating the permutations for an *n*\\ x\\ *n*\nmatrix requires *n*! operations. For a 12x12 matrix, that's 479,001,600\ntraversals. Even if you could manage to perform each traversal in just one\nmillisecond, it would still take more than 133 hours to perform the entire\ntraversal. A 20x20 matrix would take 2,432,902,008,176,640,000 operations. At\nan optimistic millisecond per operation, that's more than 77 million years.\n\nThe Munkres algorithm runs in O(*n*\\ ^3) time, rather than O(*n*!). This\npackage provides an implementation of that algorithm.\n\nThis version is based on\nhttp://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.\n\nThis version was written for Python by Brian Clapper from the (Ada) algorithm\nat the above web site. (The ``Algorithm::Munkres`` Perl version, in CPAN, was\nclearly adapted from the same web site.)\n\nUsage\n=====\n\nConstruct a Munkres object::\n\n from munkres import Munkres\n\n m = Munkres()\n\nThen use it to compute the lowest cost assignment from a cost matrix. Here's\na sample program::\n\n from munkres import Munkres, print_matrix\n\n matrix = [[5, 9, 1],\n [10, 3, 2],\n [8, 7, 4]]\n m = Munkres()\n indexes = m.compute(matrix)\n print_matrix(matrix, msg='Lowest cost through this matrix:')\n total = 0\n for row, column in indexes:\n value = matrix[row][column]\n total += value\n print '(%d, %d) -> %d' % (row, column, value)\n print 'total cost: %d' % total\n\nRunning that program produces::\n\n Lowest cost through this matrix:\n [5, 9, 1]\n [10, 3, 2]\n [8, 7, 4]\n (0, 0) -> 5\n (1, 1) -> 3\n (2, 2) -> 4\n total cost=12\n\nThe instantiated Munkres object can be used multiple times on different\nmatrices.\n\nNon-square Cost Matrices\n========================\n\nThe Munkres algorithm assumes that the cost matrix is square. However, it's\npossible to use a rectangular matrix if you first pad it with 0 values to make\nit square. This module automatically pads rectangular cost matrices to make\nthem square.\n\nNotes:\n\n- The module operates on a *copy* of the caller's matrix, so any padding will\n not be seen by the caller.\n- The cost matrix must be rectangular or square. An irregular matrix will\n *not* work.\n\nCalculating Profit, Rather than Cost\n====================================\n\nThe cost matrix is just that: A cost matrix. The Munkres algorithm finds\nthe combination of elements (one from each row and column) that results in\nthe smallest cost. It's also possible to use the algorithm to maximize\nprofit. To do that, however, you have to convert your profit matrix to a\ncost matrix. The simplest way to do that is to subtract all elements from a\nlarge value. For example::\n\n from munkres import Munkres, print_matrix\n\n matrix = [[5, 9, 1],\n [10, 3, 2],\n [8, 7, 4]]\n cost_matrix = []\n for row in matrix:\n cost_row = []\n for col in row:\n cost_row += [sys.maxint - col]\n cost_matrix += [cost_row]\n\n m = Munkres()\n indexes = m.compute(cost_matrix)\n print_matrix(matrix, msg='Highest profit through this matrix:')\n total = 0\n for row, column in indexes:\n value = matrix[row][column]\n total += value\n print '(%d, %d) -> %d' % (row, column, value)\n\n print 'total profit=%d' % total\n\nRunning that program produces::\n\n Highest profit through this matrix:\n [5, 9, 1]\n [10, 3, 2]\n [8, 7, 4]\n (0, 1) -> 9\n (1, 0) -> 10\n (2, 2) -> 4\n total profit=23\n\nThe ``munkres`` module provides a convenience method for creating a cost\nmatrix from a profit matrix. Since it doesn't know whether the matrix contains\nfloating point numbers, decimals, or integers, you have to provide the\nconversion function; but the convenience method takes care of the actual\ncreation of the cost matrix::\n\n import munkres\n\n cost_matrix = munkres.make_cost_matrix(matrix,\n lambda cost: sys.maxint - cost)\n\nSo, the above profit-calculation program can be recast as::\n\n from munkres import Munkres, print_matrix, make_cost_matrix\n\n matrix = [[5, 9, 1],\n [10, 3, 2],\n [8, 7, 4]]\n cost_matrix = make_cost_matrix(matrix, lambda cost: sys.maxint - cost)\n m = Munkres()\n indexes = m.compute(cost_matrix)\n print_matrix(matrix, msg='Lowest cost through this matrix:')\n total = 0\n for row, column in indexes:\n value = matrix[row][column]\n total += value\n print '(%d, %d) -> %d' % (row, column, value)\n print 'total profit=%d' % total\n\nReferences\n==========\n\n1. http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html\n\n2. Harold W. Kuhn. The Hungarian Method for the assignment problem.\n *Naval Research Logistics Quarterly*, 2:83-97, 1955.\n\n3. Harold W. Kuhn. Variants of the Hungarian method for assignment\n problems. *Naval Research Logistics Quarterly*, 3: 253-258, 1956.\n\n4. Munkres, J. Algorithms for the Assignment and Transportation Problems.\n *Journal of the Society of Industrial and Applied Mathematics*,\n 5(1):32-38, March, 1957.\n\n5. http://en.wikipedia.org/wiki/Hungarian_algorithm\n\nCopyright and License\n=====================\n\nThis software is released under a BSD license, adapted from\n\n\nCopyright (c) 2008 Brian M. Clapper\nAll rights reserved.\n\nRedistribution and use in source and binary forms, with or without\nmodification, are permitted provided that the following conditions are met:\n\n* Redistributions of source code must retain the above copyright notice,\n this list of conditions and the following disclaimer.\n\n* Redistributions in binary form must reproduce the above copyright notice,\n this list of conditions and the following disclaimer in the documentation\n and/or other materials provided with the distribution.\n\n* Neither the name \"clapper.org\" nor the names of its contributors may be\n used to endorse or promote products derived from this software without\n specific prior written permission.\n\nTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS \"AS IS\"\nAND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\nIMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\nARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE\nLIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR\nCONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF\nSUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS\nINTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN\nCONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\nARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE\nPOSSIBILITY OF SUCH DAMAGE.", "description_content_type": null, "docs_url": null, "download_url": "UNKNOWN", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "http://github.com/datapublica/munkres", "keywords": null, "license": "BSD-style license", "maintainer": null, "maintainer_email": null, "name": "munkres3", "package_url": "https://pypi.org/project/munkres3/", "platform": "UNKNOWN", "project_url": "https://pypi.org/project/munkres3/", "project_urls": { "Download": "UNKNOWN", "Homepage": "http://github.com/datapublica/munkres" }, "release_url": "https://pypi.org/project/munkres3/1.0.5.5/", "requires_dist": null, "requires_python": null, "summary": "munkres algorithm for the Assignment Problem. Python 3 port.", "version": "1.0.5.5" }, "last_serial": 733506, "releases": { "1.0.5.5": [ { "comment_text": "", "digests": { "md5": "4e369369d280bd5e304ce5254c2f855f", "sha256": "f7c110d39296b580458bf0dc8cbc1c461c4d7525da243f4dcc3f3897b125cccf" }, "downloads": -1, "filename": "munkres3-1.0.5.5.tar.gz", "has_sig": false, "md5_digest": "4e369369d280bd5e304ce5254c2f855f", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9550, "upload_time": "2012-12-19T13:55:48", "url": "https://files.pythonhosted.org/packages/a3/07/f535738fa57756f53f7bbe6338f1a2e809528c542045769d89c633b47b62/munkres3-1.0.5.5.tar.gz" }, { "comment_text": "", "digests": { "md5": "5989ce658555481ece37f256a1496821", "sha256": "cd2e0570e564801127ebe54c442ea02c87472a2e530fc65d8bab4d779f4ff299" }, "downloads": -1, "filename": "munkres3-1.0.5.5.zip", "has_sig": false, "md5_digest": "5989ce658555481ece37f256a1496821", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 13882, "upload_time": "2012-12-19T13:55:50", "url": "https://files.pythonhosted.org/packages/f1/b0/ffffce607237e0457dfb3d110dc51425ae58f9c0c0c8964b4689f3abdc60/munkres3-1.0.5.5.zip" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "4e369369d280bd5e304ce5254c2f855f", "sha256": "f7c110d39296b580458bf0dc8cbc1c461c4d7525da243f4dcc3f3897b125cccf" }, "downloads": -1, "filename": "munkres3-1.0.5.5.tar.gz", "has_sig": false, "md5_digest": "4e369369d280bd5e304ce5254c2f855f", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9550, "upload_time": "2012-12-19T13:55:48", "url": "https://files.pythonhosted.org/packages/a3/07/f535738fa57756f53f7bbe6338f1a2e809528c542045769d89c633b47b62/munkres3-1.0.5.5.tar.gz" }, { "comment_text": "", "digests": { "md5": "5989ce658555481ece37f256a1496821", "sha256": "cd2e0570e564801127ebe54c442ea02c87472a2e530fc65d8bab4d779f4ff299" }, "downloads": -1, "filename": "munkres3-1.0.5.5.zip", "has_sig": false, "md5_digest": "5989ce658555481ece37f256a1496821", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 13882, "upload_time": "2012-12-19T13:55:50", "url": "https://files.pythonhosted.org/packages/f1/b0/ffffce607237e0457dfb3d110dc51425ae58f9c0c0c8964b4689f3abdc60/munkres3-1.0.5.5.zip" } ] }