|
|
list of lists
|
|
list
|
compute(self,
cost_matrix)
Compute the indexes for the lowest-cost pairings between rows and
columns in the database. Returns a list of (row, column) tuples
that can be used to traverse the matrix. |
source code
|
|
|
__copy_matrix(self,
matrix)
Return an exact copy of the supplied matrix |
source code
|
|
|
__make_matrix(self,
n,
val)
Create an n*x*n matrix, populating it with the specific value. |
source code
|
|
|
__step1(self)
For each row of the matrix, find the smallest element and
subtract it from every element in its row. Go to Step 2. |
source code
|
|
|
__step2(self)
Find a zero (Z) in the resulting matrix. If there is no starred
zero in its row or column, star Z. Repeat for each element in the
matrix. Go to Step 3. |
source code
|
|
|
__step3(self)
Cover each column containing a starred zero. If K columns are
covered, the starred zeros describe a complete set of unique
assignments. In this case, Go to DONE, otherwise, Go to Step 4. |
source code
|
|
|
__step4(self)
Find a noncovered zero and prime it. If there is no starred zero
in the row containing this primed zero, Go to Step 5. Otherwise,
cover this row and uncover the column containing the starred
zero. Continue in this manner until there are no uncovered zeros
left. Save the smallest uncovered value and Go to Step 6. |
source code
|
|
|
__step5(self)
Construct a series of alternating primed and starred zeros as
follows. Let Z0 represent the uncovered primed zero found in Step 4.
Let Z1 denote the starred zero in the column of Z0 (if any).
Let Z2 denote the primed zero in the row of Z1 (there will always
be one). Continue until the series terminates at a primed zero
that has no starred zero in its column. Unstar each starred zero
of the series, star each primed zero of the series, erase all
primes and uncover every line in the matrix. Return to Step 3 |
source code
|
|
|
__step6(self)
Add the value found in Step 4 to every element of each covered
row, and subtract it from every element of each uncovered column.
Return to Step 4 without altering any stars, primes, or covered
lines. |
source code
|
|
|
__find_smallest(self)
Find the smallest uncovered value in the matrix. |
source code
|
|
|
__find_a_zero(self)
Find the first uncovered element with value 0 |
source code
|
|
|
__find_star_in_row(self,
row)
Find the first starred element in the specified row. Returns
the column index, or -1 if no starred element was found. |
source code
|
|
|
__find_star_in_col(self,
col)
Find the first starred element in the specified row. Returns
the row index, or -1 if no starred element was found. |
source code
|
|
|
__find_prime_in_row(self,
row)
Find the first prime element in the specified row. Returns
the column index, or -1 if no starred element was found. |
source code
|
|
|
|
|
__clear_covers(self)
Clear all covered matrix cells |
source code
|
|
|
__erase_primes(self)
Erase all prime markings |
source code
|
|