fr.inrialpes.exmo.align.impl
Class HungarianAlgorithm
java.lang.Object
fr.inrialpes.exmo.align.impl.HungarianAlgorithm
- public class HungarianAlgorithm
- extends java.lang.Object
Method Summary |
static void |
clearCovers(int[] rowCover,
int[] colCover)
|
static void |
convertPath(int[][] mask,
int[][] path,
int count)
|
static double[][] |
copyOf(double[][] original)
|
static void |
erasePrimes(int[][] mask)
|
static double |
findLargest(double[][] array)
|
static int |
findPrimeInRow(int[][] mask,
int row)
|
static double |
findSmallest(double[][] cost,
int[] rowCover,
int[] colCover,
double maxCost)
|
static int |
findStarInCol(int[][] mask,
int col)
|
static int[] |
findUncoveredZero(int[] row_col,
double[][] cost,
int[] rowCover,
int[] colCover)
|
static int |
hg_step1(int step,
double[][] cost)
|
static int |
hg_step2(int step,
double[][] cost,
int[][] mask,
int[] rowCover,
int[] colCover)
What STEP 2 does:
Marks uncovered zeros as starred and covers their row and column. |
static int |
hg_step3(int step,
int[][] mask,
int[] colCover)
What STEP 3 does:
Cover columns of starred zeros. |
static int |
hg_step4(int step,
double[][] cost,
int[][] mask,
int[] rowCover,
int[] colCover,
int[] zero_RC)
What STEP 4 does:
Find an uncovered zero in cost and prime it (if none go to step 6). |
static int |
hg_step5(int step,
int[][] mask,
int[] rowCover,
int[] colCover,
int[] zero_RC)
|
static int |
hg_step6(int step,
double[][] cost,
int[] rowCover,
int[] colCover,
double maxCost)
|
static int[][] |
hgAlgorithm(double[][] costPrm,
java.lang.String sumType)
|
static void |
main(java.lang.String[] args)
|
static double[][] |
transpose(double[][] array)
|
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
HungarianAlgorithm
public HungarianAlgorithm()
findLargest
public static double findLargest(double[][] array)
transpose
public static double[][] transpose(double[][] array)
copyOf
public static double[][] copyOf(double[][] original)
hgAlgorithm
public static int[][] hgAlgorithm(double[][] costPrm,
java.lang.String sumType)
hg_step1
public static int hg_step1(int step,
double[][] cost)
hg_step2
public static int hg_step2(int step,
double[][] cost,
int[][] mask,
int[] rowCover,
int[] colCover)
- What STEP 2 does:
Marks uncovered zeros as starred and covers their row and column.
hg_step3
public static int hg_step3(int step,
int[][] mask,
int[] colCover)
- What STEP 3 does:
Cover columns of starred zeros. Check if all columns are covered.
hg_step4
public static int hg_step4(int step,
double[][] cost,
int[][] mask,
int[] rowCover,
int[] colCover,
int[] zero_RC)
- What STEP 4 does:
Find an uncovered zero in cost and prime it (if none go to step 6). Check for star in same row:
if yes, cover the row and uncover the star's column. Repeat until no uncovered zeros are left
and go to step 6. If not, save location of primed zero and go to step 5.
findUncoveredZero
public static int[] findUncoveredZero(int[] row_col,
double[][] cost,
int[] rowCover,
int[] colCover)
hg_step5
public static int hg_step5(int step,
int[][] mask,
int[] rowCover,
int[] colCover,
int[] zero_RC)
findStarInCol
public static int findStarInCol(int[][] mask,
int col)
findPrimeInRow
public static int findPrimeInRow(int[][] mask,
int row)
convertPath
public static void convertPath(int[][] mask,
int[][] path,
int count)
erasePrimes
public static void erasePrimes(int[][] mask)
clearCovers
public static void clearCovers(int[] rowCover,
int[] colCover)
hg_step6
public static int hg_step6(int step,
double[][] cost,
int[] rowCover,
int[] colCover,
double maxCost)
findSmallest
public static double findSmallest(double[][] cost,
int[] rowCover,
int[] colCover,
double maxCost)
main
public static void main(java.lang.String[] args)
..no bottom yet...