Galaxy |

Changeset 33:5064f618ec1c (2013-09-20)

Previous changeset 32:03c22b722882 (2013-09-20) Next changeset 34:f739a296a339 (2013-09-23)

Commit message:
remove munkres dependency

modified:
assignment_of_optimal_breeding_pairs.xml
tool_dependencies.xml

added:
munkres.py

diff -r 03c22b722882 -r 5064f618ec1c assignment_of_optimal_breeding_pairs.xml
--- a/assignment_of_optimal_breeding_pairs.xml Fri Sep 20 13:54:23 2013 -0400
+++ b/assignment_of_optimal_breeding_pairs.xml Fri Sep 20 14:01:30 2013 -0400

@@ -14,9 +14,11 @@
     <data name="output" format="txt" />
   </outputs>

+  

   <!--
   <tests>

diff -r 03c22b722882 -r 5064f618ec1c munkres.py
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/munkres.py Fri Sep 20 14:01:30 2013 -0400

[

b'@@ -0,0 +1,791 @@\n+#!/usr/bin/env python\n+# -*- coding: iso-8859-1 -*-\n+\n+# Documentation is intended to be processed by Epydoc.\n+\n+"""\n+Introduction\n+============\n+\n+The Munkres module provides an implementation of the Munkres algorithm\n+(also called the Hungarian algorithm or the Kuhn-Munkres algorithm),\n+useful for solving the Assignment Problem.\n+\n+Assignment Problem\n+==================\n+\n+Let *C* be an *n*\\ x\\ *n* matrix representing the costs of each of *n* workers\n+to perform any of *n* jobs. The assignment problem is to assign jobs to\n+workers in a way that minimizes the total cost. Since each worker can perform\n+only one job and each job can be assigned to only one worker the assignments\n+represent an independent set of the matrix *C*.\n+\n+One way to generate the optimal set is to create all permutations of\n+the indexes necessary to traverse the matrix so that no row and column\n+are used more than once. For instance, given this matrix (expressed in\n+Python)::\n+\n+ matrix = [[5, 9, 1],\n+ [10, 3, 2],\n+ [8, 7, 4]]\n+\n+You 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+\n+After 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+\n+You could then use that index matrix to loop over the original cost matrix\n+and 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+\n+While this approach works fine for small matrices, it does not scale. It\n+executes in O(*n*!) time: Calculating the permutations for an *n*\\ x\\ *n*\n+matrix requires *n*! operations. For a 12x12 matrix, that\'s 479,001,600\n+traversals. Even if you could manage to perform each traversal in just one\n+millisecond, it would still take more than 133 hours to perform the entire\n+traversal. A 20x20 matrix would take 2,432,902,008,176,640,000 operations. At\n+an optimistic millisecond per operation, that\'s more than 77 million years.\n+\n+The Munkres algorithm runs in O(*n*\\ ^3) time, rather than O(*n*!). This\n+package provides an implementation of that algorithm.\n+\n+This version is based on\n+http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.\n+\n+This version was written for Python by Brian Clapper from the (Ada) algorithm\n+at the above web site. (The ``Algorithm::Munkres`` Perl version, in CPAN, was\n+clearly adapted from the same web site.)\n+\n+Usage\n+=====\n+\n+Construct a Munkres object::\n+\n+ from munkres import Munkres\n+\n+ m = Munkres()\n+\n+Then use it to compute the lowest cost assignment from a cost matrix. Here\'s\n+a 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+\n+Running 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) -> '..b'\n+ else:\n+ self.marked[path[i][0]][path[i][1]] = 1\n+\n+ def __clear_covers(self):\n+ """Clear all covered matrix cells"""\n+ for i in range(self.n):\n+ self.row_covered[i] = False\n+ self.col_covered[i] = False\n+\n+ def __erase_primes(self):\n+ """Erase all prime markings"""\n+ for i in range(self.n):\n+ for j in range(self.n):\n+ if self.marked[i][j] == 2:\n+ self.marked[i][j] = 0\n+\n+# ---------------------------------------------------------------------------\n+# Functions\n+# ---------------------------------------------------------------------------\n+\n+def make_cost_matrix(profit_matrix, inversion_function):\n+ """\n+ Create a cost matrix from a profit matrix by calling\n+ \'inversion_function\' to invert each value. The inversion\n+ function must take one numeric argument (of any type) and return\n+ another numeric argument which is presumed to be the cost inverse\n+ of the original profit.\n+\n+ This is a static method. Call it like this:\n+\n+ .. python::\n+\n+ cost_matrix = Munkres.make_cost_matrix(matrix, inversion_func)\n+\n+ For example:\n+\n+ .. python::\n+\n+ cost_matrix = Munkres.make_cost_matrix(matrix, lambda x : sys.maxint - x)\n+\n+ :Parameters:\n+ profit_matrix : list of lists\n+ The matrix to convert from a profit to a cost matrix\n+\n+ inversion_function : function\n+ The function to use to invert each entry in the profit matrix\n+\n+ :rtype: list of lists\n+ :return: The converted matrix\n+ """\n+ cost_matrix = []\n+ for row in profit_matrix:\n+ cost_matrix.append([inversion_function(value) for value in row])\n+ return cost_matrix\n+\n+def print_matrix(matrix, msg=None):\n+ """\n+ Convenience function: Displays the contents of a matrix of integers.\n+\n+ :Parameters:\n+ matrix : list of lists\n+ Matrix to print\n+\n+ msg : str\n+ Optional message to print before displaying the matrix\n+ """\n+ import math\n+\n+ if msg is not None:\n+ print msg\n+\n+ # Calculate the appropriate format width.\n+ width = 0\n+ for row in matrix:\n+ for val in row:\n+ width = max(width, int(math.log10(val)) + 1)\n+\n+ # Make the format string\n+ format = \'%%%dd\' % width\n+\n+ # Print the matrix\n+ for row in matrix:\n+ sep = \'[\'\n+ for val in row:\n+ sys.stdout.write(sep + format % val)\n+ sep = \', \'\n+ sys.stdout.write(\']\\n\')\n+\n+# ---------------------------------------------------------------------------\n+# Main\n+# ---------------------------------------------------------------------------\n+\n+if __name__ == \'__main__\':\n+\n+\n+ matrices = [\n+ # Square\n+ ([[400, 150, 400],\n+ [400, 450, 600],\n+ [300, 225, 300]],\n+ 850 # expected cost\n+ ),\n+\n+ # Rectangular variant\n+ ([[400, 150, 400, 1],\n+ [400, 450, 600, 2],\n+ [300, 225, 300, 3]],\n+ 452 # expected cost\n+ ),\n+\n+ # Square\n+ ([[10, 10, 8],\n+ [ 9, 8, 1],\n+ [ 9, 7, 4]],\n+ 18\n+ ),\n+\n+ # Rectangular variant\n+ ([[10, 10, 8, 11],\n+ [ 9, 8, 1, 1],\n+ [ 9, 7, 4, 10]],\n+ 15\n+ ),\n+ ]\n+\n+ m = Munkres()\n+ for cost_matrix, expected_total in matrices:\n+ print_matrix(cost_matrix, msg=\'cost matrix\')\n+ indexes = m.compute(cost_matrix)\n+ total_cost = 0\n+ for r, c in indexes:\n+ x = cost_matrix[r][c]\n+ total_cost += x\n+ print \'(%d, %d) -> %d\' % (r, c, x)\n+ print \'lowest cost=%d\' % total_cost\n+ assert expected_total == total_cost\n+\n'

diff -r 03c22b722882 -r 5064f618ec1c tool_dependencies.xml
--- a/tool_dependencies.xml Fri Sep 20 13:54:23 2013 -0400
+++ b/tool_dependencies.xml Fri Sep 20 14:01:30 2013 -0400

@@ -20,9 +20,11 @@
   <package name="mechanize" version="0.2.5">
     <repository prior_installation_required="True" toolshed="http://toolshed.g2.bx.psu.edu/" owner="miller-lab" name="package_mechanize_0_2_5" changeset_revision="59801857421b" />
   </package>
+  
   <package name="networkx" version="1.8.1">
     <repository prior_installation_required="True" toolshed="http://toolshed.g2.bx.psu.edu/" owner="miller-lab" name="package_networkx_1_8_1" changeset_revision="43c20433f2d6" />
   </package>