annotate munkres.py @ 39:e56023008e36 default tip

Changed revision of package_fisher_0_1_4 to be2fc454d121 Changed revision of package_matplotlib_1_2 to a03ee94316b5
author miller-lab
date Mon, 06 Jul 2015 10:32:24 -0400
parents 5064f618ec1c
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
33
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
1 #!/usr/bin/env python
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
2 # -*- coding: iso-8859-1 -*-
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
3
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
4 # Documentation is intended to be processed by Epydoc.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
5
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
6 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
7 Introduction
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
8 ============
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
9
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
10 The Munkres module provides an implementation of the Munkres algorithm
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
11 (also called the Hungarian algorithm or the Kuhn-Munkres algorithm),
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
12 useful for solving the Assignment Problem.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
13
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
14 Assignment Problem
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
15 ==================
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
16
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
17 Let *C* be an *n*\ x\ *n* matrix representing the costs of each of *n* workers
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
18 to perform any of *n* jobs. The assignment problem is to assign jobs to
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
19 workers in a way that minimizes the total cost. Since each worker can perform
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
20 only one job and each job can be assigned to only one worker the assignments
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
21 represent an independent set of the matrix *C*.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
22
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
23 One way to generate the optimal set is to create all permutations of
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
24 the indexes necessary to traverse the matrix so that no row and column
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
25 are used more than once. For instance, given this matrix (expressed in
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
26 Python)::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
27
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
28 matrix = [[5, 9, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
29 [10, 3, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
30 [8, 7, 4]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
31
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
32 You could use this code to generate the traversal indexes::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
33
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
34 def permute(a, results):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
35 if len(a) == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
36 results.insert(len(results), a)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
37
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
38 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
39 for i in range(0, len(a)):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
40 element = a[i]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
41 a_copy = [a[j] for j in range(0, len(a)) if j != i]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
42 subresults = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
43 permute(a_copy, subresults)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
44 for subresult in subresults:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
45 result = [element] + subresult
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
46 results.insert(len(results), result)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
47
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
48 results = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
49 permute(range(len(matrix)), results) # [0, 1, 2] for a 3x3 matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
50
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
51 After the call to permute(), the results matrix would look like this::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
52
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
53 [[0, 1, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
54 [0, 2, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
55 [1, 0, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
56 [1, 2, 0],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
57 [2, 0, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
58 [2, 1, 0]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
59
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
60 You could then use that index matrix to loop over the original cost matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
61 and calculate the smallest cost of the combinations::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
62
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
63 n = len(matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
64 minval = sys.maxint
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
65 for row in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
66 cost = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
67 for col in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
68 cost += matrix[row][col]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
69 minval = min(cost, minval)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
70
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
71 print minval
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
72
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
73 While this approach works fine for small matrices, it does not scale. It
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
74 executes in O(*n*!) time: Calculating the permutations for an *n*\ x\ *n*
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
75 matrix requires *n*! operations. For a 12x12 matrix, that's 479,001,600
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
76 traversals. Even if you could manage to perform each traversal in just one
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
77 millisecond, it would still take more than 133 hours to perform the entire
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
78 traversal. A 20x20 matrix would take 2,432,902,008,176,640,000 operations. At
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
79 an optimistic millisecond per operation, that's more than 77 million years.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
80
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
81 The Munkres algorithm runs in O(*n*\ ^3) time, rather than O(*n*!). This
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
82 package provides an implementation of that algorithm.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
83
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
84 This version is based on
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
85 http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
86
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
87 This version was written for Python by Brian Clapper from the (Ada) algorithm
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
88 at the above web site. (The ``Algorithm::Munkres`` Perl version, in CPAN, was
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
89 clearly adapted from the same web site.)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
90
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
91 Usage
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
92 =====
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
93
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
94 Construct a Munkres object::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
95
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
96 from munkres import Munkres
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
97
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
98 m = Munkres()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
99
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
100 Then use it to compute the lowest cost assignment from a cost matrix. Here's
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
101 a sample program::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
102
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
103 from munkres import Munkres, print_matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
104
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
105 matrix = [[5, 9, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
106 [10, 3, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
107 [8, 7, 4]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
108 m = Munkres()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
109 indexes = m.compute(matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
110 print_matrix(matrix, msg='Lowest cost through this matrix:')
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
111 total = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
112 for row, column in indexes:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
113 value = matrix[row][column]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
114 total += value
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
115 print '(%d, %d) -> %d' % (row, column, value)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
116 print 'total cost: %d' % total
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
117
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
118 Running that program produces::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
119
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
120 Lowest cost through this matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
121 [5, 9, 1]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
122 [10, 3, 2]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
123 [8, 7, 4]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
124 (0, 0) -> 5
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
125 (1, 1) -> 3
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
126 (2, 2) -> 4
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
127 total cost=12
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
128
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
129 The instantiated Munkres object can be used multiple times on different
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
130 matrices.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
131
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
132 Non-square Cost Matrices
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
133 ========================
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
134
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
135 The Munkres algorithm assumes that the cost matrix is square. However, it's
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
136 possible to use a rectangular matrix if you first pad it with 0 values to make
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
137 it square. This module automatically pads rectangular cost matrices to make
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
138 them square.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
139
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
140 Notes:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
141
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
142 - The module operates on a *copy* of the caller's matrix, so any padding will
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
143 not be seen by the caller.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
144 - The cost matrix must be rectangular or square. An irregular matrix will
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
145 *not* work.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
146
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
147 Calculating Profit, Rather than Cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
148 ====================================
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
149
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
150 The cost matrix is just that: A cost matrix. The Munkres algorithm finds
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
151 the combination of elements (one from each row and column) that results in
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
152 the smallest cost. It's also possible to use the algorithm to maximize
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
153 profit. To do that, however, you have to convert your profit matrix to a
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
154 cost matrix. The simplest way to do that is to subtract all elements from a
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
155 large value. For example::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
156
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
157 from munkres import Munkres, print_matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
158
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
159 matrix = [[5, 9, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
160 [10, 3, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
161 [8, 7, 4]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
162 cost_matrix = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
163 for row in matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
164 cost_row = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
165 for col in row:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
166 cost_row += [sys.maxint - col]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
167 cost_matrix += [cost_row]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
168
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
169 m = Munkres()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
170 indexes = m.compute(cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
171 print_matrix(matrix, msg='Highest profit through this matrix:')
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
172 total = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
173 for row, column in indexes:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
174 value = matrix[row][column]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
175 total += value
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
176 print '(%d, %d) -> %d' % (row, column, value)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
177
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
178 print 'total profit=%d' % total
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
179
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
180 Running that program produces::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
181
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
182 Highest profit through this matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
183 [5, 9, 1]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
184 [10, 3, 2]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
185 [8, 7, 4]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
186 (0, 1) -> 9
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
187 (1, 0) -> 10
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
188 (2, 2) -> 4
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
189 total profit=23
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
190
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
191 The ``munkres`` module provides a convenience method for creating a cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
192 matrix from a profit matrix. Since it doesn't know whether the matrix contains
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
193 floating point numbers, decimals, or integers, you have to provide the
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
194 conversion function; but the convenience method takes care of the actual
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
195 creation of the cost matrix::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
196
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
197 import munkres
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
198
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
199 cost_matrix = munkres.make_cost_matrix(matrix,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
200 lambda cost: sys.maxint - cost)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
201
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
202 So, the above profit-calculation program can be recast as::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
203
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
204 from munkres import Munkres, print_matrix, make_cost_matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
205
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
206 matrix = [[5, 9, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
207 [10, 3, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
208 [8, 7, 4]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
209 cost_matrix = make_cost_matrix(matrix, lambda cost: sys.maxint - cost)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
210 m = Munkres()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
211 indexes = m.compute(cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
212 print_matrix(matrix, msg='Lowest cost through this matrix:')
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
213 total = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
214 for row, column in indexes:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
215 value = matrix[row][column]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
216 total += value
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
217 print '(%d, %d) -> %d' % (row, column, value)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
218 print 'total profit=%d' % total
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
219
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
220 References
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
221 ==========
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
222
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
223 1. http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
224
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
225 2. Harold W. Kuhn. The Hungarian Method for the assignment problem.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
226 *Naval Research Logistics Quarterly*, 2:83-97, 1955.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
227
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
228 3. Harold W. Kuhn. Variants of the Hungarian method for assignment
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
229 problems. *Naval Research Logistics Quarterly*, 3: 253-258, 1956.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
230
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
231 4. Munkres, J. Algorithms for the Assignment and Transportation Problems.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
232 *Journal of the Society of Industrial and Applied Mathematics*,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
233 5(1):32-38, March, 1957.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
234
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
235 5. http://en.wikipedia.org/wiki/Hungarian_algorithm
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
236
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
237 Copyright and License
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
238 =====================
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
239
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
240 This software is released under a BSD license, adapted from
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
241 <http://opensource.org/licenses/bsd-license.php>
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
242
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
243 Copyright (c) 2008 Brian M. Clapper
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
244 All rights reserved.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
245
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
246 Redistribution and use in source and binary forms, with or without
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
247 modification, are permitted provided that the following conditions are met:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
248
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
249 * Redistributions of source code must retain the above copyright notice,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
250 this list of conditions and the following disclaimer.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
251
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
252 * Redistributions in binary form must reproduce the above copyright notice,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
253 this list of conditions and the following disclaimer in the documentation
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
254 and/or other materials provided with the distribution.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
255
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
256 * Neither the name "clapper.org" nor the names of its contributors may be
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
257 used to endorse or promote products derived from this software without
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
258 specific prior written permission.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
259
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
260 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
261 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
262 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
263 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
264 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
265 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
266 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
267 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
268 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
269 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
270 POSSIBILITY OF SUCH DAMAGE.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
271 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
272
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
273 __docformat__ = 'restructuredtext'
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
274
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
275 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
276 # Imports
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
277 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
278
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
279 import sys
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
280
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
281 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
282 # Exports
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
283 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
284
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
285 __all__ = ['Munkres', 'make_cost_matrix']
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
286
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
287 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
288 # Globals
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
289 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
290
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
291 # Info about the module
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
292 __version__ = "1.0.5.4"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
293 __author__ = "Brian Clapper, bmc@clapper.org"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
294 __url__ = "http://bmc.github.com/munkres/"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
295 __copyright__ = "(c) 2008 Brian M. Clapper"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
296 __license__ = "BSD-style license"
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
297
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
298 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
299 # Classes
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
300 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
301
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
302 class Munkres:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
303 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
304 Calculate the Munkres solution to the classical assignment problem.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
305 See the module documentation for usage.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
306 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
307
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
308 def __init__(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
309 """Create a new instance"""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
310 self.C = None
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
311 self.row_covered = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
312 self.col_covered = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
313 self.n = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
314 self.Z0_r = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
315 self.Z0_c = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
316 self.marked = None
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
317 self.path = None
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
318
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
319 def make_cost_matrix(profit_matrix, inversion_function):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
320 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
321 **DEPRECATED**
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
322
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
323 Please use the module function ``make_cost_matrix()``.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
324 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
325 import munkres
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
326 return munkres.make_cost_matrix(profit_matrix, inversion_function)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
327
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
328 make_cost_matrix = staticmethod(make_cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
329
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
330 def pad_matrix(self, matrix, pad_value=0):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
331 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
332 Pad a possibly non-square matrix to make it square.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
333
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
334 :Parameters:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
335 matrix : list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
336 matrix to pad
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
337
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
338 pad_value : int
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
339 value to use to pad the matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
340
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
341 :rtype: list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
342 :return: a new, possibly padded, matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
343 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
344 max_columns = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
345 total_rows = len(matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
346
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
347 for row in matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
348 max_columns = max(max_columns, len(row))
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
349
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
350 total_rows = max(max_columns, total_rows)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
351
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
352 new_matrix = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
353 for row in matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
354 row_len = len(row)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
355 new_row = row[:]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
356 if total_rows > row_len:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
357 # Row too short. Pad it.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
358 new_row += [0] * (total_rows - row_len)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
359 new_matrix += [new_row]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
360
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
361 while len(new_matrix) < total_rows:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
362 new_matrix += [[0] * total_rows]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
363
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
364 return new_matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
365
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
366 def compute(self, cost_matrix):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
367 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
368 Compute the indexes for the lowest-cost pairings between rows and
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
369 columns in the database. Returns a list of (row, column) tuples
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
370 that can be used to traverse the matrix.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
371
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
372 :Parameters:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
373 cost_matrix : list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
374 The cost matrix. If this cost matrix is not square, it
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
375 will be padded with zeros, via a call to ``pad_matrix()``.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
376 (This method does *not* modify the caller's matrix. It
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
377 operates on a copy of the matrix.)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
378
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
379 **WARNING**: This code handles square and rectangular
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
380 matrices. It does *not* handle irregular matrices.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
381
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
382 :rtype: list
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
383 :return: A list of ``(row, column)`` tuples that describe the lowest
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
384 cost path through the matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
385
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
386 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
387 self.C = self.pad_matrix(cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
388 self.n = len(self.C)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
389 self.original_length = len(cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
390 self.original_width = len(cost_matrix[0])
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
391 self.row_covered = [False for i in range(self.n)]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
392 self.col_covered = [False for i in range(self.n)]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
393 self.Z0_r = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
394 self.Z0_c = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
395 self.path = self.__make_matrix(self.n * 2, 0)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
396 self.marked = self.__make_matrix(self.n, 0)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
397
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
398 done = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
399 step = 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
400
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
401 steps = { 1 : self.__step1,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
402 2 : self.__step2,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
403 3 : self.__step3,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
404 4 : self.__step4,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
405 5 : self.__step5,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
406 6 : self.__step6 }
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
407
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
408 while not done:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
409 try:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
410 func = steps[step]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
411 step = func()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
412 except KeyError:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
413 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
414
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
415 # Look for the starred columns
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
416 results = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
417 for i in range(self.original_length):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
418 for j in range(self.original_width):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
419 if self.marked[i][j] == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
420 results += [(i, j)]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
421
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
422 return results
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
423
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
424 def __copy_matrix(self, matrix):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
425 """Return an exact copy of the supplied matrix"""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
426 return copy.deepcopy(matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
427
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
428 def __make_matrix(self, n, val):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
429 """Create an *n*x*n* matrix, populating it with the specific value."""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
430 matrix = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
431 for i in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
432 matrix += [[val for j in range(n)]]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
433 return matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
434
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
435 def __step1(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
436 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
437 For each row of the matrix, find the smallest element and
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
438 subtract it from every element in its row. Go to Step 2.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
439 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
440 C = self.C
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
441 n = self.n
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
442 for i in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
443 minval = min(self.C[i])
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
444 # Find the minimum value for this row and subtract that minimum
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
445 # from every element in the row.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
446 for j in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
447 self.C[i][j] -= minval
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
448
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
449 return 2
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
450
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
451 def __step2(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
452 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
453 Find a zero (Z) in the resulting matrix. If there is no starred
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
454 zero in its row or column, star Z. Repeat for each element in the
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
455 matrix. Go to Step 3.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
456 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
457 n = self.n
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
458 for i in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
459 for j in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
460 if (self.C[i][j] == 0) and \
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
461 (not self.col_covered[j]) and \
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
462 (not self.row_covered[i]):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
463 self.marked[i][j] = 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
464 self.col_covered[j] = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
465 self.row_covered[i] = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
466
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
467 self.__clear_covers()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
468 return 3
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
469
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
470 def __step3(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
471 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
472 Cover each column containing a starred zero. If K columns are
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
473 covered, the starred zeros describe a complete set of unique
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
474 assignments. In this case, Go to DONE, otherwise, Go to Step 4.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
475 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
476 n = self.n
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
477 count = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
478 for i in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
479 for j in range(n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
480 if self.marked[i][j] == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
481 self.col_covered[j] = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
482 count += 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
483
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
484 if count >= n:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
485 step = 7 # done
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
486 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
487 step = 4
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
488
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
489 return step
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
490
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
491 def __step4(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
492 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
493 Find a noncovered zero and prime it. If there is no starred zero
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
494 in the row containing this primed zero, Go to Step 5. Otherwise,
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
495 cover this row and uncover the column containing the starred
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
496 zero. Continue in this manner until there are no uncovered zeros
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
497 left. Save the smallest uncovered value and Go to Step 6.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
498 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
499 step = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
500 done = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
501 row = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
502 col = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
503 star_col = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
504 while not done:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
505 (row, col) = self.__find_a_zero()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
506 if row < 0:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
507 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
508 step = 6
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
509 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
510 self.marked[row][col] = 2
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
511 star_col = self.__find_star_in_row(row)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
512 if star_col >= 0:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
513 col = star_col
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
514 self.row_covered[row] = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
515 self.col_covered[col] = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
516 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
517 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
518 self.Z0_r = row
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
519 self.Z0_c = col
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
520 step = 5
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
521
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
522 return step
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
523
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
524 def __step5(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
525 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
526 Construct a series of alternating primed and starred zeros as
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
527 follows. Let Z0 represent the uncovered primed zero found in Step 4.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
528 Let Z1 denote the starred zero in the column of Z0 (if any).
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
529 Let Z2 denote the primed zero in the row of Z1 (there will always
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
530 be one). Continue until the series terminates at a primed zero
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
531 that has no starred zero in its column. Unstar each starred zero
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
532 of the series, star each primed zero of the series, erase all
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
533 primes and uncover every line in the matrix. Return to Step 3
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
534 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
535 count = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
536 path = self.path
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
537 path[count][0] = self.Z0_r
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
538 path[count][1] = self.Z0_c
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
539 done = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
540 while not done:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
541 row = self.__find_star_in_col(path[count][1])
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
542 if row >= 0:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
543 count += 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
544 path[count][0] = row
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
545 path[count][1] = path[count-1][1]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
546 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
547 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
548
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
549 if not done:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
550 col = self.__find_prime_in_row(path[count][0])
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
551 count += 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
552 path[count][0] = path[count-1][0]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
553 path[count][1] = col
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
554
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
555 self.__convert_path(path, count)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
556 self.__clear_covers()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
557 self.__erase_primes()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
558 return 3
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
559
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
560 def __step6(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
561 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
562 Add the value found in Step 4 to every element of each covered
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
563 row, and subtract it from every element of each uncovered column.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
564 Return to Step 4 without altering any stars, primes, or covered
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
565 lines.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
566 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
567 minval = self.__find_smallest()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
568 for i in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
569 for j in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
570 if self.row_covered[i]:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
571 self.C[i][j] += minval
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
572 if not self.col_covered[j]:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
573 self.C[i][j] -= minval
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
574 return 4
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
575
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
576 def __find_smallest(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
577 """Find the smallest uncovered value in the matrix."""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
578 minval = sys.maxint
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
579 for i in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
580 for j in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
581 if (not self.row_covered[i]) and (not self.col_covered[j]):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
582 if minval > self.C[i][j]:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
583 minval = self.C[i][j]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
584 return minval
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
585
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
586 def __find_a_zero(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
587 """Find the first uncovered element with value 0"""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
588 row = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
589 col = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
590 i = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
591 n = self.n
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
592 done = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
593
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
594 while not done:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
595 j = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
596 while True:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
597 if (self.C[i][j] == 0) and \
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
598 (not self.row_covered[i]) and \
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
599 (not self.col_covered[j]):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
600 row = i
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
601 col = j
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
602 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
603 j += 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
604 if j >= n:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
605 break
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
606 i += 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
607 if i >= n:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
608 done = True
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
609
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
610 return (row, col)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
611
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
612 def __find_star_in_row(self, row):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
613 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
614 Find the first starred element in the specified row. Returns
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
615 the column index, or -1 if no starred element was found.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
616 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
617 col = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
618 for j in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
619 if self.marked[row][j] == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
620 col = j
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
621 break
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
622
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
623 return col
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
624
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
625 def __find_star_in_col(self, col):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
626 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
627 Find the first starred element in the specified row. Returns
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
628 the row index, or -1 if no starred element was found.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
629 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
630 row = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
631 for i in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
632 if self.marked[i][col] == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
633 row = i
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
634 break
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
635
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
636 return row
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
637
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
638 def __find_prime_in_row(self, row):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
639 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
640 Find the first prime element in the specified row. Returns
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
641 the column index, or -1 if no starred element was found.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
642 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
643 col = -1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
644 for j in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
645 if self.marked[row][j] == 2:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
646 col = j
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
647 break
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
648
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
649 return col
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
650
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
651 def __convert_path(self, path, count):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
652 for i in range(count+1):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
653 if self.marked[path[i][0]][path[i][1]] == 1:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
654 self.marked[path[i][0]][path[i][1]] = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
655 else:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
656 self.marked[path[i][0]][path[i][1]] = 1
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
657
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
658 def __clear_covers(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
659 """Clear all covered matrix cells"""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
660 for i in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
661 self.row_covered[i] = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
662 self.col_covered[i] = False
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
663
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
664 def __erase_primes(self):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
665 """Erase all prime markings"""
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
666 for i in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
667 for j in range(self.n):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
668 if self.marked[i][j] == 2:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
669 self.marked[i][j] = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
670
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
671 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
672 # Functions
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
673 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
674
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
675 def make_cost_matrix(profit_matrix, inversion_function):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
676 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
677 Create a cost matrix from a profit matrix by calling
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
678 'inversion_function' to invert each value. The inversion
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
679 function must take one numeric argument (of any type) and return
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
680 another numeric argument which is presumed to be the cost inverse
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
681 of the original profit.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
682
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
683 This is a static method. Call it like this:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
684
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
685 .. python::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
686
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
687 cost_matrix = Munkres.make_cost_matrix(matrix, inversion_func)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
688
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
689 For example:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
690
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
691 .. python::
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
692
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
693 cost_matrix = Munkres.make_cost_matrix(matrix, lambda x : sys.maxint - x)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
694
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
695 :Parameters:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
696 profit_matrix : list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
697 The matrix to convert from a profit to a cost matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
698
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
699 inversion_function : function
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
700 The function to use to invert each entry in the profit matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
701
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
702 :rtype: list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
703 :return: The converted matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
704 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
705 cost_matrix = []
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
706 for row in profit_matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
707 cost_matrix.append([inversion_function(value) for value in row])
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
708 return cost_matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
709
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
710 def print_matrix(matrix, msg=None):
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
711 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
712 Convenience function: Displays the contents of a matrix of integers.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
713
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
714 :Parameters:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
715 matrix : list of lists
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
716 Matrix to print
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
717
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
718 msg : str
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
719 Optional message to print before displaying the matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
720 """
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
721 import math
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
722
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
723 if msg is not None:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
724 print msg
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
725
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
726 # Calculate the appropriate format width.
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
727 width = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
728 for row in matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
729 for val in row:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
730 width = max(width, int(math.log10(val)) + 1)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
731
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
732 # Make the format string
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
733 format = '%%%dd' % width
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
734
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
735 # Print the matrix
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
736 for row in matrix:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
737 sep = '['
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
738 for val in row:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
739 sys.stdout.write(sep + format % val)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
740 sep = ', '
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
741 sys.stdout.write(']\n')
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
742
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
743 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
744 # Main
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
745 # ---------------------------------------------------------------------------
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
746
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
747 if __name__ == '__main__':
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
748
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
749
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
750 matrices = [
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
751 # Square
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
752 ([[400, 150, 400],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
753 [400, 450, 600],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
754 [300, 225, 300]],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
755 850 # expected cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
756 ),
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
757
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
758 # Rectangular variant
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
759 ([[400, 150, 400, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
760 [400, 450, 600, 2],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
761 [300, 225, 300, 3]],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
762 452 # expected cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
763 ),
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
764
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
765 # Square
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
766 ([[10, 10, 8],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
767 [ 9, 8, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
768 [ 9, 7, 4]],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
769 18
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
770 ),
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
771
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
772 # Rectangular variant
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
773 ([[10, 10, 8, 11],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
774 [ 9, 8, 1, 1],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
775 [ 9, 7, 4, 10]],
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
776 15
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
777 ),
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
778 ]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
779
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
780 m = Munkres()
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
781 for cost_matrix, expected_total in matrices:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
782 print_matrix(cost_matrix, msg='cost matrix')
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
783 indexes = m.compute(cost_matrix)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
784 total_cost = 0
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
785 for r, c in indexes:
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
786 x = cost_matrix[r][c]
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
787 total_cost += x
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
788 print '(%d, %d) -> %d' % (r, c, x)
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
789 print 'lowest cost=%d' % total_cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
790 assert expected_total == total_cost
5064f618ec1c remove munkres dependency
Richard Burhans <burhans@bx.psu.edu>
parents:
diff changeset
791